PaperlayerView exact revision on arXiv

Source-linked AI summary

Detecting Code Clones with Graph Neural Networkand Flow-Augmented Abstract Syntax Tree

Wenhan Wang, Ge Li, Bo Ma, Xin Xia, Zhi Jin

arXiv:2002.08653v1cs.SEcs.AI

TL;DR

Semantic clone detection remains challenging because AST-based approaches do not fully capture control and data flow. This paper augments ASTs into FA-AST and applies two GNNs to compare code fragments, outperforming most existing approaches across Google Code Jam and BigCloneBench.

  • Problem

    Most clone detectors focus on syntactic similarity, while AST-based methods do not fully leverage semantic information such as control flow and data flow.

  • Method

    The paper constructs FA-AST by adding control- and data-flow edges to ASTs, then applies GGNN and GMN to learn code representations and measure pair similarity.

  • Results

    The approach outperforms most existing approaches, including several AST-based deep-learning methods, on Google Code Jam and BigCloneBench.

  • Takeaways & Limitations

    Combining AST syntax with explicit control and data flow through GNNs enhances semantic code-clone detection on the evaluated Java datasets.

Abstract

from arXiv · show

Code clones are semantically similar code fragments pairs that are syntactically similar or different. Detection of code clones can help to reduce the cost of software maintenance and prevent bugs. Numerous approaches of detecting code clones have been proposed previously, but most of them focus on detecting syntactic clones and do not work well on semantic clones with different syntactic features. To detect semantic clones, researchers have tried to adopt deep learning for code clone detection to automatically learn latent semantic features from data. Especially, to leverage grammar information, several approaches used abstract syntax trees (AST) as input and achieved significant progress on code clone benchmarks in various programming languages. However, these AST-based approaches still can not fully leverage the structural information of code fragments, especially semantic information such as control flow and data flow. To leverage control and data flow information, in this paper, we build a graph representation of programs called flow-augmented abstract syntax tree (FA-AST). We construct FA-AST by augmenting original ASTs with explicit control and data flow edges. Then we apply two different types of graph neural networks (GNN) on FA-AST to measure the similarity of code pairs. As far as we have concerned, we are the first to apply graph neural networks on the domain of code clone detection. We apply our FA-AST and graph neural networks on two Java datasets: Google Code Jam and BigCloneBench. Our approach outperforms the state-of-the-art approaches on both Google Code Jam and BigCloneBench tasks.

I. INTRODUCTION

Code clone detection increasingly targets semantic similarity, but AST-based methods omit control- and data-flow information. The paper introduces FA-AST with GNNs and evaluates it on two Java datasets.

  • Type-4 clones are syntactically dissimilar but functionally similar, making semantic clone detection especially difficult.
  • AST-based deep-learning approaches capture program syntax but do not include semantic information such as control flow and data flow.
  • CFG-based approaches capture control flow but may lack data flow, low-level syntax, or easy availability across programming languages.
  • FA-AST augments ASTs with control- and data-flow edges, combining syntactic and semantic program information.
  • GGNN and GMN learn code-fragment representations, whose similarity is used to determine whether fragment pairs are clones.
  • The approach is evaluated on Google Code Jam and BigCloneBench, with comparable state-of-the-art performance on BigCloneBench and better performance on Google Code Jam.

A. Code Clone Detection

Code clones range from nearly identical fragments to syntactically dissimilar fragments sharing functionality. Graph neural networks address graph-structured program information, where nodes and edges encode entities and their relationships.

  • A. Code Clone Detection: Type-1 clones differ only in whitespace and comments, while Type-2 clones also permit identifier-name and literal-value differences.
  • A. Code Clone Detection: Type-3 clones are syntactically similar but can add, modify, or remove statements relative to one another.
  • A. Code Clone Detection: Type-4 clones are syntactically dissimilar fragments that implement the same functionality, such as bubble sort and quick sort.
  • A. Code Clone Detection: BigCloneBench subdivides the ambiguous Type-3/Type-4 boundary into strongly, moderately, and weakly Type-3 categories.
  • B. Graph Neural Networks: Graph data contains nodes and relationships between nodes, unlike the pixels of images or the word sequences of natural language.
  • B. Graph Neural Networks: Message-passing GNNs update node states using neighboring information and then compute a whole-graph representation through a readout function.

