Access analysis-based tight localization of abstract memories

Hakjoo Oh, Lucas Brutschy, Kwangkeun Yi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Citations (Scopus)


On-the-fly localization of abstract memory states is vital for economical abstract interpretation of imperative programs. Such localization is sometimes called "abstract garbage collection" or "framing". In this article we present a new memory localization technique that is more effective than the conventional reachability-based approach. Our technique is based on a key observation that collecting the reachable memory parts is too conservative and the accessed parts are usually tiny subsets of the reachable. Our technique first estimates, by an efficient pre-analysis, the set of locations that will be accessed during the analysis of each code block. Then the main analysis uses the access-set results to trim the memory entries before analyzing code blocks. In experiments with an industrial-strength global C static analyzer, the technique is applied right before analyzing each procedure's body and reduces the average analysis time and memory by 92.1% and 71.2%, respectively, without sacrificing the analysis precision. Localizing more frequently such as at loop bodies and basic blocks as well as procedure bodies, the generalized localization additionally reduces analysis time by an average of 31.8%.

Original languageEnglish
Title of host publicationVerification, Model Checking, and Abstract Interpretation - 12th International Conference, VMCAI 2011, Proceedings
Number of pages15
Publication statusPublished - 2011
Externally publishedYes
Event12th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2011 - Austin, TX, United States
Duration: 2011 Jan 232011 Jan 25

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6538 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference12th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2011
Country/TerritoryUnited States
CityAustin, TX

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Access analysis-based tight localization of abstract memories'. Together they form a unique fingerprint.

Cite this