Generating Efficient Test Sets with a Model Checker

Grégoire Hamon, Leonardo de Moura, and John Rushby

Presented at SEFM 04, Beijing, China, September 2004; appears in the proceedings published by IEEE, pp. 261-270.

Abstract

It is well-known that counterexamples produced by model checkers can provide a basis for automated generation of test cases. However, when this approach is used to meet a coverage criterion, it generally results in very inefficient test sets having many tests and much redundancy. We describe an improved approach that uses model checkers to generate efficient test sets. Furthermore, the generation is itself efficient, and is able to reach deep regions of the statespace. We have prototyped the approach using the model checkers of our SAL system and have applied it to model-based designs developed in Stateflow. In one example, our method achieves complete state and transition coverage in a Stateflow model for the shift scheduler of a 4-speed automatic transmission with a single test case.

gzipped postscript, or plain postscript or PDF or crude ascii (for your Palm Pilot)

Download

You can download sal-atg, a tool that implements this approach, from here.

Slides

These are from a talk given at the National Institute of Aerospace, Hampton VA on 26 July 2004.
gzipped postscript, or plain postscript or pdf

BibTeX Entry

@inproceedings{HdeMR04,
	AUTHOR = {Gr\'{e}goire Hamon and Leonardo deMoura and John Rushby},
	TITLE = {Generating Efficient Test Sets with a Model Checker},
	BOOKTITLE = {2nd International Conference on Software Engineering and Formal Methods},
	ADDRESS = {Beijing, China},
	ORGANIZATION = {IEEE Computer Society},
	PAGES = {261--270},
	MONTH = sep,
	YEAR = 2004
}
Having trouble reading our papers?
Return to the Formal Methods Program home page
Return to the Computer Science Laboratory home page