III. PROBLEM DEFINITION

The paper defines clone detection as learning similarity between labeled code-fragment pairs, then represents programs as FA-AST graphs enriched with syntactic, control-flow, and data-flow information.

  • Clone detection learns a similarity function that maps code fragments to vectors and approximates clone labels for fragment pairs.
  • The approach parses code into ASTs, augments them with control- and data-flow edges, and processes paired graphs with neural networks.
  • FA-AST preserves AST syntax while adding sequential, conditional, loop, and other control-flow edges to represent program behavior.
  • The design retains AST-level semantics because control-flow graphs may have fewer edges and statement-level nodes that lose internal semantic information when simply embedded.
  • If statements use CondTrue and CondFalse edges, while loops use WhileExec and WhileNext edges, and for loops use ForExec and ForNext edges.
  • Sequential statement subtrees are connected by Nextstmt edges, and forward-only edges receive backward counterparts to increase message passing.

C. Neural Network Model for Modeling Code Pairs

The paper uses two GNN families for code-pair modeling: separate graph embedding and joint graph matching.

  • The method uses a traditional GNN for graph embeddings and a graph matching network that jointly models two graphs.

1) Graph Embedding Model:

The graph embedding model uses GGNN message passing and readout components to learn embeddings for individual program graphs.

  • GGNN learns graph embeddings using an MLP as the message function and a GRU as the vertex-update function.
  • The model uses a readout function to derive a whole-graph representation from node states.

2) Graph Matching Networks:

Graph Matching Networks jointly embed code-graph pairs by adding cross-graph attention to standard graph propagation. In this approach, GMN operates on FA-AST graphs that encode syntax, control flow, and data flow.

  • Graph Matching Networks: GMN jointly learns embeddings for a pair of graphs using cross-graph attention between nodes.Unlike traditional GNN propagation, GMN computes matching information across the two input graphs.
  • Graph Matching Networks: The matching mechanism uses node similarity to aggregate information from the other graph into each node’s update.The paper uses dot product for vector similarity and a GRU-based node updater.
  • Experiment Data: The experiments evaluate the approach on Google Code Jam and BigCloneBench, which differ in dataset size, fragment length, and clone composition.BigCloneBench contains over 6,000,000 true clone pairs and 260,000 false clone pairs, whereas GCJ contains 1,669 Java files from 12 problems.
  • Experiment Data: The datasets contain varied control-flow patterns, with BlockStatement most frequent and ForStatement more common in GCJ than BigCloneBench.The authors use these differences to examine generalizability across code domains and granularities.

B. Experiment Settings

The experiments compare FA-AST-based GNN models with established AST and CFG-oriented clone detectors under fixed training and evaluation settings.

  • Baselines: The comparison includes DECKARD, RtvNN, CDLH, and ASTNN as representative AST-based clone detection approaches.These baselines use subtree vectors, recursive neural representations, Tree-LSTM encodings, or statement-subtree sequences.
  • Implementation: The models use 100-dimensional GNN layers and token embeddings, four propagation steps, Adam with learning rate 0.001, and batch size 32.Thresholds are tuned on validation results.
  • Data Preparation: Both datasets are split into training, validation, and test sets at 8:1:1, with false clone pairs downsampled to achieve a 1:1 training ratio.The BigCloneBench experiments use the same 9,134 code fragments as prior work.

C. Experiment Results

