PaperlayerView exact revision on arXiv

Source-linked AI summary

Convolutional Neural Networks over Control Flow Graphs for Software Defect Prediction

Anh Viet Phan, Minh Le Nguyen, Lam Thu Bui

arXiv:1802.04986v1cs.SEcs.LGcs.NE

TL;DR

Existing metrics and AST representations may fail to capture program semantics, while defects can emerge only under specific execution conditions. The method compiles source code into assembly, constructs execution-flow CFGs, and applies DGCNNs to learn defect features. On four real-world datasets, learning on graphs improved accuracies by 4.08% to 15.49% over feature-based approaches and 1.2% to 12.39% over tree-based approaches.

  • Problem

    Existing metrics and AST representations may fail to capture program semantics, while defects can emerge only under specific execution conditions.

    Source: §I · p. 1

  • Method

    The method compiles source code into assembly, constructs execution-flow CFGs, and applies DGCNNs to learn defect features.

    Source: §I · p. 2, §VI · p. 8

  • Results

    On four real-world datasets, learning on graphs improved accuracies by 4.08% to 15.49% over feature-based approaches and 1.2% to 12.39% over tree-based approaches.

    Source: §VI · p. 8

  • Takeaways & Limitations

    The evaluation concludes that precise control-flow graphs of binary code are suitable for software defect prediction and improve discrimination, including on imbalanced data.

    Source: §IV · p. 6

Abstract

from arXiv · show

Existing defects in software components is unavoidable and leads to not only a waste of time and money but also many serious consequences. To build predictive models, previous studies focus on manually extracting features or using tree representations of programs, and exploiting different machine learning algorithms. However, the performance of the models is not high since the existing features and tree structures often fail to capture the semantics of programs. To explore deeply programs' semantics, this paper proposes to leverage precise graphs representing program execution flows, and deep neural networks for automatically learning defect features. Firstly, control flow graphs are constructed from the assembly instructions obtained by compiling source code; we thereafter apply multi-view multi-layer directed graph-based convolutional neural networks (DGCNNs) to learn semantic features. The experiments on four real-world datasets show that our method significantly outperforms the baselines including several other deep learning approaches.

I. INTRODUCTION

Software defect prediction matters because defects can raise costs and cause serious deployment consequences. The paper argues that existing metrics and tree representations can miss program semantics, motivating execution-flow graphs and deep learning.

I. INTRODUCTION

  • Manually designed software metrics often fail to capture program semantics, and classifier performance has remained limited despite efforts to improve learning algorithms and data.Traditional metrics include Halstead, CK, and McCabe measures.Source: §I · p. 1
  • Metrics and ASTs can represent two procedures identically even when one contains an assignment that causes an infinite loop for N>=1.The procedures have the same name and differ only slightly, but the defect affects execution under a specific condition.Source: §I · pp. 1–2
  • The proposed pipeline compiles source code to assembly, constructs CFGs of execution flows, and uses DGCNNs to learn defect features.The paper describes assembly instructions as atomic and their CFGs as representing step-by-step execution.Source: §I · p. 2
  • The paper presents CFGs as an application to defect prediction and reports experimentally evaluating their use for high-performance classifiers.It also presents an algorithm for constructing assembly-code CFGs and releases the model implementation.Source: §I · p. 2

II. THE PROPOSED APPROACH

The approach has two stages: construct CFGs from compiled assembly to represent program behavior, then train a directed-graph neural network on those graphs to build defect-prediction models.

II. THE PROPOSED APPROACH

  • The approach first compiles source code into assembly and constructs CFGs that describe the execution flows of assembly instructions.The paper presents the pipeline as generating CFGs followed by applying a graphical model to CFG datasets.Source: §II · p. 2
  • The second stage uses a multi-view, multi-layer convolutional neural network for directed labeled graphs to build predictive models from CFG data.The model is used to learn automatically from the CFG datasets.Source: §II · p. 2

A. Control Flow Graphs

