PaperlayerView exact revision on arXiv

Source-linked AI summary

SourcererCC: Scaling Code Clone Detection to Big Code

Hitesh Sajnani, Vaibhav Saini, Jeffrey Svajlenko, Chanchal K. Roy, Cristina V. Lopes

arXiv:1512.06448v1cs.SE

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.

    Source: §1 · p. 1

  • Method

    SourcererCC combines bag-of-tokens similarity with a partial inverted index and token-ordering filtering heuristics to reduce candidate and token comparisons.

    Source: §1 · p. 2

  • Results

    SourcererCC shows strong precision and recall, remains competitive with state-of-the-art Type-3 detectors, and processes 250MLOC on a standard workstation.

    Source: §1 · p. 2, §7 · p. 10

  • Takeaways & Limitations

    SourcererCC provides a scalable tool for clone analysis across large inter-project repositories and detects exact and near-miss clones.

    Source: §1 · p. 2, §7 · p. 10

    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.

    Source: §4.3.1 · p. 8, §5 · p. 10

Abstract

from arXiv · show

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.Source: §1 · p. 1
  • Large repositories require general-purpose clone detectors that scale to hundreds of millions of lines across inter-project software.Source: §1 · p. 1
  • SourcererCC targets accurate near-miss detection, language agnosticism, non-distributed operation, and scalability on a single machine.Source: §1 · pp. 1–2
  • SourcererCC uses a bag-of-tokens strategy, a partial inverted index, and token-ordering bounds to reduce candidate and token comparisons.Source: §1 · p. 2
  • 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.Source: §1 · p. 2

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.Source: §2 · p. 2
  • 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.Source: §2 · p. 2
  • A code block is a sequence of statements and local declarations within braces.Source: §2 · p. 2
  • Type-1 clones differ only in whitespace, layout, and comments, while Type-2 clones additionally permit changed identifiers and literal values.Source: §2 · p. 2
  • 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.Source: §2 · p. 2

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.Source: §3.1 · p. 2
  • Overlap similarity counts shared source tokens, and code blocks exceeding a configured threshold are identified as clones.Source: §3.1 · p. 2

3.1 Problem Formulation

  • Exhaustive pairwise comparison has O(n^2) time complexity because candidate comparisons grow quadratically with the number of code blocks.Source: §3.1 · p. 3, §3.2 · p. 3

3.2 Overview

  • SourcererCC operates through partial-index creation followed by clone detection, retrieving candidates from indexed token sub-blocks.Source: §3.2 · p. 3

3.4 Clone Detection Algorithm

  • The partial index stores only selected sub-block tokens, reducing index size and accelerating candidate retrieval.Source: §3.2 · p. 3
  • Token-ordering bounds reject candidates whose maximum similarity is too low and accept candidates whose minimum similarity is high enough.Source: §3.2 · p. 3

Filtering heuristics

  • Filtering reduced candidate comparisons so substantially that the measured relationship became empirically near-linear rather than quadratic.Source: §3.3.2 · p. 4, §3.3.1 · p. 4

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.Source: §3.5 · p. 5

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.Source: §4 · p. 6, §4.1 · p. 6, §4.3 · p. 7

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.Source: §4.1 · pp. 6–7

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.Source: §4.1 · p. 7

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.Source: §4.3.1 · p. 8

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.Source: §4.3.2 · pp. 8–9

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.Source: §5 · p. 10
  • 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.Source: §5 · p. 10

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.Source: §6 · p. 10
  • Partitioning and distributed execution scale non-scalable tools, while shuffling reduces executions at some cost to recall.Source: §6 · p. 10
  • Hash-based method detection achieves fast execution but misses Type-3 clones, which are common in large inter-project repositories.Source: §6 · p. 10
  • An earlier index-based approach detects only Type-1 and Type-2 clones and requires MapReduce because its index is very large.Source: §6 · p. 10
  • SourcererCC uses a 1.2GB index for 18GB of code, or 250MLOC, and detects Type-3 clones on a single machine.Source: §6 · p. 10
  • Other approaches address license-violation detection, clone search, or cloned Android applications in domain-specific settings.Source: §6 · p. 10

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.Source: §7 · p. 10
  • SourcererCC was competitive with the best state-of-the-art Type-3 clone detectors in recall.Source: §7 · p. 10
  • Manual inspection of a statistically significant output sample found strong precision.Source: §7 · p. 10
  • SourcererCC is available on the authors’ website.Source: §7 · p. 11

Related papers

Loading 1512.06448v1…