Name
Abstract | ||
|---|---|---|
We present a new approach to program testing which enables the programmer to specify test suites in terms of a versatile query language. Our query language subsumes standard coverage criteria ranging from simple basic block coverage all the way to predicate complete coverage and multiple condition coverage, but also facilitates on-the-fly requests for test suites specific to the code structure, to external requirements, or to ad hoc needs arising in program understanding/exploration. The query language is supported by a model checking backend which employs the CBMC framework. Our main algorithmic contribution is a method called iterative constraint strengthening which enables us to solve a query for an arbitrary coverage criterion by a single call to the model checker and a novel form of incremental SAT solving: Whenever the SAT solver finds a solution, our algorithm compares this solution against the coverage criterion, and strengthens the clause database with additional clauses which exclude redundant new solutions. We demonstrate the scalability of our approach and its ability to compute compact test suites with experiments involving device drivers, automotive controllers, and open source projects. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-540-93900-9_15 | VMCAI |
Keywords | Field | DocType |
versatile query language,query language,multiple condition coverage,query-driven program testing,coverage criterion,compact test suite,simple basic block coverage,standard coverage criterion,arbitrary coverage criterion,complete coverage,test suite,model checking,sat solver | Test suite,Query language,Model checking,Programming language,Programmer,Computer science,Boolean satisfiability problem,Basic block,Theoretical computer science,Automotive industry,Scalability | Conference |
Volume | ISSN | Citations |
5403 | 0302-9743 | 20 |
PageRank | References | Authors |
0.73 | 11 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andreas Holzer | 1 | 197 | 13.62 |
| Christian Schallhart | 2 | 1137 | 56.06 |
| Michael Tautschnig | 3 | 425 | 25.84 |
| Helmut Veith | 4 | 2476 | 140.58 |