The paper uses assembly-code CFGs to represent execution paths for defect prediction. Its construction procedure partitions instructions into blocks and adds directed edges for possible control transfers.

A. Control Flow Graphs

  • A CFG is a directed graph whose vertices are basic blocks and whose edges represent control-flow paths.Each basic block is a linear instruction sequence with one entry point and one exit point.Source: A. Control Flow Graphs · p. 2
  • The paper focuses on C source code and uses CFGs of compiled assembly because semantic errors become visible during program execution.The authors suggest that analyzing assembly-instruction execution flows may help distinguish faulty from non-faulty patterns.Source: A. Control Flow Graphs · p. 2
  • The CFG construction algorithm partitions assembly instructions into blocks based on labels, then creates edges to represent control-flow transfers.The algorithm takes an assembly file as input and outputs a CFG.Source: A. Control Flow Graphs · p. 2
  • Sequential instructions are linked, jumps connect to target blocks, and function calls use edges into the function and back to the following instruction.The described edge rules model possible execution paths through the instruction blocks.Source: A. Control Flow Graphs · p. 3

B. Multi-view Multi-layer Graph-based Convolutional Neural Networks

The DGCNN represents CFG vertices through multiple views, extracts features with stacked graph convolutions, and pools them into a fixed-size representation. Its design accommodates varying graph structures and vertex labels.

B. Multi-view Multi-layer Graph-based Convolutional Neural Networks

A. Datasets

The study evaluates four benchmark datasets drawn from CodeChef programming submissions. The datasets cover distinct problems and use assessment outcomes as class labels.

A. Datasets

  • The four datasets represent CodeChef problems SUMTRIAN, FLOW016, MNMX, and SUBINC.They concern triangle paths, GCD/LCM, array reduction, and counting non-decreasing subarrays, respectively.Source: A. Datasets · p. 4
  • Each program is labeled by its assessment outcome: accepted, time limit exceeded, wrong answer, runtime error, or syntax error.Source: A. Datasets · p. 4
  • Submissions in C or C++ collected through March 14, 2017 were filtered to remove empty or uncompilable source files.Source: A. Datasets · p. 4
  • All datasets are imbalanced; in MNMX, classes 2, 3, and 4 occur at ratios of 1:27, 1:46, and 1:24 relative to class 0.Each dataset is randomly divided into training, validation, and test folds in a 3:1:1 ratio.Source: A. Datasets · p. 4

B. Experimental Setup

The experiments compare DGCNN with tree-based and neural-network baselines using common hyperparameters. DGCNN inputs use instruction and instruction-type views, with symbol-based vector representations.

B. Experimental Setup

  • Neural-network baselines include TBCNN, SibStCNN, and RvNN, and share a learning rate of 0.1 and token-vector size of 30 with DGCNN.Source: B. Experimental Setup · p. 5
  • DGCNN uses instruction and instruction-type views, grouping related instructions and replacing operands such as names, registers, and literals with symbols.For example, addq $32, %rsp becomes addq value, reg.Source: B. Experimental Setup · p. 5
  • Instruction-view vectors are formed as linear combinations of randomly initialized symbol vectors.The addq example combines the vectors for addq, value, and reg.Source: B. Experimental Setup · p. 5
  • The baselines also include kNN with tree-edit or Levenshtein distance at k=3, and an RBF-kernel SVM using bag-of-words features.The SVM parameters are C=1 and γ=0.Source: B. Experimental Setup · p. 5

C. Evaluation Measures

The study evaluates classifiers using accuracy and AUC. AUC is emphasized as informative for imbalanced datasets, where minority-class hit rates can remain low despite high overall accuracy.

