Koushik Sen
Gul Agha
Abstract
In unit testing, a program is decomposed into units which are collections of functions. A part of unit can be tested by generating inputs for a single entry function. The entry function may contain pointer arguments, in which case the inputs to the unit are memory graphs. The paper addresses the problem of automating unit testing with memory graphs as inputs. The approach used builds on previous work combining symbolic and concrete execution, and more specifically, using such a combination to generate test inputs to explore all feasible execution paths. The current work develops a method to represent and track constraints that capture the behavior of a symbolic execution of a unit with memory graphs as inputs. Moreover, an efficient constraint solver is proposed to facilitate incremental generation of such test inputs. Finally, CUTE, a tool implementing the method is described together with the results of applying CUTE to real-world examples of C code.
- T. Ball. Abstraction-guided test generation: A case study. Technical Report MSR-TR-2003-86, Microsoft Research.Google Scholar
- C. W. Barrett and S. Berezin. CVC Lite: A new implementation of the cooperating validity checker. In Proc. 16th International Conference on Computer Aided Verification, pages 515--518, July 2004.Google ScholarCross Ref
- D. Beyer, A. J. Chlipala, T. A. Henzinger, R. Jhala, and R. Majumdar. Generating Test from Counterexamples. In Proc. of the 26th ICSE, pages 326--335, 2004. Google ScholarDigital Library
- D. Bird and C. Munoz. Automatic Generation of Random Self-Checking Test Cases. IBM Systems Journal, 22(3):229--245, 1983. Google ScholarDigital Library
- C. Boyapati, S. Khurshid, and D. Marinov. Korat: Automated testing based on Java predicates. In Proc. of International Symposium on Software Testing and Analysis, pages 123--133, 2002. Google ScholarDigital Library
- C. Cadar and D. Engler. Execution generated test cases: How to make systems code crash itself. In Proc. of SPIN Workshop, 2005. Google ScholarDigital Library
- K. Claessen and J. Hughes. Quickcheck: A lightweight tool for random testing of Haskell programs. In Proc. of 5th ACM SIGPLAN International Conference on Functional Programming (ICFP), pages 268--279, 2000. Google ScholarDigital Library
- C. Csallner and Y. Smaragdakis. JCrasher: an automatic robustness tester for Java. Software: Practice and Experience, 34:1025--1050, 2004. Google ScholarDigital Library
- C. Csallner and Y. Smaragdakis. Check 'n' Crash: Combining static checking and testing. In 27th International Conference on Software Engineering, 2005. Google ScholarDigital Library
- J. E. Forrester and B. P. Miller. An Empirical Study of the Robustness of Windows NT Applications Using Random Testing. In Proceedings of the 4th USENIX Windows System Symposium, 2000. Google ScholarDigital Library
- P. Godefroid, N. Klarlund, and K. Sen. DART: Directed automated random testing. In Proc. of the ACM SIGPLAN 2005 Conference on Programming Language Design and Implementation (PLDI), 2005. Google ScholarDigital Library
- W. Grieskamp, Y. Gurevich, W. Schulte, and M. Veanes. Generating finite state machines from abstract state machines. In Proc. International Symposium on Software Testing and Analysis, pages 112--122, 2002. Google ScholarDigital Library
- N. Gupta, A. P. Mathur, and M. L. Soffa. Generating test data for branch coverage. In Proc. of the International Conference on Automated Software Engineering, pages 219--227, 2000. Google ScholarDigital Library
- S. Khurshid, C. S. Pasareanu, and W. Visser. Generalized symbolic execution for model checking and testing. In Proc. 9th Int. Conf. on TACAS, pages 553--568, 2003. Google ScholarDigital Library
- B. Korel. A dynamic Approach of Test Data Generation. In IEEE Conference on Software Maintenance, pages 311--317, November 1990.Google ScholarCross Ref
- E. Larson and T. Austin. High coverage detection of input-related security faults. In Proc. of the 12th USENIX Security Symposium (Security '03), Aug. 2003. Google ScholarDigital Library
- lp_solve. http://groups.yahoo.com/group/lp_solve/.Google Scholar
- J. McCarthy and J. Painter. Correctness of a compiler for arithmetic expressions. In Proceedings of Symposia in Applied Mathematics. AMS, 1967.Google ScholarCross Ref
- G. C. Necula, S. McPeak, S. P. Rahul, and W. Weimer. CIL: Intermediate Language and Tools for Analysis and transformation of C Programs. In Proceedings of Conference on compiler Construction, pages 213--228, 2002. Google ScholarDigital Library
- J. Offut and J. Hayes. A Semantic Model of Program Faults. In Proc. of ISSTA'96, pages 195--200, 1996. Google ScholarDigital Library
- C. Pacheco and M. D. Ernst. Eclat: Automatic generation and classification of test inputs. In 19th European Conference Object-Oriented Programming, 2005. Google ScholarDigital Library
- Parasoft. Jtest manuals version 6.0. Online manual, February 2005. http://www.parasoft.com/.Google Scholar
- C. S. Pasareanu, M. B. Dwyer, and W. Visser. Finding feasible counter-examples when model checking abstracted java programs. In Proc. of TACAS'01, pages 284--298, 2001. Google ScholarDigital Library
- K. Sen, D. Marinov, and G. Agha. CUTE: A concolic unit testing engine for C. Technical Report UIUCDCS-R-2005-2597, UIUC, 2005.Google ScholarCross Ref
- SGLIB. http://xref-tech.com/sglib/main.html.Google Scholar
- Valgrind. http://valgrind.org/.Google Scholar
- W. Visser, C. S. Pasareanu, and S. Khurshid. Test input generation with Java PathFinder. In Proc. 2004 ACM SIGSOFT International Symposium on Software Testing and Analysis, pages 97--107, 2004. Google ScholarDigital Library
- S. Visvanathan and N. Gupta. Generating test data for functions with pointer inputs. In 17th IEEE International Conference on Automated Software Engineering, 2002. Google ScholarDigital Library
- T. Xie, D. Marinov, and D. Notkin. Rostra: A framework for detecting redundant object-oriented unit tests. In Proc. 19th IEEE International Conference on Automated Software Engineering, pages 196--205, Sept. 2004. Google ScholarDigital Library
- T. Xie, D. Marinov, W. Schulte, and D. Notkin. Symstra: A framework for generating object-oriented unit tests using symbolic execution. In Proc. of the Tools and Algorithms for the Construction and Analysis of Systems, 2005. Google ScholarDigital Library
Index Terms
- CUTE: a concolic unit testing engine for C
Recommendations
CUTE: a concolic unit testing engine for C
ESEC/FSE-13: Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineeringIn unit testing, a program is decomposed into units which are collections of functions. A part of unit can be tested by generating inputs for a single entry function. The entry function may contain pointer arguments, in which case the inputs to the unit ...
Concolic testing
ASE '07: Proceedings of the 22nd IEEE/ACM International Conference on Automated Software EngineeringConcolic testing automates test input generation by combining the concrete and symbolic (concolic) execution of the code under test. Traditional test input generation techniques use either (1) concrete execution or (2) symbolic execution that builds ...
Predictive testing: amplifying the effectiveness of software testing
ESEC-FSE '07: Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineeringTesting with manually generated test cases often results in poor coverage and fails to discover many corner case bugs and security vulnerabilities. Automated test generation techniques based on static or symbolic analysis usually do not scale beyond ...
Comments