Predictive testing: amplifying the effectiveness of software testing

ABSTRACT

Testing 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 small program units. We propose predictive testing, a new method for amplifying the effectiveness of existing test cases using symbolic analysis. We assume that a software system has an associated test suite consisting of a set of test inputs and a set of program invariants, in the form of a set of assert statements that the software must always satisfy. Predictive testing uses a combination of concrete and symbolic execution, similar to concolic execution, on the provided test inputs to discover if any of the assertions encountered along a test execution path could be violated for some closely related inputs. We extend predictive testing to catch bugs related to memory-safety violations, integer overflows, and string-related vulnerabilities. Furthermore, we propose a novel technique that leverages the results of unit testing to hoist assertions located deep inside the body of a unit function to the beginning of the unit function. This enables predictive testing to encounter assertions more often in test executions and thereby significantly amplifies the effectiveness of testing.

REFERENCES

• 1: 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
• 2: 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
• 3: J. Condit, M. Harren, Z. Anderson, D. Gay, and G. Necula. Dependent types for low-level programs. Technical Report EECS-2006-129, UC Berkeley, 2006.
• 4: B. Dutertre and L. M. de Moura. A fast linear-arithmetic solver for dpll(t). In Computer Aided Verification, volume 4144 of LNCS, pages 81--94, 2006.
• 5: Justin E. Forrester , Barton P. Miller, An empirical study of the robustness of Windows NT applications using random testing, Proceedings of the 4th conference on USENIX Windows Systems Symposium, p.6-6, August 03-04, 2000, Seattle, Washington
• 6: 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
• 7: R. W. M. Jones and P. H. J. Kelly. Backwards-compatible bounds checking for arrays and pointers in C programs. AADEBUG, 1997.
• 8: 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.
• 9: 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]
• 10: 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]
• 11: George C. Necula , Jeremy Condit , Matthew Harren , Scott McPeak , Westley Weimer, CCured: type-safe retrofitting of legacy software, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.3, p.477-526, May 2005 [doi>10.1145/1065887.1065892]
• 12: George C. Necula , Scott McPeak , Shree Prakash Rahul , Westley Weimer, CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs, Proceedings of the 11th International Conference on Compiler Construction, p.213-228, April 08-12, 2002
• 13: 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
• 14: 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

INDEX TERMS

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

General Terms:
Reliability, Verification