An Evaluation of Exhaustive Testing for Data Structures
Darko Marinov, Alexandr Andoni, Dumitru Daniliuc, Sarfraz Khurshid, Martin Rinard · 2003
We present an evaluation of exhaustive testing of linked data structures with sophisticated structural constraints. Specifically, we use the Korat testing framework to systematically enumerate all legal inputs within a certain size. We then evaluate the quality of this test suite according to several measurements: ability to detect injected faults in the original correct implementations, code coverage, and specification coverage. Our results indicate that it is feasible to use exhaustive testing to obtain, within a reasonable amount of time, a high-quality test suite that can detect almost all faults and achieve complete code and specification coverage. Moreover, our results show that our exhaustive tests are of higher quality than randomly selected test suites that contain the same number of inputs selected from a larger potential input set. We conclude that exhaustive testing is a practical and effective testing methodology for sophisticated linked data structures. 1.