Construction of Verifier Combinations Based on Off-the-Shelf Verifiers
Open Access
- 29 March 2022
- book chapter
- Published by Springer Nature
- p. 49-70
Abstract
Software verifiers have different strengths and weaknesses, depending on properties of the verification task. It is well-known that combinations of verifiers via portfolio and selection approaches can help to combine the strengths. In this paper, we investigate (a) how to easily compose such combinations fromexisting, ‘off-the-shelf’ verification tools without changing them and (b) how much performance improvement easy combinations can yield, regarding the effectiveness (number of solved problems) and efficiency (consumed resources). First, we contribute a method to systematically and conveniently construct verifier combinations from existing tools, using the composition frameworkCoVeriTeam. We consider sequential portfolios, parallel portfolios, and algorithm selections. Second, we perform a large experiment on 8 883 verification tasks to show that combinations can improve the verification resultswithoutadditional computational resources. All combinations are constructed from off-the-shelf verifiers, that is, we use them as published. The result of our work suggests that users of verification tools can achieve a significant improvement at a negligible cost (only configure our composition scripts).Keywords
This publication has 50 references indexed in Scilit:
- Second Competition on Software Verification2013
- Ufo: A Framework for Abstraction- and Interpolation-Based Software Verification2012
- Learning Algorithm Portfolios for Parallel Execution2012
- CPAchecker: A Tool for Configurable Software Verification2011
- Software model checkingACM Computing Surveys, 2009
- Hierarchical Hardness Models for SAT2007
- The verifying compilerJournal of the ACM, 2003
- An Economics Approach to Hard Computational ProblemsScience, 1997
- Automatically configuring constraint satisfaction programs: A case studyConstraints, 1996
- The Algorithm Selection Problem1976