Skip to content

Software Quality

Clone detection

Clone detection is a similarity search over code. It finds duplication in three shapes: the same logic copied across files, the same function reimplemented twice, the same vulnerable snippet propagated through a codebase.

The four clone types

The standard taxonomy (Roy et al. 2009)1 graduates by how far the copy has drifted from its source, and each tier needs a different representation to detect it.

Clone type What has drifted from the original Representation that detects it
Type-1 — exact Identical but for whitespace, layout, and comments. Token / line.
Type-2 — renamed Type-1 plus renamed identifiers, literals, and types: an identical token stream after normalization. Token / line.
Type-3 — near-miss Type-2 plus added, removed, or changed statements; the copy has been edited. Token/line reaches some; tree/AST extends the reach.
Type-4 — semantic Functionally equivalent but syntactically different: two implementations that share no tokens. The hard case. Learned representations — embeddings or program graphs — are the only ones with a chance.

What it catches

  • Copy-paste duplication. The maintenance hazard: a fix applied to one copy and not its siblings. Clone detection enumerates the siblings.
  • Reimplemented logic. Two people write the same routine independently, and the pair is a candidate for merging into one function.
  • Propagated vulnerabilities. A known-bad snippet (an unchecked memcpy, a flawed auth check) copied across the tree. A clone search against that fragment names every site the fix has to reach.
  • License contamination. Vendored or copied third-party code that the project's license can't carry; clone detection against a reference corpus flags it.

Tools

Token / line based — Type-1/2, some Type-3

These tools install and run as they ship. They are fast, language-broad and low in false positives — the default for a CI duplication gate.

  • jscpd — Rabin-Karp token matcher; 225+ language formats; CLI and CI-friendly; a Rust rewrite for speed. The pragmatic default for "find copy-paste in this repo."
  • PMD CPD (Copy-Paste Detector) — 30+ languages; reports each duplication group together rather than pairwise; ships with PMD.
  • Simian — line-based; commercial; long-standing in the Java world.
  • SourcererCC — bag-of-tokens with a partial inverted index; built for scale (hundreds of millions of LOC) at Type-2/3 (Sajnani et al. 2016)2.

Tree / AST based — extends Type-3 reach

These tools parse to an AST and compare structure. They are more precise on near-miss clones and need a grammar per language.

  • NiCad — TXL-based; normalizes and pretty-prints each fragment, then compares the results line by line.

Learned embedding + nearest-neighbor — the Type-4 attempt

These tools encode each fragment into a dense vector with a code-trained model, then find duplicates by approximate nearest-neighbor search. The design targets Type-3/4 and avoids the O(n²) pairwise comparison of earlier neural clone classifiers.

  • SSCD / DB-SSCD — the reference architecture: CodeBERT embeddings + GPU-accelerated k-ANN; DB-SSCD adds a disk-based index for industrial corpora (Ahmed et al. 2024)3. Research code, not a packaged product.
  • Embedding models to build on — CodeBERT, GraphCodeBERT, UniXcoder (Microsoft), code2vec, ASTNN. These are encoders; the clone-detection harness around them is separate work.
  • ANN index — FAISS (Meta), hnswlib, or ScaNN (Google) provide the nearest-neighbor layer; HDBSCAN or a cosine threshold does the clustering.

Graph based — Type-4 research

  • SEED (semantic graph) (Xue et al. 2022)4 and Gitor (global sample graph) (Shan et al. 2023)5 represent a program as a graph and target Type-4. Both are research-stage.

When to use, when not

Use:

  • Any codebase past the point where developers can't hold its duplication in their heads. A token gate (jscpd, PMD CPD) at Type-1/2 is cheap and pays for itself on the first cross-copy bug.
  • Before a refactoring campaign — clone clusters name the merge candidates, and git hotspots ranks those candidates by churn weighted by bug-fix density.
  • Security audits where a known-bad fragment may have been copied around: detect clones of the specific vulnerable snippet.
  • License/provenance audits against a reference corpus.

Don't:

  • As a correctness oracle. A clone is a maintenance smell, not a bug; much duplication is intentional, generated, or in test fixtures. Every finding is a candidate, not a defect.
  • Neural embedding + ANN as the first attempt. For the common "we copy-pasted this" case, jscpd finds the duplication and the embedding pipeline doesn't earn its operational cost.
  • Trust headline Type-4 scores. The dominant benchmark is contested; a labeled sample from the codebase under test is what settles whether a detector works there.
  • Gate CI on Type-4 detection. Precision at usable recall is not there yet, which makes a Type-4 report advisory rather than a blocker.

