TacoFlow: optimizing SAT program verification using dataflow analysis
by
Bruno Cuervo Parrino, Juan Pablo Galeotti, Diego Garbervetsky, Marcelo F. Frias
SoSyM: Software and Systems Modeling, Springer Berlin Heidelberg, 2014.
ISSN: 16191366
Digital Library via DOI: 10.1007/s10270-014-0401-9
Abstract
In previous work, we presented TACO, a tool for efficient bounded verification. TACO translates programs annotated with contracts to a SAT problem which is then solved resorting to off-the-shelf SAT-solvers. TACO may deem propositional variables used in the description of a program initial states as being unnecessary. Since the worst-case complexity of SAT (a known NP problem) depends on the number of variables, most times this allows us to obtain significant speed ups. In this article, we present TacoFlow, an improvement over TACO that uses dataflow analysis in order to also discard propositional variables that describe intermediate program states. We present an extensive empirical evaluation that considers the effect of removing those variables at different levels of abstraction, and a discussion on the benefits of the proposed approach.
Keywords
- SAT-based verification
- Dataflow analysis
- Java-like program verification
BibTeX Entry
@article{galeotti-sosym-2014,
title = "TacoFlow: optimizing SAT program verification using dataflow analysis",
author = "Bruno Cuervo Parrino and Juan Pablo Galeotti and Diego Garbervetsky and Marcelo F. Frias",
year = "2014",
journal = "SoSyM: Software and Systems Modeling",
publisher = "Springer Berlin Heidelberg",
ISSN = "16191366",
doi = "10.1007/s10270-014-0401-9",
}