Shape Analysis by Refining on Abstract Evaluation Path

Xiaodong Ma, Ji Wang, Wei DongTTSS 2007 · DOI

TL;DR

This paper introduces a novel shape analysis technique for C programs that can handle complex pointer expressions and memory manipulations. By defining "Abstract Evaluation Paths" (AEPs), the authors refine abstract shape graphs (ASGs) to precisely track memory states, enabling more accurate detection of memory leaks and a clearer definition of program semantics.

What Problem Does This Paper Address?

Static analysis of C programs, particularly those involving pointers and dynamic memory allocation, is notoriously challenging. Understanding how data structures in memory are manipulated is crucial for tasks like memory leak detection and program verification. Traditional shape analysis methods often struggle with complex pointer expressions (like dereferences and field accesses within structures) and the dynamic nature of memory, leading to imprecision or an explosion of possible program states. This paper aims to address this by providing a more precise and efficient way to analyze memory states, especially in the presence of intricate pointer arithmetic and structure traversals.

Methods

The core contribution of this paper is the concept of Abstract Evaluation Path (AEP). An AEP represents a sequence of abstract memory accesses needed to evaluate an expression. The authors define both left AEPs (for l-values) and right AEPs (for r-values).

The key steps of their approach are:

  • Abstract Shape Graph (ASG): The paper builds upon the concept of ASGs, which represent memory states abstractly. They use a 3-valued logic for predicates to handle uncertainty.
  • Refinement using AEPs: The ASG is refined based on the computed AEPs. This process involves creating a set of more precise ASGs where the l-value or r-value of an expression is represented by a unique memory cell. This refinement is crucial for defining statement semantics, as it resolves the ambiguity of multiple possible memory locations for an expression in a standard ASG.
  • Transfer Functions: The paper defines abstract semantics for C statements (like malloc, free, and assignments) as transfer functions that operate on sets of ASGs. These functions use the AEP-based refinement to precisely update the memory state.
  • Memory Leak Detection: The refined ASGs are used to detect memory leaks by identifying specific conditions within the fix-point of the analysis, indicating unreachable memory.

Datasets

Not discussed in the paper. The paper focuses on a novel analysis technique and evaluates it on existing benchmark programs.

Key Insights and Ideas

  • AEPs as a Unifying Concept: AEPs provide a systematic way to navigate and understand complex pointer expressions within an abstract memory model. They bridge the gap between abstract representations and concrete memory access patterns.
  • Refinement for Precision: The core idea of refining the ASG based on AEPs is key. By ensuring that expression values resolve to unique cells in the refined graphs, the authors enable precise definition of statement semantics, similar to concrete execution.
  • Handling Complex Expressions: The method explicitly supports pointers into the middle of structures and arbitrary combinations of pointer operations, which are common sources of imprecision in other analyses.
  • Conservative Memory Leak Detection: The analysis is designed to be conservative, meaning it will flag all real memory leaks (as case 1 or case 2 errors) but may also report false positives.

Key Results

The paper presents experimental results on several benchmark programs, including linked list and tree manipulations.

  • Memory Leak Detection: The prototype successfully detected memory leaks in various programs. The results show that "case 2 error" (a more specific condition) is more precise than "case 1 error."
  • Graph Size: The number of generated shape graphs varied significantly across programs. The paper notes that the choice of core predicates can impact the number of graphs, with shared being beneficial for some programs but detrimental for others.
  • Minimization Trade-offs: The "collapse" operation, used for minimization, can introduce imprecision. For bintree_rotate_left, the analysis without collapse resulted in fewer graphs.

Limitations and Future Work

  • Cut Operation Power: The authors acknowledge that their "cut" operation for cleaning up redundant edges is not very powerful and plan to improve it.
  • Efficiency: While the method is precise, the number of generated graphs can still be large, impacting efficiency. Future work includes improving the efficiency of the method.
  • Core Predicates: The effectiveness of the analysis can depend on the choice of core predicates, and finding optimal sets for different program types is an area for further exploration.
  • Verification: The authors plan to apply their shape analysis results to verify the correctness of C programs.

Summary updated

BibTeX
@article{ma2007shape,
  author = {Xiaodong Ma and Ji Wang and Wei Dong},
  title = {{Shape Analysis by Refining on Abstract Evaluation Path}},
  journal = {TTSS},
  year = {2007},
  doi = {10.1016/j.entcs.2008.03.090},
}
Figure