Source-linked AI summary
SourcererCC: Scaling Code Clone Detection to Big Code
Hitesh Sajnani, Vaibhav Saini, Jeffrey Svajlenko, Chanchal K. Roy, Cristina V. Lopes
TL;DR
Large-scale clone detection lacks tools that reliably handle very large repositories, especially near-miss clones with substantial edits. SourcererCC uses token-based similarity, an optimized partial inverted index, and filtering heuristics, and is reported to achieve strong detection quality while processing 250MLOC on a standard workstation. Its artificial-clone recall is perfect, although the Mutation Framework does not represent complex multi-edit clones and precision measurement involves judge subjectivity.
Problem
Clone detectors rarely scale to hundreds of millions of lines while accurately detecting near-miss clones with substantial edits.
Method
SourcererCC combines bag-of-tokens similarity with a partial inverted index and token-ordering filtering heuristics to reduce candidate and token comparisons.
Results
SourcererCC shows strong precision and recall, remains competitive with state-of-the-art Type-3 detectors, and processes 250MLOC on a standard workstation.
Takeaways & Limitations
SourcererCC provides a scalable tool for clone analysis across large inter-project repositories and detects exact and near-miss clones.
Takeaways & Limitations
The Mutation Framework uses one mutation operator per clone, so it does not produce complex clones with multiple edit types; precision is also affected by judge subjectivity.
Abstract
from arXiv · showhide
Despite a decade of active research, there is a marked lack in clone detectors that scale to very large repositories of source code, in particular for detecting near-miss clones where significant editing activities may take place in the cloned code. We present SourcererCC, a token-based clone detector that targets three clone types, and exploits an index to achieve scalability to large inter-project repositories using a standard workstation. SourcererCC uses an optimized inverted-index to quickly query the potential clones of a given code block. Filtering heuristics based on token ordering are used to significantly reduce the size of the index, the number of code-block comparisons needed to detect the clones, as well as the number of required token-comparisons needed to judge a potential clone. We evaluate the scalability, execution time, recall and precision of SourcererCC, and compare it to four publicly available and state-of-the-art tools. To measure recall, we use two recent benchmarks, (1) a large benchmark of real clones, BigCloneBench, and (2) a Mutation/Injection-based framework of thousands of fine-grained artificial clones. We find SourcererCC has both high recall and precision, and is able to scale to a large inter-project repository (250MLOC) using a standard workstation.
1. INTRODUCTION
SourcererCC addresses the need for general-purpose clone detection that scales to hundreds of millions of lines while detecting heavily edited near-miss clones. It combines token-based similarity, indexing, and filtering heuristics, and is evaluated for scalability and detection quality.
- Clone detection supports software-quality maintenance and applications including library mining, license-violation detection, reverse engineering, provenance analysis, and code search.
- Large repositories require general-purpose clone detectors that scale to hundreds of millions of lines across inter-project software.
- SourcererCC targets accurate near-miss detection, language agnosticism, non-distributed operation, and scalability on a single machine.
- SourcererCC uses a bag-of-tokens strategy, a partial inverted index, and token-ordering bounds to reduce candidate and token comparisons.
- 250MLOC were processed in 4.5 days on a single machine, while evaluation found strong precision and recall and no scalability issues on a standard workstation.
2. DEFINITIONS
The paper defines code fragments, blocks, clone pairs, clone classes, and four clone types according to their structural and syntactic similarity.
- A code fragment is a continuous source-code segment identified by its file and starting and ending lines.
- A clone pair contains two similar code fragments and their clone type, whereas a clone class is a set whose distinct fragment pairs are clone pairs.
- A code block is a sequence of statements and local declarations within braces.
- Type-1 clones differ only in whitespace, layout, and comments, while Type-2 clones additionally permit changed identifiers and literal values.
- Type-3 clones are syntactically similar but differ through added, modified, or removed statements, whereas Type-4 clones implement the same functionality despite syntactic dissimilarity.
3. THE PROPOSED METHOD: SourcererCC
SourcererCC detects similar code blocks using token overlap, a partial inverted index, and filtering heuristics that reduce comparisons. Its design addresses the quadratic cost of exhaustive pairwise comparison and supports near-miss clones.
- Projects are collections of code blocks, and each block is represented as a frequency-aware bag of programming-language tokens.
- Overlap similarity counts shared source tokens, and code blocks exceeding a configured threshold are identified as clones.
- 3.1 Problem Formulation: Exhaustive pairwise comparison has O(n^2) time complexity because candidate comparisons grow quadratically with the number of code blocks.
- 3.2 Overview: SourcererCC operates through partial-index creation followed by clone detection, retrieving candidates from indexed token sub-blocks.
- 3.4 Clone Detection Algorithm: The partial index stores only selected sub-block tokens, reducing index size and accelerating candidate retrieval.
- 3.4 Clone Detection Algorithm: Token-ordering bounds reject candidates whose maximum similarity is too low and accept candidates whose minimum similarity is high enough.
- Filtering heuristics: Filtering reduced candidate comparisons so substantially that the measured relationship became empirically near-linear rather than quadratic.
- 3.5 Detection of Near-miss (Type-3) clones: The bag-of-tokens model supports Type-3 detection because it is resilient to statement additions, removals, and modifications.
4. EVALUATION
SourcererCC is evaluated against competing clone detectors for scalability, execution time, and recall across large inputs and two complementary clone benchmarks. It scales to 100MLOC and large inter-project repositories while maintaining strong recall, including difficult Type-3 clones.
- Evaluation Design: SourcererCC was compared with CCFinderX, Deckard, iClones, and NiCad using execution, scalability, recall, and precision evaluations.The study uses varying-size inputs, IJaDataset, the Mutation Framework, and BigCloneBench.
- Scalability: SourcererCC scaled to at least 100MLOC, while the competing Type-3 tools encountered scalability limits before that size.Deckard and iClones ran out of memory, and NiCad refused the 100MLOC input.
- Execution Time: At 100MLOC, SourcererCC was twice as fast as CCFinderX while also detecting Type-3 clones.For smaller inputs, its execution time was generally comparable to or better than competing tools.
- Mutation Framework Recall: The Mutation Framework gave SourcererCC perfect recall for the first three clone types, including Type-3 clones, across Java, C, and C#.The framework uses one mutation operator per clone, enabling precise recall measurement but producing simpler clones than those with multiple edits.
- BigCloneBench Recall: On BigCloneBench, SourcererCC achieved 93% VST3 recall overall, 99% for intra-project clones, and 86% for inter-project clones, while ST3 recall fell to 61%.ST3 recall was 86% intra-project and 48% inter-project, partly because identifier names are not normalized and the 70% threshold is harder to exceed across systems.
5. THREATS OF VALIDITY
The evaluation is sensitive to tool configurations and to judge subjectivity in precision assessment, so the authors used multiple experts and careful configuration experiments.
- Tool configurations can affect clone detection studies, including SourcererCC’s results.The authors experimented with SourcererCC and competing-tool configurations to obtain proper settings.
- Precision judgments may reflect individual subjectivity, so three clone experts independently shared the validation effort.For competing tools, the authors used published precision values rather than conducting new measurements.
6. RELATED WORK
Prior clone-detection research includes partitioning, shuffling, hashing, and indexing strategies, but few tools target very large repositories. SourcererCC differs by combining scalability with Type-3 clone detection and a compact index on a single machine.
- Few existing clone-detection tools target scalability to very large repositories.
- Partitioning and distributed execution scale non-scalable tools, while shuffling reduces executions at some cost to recall.
- Hash-based method detection achieves fast execution but misses Type-3 clones, which are common in large inter-project repositories.
- An earlier index-based approach detects only Type-1 and Type-2 clones and requires MapReduce because its index is very large.
- SourcererCC uses a 1.2GB index for 18GB of code, or 250MLOC, and detects Type-3 clones on a single machine.
- Other approaches address license-violation detection, clone search, or cloned Android applications in domain-specific settings.
7. CONCLUSION
SourcererCC achieves large-scale clone detection on a standard workstation while maintaining competitive recall and strong precision. The tool was demonstrated on a 250MLOC inter-project repository and is publicly available.
- 250MLOC: SourcererCC demonstrated scalability on IJaDataset, containing 25,000 open-source Java systems.
- SourcererCC was competitive with the best state-of-the-art Type-3 clone detectors in recall.
- Manual inspection of a statistically significant output sample found strong precision.
- SourcererCC is available on the authors’ website.