2007 | OriginalPaper | Buchkapitel
Shape Analysis by Graph Decomposition
verfasst von : R. Manevich, J. Berdine, B. Cook, G. Ramalingam, M. Sagiv
Erschienen in: Tools and Algorithms for the Construction and Analysis of Systems
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
Programs commonly maintain multiple linked data structures. Correlations between multiple data structures may often be
non-existent or irrelevant to verifying that the program satisfies certain safety properties or invariants
. In this paper, we show how this
independence
between different (singly-linked) data structures can be utilized to perform shape analysis and verification more efficiently. We present a new abstraction based on decomposing graphs into sets of subgraphs, and show that, in practice, this new abstraction leads to very little loss of precision, while yielding substantial improvements to efficiency.