C. Evaluation Measures

  • Both accuracy and AUC are used to evaluate the approaches, with AUC estimated from macro-averaged ROC curves.Macro-averaging gives each class equal weight, unlike micro-averaging, which weights each sample decision equally.Source: C. Evaluation Measures · p. 5
  • For multiclass classification, accuracy is estimated as the average hit rate.Source: C. Evaluation Measures · p. 5
  • Because the datasets are imbalanced, the authors use AUC alongside accuracy; high overall accuracy can coexist with low hit rates on minority classes.The paper identifies faulty instances as minority classes in many software defect datasets.Source: C. Evaluation Measures · p. 5

IV. RESULTS AND DISCUSSION

CFG-based approaches achieve the highest accuracies on the four experimental datasets, with DGCNN improving on the second-best classifiers. DGCNN also improves AUC on average, including on imbalanced data.

IV. RESULTS AND DISCUSSION

  • CFG-based approaches significantly outperform others, improving accuracy over the second-best classifiers by 12.39% on FLOW016, 1.2% on MNMX, 7.71% on SUBINC, and 1.98% on SUMTRIAN.Applying DGCNN to CFGs achieves the highest accuracies on the experimental datasets.Source: §IV · pp. 5–6, Table III · p. 6
  • DGCNN improves on the second-best classifiers by an average of 0.03 on AUC scores, and graph-based approaches outperform tree-based approaches.The paper reports this advantage for probabilistic classifiers and notes it holds even on imbalanced data.Source: Table IV · p. 6, §IV · p. 6
  • DGCNN with one view reaches accuracies of 75.49% on FLOW016 and 84.05% on MNMX, while two views reach 76.02% on SUBINC and 68.95% on SUMTRIAN.The authors report that using both instruction and instruction-group views, and including instruction components, benefits accuracy.Source: §IV · p. 6
  • On MNMX, both TBCNN and DGCNN 1V NoOp have lower ability to detect minority instances, and TBCNN is equivalent to random classification for class 4.The authors report similar minority-class detection problems across approaches and experimental datasets.Source: Figure 4 · p. 6, §IV · p. 6

V. ERROR ANALYSIS

The error analysis finds that CFG-based approaches handle some code-structure changes that affect tree-based approaches, but DGCNN may still struggle when statement replacements substantially change CFG node contents. Both tree- and graph-based approaches also miss semantics from external library procedures absent from the generated representations.

V. ERROR ANALYSIS

  • RvNN performance degrades as tree size increases, with lower accuracy and AUC on larger trees, especially on SUMTRIAN.SibStCNN and TBCNN outperform other tree-based baselines by learning features from subtrees.Source: §V · p. 7
  • Tree-based approaches are affected by AST structure changes because position-determined node weights make SibStCNN and TBCNN sensitive to tree shape and size.Reordering statements or replacing them with equivalent ones can reorder or add AST branches.Source: §V · p. 7
  • CFG-based approaches handle varied loop representations and statement relocation that may leave assembly largely unchanged, and CFG edges capture procedure calls.The analysis contrasts these cases with tree-based approaches’ sensitivity to AST shape.Source: §V · p. 7
  • DGCNN may fail on replacements that substantially change CFG node contents, including equivalent output statements such as printf and cout.The assembly instruction sets for int and long int also differ even when the operator is the same.Source: §V · pp. 7–8
  • Neither tree- nor graph-based approaches captures semantics of external library procedures when their contents are absent from the generated representations.The example contrasts a library __gcd call with ordinary C statements for computing the same function.Source: §V · p. 8

VI. CONCLUSION

The paper presents defect prediction using assembly-derived control flow graphs and a graph-based neural network. Across four real-world datasets, it reports improved performance over feature-based and tree-based approaches.

VI. CONCLUSION

  • The end-to-end model constructs a program’s CFG from assembly code generated by compiling its source code.Source: §VI · p. 8
  • DGCNN learns from CFG information to build predictive models for detecting faulty source code.Source: §VI · p. 8
  • 4.08% to 15.49% accuracy improvement over feature-based approaches and 1.2% to 12.39% over tree-based approaches are reported across four real-world datasets.Source: §VI · p. 8
Loading 1802.04986v1…