ARTOO: adaptive random testing for object-oriented software

ABSTRACT

Intuition is often not a good guide to know which testing strategies will work best. There is no substitute for experimental analysis based on objective criteria: how many faults a strategy finds, and how fast. "Random" testing is an example of an idea that intuitively seems simplistic or even dumb, but when assessed through such criteria can yield better results than seemingly smarter strategies. The efficiency of random testing is improved if the generated inputs are evenly spread across the input domain. This is the idea of Adaptive Random Testing (ART).

ART was initially proposed for numerical inputs, on which a notion of distance is immediately available. To extend the ideas to the testing of object-oriented software, we have developed a notion of distance between objects and a new testing strategy called ARTOO, which selects as inputs objects that have the highest average distance to those already used as test inputs. ARTOO has been implemented as part of a tool for automated testing of object-oriented software.

We present the ARTOO concepts, their implementation, and a set of experimental results of its application. Analysis of the results shows in particular that, compared to a directed random strategy, ARTOO reduces the number of tests generated until the first fault is found, in some cases by as much as two orders of magnitude. ARTOO also uncovers faults that the random strategy does not find in the time allotted, and its performance is more predictable.

REFERENCES

• 1: Jtest. Parasoft Corporation. http://www.parasoft.com/.
• 2: The EiffelBase Library. Eiffel Software Inc. http://www.eiffel.com/.
• 3: Andrews, J. H., Haldar, S., Lei, Y., and Li, C. H. Randomized unit testing: Tool support and best practices. Tech. Rep. 663, Department of Computer Science, University of Western Ontario, January 2006.
• 4: James H. Andrews , Susmita Haldar , Yong Lei , Felix Chun Hang Li, Tool support for randomized unit testing, Proceedings of the 1st international workshop on Random testing, July 20-20, 2006, Portland, Maine [doi>10.1145/1145735.1145741]
• 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: Kwok Ping Chan , Tsong Yueh Chen , Dave Towey, Restricted Random Testing, Proceedings of the 7th International Conference on Software Quality, p.321-330, June 09-13, 2002
• 7: T. Y. Chen , R. Merkel , G. Eddy , P. K. Wong, Adaptive Random Testing Through Dynamic Partitioning, Proceedings of the Quality Software, Fourth International Conference, p.79-86, September 08-10, 2004 [doi>10.1109/QSIC.2004.6]
• 8: T. Y. Chen , F. C. Kuo , R. G. Merkel , S. P. Ng, Mirror Adaptive Random Testing, Proceedings of the Third International Conference on Quality Software, p.4, November 06-07, 2003
• 9: Chen, T. Y., Leung, H., and Mak, I. K. Adaptive random testing. In Advances in Computer Science - ASIAN 2004: Higher-Level Decision Making. 9th Asian Computing Science Conference. Proceedings (2004), M. J. Maher, Ed., Springer-Verlag GmbH.
• 10: Tsong Yueh Chen , Robert Merkel, Quasi-random testing, Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, November 07-11, 2005, Long Beach, CA, USA [doi>10.1145/1101908.1101957]
• 11: Ilinca Ciupa , Andreas Leitner , Manuel Oriol , Bertrand Meyer, Object distance and its application to adaptive random testing of object-oriented programs, Proceedings of the 1st international workshop on Random testing, July 20-20, 2006, Portland, Maine [doi>10.1145/1145735.1145744]
• 12: Ilinca Ciupa , Andreas Leitner , Manuel Oriol , Bertrand Meyer, Experimental assessment of random testing for object-oriented software, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273476]
• 13: 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]
• 14: Duran, J., and Ntafos, S. An evaluation of random testing. IEEE Transactions on Software Engineering SE-10 (July 1984), 438 -- 444.
• 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: 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]
• 17: Hamlet, R. Random testing. In Encyclopedia of Software Engineering, J. Marciniak, Ed. Wiley, 1994, pp. 970--978.
• 18: Khurshid, S., Pasareanu, C. S., and Visser, W. Generalized symbolic execution for model checking and testing. In Proceedings of the Ninth International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2003) (2003), vol. LNCS 2619, Springer-Verlag, pp. 553--568.
• 19: Leitner, A., and Ciupa, I. AutoTest. http://se.inf.ethz.ch/people/leitner/auto_test/, 2005 - 2007.
• 20: Levenshtein, V. I. Binary codes capable of correcting deletions, insertions, and reversals. Doklady Akademii Nauk SSSR 163, 4 (1965), 845--848.
• 21: Mayer, J. Adaptive random testing by bisection with restriction. In Proceedings of the Seventh International Conference on Formal Engineering Methods (ICFEM 2005) (2005), LNCS 3785, Springer-Verlag, Berlin, pp. 251--263.
• 22: Johannes Mayer, Lattice-based adaptive random testing, Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, November 07-11, 2005, Long Beach, CA, USA [doi>10.1145/1101908.1101963]
• 23: Bertrand Meyer, Object-oriented software construction (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
• 24: Meyer, B., Ciupa, I., Leitner, A., and Liu, L. L. Automatic testing of object-oriented software. In Proceedings of SOFSEM 2007 (Current Trends in Theory and Practice of Computer Science) (2007), J. van Leeuwen, Ed., Lecture Notes in Computer Science, Springer-Verlag.
• 25: Glenford J. Myers, Art of Software Testing, John Wiley & Sons, Inc., New York, NY, 1979
• 26: Oriat, C. Jartege: a tool for random generation of unit tests for Java classes. Tech. Rep. RR-1069-I, Centre National de la Recherche Scientifique, Institut National Polytechnique de Grenoble, Universit´e Joseph Fourier Grenoble I, June 2004.
• 27: Pacheco, C., and Ernst, M. D. Eclat: Automatic generation and classification of test inputs. In ECOOP 2005 - Object-Oriented Programming, 19th European Conference (Glasgow, Scotland, July 25-29, 2005).
• 28: 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]
• 29: Paolo Tonella, Evolutionary testing of classes, Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, July 11-14, 2004, Boston, Massachusetts, USA
• 30: 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
          Subjects: Testing tools (e.g., data generators, coverage testing)

General Terms:
Verification

Keywords:
adaptive random testing, object distance, software testing