Modular Verification of Procedure Equivalence in the Presence of Memory Allocation

Tim Wood, Sophia Drossopoulou, Shuvendu K. Lahiri, Susan EisenbachESOP 2017 · DOI

TL;DR

This paper introduces RIE, a novel methodology for automatically verifying that two procedures behave identically, even when they dynamically allocate memory and use recursion. It addresses a critical gap in existing tools, enabling more robust program maintenance and refactoring by proving behavioral equivalence under realistic memory management scenarios.

What Problem Does This Paper Address?

Program maintenance and refactoring are crucial but error-prone processes. A significant challenge is automatically verifying that a modified version of a program (e.g., after refactoring) behaves identically to the original. Existing tools often struggle with programs that involve dynamic memory allocation and recursion, as they typically enforce a stricter equivalence (e.g., requiring identical memory states) than what programmers intuitively expect. This paper tackles the problem of establishing "isomorphic equivalence" for procedures, meaning they are equivalent if they transform isomorphic memory states into isomorphic memory states, allowing for differences in memory allocation and garbage collection.

Methods

The core of the paper is the RIE (Replace Isomorphism with Equality) methodology, implemented in a tool called APE (Automatic Program Equivalence tool). RIE leverages the Boogie program verifier and the Z3 SMT solver. Key techniques include:

  • Angelic Allocation: This assumption allows the verifier to treat memory allocation sites as if they could produce addresses that make isomorphic heaps also equal, simplifying the proof.
  • Heap Equality: Instead of strict heap equality, the approach uses "regional isomorphism" and "heap equality" focusing on reachable memory from procedure parameters. This allows for differences in garbage.
  • Product Programs and Mutual Summaries: The authors encode pairs of procedures into a single "product procedure" and use mutual summaries to reason about equivalent procedure calls, enabling modular verification.
  • Under-approximation: Surprisingly, under-approximating memory allocation (rather than over-approximating) is found to be a useful approach for proving soundness.

Datasets

Not discussed in the paper. The paper focuses on a methodology and its implementation, demonstrating its capabilities with examples rather than large-scale dataset evaluations.

Key Insights and Ideas

  • Isomorphism is Key: The paper's central insight is that true procedure equivalence in the presence of memory allocation requires reasoning about isomorphic memory states, not just identical ones. This aligns better with programmer intuition.
  • Equality as a Tool: RIE cleverly uses equality of memory regions (under specific conditions) to establish isomorphism, sidestepping the computational difficulty of directly proving isomorphism.
  • Angelic Allocation Simplifies Proofs: The "angelic allocation" assumption is a powerful abstraction that allows the verifier to find favorable memory configurations, making proofs tractable.
  • Modular Verification is Achievable: By using product programs and mutual summaries, the approach enables modular verification, breaking down complex equivalence checks into manageable parts.

Key Results

The paper presents a sound methodology (RIE) and its implementation (APE) that can automatically verify procedure equivalence for programs with dynamic memory allocation and recursion. The authors demonstrate its effectiveness on examples, including copying binary trees with reordered allocations and recursive calls, and handling cyclic data structures. While specific quantitative results (like accuracy percentages) are not the focus, the paper shows that RIE can tackle challenges that previous tools like Symdiff could not. The timings provided for various examples (Figure 7) show that verification times are generally low (seconds) for many cases, though they increase with the complexity of allocations and recursion.

Limitations and Future Work

  • Allocation Site Permutations: The number of allocation correspondences can be factorial in the number of allocation sites, making the approach potentially impractical for procedures with many distinct allocation sites. The authors suggest that additional static analysis could help eliminate permutations in advance.
  • Framing and Disjointness: The current approach to framing and disjointness of heap regions is described as "naive" and limits the class of examples that can be handled. Improving this is a key area for future work.
  • Mutual Termination: The current verification does not explicitly reason about the termination behavior of procedures, which is noted as an area for potential extension.
  • Completeness: The paper acknowledges that RIE's reliance on equality to establish isomorphism might prevent it from proving equivalence in some cases where it would be helpful, suggesting that tools might need to combine RIE with other techniques or manual annotations.

Summary updated

BibTeX
@inproceedings{wood2017modular,
  author = {Tim Wood and Sophia Drossopoulou and Shuvendu K. Lahiri and Susan Eisenbach},
  title = {{Modular Verification of Procedure Equivalence in the Presence of Memory Allocation}},
  booktitle = {ESOP},
  year = {2017},
  doi = {10.1007/978-3-662-54434-1\_35},
}

Loading related content...

Figure