The effect of program and model structure on mc/dc test adequacy coverage

ABSTRACT

In avionics and other critical systems domains, adequacy of test suites is currently measured using the MC/DC metric on source code (or on a model in model-based development). We believe that the rigor of the MC/DC metric is highly sensitive to the structure of the implementation and can therefore be misleading as a test adequacy criterion. We investigate this hypothesis by empirically studying the effect of program structure on MC/DC coverage.

To perform this investigation, we use six realistic systems from the civil avionics domain and two toy examples. For each of these systems, we use two versions of their implementation-with and without expression folding (i.e., inlining). To assess the sensitivity of MC/DC to program structure, we first generate test suites that satisfy MC/DC over a non-inlined implementation. We then run the generated test suites over the inlined implementation and measure MC/DC achieved. For our realistic examples, the test suites yield an average reduction of 29.5% in MC/DC achieved over the inlined implementations at 5% statistical significance level.

REFERENCES

• 1: J. Chilenski. An investigation of three forms of the modified condition decision coverage (mcdc) criterion. Technical Report DOT/FAA/AR--01/18, Office of Aviation Research, Washington, D.C., April 2001.
• 2: J. J. Chilenski and S. P. Miller. Applicability of modified condition/decision coverage to software testing. Software Engineering Journal, pages 193---200, September 1994.
• 3: Esterel-Technologies. Corporate web page. www.esterel-technologies.com, 2004.
• 4: Esterel-Technologies. SCADE Suite product description. http://www.esterel-technologies.com/v2/ scadeSuiteFor-SafetyCriticalSoftwareDevelopment/index.html,2004.
• 5: R. Fisher. The Design of Experiment. New York: Hafner, 1935.
• 6: Angelo Gargantini , Constance Heitmeyer, Using model checking to generate tests from requirements specifications, ACM SIGSOFT Software Engineering Notes, v.24 n.6, p.146-162, Nov. 1999
• 7: N. Halbwachs, P. Caspi, P. Raymond, and D. Pilaud. The synchronous dataflow programming language Lustre. Proceedings of the IEEE, 79(9):1305--1320, September 1991.
• 8: Hayhurst Kelly J. , Veerhusen Dan S. , Chilenski John J. , Rierson Leanna K., A Practical Tutorial on Modified Condition/Decision Coverage, NASA Langley Technical Report Server, 2001
• 9: Mats P. E. Heimdahl , Devaraj George, Test-Suite Reduction for Model Based Tests: Effects on Test Quality and Implications for Testing, Proceedings of the 19th IEEE international conference on Automated software engineering, p.176-185, September 20-24, 2004 [doi>10.1109/ASE.2004.67]
• 10: A. Joshi and M. P. Heimdahl. Model-Based Safety Analysis of Simulink Models Using SCADE Design Verifier. In SAFECOMP, volume 3688 of LNCS, pages 122U--135. Springer-Verlag, Sept 2005.
• 11: N. G. Leveson, M. Heimdahl, H. Hildreth, and J. Reese. TCAS II Requirements Speci¯cation.
• 12: MathWorks. The MathWorks Inc. corporate web page. Via the world-wide-web: http://www.mathworks.com, 2004.
• 13: Mathworks Inc. Simulink product web site. Via the world-wide-web: http://www.mathworks.com/products/simulink.
• 14: S. Miller, A. Tribble, T. Carlson, and E. J. Danielson. Flight guidance system requirements specification. Technical Report CR-2003-212426, NASA, June 2003.
• 15: S. P. Miller, E. A. Anderson, L. G. Wagner, M. W. Whalen, and M. P. Heimdahl. Formal veri¯cation of flight critical software. In Proceedings of the AIAA Guidance, Navigation and Control Conference and Exhibit, August 2005.
• 16: S. P. Miller, M. P. Heimdahl, and A. Tribble. Proving the shalls. In Proceedings of FM 2003: the 12th International FME Symposium, September 2003.
• 17: The NuSMV Toolset, 2005. Available at http://nusmv.irst.itc.it/.
• 18: Sanjai Rayadurgam , Mats Per Heimdahl, Automatic test-case generation from formal models of software, University of Minnesota, 2004
• 19: S. Rayadurgam and M. P. Heimdahl. Coverage based test-case generation using model checkers. In Proceedings of the 8th Annual IEEE International Conference and Workshop on the Engineering of Computer Based Systems (ECBS 2001), pages 83--91. IEEE Computer Society, April 2001.
• 20: RTCA. DO-178B: Software Considerations In Airborne Systems and Equipment Certi¯cation. RTCA, 1992.
• 21: ARP 4761: Guidelines and Methods for Conducting the Safety Assessment Process on Civil Airborne Systems and Equipment. SAE International, December 1996.
• 22: RTCA SC-205 (Joint with EUROCAE WG-71) Software Considerations. http://www.rtca.org/comm/Committee.cfm?id=55.
• 23: M. Whalen. Autocoding tools interim report. In NASA Contract NCC-01-001 Project Report, February 2004.

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:
Experimentation

Keywords:
structural coverage metrics