Empirical analysis of a genetic algorithm-based stress test technique

ABSTRACT

Evolutionary testing denotes the use of evolutionary algorithms, e.g., Genetic Algorithms (GAs), to support various test automation tasks. Since evolutionary algorithms are heuristics, their performance and output efficiency can vary across multiple runs. Therefore, there is a strong need to empirically investigate the capacity of evolutionary test techniques to achieve the desired objectives (e.g., generate stress test cases) and their scalability in terms of the complexity of the System Under Test (SUT), the inputs, and the control parameters of the search algorithms. In a previous work, we presented a GA-based UML-driven, stress test technique aimed at increasing chances of discovering faults related to network traffic in distributed real-time software. This paper reports a carefully-designed empirical study which was conducted to analyze and improve the applicability, efficiency and effectiveness of the above GA-based stress test technique. Detailed stages and objectives of the empirical analysis are reported. The findings of the study are furthermore used to better calibrate the parameters of the GA-based stress test technique.

REFERENCES

• 1: Jeffrey J. P. Tsai , Yaodong Bi , Steve J. H. Yang , Ross A. W. Smith, Distributed real-time systems: monitoring, visualization, debugging, and analysis, John Wiley & Sons, Inc., New York, NY, 1996
• 2: D. Richard Kuhn, Sources of Failure in the Public Switched Telephone Network, Computer, v.30 n.4, p.31-36, April 1997 [doi>10.1109/2.585151]
• 3: Object Management Group (OMG), "UML 2.1.1 Superstructure Specification," 2007.
• 4: Vahid Garousi , Lionel C. Briand , Yvan Labiche, Traffic-aware stress testing of distributed real-time systems based on UML models using genetic algorithms, Journal of Systems and Software, v.81 n.2, p.161-185, February, 2008 [doi>10.1016/j.jss.2007.05.037]
• 5: Vahid Garousi , Lionel C. Briand , Yvan Labiche, Traffic-aware stress testing of distributed systems based on UML models, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134340]
• 6: Mark Harman, The Current State and Future of Search Based Software Engineering, 2007 Future of Software Engineering, p.342-357, May 23-25, 2007 [doi>10.1109/FOSE.2007.29]
• 7: Lionel C. Briand, A Critical Analysis of Empirical Research in Software Testing, Proceedings of the First International Symposium on Empirical Software Engineering and Measurement, p.1-8, September 20-21, 2007 [doi>10.1109/ESEM.2007.8]
• 8: Y. Min, X. Jin, X. Su, and B. Peng, "Empirical Analysis of the Spatial Genetic Algorithm on Small-World Networks," Proc. of Int. Conf. on Computational Science, pp. 1032--1039, 2006.
• 9: G. Rudolph, "Convergence Analysis of Canonical Genetic Algorithms," IEEE Transactions on Neural Networks, vol. 5, no. 1, pp. 96--101, 1994.
• 10: Kumara Sastry , Martin Pelikan , David E. Goldberg, Empirical analysis of ideal recombination on random decomposable problems, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277216]
• 11: Giulio Antoniol , Massimiliano Di Penta , Mark Harman, Search-Based Techniques Applied to Optimization of Project Planning for a Massive Maintenance Project, Proceedings of the 21st IEEE International Conference on Software Maintenance, p.240-249, September 25-30, 2005 [doi>10.1109/ICSM.2005.79]
• 12: Mark Harman , Youssef Hassoun , Kiran Lakhotia , Phil McMinn , Joachim Wegener, The impact of input domain reduction on search-based test data generation, Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, September 03-07, 2007, Dubrovnik, Croatia [doi>10.1145/1287624.1287647]
• 13: Mark Harman , Phil McMinn, A theoretical & empirical znalysis of evolutionary testing and hill climbing for structural test data generation, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273475]
• 14: Man Xiao , Mohamed El-Attar , Marek Reformat , James Miller, Empirical evaluation of optimization algorithms when used in goal-oriented automated test data generation techniques, Empirical Software Engineering, v.12 n.2, p.183-239, April 2007 [doi>10.1007/s10664-006-9026-0]
• 15: Kenneth Alan De Jong, An analysis of the behavior of a class of genetic adaptive systems., University of Michigan, Ann Arbor, MI, 1975
• 16: J Grefenstette, Optimization of control parameters for genetic algorithms, IEEE Transactions on Systems, Man and Cybernetics, v.16 n.1, p.122-128, Jan./Feb. 1986 [doi>10.1109/TSMC.1986.289288]
• 17: V. Garousi, "GARUS (Genetic Algorithm-based test Requirement tool for real-time distribUted Systems)," http://www.enel.ucalgary.ca/~vgarousi/tools/GARUS, 2006.
• 18: Vahid Garousi, Traffic-aware stress testing of distributed real-time systems based on uml models using genetic algorithms, Carleton University, Ottawa, Ont., Canada, 2006
• 19: M. Wall, "GAlib: A C++ Library of Genetic Algorithm Components," Documentation version 2.4, Massachusetts Institute of Technology 1996.
• 20: S. J. Louis and G. J. E. Rawlins, "Predicting Convergence Time for Genetic Algorithms," Technical Report 370, Computer Science Department, Indiana University 1993.
• 21: Randy L. Haupt , Sue Ellen Haupt, Practical genetic algorithms, John Wiley & Sons, Inc., New York, NY, 1998
• 22: Helen G. Cobb , John J. Grefenstette, Genetic Algorithms for Tracking Changing Environments, Proceedings of the 5th International Conference on Genetic Algorithms, p.523-530, June 01, 1993

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:
Algorithms, Experimentation, Reliability

Keywords:
empirical analysis, genetic algorithms, stress testing