Finding errors in .net with feedback-directed random testing

ABSTRACT

We present a case study in which a team of test engineers at Microsoft applied a feedback-directed random testing tool to a critical component of the .NET architecture. Due to its complexity and high reliability requirements, the component had already been tested by 40 test engineers over five years, using manual testing and many automated testing techniques.

Nevertheless, the feedback-directed random testing tool found errors in the component that eluded previous testing, and did so two orders of magnitude faster than a typical test engineer (including time spent inspecting the results of the tool). The tool also led the test team to discover errors in other testing and analysis tools, and deficiencies in previous best-practice guidelines for manual testing. Finally, we identify challenges that random testing faces for continued effectiveness, including an observed decrease in the technique's error detection rate over time.

REFERENCES

• 1: Microsoft .NET Framework. http://www.microsoft.com/net/.
• 2: Agitar. Agitator tool, http://www.agitar.com.
• 3: Boris Beizer, Software Testing Techniques, John Wiley & Sons, Inc., New York, NY, 1990
• 4: 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]
• 5: I. Ciupa and A. Leitner. Automatic testing based on design by contract. In Proceedings of Net.ObjectDays 2005 (6th Annual International Conference on Object--Oriented and Internet-based Technologies, Concepts, and Applications for a Networked World), pages 545--557, September 19-22 2005.
• 6: 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
• 7: 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]
• 8: Roger Ferguson , Bogdan Korel, The chaining approach for software test data generation, ACM Transactions on Software Engineering and Methodology (TOSEM), v.5 n.1, p.63-86, Jan. 1996 [doi>10.1145/226155.226158]
• 9: 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
• 10: 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
• 11: Alex Groce , Gerard Holzmann , Rajeev Joshi, Randomized Differential Testing as a Prelude to Formal Verification, Proceedings of the 29th international conference on Software Engineering, p.621-631, May 20-26, 2007 [doi>10.1109/ICSE.2007.68]
• 12: D. Hamlet. Random testing. In Encyclopedia of Software Engineering. John Wiley and Sons, 1994.
• 13: Dick Hamlet , Ross Taylor, Partition Testing Does Not Inspire Confidence (Program Testing), IEEE Transactions on Software Engineering, v.16 n.12, p.1402-1411, December 1990 [doi>10.1109/32.62448]
• 14: 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]
• 15: D. Marinov, A. Andoni, D. Daniliuc, S. Khurshid, and M. Rinard. An evaluation of exhaustive testing for data structures. Technical Report MIT/LCS/TR-921, MIT Laboratory for Computer Science, Sept. 2003.
• 16: 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]
• 17: Glenford J. Myers , Corey Sandler, The Art of Software Testing, John Wiley & Sons, 2004
• 18: Simeon Ntafos, On random and partition testing, Proceedings of the 1998 ACM SIGSOFT international symposium on Software testing and analysis, p.42-48, March 02-04, 1998, Clearwater Beach, Florida, United States
• 19: C. Oriat. Jartege: A tool for random generation of unit tests for Java classes. In QoSA/SOQUA, pages 242--256, Sept. 2005.
• 20: C. Pacheco and M. D. Ernst. Eclat: Automatic generation and classification of test inputs. In ECOOP 2005 -- Object-Oriented Programming, 19th European Conference, Glasgow, Scotland, July 25-29, 2005.
• 21: Carlos Pacheco , Michael D. Ernst, Randoop: feedback-directed random testing for Java, Companion to the 22nd ACM SIGPLAN conference on Object oriented programming systems and applications companion, October 21-25, 2007, Montreal, Quebec, Canada [doi>10.1145/1297846.1297902]
• 22: 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]
• 23: Parasoft. JTest manuals version 6.0. Online manual.
• 24: K. Sen and G. Agha. CUTE and jCUTE: Concolic unit testing and explicit path model-checking tools. In 18th International Conference on Computer Aided Verification (CAV'06), volume 4144 of Lecture Notes in Computer Science, pages 419--423. Springer, 2006. (Tool Paper).
• 25: Willem Visser , Corina S. Pǎsǎreanu , Radek Pelánek, Test input generation for java containers using state matching, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA [doi>10.1145/1146238.1146243]

INDEX TERMS

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

General Terms:
Reliability

Keywords:
random testing