A combination framework for tracking partition sizes
Authors:
Open Access
- 21 January 2009
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 44 (1) , 239-251
Abstract
We describe an abstract interpretation based framework for proving relationships between sizes of memory partitions. Instances of this framework can prove traditional properties such as memory safety and program termination but can also establish upper bounds on usage of dynamically allocated memory. Our framework also stands out in its ability to prove properties of programs manipulating both heap and arrays which is considered a difficult task. Technically, we define an abstract domain that is parameterized by an abstract domain for tracking memory partitions (sets of memory locations) and by a numerical abstract domain for tracking relationships between cardinalities of the partitions. We describe algorithms to construct the transfer functions for the abstract domain in terms of the corresponding transfer functions of the parameterized abstract domains. A prototype of the framework was implemented and used to prove interesting properties of realistic programs, including programs that could not have been automatically analyzed before.Keywords
This publication has 24 references indexed in Scilit:
- The Parma Polyhedra Library: Toward a complete set of numerical abstractions for the analysis and verification of hardware and software systemsScience of Computer Programming, 2008
- Towards Efficient Satisfiability Checking for Boolean Algebra with Presburger Arithmetic2007
- Predicate Abstraction and Canonical Abstraction for Singly-Linked ListsLecture Notes in Computer Science, 2005
- Boolean Heaps2005
- Partially Disjunctive Heap AbstractionLecture Notes in Computer Science, 2004
- Quantitative Shape AnalysisLecture Notes in Computer Science, 2004
- Numeric Domains with Summarized Dimensions2004
- Parametric shape analysis via 3-valued logicACM Transactions on Programming Languages and Systems, 2002
- Fast Decision Procedures Based on Congruence ClosureJournal of the ACM, 1980
- Affine relationships among variables of a programActa Informatica, 1976