Oreo: Detection of Clones in the Twilight Zone

Vaibhav Saini, Farima Farmahinifarahani, Yadong Lu, Pierre Baldi, Cristina V. Lopes

Abstract

Source code clones are categorized into four types of increasing difficulty of detection, ranging from purely textual (Type-1) to purely semantic (Type-4). Most clone detectors reported in the literature work well up to Type-3, which accounts for syntactic differences. In between Type-3 and Type-4, however, there lies a spectrum of clones that, although still exhibiting some syntactic similarities, are extremely hard to detect — the "Twilight Zone." Most clone detectors fail to operate in this zone. We present Oreo, a novel approach to source code clone detection that not only detects Type-1 to Type-3 clones accurately, but is also capable of detecting harder-to-detect clones in the Twilight Zone. Oreo is built using a combination of machine learning, information retrieval, and software metrics. We evaluate the recall of Oreo on BigCloneBench and perform manual evaluation for precision. Oreo has both high recall and precision. More importantly, it pushes the boundary in detection of clones with moderate to weak syntactic similarity in a scalable manner.

Introduction

In software engineering, code clones—snippets of code that are identical or highly similar—are generally categorized into four types:

  • Type-1: Identical (except for whitespace/comments).
  • Type-2: Lexically identical (different variable names/literals).
  • Type-3: Syntactically similar (some statements added or removed).
  • Type-4: Semantically similar (identical functionality with different implementations).

Most existing tools excel at Types 1 and 2, and some handle "Strong" Type-3 clones well. However, there is a "Twilight Zone" between Type-3 and Type-4 where syntactic similarity is weak (below 70%), but the code isn't yet a "pure" semantic clone. Most tools fail here because they rely too heavily on text or structure. Conversely, tools that attempt to find pure Type-4 clones often don't scale to large industrial codebases. Oreo aims to be both accurate in this Twilight Zone and scalable to millions of lines of code.

Methodology

Oreo uses a multi-stage pipeline to balance speed and depth, moving from coarse-grained filtering to fine-grained neural analysis.

The Oreo system architecture, illustrating the multi-stage pipeline from source code to clone detection.

The Detection Pipeline

  1. Size Similarity Sharding: To avoid the $O(N^2)$ complexity of comparing every possible pair of methods, Oreo partitions code into "shards" based on token count. It only compares methods of similar sizes.
  2. The Action Filter: This is a key innovation. Instead of looking at variable names, Oreo extracts "Action tokens"—the specific library methods called and fields accessed by a piece of code. It uses a "bag-of-words" approach to calculate an overlap similarity. If two methods don't share enough "actions," they are rejected early.
  3. Metrics Similarity & Siamese DNN: For pairs that pass the filters, Oreo calculates 24 software metrics (e.g., number of loops, nesting depth, number of variables). These metrics are fed into a Siamese Deep Neural Network.

Why Siamese Networks?

This architecture consists of two identical subnetworks that share weights. This ensures that the similarity of pair $(A, B)$ is identical to $(B, A)$—a property called symmetry that is vital for clone detection. It reduces the number of parameters the model needs to learn and guarantees consistent results regardless of which code snippet is processed first.

The Siamese Deep Neural Network architecture used by Oreo to ensure symmetric similarity comparisons.

Key Insights

  • Actions Speak Louder than Words: While developers might rename variables or swap loop types, the API calls they make to achieve a goal (like StringBuilder.append or MessageDigest.getInstance) usually remain consistent.
  • The Twilight Zone Spectrum: Rather than treating Type-3 and Type-4 as binary categories, Oreo highlights a vast middle ground (Moderately and Weakly Type-3) where most current research fails.

Key Results

Oreo was compared against four major tools: SourcererCC, NiCad, CloneWorks, and Deckard using the industry-standard BigCloneBench and the IJaDataset (250 million lines of code).

  • Superior Recall: In the "Moderately Type-3" category, Oreo achieved 30% recall, while the next best tool (SourcererCC) managed only 5%. In the even harder "Weakly Type-3/Type-4" category, Oreo detected over 57,000 clones, whereas most other tools detected fewer than 50.
  • High Precision: Despite hunting for harder clones, Oreo maintained a precision of 89.5%, proving it wasn't just generating false positives.
  • Scalability: Oreo processed the 250MLOC IJaDataset in approximately 26 hours. While slower than some purely token-based tools, it is significantly more capable and remains practical for large-scale industrial use.

Limitations and Future Work

The current implementation is specific to Java, as the Action Filter and metrics extraction are tailored to Java's syntax. Additionally, the tool currently filters out methods with fewer than 50 tokens to ensure the Action Filter has sufficient data. Future work includes adding method names as a feature to help identify clones in smaller snippets and training on an ensemble of different tools to produce an even more robust model.

Summary updated

Abstract

Source code clones are categorized into four types of increasing difficulty of detection, ranging from purely textual (Type-1) to purely semantic (Type-4). Most clone detectors reported in the literature work well up to Type-3, which accounts for syntactic differences. In between Type-3 and Type-4, however, there lies a spectrum of clones that, although still exhibiting some syntactic similarities, are extremely hard to detect -- the Twilight Zone. Most clone detectors reported in the literature fail to operate in this zone. We present Oreo, a novel approach to source code clone detection that not only detects Type-1 to Type-3 clones accurately, but is also capable of detecting harder-to-detect clones in the Twilight Zone. Oreo is built using a combination of machine learning, information retrieval, and software metrics. We evaluate the recall of Oreo on BigCloneBench, and perform manual evaluation for precision. Oreo has both high recall and precision. More importantly, it pushes the boundary in detection of clones with moderate to weak syntactic similarity in a scalable manner.
BibTeX
@inproceedings{saini2018oreo,
  author = {Vaibhav Saini and Farima Farmahinifarahani and Yadong Lu and Pierre Baldi and Cristina V. Lopes},
  title = {{Oreo: Detection of Clones in the Twilight Zone}},
  booktitle = {ESEC/SIGSOFT FSE},
  year = {2018},
  url = {https://openreview.net/forum?id=MRuDYeIL0A_d},
}
Figure