Validating system properties exhibited in execution traces

ABSTRACT

Execution traces produced by software systems during their operation can capture important runtime information, and thus are valuable sources for validating software functional properties. Automating the validation of such properties is currently achieved by writing test scripts, where most of the effort focuses on programming operations rather than specifying properties clearly. Improving this practice calls for domain-specific languages that can capture properties exhibited in traces at a higher abstract level.

This paper presents a Test Behavior Language (TBL) that uses parameterized patterns as logical predicates to specify and validate trace-based properties abstractly but precisely. TBL has been used to automate the testing of several software systems, including a large telecommunication system. Initial results show that TBL is powerfulfor validating complex properties of these systems in real time, resulting in a big increase in the thoroughness of behavioral analysis and the number of bugs revealed. TBL also reduces the effort of script writing. TBL specifications range from 1/2 to 1/5 the size of their Tcl script counterparts, with a greater benefit realized where thorough trace analysis is needed.

REFERENCES

• 1: Alfred V. Aho, Algorithms for finding patterns in strings, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 2: James H. Andrews , Yingjun Zhang, General Test Result Checking with Log File Analysis, IEEE Transactions on Software Engineering, v.29 n.7, p.634-648, July 2003 [doi>10.1109/TSE.2003.1214327]
• 3: Wolfram Bartussek , David Lorge Parnas, Using assertions about traces to write abstract specifications for software modules, Proceedings of the 2nd Conference of the European Cooperation on Informatics: Information Systems Methodology, p.211-236, October 10-12, 1978
• 4: L. Destailleur. AWStats log file analyzer. http://awstats.sourceforge.net/docs/awstats.pdf.
• 5: S. Alan Ezust , Gregor v. Bochmann, An automatic trace analysis tool generator for Estelle specifications, ACM SIGCOMM Computer Communication Review, v.25 n.4, p.175-184, Oct. 1995
• 6: George Fink , Matt Bishop, Property-based testing: a new approach to testing for assurance, ACM SIGSOFT Software Engineering Notes, v.22 n.4, p.74-80, July 1997 [doi>10.1145/263244.263267]
• 7: Kim S. Larsen, Regular expressions with nested levels of back referencing form a hierarchy, Information Processing Letters, v.65 n.4, p.169-172, Feb. 1998 [doi>10.1016/S0020-0190(98)00007-6]
• 8: Don Libes, Writing a Tcl extension in only 7 years, Proceedings of the 5th conference on Annual Tcl/Tk Workshop 1997, p.8-8, July 14-17, 1997, Boston, Massachusetts
• 9: J. McLean. Proving noninterference and functional correctness using traces. Journal of Computer Security, 1(1), 1992.
• 10: Debra J. Richardson , Stephanie Leif Aha , T. Owen O'Malley, Specification-based test oracles for reactive systems, Proceedings of the 14th international conference on Software engineering, p.105-118, May 11-15, 1992, Melbourne, Australia [doi>10.1145/143062.143100]
• 11: U. Sammapun, A. Easwaran, I. Lee, and O. Sokolsky. Simulation of simultaneous events in regular expressions for run-time verification. In Workshop on Runtime Verification, 2004.
• 12: R. Savoye. DejaGnu: The GNU testing framework. www.gnu.org/software/dejagnu.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

General Terms:
Languages, Verification

Keywords:
system testing automation, trace analysis