Directed test generation using symbolic grammars

ABSTRACT

We present CESE, a tool that combines exhaustive enumeration of test inputs from a structured domain with symbolic execution driven test generation. We target programs whose valid inputs are determined by some context free grammar. We abstract the concrete input syntax with symbolic grammars, where some original tokens are replaced with symbolic constants. This reduces the set of input strings that must be enumerated exhaustively. For each enumerated input string, which may contain symbolic constants, symbolic execution based test generation instantiates the constants based on program execution paths. The "template" generated by enumerating valid strings reduces the burden on the symbolic execution to generate syntactically valid inputs and helps exercise interesting code paths. Together, symbolic grammars provide a link between exhaustive enumeration of valid inputs and execution-directed symbolic test generation

Preliminary experiments with CESE show that the combination achieves better coverage than both pure enumerative test generation and pure directed symbolic test generation, in orders of magnitude less time and number of generated inputs. In addition, CESE is able to automatically generate inputs that achieve coverage within 10% of manually constructed tests.

REFERENCES

• 1: M. Berkelaar, J. Dirks, K. Eikland, and P. Notebaert. lp_solve (5.5.0.10). 2007.
• 2: A. Bertolino, J. Gao, E. Marchetti, and A. Polini. Systematic generation of XML instances to test complex software applications. In RISE, 2006.
• 3: Dirk Beyer , Adam J. Chlipala , Rupak Majumdar, Generating Tests from Counterexamples, Proceedings of the 26th International Conference on Software Engineering, p.326-335, May 23-28, 2004
• 4: David L Bird , Carlos Urias Munoz, Automatic generation of random self-checking test cases, IBM Systems Journal, v.22 n.3, p.229-245, 1983
• 5: Chandrasekhar Boyapati , Sarfraz Khurshid , Darko Marinov, Korat: automated testing based on Java predicates, Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, July 22-24, 2002, Roma, Italy
• 6: Cristian Cadar , Vijay Ganesh , Peter M. Pawlowski , David L. Dill , Dawson R. Engler, EXE: automatically generating inputs of death, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180445]
• 7: Koen Claessen , John Hughes, QuickCheck: a lightweight tool for random testing of Haskell programs, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.268-279, September 2000
• 8: L. A. Clarke, A System to Generate Test Data and Symbolically Execute Programs, IEEE Transactions on Software Engineering, v.2 n.3, p.215-222, May 1976 [doi>10.1109/TSE.1976.233817]
• 9: David Coppit , Jiexin Lian, yagg: an easy-to-use generator for structured test inputs, Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, November 07-11, 2005, Long Beach, CA, USA [doi>10.1145/1101908.1101969]
• 10: Christoph Csallner , Yannis Smaragdakis, JCrasher: an automatic robustness tester for Java, Software—Practice & Experience, v.34 n.11, p.1025-1050, September 2004 [doi>10.1002/spe.602]
• 11: Christoph Csallner , Yannis Smaragdakis, Check 'n' crash: combining static checking and testing, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062533]
• 12: Christoph Csallner , Yannis Smaragdakis, DSD-Crasher: a hybrid analysis tool for bug finding, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA [doi>10.1145/1146238.1146267]
• 13: Nurit Dor , Michael Rodeh , Mooly Sagiv, CSSV: towards a realistic tool for statically detecting all buffer overflows in C, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 14: Patrice Godefroid, Compositional dynamic test generation, Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 17-19, 2007, Nice, France
• 15: Patrice Godefroid , Nils Klarlund , Koushik Sen, DART: directed automated random testing, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 16: J. B. Goodenough and S. L. Gerhart. Toward a theory of test data selection. IEEE Trans. Software Eng., 1(2):156--173, 1975.
• 17: R. Hamlet. Random testing. In Encyclopedia of Software Engineering, pages 970--978. Wiley, 1994.
• 18: S. C. Johnson. YACC - yet another compiler-compiler. Bell Labs Tehnical Report, (32), 1975.
• 19: Sarfraz Khurshid , Darko Marinov, TestEra: Specification-Based Testing of Java Programs Using SAT, Automated Software Engineering, v.11 n.4, p.403-434, October 2004 [doi>10.1023/B:AUSE.0000038938.10589.b9]
• 20: James C. King, Symbolic execution and program testing, Communications of the ACM, v.19 n.7, p.385-394, July 1976 [doi>10.1145/360248.360252]
• 21: R. Lämmel and W. Schulte. Controllable combinatorial coverage in grammar-based testing. In TestCom, 2006.
• 22: M. E. Lesk and E. Schmidt. Lex - a lexical analyser generator. Bell Labs Tehnical Report, (39), 1975.
• 23: Rupak Majumdar , Koushik Sen, Hybrid Concolic Testing, Proceedings of the 29th international conference on Software Engineering, p.416-426, May 20-26, 2007 [doi>10.1109/ICSE.2007.41]
• 24: Peter M. Maurer, Generating Test Data with Enhanced Context-Free Grammars, IEEE Software, v.7 n.4, p.50-55, July 1990 [doi>10.1109/52.56422]
• 25: W. M. McKeeman. Differential testing for software. Digital Technical Journal, 10(1):100--107, 1998.
• 26: Barton P. Miller , Gregory Cooksey , Fredrick Moore, An empirical study of the robustness of MacOS applications using random testing, Proceedings of the 1st international workshop on Random testing, July 20-20, 2006, Portland, Maine [doi>10.1145/1145735.1145743]
• 27: Barton P. Miller , Louis Fredriksen , Bryan So, An empirical study of the reliability of UNIX utilities, Communications of the ACM, v.33 n.12, p.32-44, Dec. 1990 [doi>10.1145/96267.96279]
• 28: A. Jefferson Offutt , J. Huffman Hayes, A semantic model of program faults, Proceedings of the 1996 ACM SIGSOFT international symposium on Software testing and analysis, p.195-200, January 08-10, 1996, San Diego, California, United States
• 29: C. Pacheco and M. D. Ernst. Eclat: Automatic generation and classification of test inputs. In ECOOP, 2005.
• 30: Carlos Pacheco , Shuvendu K. Lahiri , Michael D. Ernst , Thomas Ball, Feedback-Directed Random Test Generation, Proceedings of the 29th international conference on Software Engineering, p.75-84, May 20-26, 2007 [doi>10.1109/ICSE.2007.37]
• 31: Koushik Sen , Darko Marinov , Gul Agha, CUTE: a concolic unit testing engine for C, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 32: Michael Sipser, Introduction to the Theory of Computation, International Thomson Publishing, 1996
• 33: Emin Gün Sirer , Brian N. Bershad, Using production grammars in software testing, Proceedings of the 2nd conference on Domain-specific languages, p.1-13, October 03-06, 1999, Austin, Texas, United States
• 34: Donald R. Slutz, Massive Stochastic Testing of SQL, Proceedings of the 24rd International Conference on Very Large Data Bases, p.618-622, August 24-27, 1998
• 35: Willem Visser , Corina S. Pǎsǎreanu , Sarfraz Khurshid, Test input generation with java PathFinder, Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, July 11-14, 2004, Boston, Massachusetts, USA

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

General Terms:
Reliability, Verification

Keywords:
concolic execution, grammar based testing, random testing, symbolic grammars, testing C programs