Control Flow Graph Embedding Based on Multi-Instance Decomposition for Bug Localization

Xuan Huo, Ming Li, Zhi-Hua ZhouAAAI 2020 · OpenReview

Abstract

During software maintenance, bug reports are essential for identifying potential defects. Automatically locating buggy source code from these reports remains a significant challenge. Traditional lexical approaches and recent deep learning models often fail to capture the structural and functional nature of programs. This paper introduces CG-CNN, a multi-instance learning framework that enhances feature representation for bug localization by exploiting the structural and sequential nature of control flow graphs (CFGs). Experimental results on standard software projects demonstrate the superior effectiveness of the CG-CNN model.

Introduction

When a software bug is reported, developers must identify the specific source code files responsible—a process known as bug localization. Historically, this was treated as an information retrieval task, matching the text of bug reports with the text of source code. While modern deep learning models using CNNs and LSTMs have improved performance by capturing local patterns and statement order, they often overlook the structural logic inherent in programming.

Code is not merely a sequence of lines; it contains complex branching (e.g., if-else) and loops (e.g., for, while) that define execution paths. Previous models typically "smeared" these distinct paths together, losing semantic nuances. CG-CNN addresses this by treating source code as a structured Control Flow Graph (CFG) and employing Multi-Instance Learning (MIL) to decompose programs into individual execution paths.

Methodology: The CG-CNN Framework

The CG-CNN (Control flow Graph based Convolutional Neural Network) architecture represents source code through a two-stage process designed to capture both local semantics and global structure.

1. Statement and Context Representation

Initially, the model uses a CNN to capture the internal semantics of individual code statements. To preserve the context of these statements within the program's architecture, DeepWalk (a graph embedding technique) is applied to the CFG. This ensures the model understands both the content of a line and its relationship to neighboring nodes in the graph.

2. Multi-Instance Decomposition

The core innovation is the application of Multi-Instance Learning. A source code file is treated as a "bag," while every possible execution path through the file's CFG is considered an "instance."

The detailed architecture of the programming language specific network in CG-CNN, showing the transition from CFG to multi-instance path processing.

As shown in the figure above, an LSTM processes the sequence of statements within each path. A pooling layer then aggregates these path-level features into a single vector representing the entire file. This approach is particularly effective because a file is deemed "buggy" if even a single execution path is relevant to the bug report. Finally, these features are fused with natural language features extracted from the bug report to predict a match.

Experimental Evaluation

The model was evaluated on four benchmark Java projects: PDE (Eclipse Plug-in Development Environment), PU (Eclipse Platform UI), JU (Eclipse JDT UI), and Tomcat.

Key Results

CG-CNN consistently outperformed six baseline models, including traditional tools like BugLocator and deep learning models like LS-CNN.

Performance comparison of CG-CNN against various baselines across the four benchmark datasets (PDE, PU, JU, and Tomcat).
  • Accuracy Improvements: CG-CNN improved Mean Average Precision (MAP) by an average of 21.3% over BugLocator and by 3.5% to 7.0% over state-of-the-art deep learning models.
  • Top-10 Ranking: The model demonstrated superior performance in identifying buggy files within the top 10 recommendations for the PDE, JU, and Tomcat datasets.

Conclusion and Future Work

The success of CG-CNN highlights that code is best modeled as a graph rather than a simple string. By utilizing CFGs and Multi-Instance Learning, the model respects the branching nature of logic and can isolate buggy signals within specific execution paths.

While the model showed less significant improvement on the PU dataset—likely due to lower code complexity—it sets a new standard for structural bug localization. Future research will explore richer graph representations, such as Data Flow Graphs and Abstract Syntax Trees (ASTs), to capture even deeper semantic information.

Summary updated

Abstract

During software maintenance, bug report is an effective way to identify potential bugs hidden in a software system. It is a great challenge to automatically locate the potential buggy source code according to a bug report. Traditional approaches usually represent bug reports and source code from a lexical perspective to measure their similarities. Recently, some deep learning models are proposed to learn the unified features by exploiting the local and sequential nature, which overcomes the difficulty in modeling the difference between natural and programming languages. However, only considering local and sequential information from one dimension is not enough to represent the semantics, some multi-dimension information such as structural and functional nature that carries additional semantics has not been well-captured. Such information beyond the lexical and structural terms is extremely vital in modeling program functionalities and behaviors, leading to a better representation for identifying buggy source code. In this paper, we propose a novel model named CG-CNN, which is a multi-instance learning framework that enhances the unified features for bug localization by exploiting structural and sequential nature from the control flow graph. Experimental results on widely-used software projects demonstrate the effectiveness of our proposed CG-CNN model.
BibTeX
@inproceedings{huo2020control,
  author = {Xuan Huo and Ming Li and Zhi-Hua Zhou},
  title = {{Control Flow Graph Embedding Based on Multi-Instance Decomposition for Bug Localization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=jNxA6EpcPyd},
}
Figure