On the effectiveness of specification-based structural test-coverage criteria as test-data generators for safety-critical systems

University of Minnesota Ph.D. dissertation. November 2012. Major: Computer science. Advisor: Dr. Mats P.E. Heimdahl. 1 computer file (PDF); ix, 138 pages.Specification based testing aims to reduce the cost of testing and increase the reliability of systems that are of a safety critical nature. A major benefit of a formal specification is the ability to automatically construct test sequences that can be executed on the implementation software. A significant portion of the testing effort in such systems requires us to demonstrate test coverage as mandated by regulatory agencies. Specification based structural test-coverage criteria that mimic source code based criteria offer us a way to analyze the structure of the specification. This typically requires coverage of certain elements such as states, branches, and decisions. These formal specifications also provide us with a means to automatically generate test sequences to satisfy test coverage. Since one of the goals of software testing is to demonstrate the existence of faults, selection of test sequences that can reveal faults is of paramount importance. Nevertheless, the relationship between test-coverage criteria and fault detection is not well established in testing literature. In this dissertation, we investigate the effectiveness of test-coverage criteria when used to drive test-data generation in the safety-critical systems domain. We provide two core contributions. First, due to the lack of sufficient evidence in testing research regarding the quality of test sets generated to satisfy test-coverage criteria, we empirically evaluate the fault-finding ability of test-sets generated to various test coverage criteria proposed in the testing literature. Second, we study the effect of test-suite reduction techniques on the generated test-data sets to empirically evaluate the sensitivity of test-coverage criteria to test-suite reduction techniques. Our findings have raised serious doubts about the use of test-coverage criteria as test-data generators in this domain. In the initial studies conducted, test sequences generated to these coverage criteria perform significantly worse at fault detection when compared to random testing that uses the same effort measured in terms of time to generate and run tests for structural test-coverage criteria such as transition coverage. In the expanded study which was conducted following the initial studies, we evaluated the fault detection effectiveness of test suites reduced to satisfy both branch and MC/DC coverage criteria against a reduced test suite of equal size using a set of random test data. The results from the expanded study validate our earlier findings and have provided us with solid statistical evidence confirming that satisfaction of a highly complex coverage criterion alone is a poor indication of test suite quality. The findings from our studies indicate a need for methods to determine test adequacy that not only provide the desired coverage, but also lend themselves as targets for automated test generation techniques. These criteria must address the problem holistically to account for all factors influencing the quality of testing, including the program structure, the nature of the state space of the system under test, the test oracle used, and finally, the test generation mechanism itself. In addition, we find that reduction techniques designed to minimize the size of a test suite while maintaining structural coverage may significantly reduce the fault-finding effectiveness of the test suite