ABSTRACT
We present a new tool, named DART, for automatically testing software that combines three main techniques: (1) automated extraction of the interface of a program with its external environment using static source-code parsing; (2) automatic generation of a test driver for this interface that performs random testing to simulate the most general environment the program can operate in; and (3) dynamic analysis of how the program behaves under random testing and automatic generation of new test inputs to direct systematically the execution along alternative program paths. Together, these three techniques constitute Directed Automated Random Testing, or DART for short. The main strength of DART is thus that testing can be performed completely automatically on any program that compiles -- there is no need to write any test driver or harness code. During testing, DART detects standard errors such as program crashes, assertion violations, and non-termination. Preliminary experiments to unit test several examples of C programs are very encouraging.
- R. Alur, P. Cerny, G. Gupta, P. Madhusudan, W. Nam, and A. Srivastava. Synthesis of Interface Specifications for Java Classes. In Proceedings of POPL'05 (32nd ACM Symposium on Principles of Programming Languages), Long Beach, January 2005.]] Google ScholarDigital Library
- T. Ball and S. Rajamani. The SLAM Toolkit. In Proceedings of CAV'2001 (13th Conference on Computer Aided Verification), volume 2102 of Lecture Notes in Computer Science, pages 260--264, Paris, July 2001. Springer-Verlag.]] Google ScholarDigital Library
- D. Beyer, A. J. Chlipala, T. A. Henzinger, R. Jhala, and R. Majumdar. Generating Test from Counterexamples. In Proceedings of ICSE'2004 (26th International Conference on Software Engineering). ACM, May 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 Proceedings of ISSTA'2002 (International Symposium on Software Testing and Analysis), pages 123--133, 2002.]] Google ScholarDigital Library
- W. Bush, J. Pincus, and D. Sielaff. A static analyzer for finding dynamic programming errors. Software Practice and Experience, 30(7):775--802, 2000.]] Google ScholarDigital Library
- K. Claessen and J. Hughes. QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs. In Proceedings of ICFP'2000, 2000.]] Google ScholarDigital Library
- C. Colby, P. Godefroid, and L. J. Jagadeesan. Automatically Closing Open Reactive Programs. In Proceedings of PLDI'98 (1998 ACM SIGPLAN Conference on Programming Language Design and Implementation), pages 345--357, Montreal, June 1998. ACM Press.]] Google ScholarDigital Library
- C. Csallner and Y. Smaragdakis. Check'n Crash: Combining Static Checking and Testing. In Proceedings of ICSE'2005 (27th International Conference on Software Engineering). ACM, May 2005.]] Google ScholarDigital Library
- J. Edvardsson. A Survey on Automatic Test Data Generation. In Proceedings of the 2nd Conference on Computer Science and Engineering, pages 21--28, Linkoping, October 1999.]]Google Scholar
- 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, Seattle, August 2000.]] Google ScholarDigital Library
- P. Godefroid. Model Checking for Programming Languages using VeriSoft. In Proceedings of POPL'97 (24th ACM Symposium on Principles of Programming Languages), pages 174--186, Paris, January 1997.]] Google ScholarDigital Library
- P. Godefroid and S. Khurshid. Exploring Very Large State Spaces Using Genetic Algorithms. In Proceedings of TACAS'2002 (8th Conference on Tools and Algorithms for the Construction and Analysis of Systems), Grenoble, April 2002.]] Google ScholarDigital Library
- S. Gulwani and G. C. Necula. Precise Interprocedural Analysis using Random Interpretation. In To appear in Proceedings of POPL'05 (32nd ACM Symposium on Principles of Programming Languages), Long Beach, January 2005.]] Google ScholarDigital Library
- N. Gupta, A. P. Mathur, and M. L. Soffa. Generating test data for branch coverage. In Proceedings of the 15th IEEE International Conference on Automated Software Engineering, pages 219--227, September 2000.]] Google ScholarDigital Library
- S. Hallem, B. Chelf, Y. Xie, and D. Engler. A System and Language for Building System-Specific Static Analyses. In Proceedings of PLDI'02 (2002 ACM SIGPLAN Conference on Programming Language Design and Implementation), pages 69--82, 2002.]] Google ScholarDigital Library
- R. Hastings and B. Joyce. Purify: Fast Detection of Memory Leaks and Access Errors. In Proceedings of the Usenix Winter 1992 technical Conference, pages 125--138, Berkeley, January 1992.]]Google Scholar
- T. Henzinger, R. Jhala, R. Majumdar, and G. Sutre. Lazy Abstraction. In Proceedings of the 29th ACM Symposium on Principles of Programming Languages, pages 58--70, Portland, January 2002.]] Google ScholarDigital Library
- S. Johnson. Lint, a C program checker, 1978. Unix Programmer's Manual, AT&T Bell Laboratories.]]Google Scholar
- Junit. web page: http://www.junit.org/.]]Google Scholar
- J. C. King. Symbolic Execution and Program Testing. Communications of the ACM, 19(7):385--394, 1976.]] Google ScholarDigital Library
- Klocwork. web page: http://klocwork.com/index.asp.]]Google Scholar
- B. Korel. A dynamic Approach of Test Data Generation. In IEEE Conference on Software Maintenance, pages 311--317, San Diego, November 1990.]]Google ScholarCross Ref
- G. Lowe. An Attack on the Needham-Schroeder Public-Key Authentication Protocol. Information Processing Letters, 1995.]] Google ScholarDigital Library
- G. Lowe. Breaking and Fixing the Needham-Schroeder Public-Key Protocol using FDR. In Proceedings of TACAS'1996 ((Second International Workshop on Tools and Algorithms for the Construction and Analysis of Systems), volume 1055 of Lecture Notes in Computer Science, pages 147--166. Springer-Verlag, 1996.]] Google ScholarDigital Library
- lp_solve. web page: http://groups.yahoo.com/group/lp_solve/.]]Google Scholar
- G. J. Myers. The Art of Software Testing. Wiley, 1979.]] Google ScholarDigital Library
- 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
- G. C. Necula, S. McPeak, and W. Weimer. CCured: Type-Safe Retrofitting of Legacy Code. In Proceedings of POPL'02 (29th ACM Symposium on Principles of Programming Languages), pages 128--139, Portland, January 2002.]] Google ScholarDigital Library
- R. Needham and M. Schroeder. Using Encryption for Authentication in Large Networks of Computers. Communications of the ACM, 21(12):993--999, 1978.]] Google ScholarDigital Library
- The economic impacts of inadequate infrastructure for software testing. National Institute of Standards and technology, Planning Report 02-3, May 2002.]]Google Scholar
- J. Offut and J. Hayes. A Semantic Model of Program Faults. In Proceedings of ISSTA'96 (International Symposium on Software Testing and Analysis), pages 195--200, San Diego, January 1996.]] Google ScholarDigital Library
- Polyspace. web page: http://www.polyspace.com.]]Google Scholar
- D. Saff and M. D. Ernst. Continuous testing in Eclipse. In Proceedings of 2nd Eclipse Technology Exchange Workshop(eTX), Barcelona, March 2004.]]Google ScholarCross Ref
- S. D. Stoller. Domain Partitioning for Open Reactive Programs. In Proceedings of ACM SIGSOFT ISSTA'02 (International Symposium on Software Testing and Analysis), 200.]] Google ScholarDigital Library
- W. Visser, C. Pasareanu, and S. Khurshid. Test Input Generation with Java PathFinder. In Proceedings of ACM SIGSOFT ISSTA'04 (International Symposium on Software Testing and Analysis), Boston, July 2004.]] Google ScholarDigital Library
- J. Whaley, M. C. Martin, and M. S. Lam. Automatic Extraction of Object-Oriented Component Interfaces. In Proceedings of ACM SIGSOFT ISSTA'02 (International Symposium on Software Testing and Analysis), 2002.]] 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 Proceedings of TACAS'05 (11th Conference on Tools and Algorithms for the Construction and Analysis of Systems), volume 3440 of LNCS, pages 365--381. Springer, 2005.]] Google ScholarDigital Library
Index Terms
- DART: directed automated random testing
Recommendations
DART: directed automated random testing
Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementationWe present a new tool, named DART, for automatically testing software that combines three main techniques: (1) automated extraction of the interface of a program with its external environment using static source-code parsing; (2) automatic generation of ...
The Effectiveness of T-Way Test Data Generation
SAFECOMP '08: Proceedings of the 27th international conference on Computer Safety, Reliability, and SecurityThis paper reports the results of a study comparing the effectiveness of automatically generated tests constructed using random and <em>t</em>-way combinatorial techniques on safety related industrial code using mutation adequacy criteria. A reference ...
Prioritizing random combinatorial test suites
SAC '17: Proceedings of the Symposium on Applied ComputingThe behaviour of a system under test can be influenced by several factors, such as system configurations, user inputs, and so on. It has also been observed that many failures are caused by only a small number of factors. Combinatorial testing aims at ...
Comments