Evolutionary testing in the presence of loop-assigned flags: a testability transformation approach

ABSTRACT

Evolutionary testing is an effective technique for automatically generating good quality test data. However, for structural testing, the technique degenerates to random testing in the presence of flag variables, which also present problems for other automated test data generation techniques. Previous work on the flag problem does not address flags assigned in loops.This paper introduces a testability transformation that transforms programs with loop--assigned flags so that existing genetic approaches can be successfully applied. It then presents empirical data demonstrating the effectiveness of the transformation. Untransformed, the genetic algorithm flounders and is unable to find a solution. Two transformations are considered. The first allows the search to find a solution. The second reduces the time taken by an order of magnitude and, more importantly, reduces the slope of the cost increase; thus, greatly increasing the complexity of the problem to which the genetic algorithm can be applied. The paper also presents a second empirical study showing that loop--assigned flags are prevalent in real world code. They account for just under 11% of all flags.

REFERENCES

• 1: A. Baresel and H. Sthamer. Evolutionary testing of flag conditions. In Genetic and Evolutionary Computation (GECCO-2003), volume 2724 of LNCS, pages 2442--2454, Chicago, 12-16 July 2003. Springer-Verlag.
• 2: 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
• 3: D. W. Binkley and K. B. Gallagher. Program slicing. In M. Zelkowitz, editor, Advances in Computing, Volume 43, pages 1--50. Academic Press, 1996.
• 4: 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
• 5: British Standards Institute. BS 7925-1 vocabulary of terms in software testing, 1998.
• 6: British Standards Institute. BS 7925-2 software component testing, 1998.
• 7: J. Clark, J. J. Dolado, M. Harman, R. M. Hierons, B. Jones, M. Lumkin, B. Mitchell, S. Mancoridis, K. Rees, M. Roper, and M. Shepperd. Reformulating software engineering as a search problem. IEE Proceedings --- Software, 150(3):161--175, 2003.
• 8: L. A. Clarke. A system to generate test data and symbolically execute programs. IEEE Transactions on Software Engineering, 2(3):215--222, Sept. 1976.
• 9: P. David Coward, Symbolic execution systems—a review, Software Engineering Journal, v.3 n.6, p.229-239, Nov. 1988
• 10: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• 11: Richard A. DeMillo , A. Jefferson Offutt, Experimental results from an automatic test case generator, ACM Transactions on Software Engineering and Methodology (TOSEM), v.2 n.2, p.109-127, April 1993 [doi>10.1145/151257.151258]
• 12: Nachum Dershowitz , Zohar Manna, The evolution of programs: a system for automatic program modification, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.144-154, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512964]
• 13: J. J. Dolado , M. Harman , M. C. Otero , L. Hu, An Empirical Investigation of the Influence of a Type of Side Effects on Program Comprehension, IEEE Transactions on Software Engineering, v.29 n.7, p.665-670, July 2003 [doi>10.1109/TSE.2003.1214329]
• 14: Martin S. Feather, A System for Assisting Program Transformation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.1, p.1-20, Jan. 1982 [doi>10.1145/357153.357154]
• 15: 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]
• 16: Grammatech Inc. The codesurfer slicing system, 2002.
• 17: 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]
• 18: M. Harman and B. F. Jones. Search based software engineering. Information and Software Technology, 43(14):833--839, Dec. 2001.
• 19: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 20: B. Jones, H.-H. Sthamer, and D. Eyres. Automatic structural testing using genetic algorithms. The Software Engineering Journal, 11:299--306, 1996.
• 21: B. F. Jones, D. E. Eyres, and H. H. Sthamer. A strategy for using genetic algorithms to automate branch and fault-based testing. The Computer Journal, 41(2):98--107, 1998.
• 22: 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]
• 23: P. McMinn. A survey of evolutionary testing. Software Testing, Verification and Reliability. To appear.
• 24: C. C. Michael , G. McGraw , M. A. Schatz, Generating Software Test Data by Evolution, IEEE Transactions on Software Engineering, v.27 n.12, p.1085-1110, December 2001 [doi>10.1109/32.988709]
• 25: Melanie Mitchell, An introduction to genetic algorithms, MIT Press, Cambridge, MA, 1996
• 26: F. Mueller , J. Wegener, A Comparison of Static Analysis and Evolutionary Testing for the Verification of Timing Constraints, Proceedings of the Fourth IEEE Real-Time Technology and Applications Symposium, p.144, June 03-05, 1998
• 27: A. Jefferson Offutt, An integrated system for automatically generating test data, Proceedings of the first international conference on systems integration on Systems integration '90, p.694-695, March 1990, Morristown, New Jersey, United States
• 28: R. P. Pargas, M. J. Harrold, and R. R. Peck. Test-data generation using genetic algorithms. The Journal of Software Testing, Verification and Reliability, 9:263--282, 1999.
• 29: Helmut A. Partsch, Specification and transformation of programs: a formal approach to software development, Springer-Verlag New York, Inc., New York, NY, 1990
• 30: H. Pohlheim. Genetic and evolutionary algorithm toolbox for use with Matlab.
• 31: H. Pohlheim and J. Wegener. Testing the temporal behavior of real-time software modules using extended evolutionary algorithms. In W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, and R. E. Smith, editors, Proceedings of the Genetic and Evolutionary Computation Conference, volume 2, page 1795, Orlando, Florida, USA, 13-17 July 1999. Morgan Kaufmann.
• 32: P. Puschner , R. Nossal, Testing the Results of Static Worst-Case Execution-Time Analysis, Proceedings of the IEEE Real-Time Systems Symposium, p.134, December 02-04, 1998
• 33: Radio Technical Commission for Aeronautics. RTCA DO178-B Software considerations in airborne systems and equipment certification, 1992.
• 34: Alan C. Schultz , John J. Grefenstette , Kenneth A. De Jong, Test and Evaluation by Genetic Algorithms, IEEE Expert: Intelligent Systems and Their Applications, v.8 n.5, p.9-14, October 1993 [doi>10.1109/64.236476]
• 35: Frank Tip, A Survey of Program Slicing Techniques., CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1994
• 36: Nigel Tracey , John Clark , Keith Mander, Automated program flaw finding using simulated annealing, Proceedings of the 1998 ACM SIGSOFT international symposium on Software testing and analysis, p.73-81, March 02-04, 1998, Clearwater Beach, Florida, United States
• 37: N. Tracey, J. Clark, and K. Mander. The way forward for unifying dynamic test-case generation: The optimisation-based approach. In International Workshop on Dependable Computing and Its Applications (DCIA), pages 169--180. IFIP, January 1998.
• 38: Jeffrey M. Voas , Keith W. Miller, Software Testability: The New Verification, IEEE Software, v.12 n.3, p.17-28, May 1995 [doi>10.1109/52.382180]
• 39: M. Ward. Reverse engineering through formal transformation. The Computer Journal, 37(5), 1994.
• 40: J. Wegener, A. Baresel, and H. Sthamer. Evolutionary test environment for automatic structural testing. Information and Software Technology Special Issue on Software Engineering using Metaheuristic Innovative Algorithms, 43(14):841--854, 2001.
• 41: J. Wegener, K. Grimm, M. Grochtmann, H. Sthamer, and B. F. Jones. Systematic testing of real-time systems. In 4th International Conference on Software Testing Analysis and Review (EuroSTAR 96), 1996.
• 42: Joachim Wegener , Frank Mueller, A Comparison of Static Analysis and Evolutionary Testing for the Verification of Timing Constraints, Real-Time Systems, v.21 n.3, p.241-268, November 2001 [doi>10.1023/A:1011132221066]
• 43: Joachim Wegener , Harmen Sthamer , Bryan F. Jones , David E. Eyres, Testing real-time systems using genetic algorithms, Software Quality Control, v.6 n.2, p.127-135, 1997 [doi>10.1023/A:1018551716639]
• 44: Mark David Weiser, Program slices: formal, psychological, and practical investigations of an automatic program abstraction method, 1979
• 45: M. Weiser. Program slicing. IEEE Transactions on Software Engineering, 10(4):352--357, 1984.

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)

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Evolutionary prototyping

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Control primitives

General Terms:
Algorithms, Experimentation, Measurement, Performance, Theory

Keywords:
empirical evaluation, evolutionary testing, flags, testability transformation