Capturing the Long-Distance Dependency in the Control Flow Graph via Structural-Guided Attention for Bug Localization

Yi-Fan Ma, Yali Du, Ming LiIJCAI 2023 · OpenReview

Abstract

To alleviate the burden of software maintenance, bug localization aims to automatically locate buggy source files based on bug reports. Recent studies indicate that program structure in source code carries vital semantics reflecting program behavior. Benefiting from the rich structural information in the Control Flow Graph (CFG), CFG-based methods have achieved state-of-the-art performance. However, existing methods using Graph Neural Networks (GNNs) suffer from information loss during step-wise propagation over long distances. We propose sgAttention, a model employing structural-guided attention to globally capture CFG information while masking irrelevant nodes. Experimental results show sgAttention improves state-of-the-art bug localization methods by up to 32.9% in MAP and 29.2% in MRR.

The Challenge of Long-Distance Dependencies

When a software bug is reported, developers must identify the specific source files responsible. Modern techniques utilize the Control Flow Graph (CFG) to represent execution paths, offering a deeper understanding than simple text matching.

However, traditional CFG-based methods rely on GNNs that propagate information between neighboring nodes. This creates two primary bottlenecks:

  1. Information Loss: In large files, a variable defined at the start may be used much later. As signals travel through dozens of intermediate nodes in a GNN, the original context often vanishes.
  2. Semantic Noise: While standard Transformers can view all lines simultaneously, most lines are logically unrelated. Treating every line as equally relevant introduces noise that degrades localization accuracy.
Figure 1: Illustration of long-distance dependencies in code. Standard GNNs lose information over many steps, while global attention captures irrelevant noise.

Methodology: Structural-Guided Attention

The core innovation of this research is the Structural-Guided Attention mechanism. Instead of allowing every statement to "attend" to every other statement, sgAttention uses the CFG to create a custom masking matrix that enforces logical relevance.

1. Dependency Masking

The model identifies two critical relationships to determine statement connectivity:

  • Execution Dependency: Determines if one statement controls the execution of another (e.g., an if condition and its block).
  • Computation Dependency: Tracks if a statement uses a value defined or modified elsewhere (e.g., a variable declaration and its subsequent return).

These dependencies are both transitive and asymmetric. By building a masking matrix $M$ based on these properties, the model allows a node to directly "see" its logical ancestors, even if they are textually distant in the source file.

Figure 4: The sgAttention framework. Source code is transformed into token and statement features, which are then filtered by a masking matrix derived from the Control Flow Graph (CFG).

2. Multi-Encoder Framework

The sgAttention architecture fuses four distinct views of the data:

  • Statement Encoder: Utilizes CodeBERT to vectorize individual lines of code.
  • CFG Encoder: Applies the structural-guided attention to extract features from the logically connected statements.
  • Lexical Encoder: Captures the raw sequential text of the source file.
  • Report Encoder: Processes the natural language bug report to align it with the code features.

A final Prediction Layer combines these features to calculate the probability that a specific file contains the reported bug.

Experimental Results

The model was evaluated on four major open-source Java projects: Platform (Eclipse), PDE, JDT, and AspectJ. These benchmarks represent complex, real-world software environments.

  • Superiority over CFG-SOTA: sgAttention outperformed previous CFG-based methods (like cFlow) by 32.9% in Mean Average Precision (MAP) and 29.2% in Mean Reciprocal Rank (MRR).
  • Outperforming Pre-trained Models: It surpassed GraphCodeBERT by 5.8% in MAP, demonstrating that explicit structural guidance is more effective than general pre-training alone.
  • Ablation Study: Removing the masking mechanism led to a significant performance drop, confirming that pruning irrelevant logical connections is the primary driver of the model's success.

Conclusion

sgAttention demonstrates that "distance" in code is a matter of logic rather than line numbers. By making the attention mechanism sparse and structurally aware, the model effectively bypasses the vanishing signal problem of GNNs and the noise of dense Transformers. Future work may involve incorporating Abstract Syntax Trees (ASTs) or Call Graphs to further refine the structural context used for localization.

Summary updated

Abstract

To alleviate the burden of software maintenance, bug localization, which aims to automatically locate the buggy source files based on the bug report, has drawn significant attention in the software mining community. Recent studies indicate that the program structure in source code carries more semantics reflecting the program behavior, which is beneficial for bug localization. Benefiting from the rich structural information in the Control Flow Graph (CFG), CFG-based bug localization methods have achieved the state-of-the-art performance. Existing CFG-based methods extract the semantic feature from the CFG via the graph neural network. However, the step-wise feature propagation in the graph neural network suffers from the problem of information loss when the propagation distance is long, while the long-distance dependency is rather common in the CFG. In this paper, we argue that the long-distance dependency is crucial for feature extraction from the CFG, and propose a novel bug localization model named sgAttention. In sgAttention, a particularly designed structural-guided attention is employed to globally capture the information in the CFG, where features of irrelevant nodes are masked for each node to facilitate better feature extraction from the CFG. Experimental results on four widely-used open-source software projects indicate that sgAttention averagely improves the state-of-the-art bug localization methods by 32.9\% and 29.2\% and the state-of-the-art pre-trained models by 5.8\% and 4.9\% in terms of MAP and MRR, respectively.
BibTeX
@inproceedings{ma2023capturing,
  author = {Yi-Fan Ma and Yali Du and Ming Li},
  title = {{Capturing the Long-Distance Dependency in the Control Flow Graph via Structural-Guided Attention for Bug Localization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=3VQXcQ7GRg},
}
Figure