Evidence

  • Deckard — characteristic vectors + LSH; vector search plus approximate nearest neighbors scaled to multi-million-LOC bases (Linux kernel, JDK), and manual inspection of 100 of its reported clone groups in JDK found 93 to be real clones (Jiang et al. 2007)6.
  • SSCD — more effective than SourcererCC on both an industrial partner's C/C++ code and BigCloneBench, and it processed the full 320-million-line benchmark in a time the authors call reasonable for industrial use. SourcererCC was the baseline because it is publicly available; SAGA, another detector the paper reports at that scale, is not (Chochlov et al. 2022)7.
  • BigCloneBench — handle with care. The standard ML benchmark for clone detection. A manual audit of 100 of its Weak-Type-3/Type-4 pairs, drawn from a single functionality, found 86% to be false positives. The benchmark itself says nothing about pairs drawn from different functionalities, and of the twenty surveyed papers that train on its ground truth, at least five relabel that unknown as non-clone — so reported Type-4 scores cannot be trusted, and the field's apparent progress on semantic clones is partly an artifact of the benchmark (Krinke and Ragkhitwetsagul 2022; Svajlenko et al. 2014)8 9.

Classification

  • Quality dimensions: Maintainability, Security (propagated-vulnerability case).
  • Area: Large or long-lived codebases; copy-paste-heavy code; refactoring campaigns; license-compliance and propagated-vulnerability audits.
  • Guarantee: Empirical — reports code pairs whose similarity exceeds a tuned threshold. Exhaustive over the chosen representation, but precision and recall move with the threshold, and semantic (Type-4) recall is contested.

Referenced by

References

  1. Roy, Chanchal K., James R. Cordy, and Rainer Koschke. 2009. "Comparison and Evaluation of Code Clone Detection Techniques and Tools: A Qualitative Approach." Science of Computer Programming 74 (7): 470–95. https://doi.org/10.1016/j.scico.2009.02.007. ↩

  2. Sajnani, Hitesh, Vaibhav Saini, Jeffrey Svajlenko, Chanchal K. Roy, and Cristina V. Lopes. 2016. "SourcererCC: Scaling Code Clone Detection to Big-Code." Proceedings of the 38th International Conference on Software Engineering (ICSE '16) (New York), 1157–68. https://doi.org/10.1145/2884781.2884877. ↩

  3. Ahmed, Gul Aftab, James Vincent Patten, Yuanhua Han, et al. 2024. "Nearest-neighbor, BERT-based, scalable clone detection: A practical approach for large-scale industrial code bases." Software: Practice and Experience 54 (12): 2349–74. https://doi.org/10.1002/spe.3355. ↩

  4. Xue, Zhipeng, Zhijie Jiang, Chenlin Huang, Rulin Xu, Xiangbing Huang, and Liumin Hu. 2022. "SEED: Semantic Graph Based Deep Detection for Type-4 Clone." Reuse and Software Quality (ICSR 2022), 120–37. https://doi.org/10.1007/978-3-031-08129-3_8. ↩

  5. Shan, Junjie, Shihan Dou, Yueming Wu, Hairu Wu, and Yang Liu. 2023. "Gitor: Scalable Code Clone Detection by Building Global Sample Graph." Proceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE 2023), 784–95. https://doi.org/10.1145/3611643.3616371. ↩

  6. Jiang, Lingxiao, Ghassan Misherghi, Zhendong Su, and Stéphane Glondu. 2007. "DECKARD: Scalable and Accurate Tree-Based Detection of Code Clones." Proceedings of the 29th International Conference on Software Engineering (ICSE '07) (Washington, DC), 96–105. https://doi.org/10.1109/ICSE.2007.30. ↩

  7. Chochlov, Muslim, Gul Aftab Ahmed, James Vincent Patten, et al. 2022. "Using a Nearest-Neighbour, BERT-Based Approach for Scalable Clone Detection." 2022 IEEE International Conference on Software Maintenance and Evolution (ICSME), 582–91. https://doi.org/10.1109/ICSME55016.2022.00080. ↩

  8. Krinke, Jens, and Chaiyong Ragkhitwetsagul. 2022. "BigCloneBench Considered Harmful for Machine Learning." Proceedings of the 16th IEEE International Workshop on Software Clones (IWSC '22), 1–7. https://doi.org/10.1109/IWSC55060.2022.00008. ↩

  9. Svajlenko, Jeffrey, Judith F. Islam, Iman Keivanloo, Chanchal K. Roy, and Mohammad Mamun Mia. 2014. "Towards a Big Data Curated Benchmark of Inter-Project Code Clones." Proceedings of the 30th IEEE International Conference on Software Maintenance and Evolution (ICSME '14), 476–80. https://doi.org/10.1109/ICSME.2014.77. ↩