MC/DC automatic test input data generation

ABSTRACT

In regulated domain such as aerospace and in safety critical domains, software quality assurance is subject to strict regulation such as the RTCA DO-178B standard. Among other conditions, the DO-178B mandates for the satisfaction of the modified condition/decision coverage (MC/DC) testing criterion for software where failure condition may have catastrophic consequences. MC/DC is a white box testing criterion aiming at proving that all conditions involved in a predicate can influence the predicate value in the desired way. In this paper, we propose a novel fitness function inspired by chaining test data generation to efficiently generate test input data satisfying the MC/DC criterion. Preliminary results show the superiority of the novel fitness function that is able to avoid plateau leading to a behavior close to random test of traditional white box fitness functions.

REFERENCES

• 1: Paul Ammann , Jeff Offutt , Hong Huang, Coverage Criteria for Logical Expressions, Proceedings of the 14th International Symposium on Software Reliability Engineering, p.99, November 17-21, 2003
• 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: L. Bottaci. Predicate expression cost functions to guide evolutionary search for test data. In E. Cantú-Paz, J.A. Foster, K. Deb, D. Davis, R. Roy, U.-M. O'Reilly, H.-G. Beyer, R. Standish, G. Kendall, S. Wilson, M. Harman, J. Wegener, D. Dasgupta, M.A. Potter, A.C. Schultz, K. Dowsland, N. Jonoska, and J. Miller, editors, Genetic and Evolutionary Computation -- GECCO-2003, pages 2455--2464, Berlin, 2003. Springer-Verlag.
• 4: 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]
• 5: Holger Hoos , Thomas Sttzle, Stochastic Local Search: Foundations & Applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 6: B. Jones, H. Sthamer, and D. Eyres. Automatic structural testing using genetic algorithms. Software Engineering Journal, 11(5):299--306, 1996.
• 7: B. Jones, H. Sthamer, X. Yang, and D.E.T. The automatic generation of software test data sets using adaptive search techniques. In Proceedings of the 3rd International Conference on So Quality Management, Seville, Spain, pages 435--444, 1995.
• 8: B. Korel. Dynamic method of software test data generation. Softw. Test, Verif. Reliab, 2(4):203--213, 1992.
• 9: 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]
• 10: 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, pages 1363--1374. SpringerVerlag, 2004.
• 11: P. McMinn , M. Holcombe, Evolutionary Testing Using an Extended Chaining Approach, Evolutionary Computation, v.14 n.1, p.41-64, March 2006 [doi>10.1162/106365606776022742]
• 12: W. Miller , D. L. Spooner, Automatic Generation of Floating-Point Test Data, IEEE Transactions on Software Engineering, v.2 n.3, p.223-226, May 1976 [doi>10.1109/TSE.1976.233818]
• 13: 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
• 14: 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
• 15: N. Tracey , J. Clark , K. Mander , J. McDermid, Automated test-data generation for exception conditions, Software—Practice & Experience, v.30 n.1, p.61-79, Jan. 2000 [doi>10.1002/(SICI)1097-024X(200001)30:1<61::AID-SPE292>3.0.CO;2-9]
• 16: A. Watkins. The automatic generation of test data using genetic algorithms. In Proceedings of the Fourth Software Quality Conference, pages 300--309. ACM, 1995.
• 17: J. Wegener, A. Baresel, and H. Sthamer. Evolutionary test environment for automatic structural testing. Information&Software Technology, 43(14):841--854, 2001.
• 18: S. Xanthakis, C. Ellis, C. Skourlas, A.L. Gall, S. Katsikas, and K. Karapoulios. Application des algorithmes génétiques au test des logiciels. In 5th Int. Conference on Software Engineering and its Applications, pages 625--636, 1992.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation

Keywords:
mc/dc, search based testing, test input data generation