FA-AST models perform strongly across Google Code Jam and BigCloneBench, with GMN generally improving F1 over GGNN and showing greater threshold stability. The analysis also finds stronger performance on semantic clone types, while graph-neighbour treatment remains a limitation.

  • Results on Google Code Jam: 0.98 F1: FA-AST+GMN improves Google Code Jam F1 from 0.95 for ASTNN to 0.98.The approach also far outperforms all baselines in precision, recall, and F1 on this dataset.
  • Results on BigCloneBench: 0.94 recall and 0.95 F1: the approach achieves much higher recall and F1 than most BigCloneBench baselines.It also outperforms ASTNN in precision and F1.
  • GMN and GGNN: GMN models outperform GGNN models in F1 on both tasks, while GGNN recall is often higher than precision.The authors attribute the F1 difference to cross-graph attention in the propagation process.
  • Threshold Analysis: GMN maintains near-best F1 across thresholds from -0.5 to 0.75, whereas GGNN achieves high F1 only in the interval (0.5,0.75).The authors report that GGNN outputs for many false pairs remain closer to 0 than the ground-truth label -1.
  • Attention Analysis: GMN attention highlights both low-level similarities such as method names and higher-level similarities such as While blocks.Some attention links remain difficult to explain, which the authors associate with limitations in modeling tree hierarchies.
  • Clone-Type Analysis: The approach outperforms ASTNN on weak type-3/type-4 semantic clones in BigCloneBench.The paper treats weak type-3/type-4 clones as semantic clones.
  • ROC Analysis: FA-AST achieves the highest ROC_AUC among the evaluated approaches on BigCloneBench.ASTNN scores slightly higher than FA-AST+GGNN but lower than FA-AST+GMN.

VI. DISCUSSION

The discussion attributes the approach’s performance to combining syntax with explicit control and data flow while preserving graph structure. An example shows FA-AST+GMN recognizing a semantically equivalent file-copy pair that ASTNN misses.

  • Discussion: FA-AST combines AST syntax with control and data-flow information, unlike prior approaches based purely on AST or CFG.This combination is presented as a reason for improved clone detection performance.
  • Discussion: The method treats each code fragment as a whole graph instead of converting or decomposing its structure before neural processing.The discussion contrasts this with CDLH’s binary-tree conversion, DeepSim’s manually extracted semantic matrix, and ASTNN’s statement-subtree sequence.
  • Discussion: FA-AST+GMN assigns a 0.94 similarity score to a true file-copy clone pair, while ASTNN assigns 5.8e-07.The two fragments implement file copying despite being significantly different syntactically.
  • Discussion: The discussion frames semantic-clone detection as the target application for combining FA-AST with GGNN and GMN.The approach is evaluated on Google Code Jam and BigCloneBench.

B. The Quality of Code Clone Datasets

The paper argues that widely used clone datasets are too small and easy to fully test current deep learning models. It points to broader functionality coverage as a path toward more realistic evaluation.

  • Dataset difficulty: F1 scores close to 1.0 on both tasks, while ASTNN results are close to the proposed approach.The authors therefore see limited room for improvement on the evaluated datasets.
  • Detector behavior: A BigCloneBench false-clone example was correctly classified by FA-AST+GMN but incorrectly classified by ASTNN.This example illustrates a concrete difference between the two detectors despite their similar overall results.
  • Dataset difficulty: The authors argue that the Google Code Jam and BigCloneBench tasks are not difficult enough to test current deep learning models.They characterize the evaluated tasks as small and propose larger, more complex clone datasets.
  • Functionality coverage: The current datasets cover only 12 functionalities in Google Code Jam and ten in BigCloneBench.The paper proposes increasing the number of functionalities represented in future datasets.

C. Generalizability of Our Approach to Other Programming Languages

The approach is demonstrated on Java but is intended to generalize to other programming languages because its FA-AST components exist in most languages. The paper also identifies richer program representations as future extensions.

  • Cross-language generalizability: FA-AST combines AST, control-flow, and data-flow information, which the authors state exist in most programming languages.The Java construction can therefore be adapted to other languages with only small modifications.
  • Evidence: Experiments on Google Code Jam and BigCloneBench show improved semantic-clone detection when GNNs are combined with control- and data-flow information.The approach applies gated graph neural networks and graph matching networks over FA-AST.
  • Future extensions: Future work includes improving the neural model and combining ASTs with token sequences or data-dependence graphs.These extensions aim to capture more accurate syntactic and semantic source-code features.
Loading 2002.08653v1…