Evolutionary testing of state-based programs

ABSTRACT

The application of Evolutionary Algorithms to structural test data generation, known as Evolutionary Testing, has to date largely focused on programs with input-output behavior. However, the existence of state behavior in test objects presents additional challenges for Evolutionary Testing, not least because certain test goals may require a search for a sequence of inputs to the test object. Furthermore, state-based test objects often make use of internal variables such as boolean flags, enumerations and counters for managing or querying their internal state. These types of variables can lead to a loss of information in computing fitness values, producing coarse or flat fitness landscapes. This results in the search receiving less guidance, and the chances of finding required test data are decreased.This paper proposes an extended approach based on previous works. Input sequences are generated, and internal variable problems are addressed through hybridization with an extended Chaining Approach. The basic idea of the Chaining Approach is to find a sequence of statements, involving internal variables, which need to be executed prior to the test goal. By requiring these statements are executed, information previously unavailable to the search can be made use of, possibly guiding it into potentially promising and unexplored areas of the test object's input domain. A number of experiments demonstrate the value of the approach.

REFERENCES

• 1: A. Baresel. Automatisierung von strukturtests mit evolutionären algorithmen. Diploma Thesis, Humboldt University, Berlin, Germany, July 2000.
• 2: André Baresel , David Binkley , Mark Harman , Bogdan Korel, Evolutionary testing in the presence of loop-assigned flags: a testability transformation approach, Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, July 11-14, 2004, Boston, Massachusetts, USA
• 3: A. Baresel, H. Pohlheim, and S. Sadeghipour. Structural and functional sequence test of dynamic and state-based software with evolutionary algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2003), Lecture Notes in Computer Science vol. 2724, pages 2428 -- 2441, Chicago, USA, 2003. Springer-Verlag.
• 4: A. Baresel and H. Sthamer. Evolutionary testing of flag conditions. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2003), Lecture Notes in Computer Science vol. 2724, pages 2442 -- 2454, Chicago, USA, 2003. Springer-Verlag.
• 5: André Baresel , Harmen Sthamer , Michael Schmidt, Fitness Function Design To Improve Evolutionary Structural Testing, Proceedings of the Genetic and Evolutionary Computation Conference, p.1329-1336, July 09-13, 2002
• 6: Leonardo Bottaci, Instrumenting Programs With Flag Variables For Test Data Search By Genetic Algorithms, Proceedings of the Genetic and Evolutionary Computation Conference, p.1337-1342, July 09-13, 2002
• 7: 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]
• 8: R. Ferguson and B. Korel. Generating test data for distributed software using the chaining approach. Information and Software Technology, 38(5):343--353, 1996.
• 9: Mark Harman , Lin Hu , Robert M. Hierons , André Baresel , Harmen Sthamer, Improving Evolutionary Testing By Flag Removal, Proceedings of the Genetic and Evolutionary Computation Conference, p.1359-1366, July 09-13, 2002
• 10: Mark Harman , Lin Hu , Rob Hierons , Joachim Wegener , Harmen Sthamer , André Baresel , Marc Roper, Testability Transformation, IEEE Transactions on Software Engineering, v.30 n.1, p.3-16, January 2004 [doi>10.1109/TSE.2004.1265732]
• 11: Bogdan Korel, Automated test data generation for programs with procedures, Proceedings of the 1996 ACM SIGSOFT international symposium on Software testing and analysis, p.209-215, January 08-10, 1996, San Diego, California, United States
• 12: Phil McMinn, Search-based software test data generation: a survey: Research Articles, Software Testing, Verification & Reliability, v.14 n.2, p.105-156, June 2004 [doi>10.1002/stvr.v14:2]
• 13: P. McMinn. Evolutionary Search for Test Data in the Presence of State Behaviour. PhD thesis, University of Sheffield, 2005.
• 14: P. McMinn and M. Holcombe. The state problem for evolutionary testing. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2003), Lecture Notes in Computer Science vol. 2724, pages 2488--2497, Chicago, USA, 2003. Springer-Verlag.
• 15: P. McMinn and M. Holcombe. Hybridizing evolutionary testing with the chaining approach. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2004), Lecture Notes in Computer Science vol. 3103, pages 1363--1374, Seattle, USA, 2004. Springer-Verlag.
• 16: 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
• 17: N. Tracey. A Search-Based Automated Test-Data Generation Framework for Safety Critical Software. PhD thesis, University of York, 2000.
• 18: N. Tracey , J. Clark , K. Mander , J. McDermid, An Automated Framework for Structural Test-Data Generation, Proceedings of the 13th IEEE international conference on Automated software engineering, p.285, October 13-16, 1998
• 19: J. Wegener, A. Baresel, and H. Sthamer. Evolutionary test environment for automatic structural testing. Information and Software Technology, 43(14):841--854, 2001.

INDEX TERMS

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

General Terms:
Verification

Keywords:
automated test data generation, chaining approach, evolutionary testing, state-based programs