2011 | OriginalPaper | Buchkapitel
Efficient Decision Procedures for Heaps Using STRAND
verfasst von : P. Madhusudan, Xiaokang Qiu
Erschienen in: Static Analysis
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The
Strand
[10] logic allows expressing structural properties of heaps combined with the data stored in the nodes of the heap. A semantic fragment of
Strand
as well as a syntactically defined subfragment of it are known to be decidable [10]. The known decision procedure works by combining a decision procedure for MSO on trees (implemented by the tool
Mona
) and a decision procedure for the quantifier-free fragment of the data-theory (say, integers, and implemented using a solver like Z3).
The known algorithm for deciding the syntactically defined decidable fragment (which is the same as the one for the semantically defined decidable fragment) involves solving large MSO formulas over trees, whose solution is the main bottleneck in obtaining efficient algorithms. In this paper, we focus on the syntactically defined decidable fragment of
Strand
, and obtain a new and more efficient algorithm. Using a set of experiments obtained from verification conditions of heap-manipulating programs, we show the practical benefits of the new algorithm.