Paper Info
Title
Efficient Bounded Model Checking of Heap-Manipulating Programs using Tight Field Bounds
Abstract
Software model checkers are able to exhaustively explore different bounded program executions arising from various sources of non-determinism. These tools provide statements to produce non-deterministic values for certain variables, thus forcing the corresponding model checker to consider all possible values for these during verification. While these statements offer an effective way of verifying programs handling basic data types and simple structured types, they are inappropriate as a mechanism for nondeterministic generation of pointers, favoring the use of insertion routines to produce dynamic data structures when verifying, via model checking, programs handling such data types. We present a technique to improve model checking of programs handling heap-allocated data types, by taming the explosion of candidate structures that can be built when non-deterministically initializing heap object fields. The technique exploits precomputed relational bounds, that disregard values deemed invalid by the structure's type invariant, thus reducing the state space to be explored by the model checker. Precomputing the relational bounds is a challenging costly task too, for which we also present an efficient algorithm, based on incremental SAT solving. We implement our approach on top of the CBMC bounded model checker, and show that, for a number of data structures implementations, we can handle significantly larger input structures and detect faults that CBMC is unable to detect.
Year
DOI
Venue
2021
10.1007/978-3-030-71500-7-11
FUNDAMENTAL APPROACHES TO SOFTWARE ENGINEERING (FASE 2021)
DocType
Volume
ISSN
Conference
12649
0302-9743
Citations 
PageRank 
References 
0
0.34
0
Authors
6
Name
Order
Citations
PageRank
Pablo Ponzio100.34
Ariel Godio200.34
Nicolás Rosner300.34
Marcelo Arroyo400.34
Nazareno Aguirre500.34
Marcelo F. Frias600.34