Access-based abstract memory localization in static analysis

Hakjoo Oh, Kwangkeun Yi

Research output: Contribution to journalArticlepeer-review

3 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 part. Our technique first estimates, by an efficient pre-analysis, which parts of input states 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. In addition, we present three extensions of access-based localization: (1) we generalize the idea and apply the localization more frequently such as at loop bodies and basic blocks as well as procedure bodies, additionally reducing analysis time by an average of 31.8%; (2) we present a technique to mitigate a performance problem of localization in handling recursive procedures, and show that this extension improves the average analysis time by 42%; (3) we show how to incorporate the access-based localization into relational numeric analyses.

Original languageEnglish
Pages (from-to)1701-1727
Number of pages27
JournalScience of Computer Programming
Issue number9
Publication statusPublished - 2013 Sept 1
Externally publishedYes


  • Abstract interpretation
  • Localization
  • Static analysis

ASJC Scopus subject areas

  • Software


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

Cite this