Thumbnail
Access Restriction
Subscribed

Author Kanvar, Vini ♦ Khedker, Uday P.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Abstraction ♦ Heap ♦ Pointers ♦ Shape analysis ♦ Static analysis ♦ Store based ♦ Storeless ♦ Summarization
Abstract Heap data is potentially unbounded and seemingly arbitrary. Hence, unlike stack and static data, heap data cannot be abstracted in terms of a fixed set of program variables. This makes it an interesting topic of study and there is an abundance of literature employing heap abstractions. Although most studies have addressed similar concerns, insights gained in one description of heap abstraction may not directly carry over to some other description. In our search of a unified theme, we view heap abstraction as consisting of two steps: (a) heap modelling, which is the process of representing a heap memory (i.e., an unbounded set of concrete locations) as a heap model (i.e., an unbounded set of abstract locations), and (b) $\textit{summarization},$ which is the process of bounding the heap model by merging multiple abstract locations into summary locations. We classify the heap models as storeless, store based, and hybrid. We describe various summarization techniques based on $\textit{k}-limiting,$ allocation sites, patterns, variables, other generic instrumentation predicates, and higher-order logics. This approach allows us to compare the insights of a large number of seemingly dissimilar heap abstractions and also paves the way for creating new abstractions by mix and match of models and summarization techniques.
Description Author Affiliation: Indian Institute of Technology Bombay, India (Kanvar, Vini; Khedker, Uday P.)
ISSN 03600300
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-06-01
Publisher Place New York
e-ISSN 15577341
Journal ACM Computing Surveys (CSUR)
Volume Number 49
Issue Number 2
Page Count 47
Starting Page 1
Ending Page 47


Open content in new tab

   Open content in new tab
Source: ACM Digital Library