A Differential Testing Approach for Evaluating Abstract Syntax Tree Mapping Algorithms

Yuanrui Fan, Xin Xia, David Lo, Ahmed E. Hassan, Yuan Wang, Shanping Li

Abstract

Abstract Syntax Tree (AST) mapping is fundamental to code evolution analysis, yet automated verification of mapping accuracy has remained elusive. This paper presents a hierarchical differential testing framework designed to identify mapping errors by comparing outputs from multiple algorithms. By abstracting tool-specific AST nodes into universal statements and tokens, the approach evaluates mappings using similarity measures like token identity and structural context. Evaluation across 263,165 file revisions in ten major Java projects reveals that state-of-the-art tools exhibit inaccuracies in 20% to 36% of cases. The framework achieves high precision (0.98–1.00) and identifies 65%–75% of human-verified errors, highlighting significant opportunities for improving code change mining tools.

Introduction: The Challenge of AST Mapping

When developers modify source code, researchers use Abstract Syntax Tree (AST) mapping to track how specific elements evolve. These algorithms compare "before" and "after" versions of a code's syntax tree to determine "edit actions"—whether a line was moved, updated, or deleted. However, the lack of a ground-truth "gold standard" for large-scale datasets has made it nearly impossible to quantify the reliability of these tools. Consequently, many downstream applications, such as automated program repair or code change miners, are built on potentially flawed foundations.

Source code diff showing additions and deletions in PublishedAddressPolicy.java.

Methodology: Hierarchical Differential Testing

The proposed solution leverages differential testing—a technique where multiple implementations of the same logic are compared to find bugs. The core logic is simple: if two different algorithms map the same code element to two different destinations, at least one of them is likely wrong.

To facilitate this comparison across different tools, the authors developed a hierarchical approach:

  1. Tokenization & Grouping: Instead of comparing raw, tool-specific AST nodes, they break code down into universal units: statements and tokens.
  2. Similarity Comparison: Six specific measures determine which algorithm's mapping is "better." For example, the Number of Identical Tokens (NIT) checks for matching content, while Parent Mapping (PM) ensures structural consistency.
  3. Inconsistency Detection: By comparing these scores, the system automatically flags "inaccurate mappings" for each algorithm.
Overview of the AST mapping process, including code changes, tree representations, and the resulting mapping table.

Evaluation and Results

The researchers evaluated their approach using an expert-validated "gold standard" of 200 statements and a massive large-scale dataset of 263,165 file revisions from 10 popular open-source Java projects (including ActiveMQ, Hibernate, and Spring Framework).

Key results include:

  • High Precision: The automated approach achieved a precision of 0.98–1.00, meaning flagged inaccuracies are almost certainly correct.
  • Solid Recall: It successfully identified 65%–75% of all mapping errors found by human experts.
  • Performance Gap: The study found that popular AST mapping tools are less reliable than previously thought:
  • GumTree (GT): Inaccurate in 20%–29% of revisions.
  • MTDiff (MTD): Inaccurate in 25%–36% of revisions.
  • IJM: Inaccurate in 21%–30% of revisions.

Discussion and Future Work

A critical insight from the study is that current algorithms struggle most with complex refactorings, such as method extraction. In these cases, simple token similarity isn't enough to capture the developer's intent. Furthermore, the "Power of Three"—comparing an algorithm against two others—caught 9–23% more errors than pairwise comparisons, highlighting the value of "triangulating" truth.

Future work involves extending support to languages like C# or Python and integrating these differential testing principles directly into AST mapping tools to help them "self-correct" or provide confidence scores to users.

Summary updated

BibTeX
@inproceedings{fan2021differential,
  author = {Yuanrui Fan and Xin Xia and David Lo and Ahmed E. Hassan and Yuan Wang and Shanping Li},
  title = {{A Differential Testing Approach for Evaluating Abstract Syntax Tree Mapping Algorithms}},
  booktitle = {ICSE},
  year = {2021},
  doi = {10.1109/icse43902.2021.00108},
}
Figure