DECKARD: Scalable and Accurate Tree-Based Detection of Code Clones
By Lingxiao Jiang, Ghassan Misherghi, Zhendong Su, Stéphane Glondu. 2007
1,147 citations recorded by the source corpus.
Detecting code clones has many software engineering applications. Existing approaches either do not scale to large code bases or are not robust against minor code modifications. In this paper, we present an efficient algorithm for identifying similar subtrees and apply it to tree representations of source code. Our algorithm is based on a novel characterization of subtrees with numerical vectors in the Euclidean space Rnmiddot and an efficient algorithm to cluster these vectors w.r.t. the Euclidean distance metric. Subtrees with vectors in one cluster are considered similar. We have implemented our tree similarity algorithm as a clone detection tool called DECKARD and evaluated it on large code bases written in C and Java including the Linux kernel and JDK. Our experiments show that DECKARD is both scalable and accurate. It is also language independent, applicable to any language with a formally specified grammar.
Subfields: Information Systems, Software, Program Analysis & Verification, Signal Processing, Software Engineering
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Information Systems
- Miltiadis Allamanis
- Charles Sutton
- Premkumar T. Devanbu
- Tien Nhut Nguyen
- Earl T. Barr
- Michael Pradel
- Baishakhi Ray
- Anh Tuan Nguyen
In Software
- Miltiadis Allamanis
- Charles Sutton
- Premkumar T. Devanbu
- Tien Nhut Nguyen
- Earl T. Barr
- Michael Pradel
- Anh Tuan Nguyen
- Swarat Chaudhuri
In Program Analysis & Verification
- Miltiadis Allamanis
- Charles Sutton
- Premkumar T. Devanbu
- Tien Nhut Nguyen
- Earl T. Barr
- Anh Tuan Nguyen
- Dawn Song
- Baishakhi Ray
In Signal Processing
- Miltiadis Allamanis
- Charles Sutton
- Premkumar T. Devanbu
- Tien Nhut Nguyen
- Baishakhi Ray
- Earl T. Barr
- Anh Tuan Nguyen
- Swarat Chaudhuri
In Software Engineering
- Dawn Song
- Chanchal Kumar Roy
- Miltiadis Allamanis
- Charles Sutton
- James R. Cordy
- Hongyu Zhang
- Artur Andrzejak
- Gang Zhao
Citations in the corpus
- GraphCodeBERT: Pre-training Code Representations with Data Flow (2020, methodology): “Deckard (Jiang et al., 2007) is to compute vectors for structural information within ASTs and then a Locality Sensitive Hashing (LSH) (Datar et al.”
- Detecting Similar Programs via The Weisfeiler-Leman Graph Kernel (2016, methodology): “The representative work here is Jiang’s Deckard [10].”
- Shaping program repair space with existing patches and similar code (2018, methodology): “Following DECKARD [20], we extract a vector from each code snippet, where each element in the vector represents a feature of AST nodes.”
- Do code clones matter? (2009, background): “Due to the information loss incurred by the reduction of variable size code fragments to finite-size numbers or vectors, the edit distance between inconsistent clones cannot be precisely controlled in feature vector [ 12 ] and hashing based [3] approaches.”
- Learning-Based Recursive Aggregation of Abstract Syntax Trees for Code Clone Detection (2019, methodology): “Deckard discards nodes of irrelevant type and all node content such as identifier names.”
- HELoC: Hierarchical Contrastive Learning of Source Code Representation (2022, methodology): “Tree-Based Models: Deckard [57] is a classical AST-based clone detector by identifying similar subtrees to learn tree representations of source code.”
- Retrieval-based Neural Source Code Summarization (2020, methodology): “Such syntactic knowledge has been explored by previous work on code clone detection [7, 25] based on costly tree-based matching methods.”
- Cross-architecture bug search in binary executables (2015, methodology): “We have designed and implemented a tool for crossarchitecture bug search in executables.”
- History Driven Program Repair (2016, background): “Barr et al. [7] empirically validate this hypothesis, showing that changes are 43% graftable from the exact version of program being changed.”
- Using web corpus statistics for program analysis (2014, methodology): “Existing plagiarism detection algorithms can be categorized into one of the following types: string-based, token-based [7, 11, 22, 25], abstract-syntax-tree-based [4, 10], and program-dependence-graph-based [6, 13, 16].”
- Juxtapp: A Scalable System for Detecting Code Reuse among Android Applications (2012, background): “A variety of approaches for static code clone detection have been proposed in the programming language literature for refactoring, finding bugs, and better understanding of the code [21, 27, 29, 25].”
- DeepSim: deep learning code functional similarity (2018, methodology): “We also compared DeepSim with the three other state-of-the-art approaches: DECKARD [26], RtvNN [58] andCDLH [57].”
- Mining Semantic Loop Idioms from Big Code (2016, methodology): “Code clone detection using ASTs has also been studied extensively (Baxter et al. 1998; Jiang et al. 2007; Koschke et al. 2006).”
- Achieving accuracy and scalability simultaneously in detecting application clones on Android markets (2014, methodology): “AST ([7, 6, 20]) O(L) Not accurate for Type 3 clones PDG ([31, 13, 9]) O(n(2) · M(2)) Robust for Type 1, 2, 3 clones”
- <inline-formula><tex-math notation="LaTeX">$\mu$</tex-math><alternatives><mml:math><mml:mi>μ</mml:mi></mml:math><inline-graphic xlink:href="zou-ieq1-2942930.gif"/></alternatives></inline-formula>VulDeePecker: A Deep Learning-Based System for Multiclass Vulnerability Detection (2019, neutral): “In this approach, similarity can be measured using tokens [10], [42], strings [7], [43], trees [44], [45], graphs [8], or their hybrids [46].”