A unified fitness function calculation rule for flag conditions to improve evolutionary testing

ABSTRACT

Evolutionary testing (ET), automatically generating test data with good quality, is an effective technique based on evolutionary algorithm. However, the presence of flag variables will make it degenerate to random testing in structural testing. Much of previous work has addressed this problem, but all can be characterized as program-specific. In this paper, flag cost function is introduced as the main component of fitness function, whose value changes with the variation of flag problem. Based on this, a unified fitness calculation rule for flag conditions is proposed. The experiments on programs with flag problems, once considered as inextricable in previous work, and the Traffic Alert and Collision Avoidance System (TCAS) code showed the effectiveness of our unified approach.

REFERENCES

• 1: A. Baresel and H. Sthamer. Evolutionary testing of flag conditions. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'03), pages 2442--2454. Chicago, Illinois, USA, July 2003.
• 2: 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
• 3: J. Wegener, A. Baresel, and H. Sthamer. Evolutionary test environment for automatic structural testing. Information and Software Technology, 43(14):841--854, Dec 2001.
• 4: L. Bottaci. Predicate expression cost functions to guide evolutionary search for test data. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'03), pages 2455--2464. Chicago, Illinois, USA, July 2003.
• 5: 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
• 6: 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
• 7: P. McMinn and M. Holcombe. Hybridizing evolutionary testing with the chaining approach. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'04), pages 1363--1374. Seattle, USA, June 2004.
• 8: 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
• 9: 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]
• 10: J. Clarke, J. J. Dolado, M. Harman, R. 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, 5(1):161--175, Jun 2003.
• 11: W. Zhong, J. Liu, M. Xue, and L. Jiao. A multiagent genetic algorithm for global numerical optimization. IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS-PART B: CYBERNETICS, 34(2):1128--41, Apr 2004.
• 12: 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

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.4 Software/Program Verification
          Subjects: Validation

General Terms:
Algorithms, Verification

Keywords:
fitness function, flag cost function, flag problem