# 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)[^roy2009] 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](https://github.com/kucherenko/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](https://pmd.github.io/)** (Copy-Paste Detector) — 30+ languages; reports each duplication group together rather than pairwise; ships with PMD. - **[Simian](https://harukizaemon.com/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)[^sajnani2016]. ### 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)[^ahmed2024]. 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)[^xue2022], **Gitor** (global sample graph) (Shan et al. 2023)[^shan2023] — 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](https://quality.stereobooster.com/git-hotspots.md) 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)[^jiang2007]. - **SSCD** — reported to beat SourcererCC and SAGA on large industrial code at hundreds of millions of LOC (Chochlov et al. 2022)[^chochlov2022]. - **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)[^krinke2022] [^svajlenko2014]. ## 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 - [Maintainability](https://quality.stereobooster.com/maintainability.md) · Quality dimensions - [Effect scope](https://quality.stereobooster.com/effect.md) · The axes - [Refactoring practice](https://quality.stereobooster.com/refactoring-practice.md) · Methods - [Static analysis](https://quality.stereobooster.com/static-analysis.md) · Methods - [How AI fits into software quality](https://quality.stereobooster.com/ai.md) · AI ## References [^roy2009]: Roy, Chanchal K., James R. Cordy, and Rainer Koschke. 2009. "[Comparison and Evaluation of Code Clone Detection Techniques and Tools: A Qualitative Approach](https://www.cs.usask.ca/~croy/papers/2009/RCK_SCP_Clones.pdf)." *Science of Computer Programming* 74 (7): 470–95. . [^sajnani2016]: Sajnani, Hitesh, Vaibhav Saini, Jeffrey Svajlenko, Chanchal K. Roy, and Cristina V. Lopes. 2016. "[SourcererCC: Scaling Code Clone Detection to Big-Code](https://arxiv.org/pdf/1512.06448)." *Proceedings of the 38th International Conference on Software Engineering (ICSE '16)* (New York), 1157–68. . [^ahmed2024]: 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](https://onlinelibrary.wiley.com/doi/10.1002/spe.3355)." *Software: Practice and Experience* 54 (12): 2349–74. . [^xue2022]: Xue, Zhipeng, Zhijie Jiang, Chenlin Huang, Rulin Xu, Xiangbing Huang, and Liumin Hu. 2022. "[SEED: Semantic Graph Based Deep Detection for Type-4 Clone](https://arxiv.org/pdf/2109.12079)." *Reuse and Software Quality (ICSR 2022)*, 120–37. [https://doi.org/10.1007/978-3-031-08129-3\\\_8](https://doi.org/10.1007/978-3-031-08129-3\_8). [^shan2023]: Shan, Junjie, Shihan Dou, Yueming Wu, Hairu Wu, and Yang Liu. 2023. "[Gitor: Scalable Code Clone Detection by Building Global Sample Graph](https://arxiv.org/pdf/2311.08778)." *Proceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE 2023)*, 784–95. . [^jiang2007]: Jiang, Lingxiao, Ghassan Misherghi, Zhendong Su, and Stéphane Glondu. 2007. "[DECKARD: Scalable and Accurate Tree-Based Detection of Code Clones](https://www.cs.ucdavis.edu/~su/publications/icse07.pdf)." *Proceedings of the 29th International Conference on Software Engineering (ICSE '07)* (Washington, DC), 96–105. . [^chochlov2022]: Chochlov, Muslim, Gul Aftab Ahmed, James Vincent Patten, et al. 2022. "[Using a Nearest-Neighbour, BERT-Based Approach for Scalable Clone Detection](https://arxiv.org/pdf/2309.02182)." *2022 IEEE International Conference on Software Maintenance and Evolution (ICSME)*, 582–91. . [^krinke2022]: Krinke, Jens, and Chaiyong Ragkhitwetsagul. 2022. "[BigCloneBench Considered Harmful for Machine Learning](http://www0.cs.ucl.ac.uk/staff/jkrinke/publications/iwsc22.pdf)." *Proceedings of the 16th IEEE International Workshop on Software Clones (IWSC '22)*, 1–7. . [^svajlenko2014]: 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](https://www.cs.usask.ca/~croy/papers/2014/SvajlenkoICSME2014BigERA.pdf)." *Proceedings of the 30th IEEE International Conference on Software Maintenance and Evolution (ICSME '14)*, 476–80. . ## Acronyms - AST — abstract syntax tree - LOC — lines of code