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 embeddings are the only representation 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. The same routine written twice by two people — a refactor-into-one-function candidate.
  • 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

Install-and-run tools. Fast, language-broad, low false-positive rate; 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

Parse to an AST, then compare structure. More precise on near-miss clones; needs 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

Encode each fragment into a dense vector with a code-trained model, then find duplicates by approximate nearest-neighbor search. This 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 yours to assemble.
  • ANN index — FAISS (Meta), hnswlib, or ScaNN (Google) provide the nearest-neighbor layer; HDBSCAN or a cosine threshold does the clustering.

No ready-made tool ships neural-embedding clone detection the way jscpd ships token detection.

Graph based — Type-4 research

  • SEED (semantic graph) (Xue et al. 2022)4, Gitor (global sample graph) (Shan et al. 2023)5 — program-graph representations aimed squarely at Type-4. 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 how often each one changes.
  • 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. Treat findings as candidates.
  • Reach for neural embedding + ANN before you've tried token methods. For the common "we copy-pasted this" case, jscpd finds it and the embedding pipeline doesn't earn its operational cost.
  • Trust headline Type-4 scores. The dominant benchmark is contested; validate on your own labeled sample.
  • Gate CI on Type-4 detection. Precision at usable recall is not there yet; run it as an advisory report, not a blocker.

Evidence

  • Deckard — characteristic vectors + LSH; demonstrated that embed-then-ANN scales to multi-million-LOC bases (Linux kernel, JDK) with ~93% real-clone precision on manual inspection (Jiang et al. 2007)6.
  • SSCD — reported to beat SourcererCC and SAGA on large industrial code at hundreds of millions of LOC (Chochlov et al. 2022)7.
  • BigCloneBench — handle with care. The standard ML benchmark for clone detection. A manual audit of a sample of its Weak-Type-3/Type-4 pairs found 86% to be false positives, and the dataset's construction assumed cross-functionality pairs are non-clones — so reported Type-4 F1 scores are inflated 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. ↩