Online citations, reference lists, and bibliographies.

Hierarchical Shape Abstraction For Analysis Of Free List Memory Allocators

B. Fang, M. Sighireanu
Published 2016 · Computer Science

Cite This
Download PDF
Analyze on Scholarcy
Share
We propose a hierarchical abstract domain for the analysis of free list memory allocators that tracks shape and numerical properties about both the heap and the free lists. Our domain is based on Separation Logic extended with predicates that capture the pointer arithmetics constraints for the heap list and the shape of the free list. These predicates are combined using a hierarchical composition operator to specify the overlapping of the heap list by the free list. In addition to expressiveness, this operator leads to a compositional and compact representation of abstract values and simplifies the implementation of the abstract domain. The shape constraints are combined with numerical constraints over integer arrays to track properties about the allocation policies (best-fit, first-fit, etc.). Such properties are out of the scope of the existing analyzers. We implemented this domain and we show its effectiveness on several implementations of free list allocators.
This paper references
Memory allocation in C. Embedded Systems Programming
L Aldridge (2008)
10.1007/978-3-642-38856-9_10
Local Shape Analysis for Overlaid Data Structures
Cezara Dragoi (2013)
10.1007/978-3-642-33386-6_14
Accurate Invariant Checking for Programs Manipulating Lists and Arrays with Infinite Data
Ahmed Bouajjani (2012)
10.1007/978-3-540-74061-2_24
Shape Analysis with Structural Invariant Checkers
B. E. Chang (2007)
10.1007/11823230_13
Beyond Reachability: Shape Abstraction in the Presence of Pointer Arithmetic
C. Calcagno (2006)
10.1145/1480881.1480912
A combination framework for tracking partition sizes
Sumit Gulwani (2009)
10.1007/11823230_15
Recency-Abstraction for Heap-Allocated Storage
G. Balakrishnan (2006)
10.1145/512950.512973
Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints
P. Cousot (1977)
10.1007/11691372_19
A Local Shape Analysis Based on Separation Logic
Dino Distefano (2006)
10.4204/EPTCS.129.11
Modular Construction of Shape-Numeric Analyzers
Bor-Yuh Evan Chang (2013)
Automated verification of heap-manipulating programs with infinite data
C. Dragoi (2011)
10.1145/1993498.1993566
On inter-procedural analysis of programs with lists and data
A. Bouajjani (2011)
Memory allocation in C
L. Aldridge (1989)
10.1007/978-3-642-33826-7_16
Frama-C - A Software Analysis Perspective
Pascal Cuoq (2012)
10.1007/978-3-662-46081-8_16
Abstraction of Arrays Based on Non Contiguous Partitions
Jiangchao Liu (2015)
10.1007/978-3-319-24953-7_7
On Automated Lemma Generation for Separation Logic with Inductive Definitions
C. Enea (2015)
10.1145/1375581.1375623
Discovering properties about arrays in simple programs
N. Halbwachs (2008)
10.1007/978-3-642-22110-1_48
Program Analysis for Overlaid Data Structures
O. Lee (2011)
10.1145/1328438.1328468
Lifting abstract interpreters to quantified logical domains
Sumit Gulwani (2008)
10.1007/978-3-642-35182-2_10
Hierarchical Shape Abstraction of Dynamic Structures in Static Blocks
Pascal Sotin (2012)
10.1007/3-540-60368-9_19
Dynamic Storage Allocation: A Survey and Critical Review
P. R. Wilson (1995)
10.2307/2283757
The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition
D. Knuth (1968)
The C++ programming language (2nd ed.)
B. Stroustrup (1991)
10.1007/978-3-642-05089-3_24
Field-Sensitive Value Analysis by Field-Insensitive Analysis
E. Albert (2009)
10.1007/3-540-44802-0_1
Local Reasoning about Programs that Alter Data Structures
P. O'Hearn (2001)
The C++ Programming Language, Second Edition
B. Stroustrup (1991)
10.1145/1159974.1134659
Field-sensitive value analysis of embedded C programs with union types and pointer arithmetics
Antoine Miné (2006)
10.1007/978-3-642-02658-4_52
Apron: A Library of Numerical Abstract Domains for Static Analysis
B. Jeannet (2009)



This paper is referenced by
Semantic Scholar Logo Some data provided by SemanticScholar