PaperlayerView exact revision on arXiv

Source-linked AI summary

Oreo: Detection of Clones in the Twilight Zone

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

arXiv:1806.05837v1cs.SE

TL;DR

Clone detectors generally struggle with the Twilight Zone between Type-3 and Type-4 clones, where syntactic similarity is weak. Oreo combines semantic signatures, software metrics, machine learning, and information-retrieval filtering to address this gap. It achieves strong performance on harder-to-detect clones while remaining scalable.

  • Problem

    Existing clone detectors generally perform poorly on the increasingly difficult clones between Type-3 and Type-4, motivating improved detection for this Twilight Zone.

  • Method

    Oreo combines semantic Action tokens, software metrics, machine learning, and information-retrieval-based filtering with partitioning to detect clones scalably.

  • Results

    Oreo performs similarly to state-of-the-art tools for Type-1 through strong Type-3 clones and detects substantially more harder-to-detect clones in the Twilight Zone.

  • Takeaways & Limitations

    Oreo significantly pushes clone detection toward clones with moderate to weak syntactic similarity while maintaining scalability and accuracy.

  • Takeaways & Limitations

    Training and evaluation cover only methods from open-source Java projects; adapting Oreo to other languages requires careful consideration of its heuristics and software metrics.

Abstract

from arXiv · show

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.

1 INTRODUCTION

Clone detection spans four types from textual similarity to semantic similarity, with a difficult Twilight Zone between Type-3 and Type-4. Oreo targets this gap while retaining accuracy on easier clone types and scaling to large datasets.

  • Clone Detection Challenge: Clone types progress from textual and lexical similarity through syntactic similarity to semantic similarity, which may have little or no syntactic overlap.Type-1 differs in whitespace, layout, and comments; Type-2 in identifiers and literals; Type-3 in statements; Type-4 in functionality and implementation.
  • Clone Detection Challenge: Clone detectors usually target up to Type-3, while clones between Type-3 and Type-4 become increasingly difficult to detect.BigCloneBench identifies Very Strongly, Strongly, Moderately, and Weakly Type-3 subcategories between Type-3 and Type-4.
  • Motivation: Moderately Type-3 and later clones form the Twilight Zone, where existing detectors’ reported precision and recall drop dramatically.The paper defines improving detection performance for these hard-to-detect clones as its goal.
  • Oreo: Oreo is a scalable method-level clone detector designed to detect Type-1 through strong Type-3 clones and Twilight Zone clones.Its approach combines machine learning, information retrieval, and software metrics, with a Siamese neural-network architecture for clone pairs.
  • Results: For clones with syntactic similarity below 70%, Oreo detects one to two orders of magnitude more harder-to-detect clones than other tools.Its recall is similar to state-of-the-art tools for Type-1 through strong Type-3 clones, and it remains scalable to very large datasets.

2 THE OREO CLONE DETECTOR

Oreo combines preprocessing, size-based partitioning, semantic Action tokens, software metrics, and learned similarity to filter and classify clone candidates efficiently. Its pipeline reduces costly comparisons while preserving recall, especially for semantically similar methods with weak syntax.

  • Preprocessing: Oreo preprocesses source files to extract methods, semantic signatures, and software metrics before clone detection.The extracted information organizes later processing and supplies the model’s inputs.
  • Preprocessing: Oreo uses size-based heuristics and partitioning to eliminate unlikely method pairs before expensive clone analysis.Two-level sharding supports candidate reduction, indexed lookup, and batch loading for in-memory processing.
  • Semantic Similarity: The Action Filter: The Action Filter represents methods with Action tokens for called methods, accessed fields, and selected array accesses.These tokens provide semantic signals when lexical and syntactic similarities are low.
  • Semantic Similarity: The Action Filter: The Action Filter improves speed and scalability by eliminating low-likelihood clone pairs before further analysis.This early filtering reduces the candidate set processed by subsequent Oreo components.

3 LEARNING METRICS

Oreo learns how to configure software-metric similarities with supervised models, using a Siamese architecture to compare method pairs symmetrically. The selected model achieves strong validation and test performance while reducing parameters and computational burden relative to a plain network.

  • Metric Learning: Supervised learning selects the best configuration of 24 software metrics from clone and non-clone training examples.The training dataset contains 50M labeled feature vectors, balanced between clone and non-clone pairs, with 48 metrics per pair.
  • Dataset Curation: The training data uses 50k randomly selected GitHub Java projects and SourcererCC-generated Type-3 clone labels, while excluding BigCloneBench from training.An 80/20 train-test split is used, with one million training pairs reserved for validation and hyper-parameter tuning.
  • Deep Learning Model: Oreo uses a Siamese neural architecture whose identical subnetworks share parameters and preserve symmetry between the two methods in a clone pair.The model processes two metric feature vectors through shared subnetworks, then concatenates their outputs for comparison and classification.
  • Deep Learning Model: The classification unit outputs a value between 0 and 1 interpreted as the probability that the input pair is a clone, with values above 0.5 treated as detections.The model uses a logistic classification unit after the comparator network.
  • Deep Learning Model: 20% dropout, relative entropy loss, and stochastic gradient descent with a learning rate of 0.0001 are used in training.The learning rate is reduced by 3% after each epoch, and training uses minibatches of 1,000 examples.
  • Model Selection: The Siamese model outperforms the compared architectures across reported metrics, including validation AUC of 0.995 and precision of 0.958 versus 0.939 for the Plain DNN.Its validation performance is better than the Plain DNN despite using significantly fewer free parameters; the Siamese model has around 25,000 parameters, 37% fewer than the plain structure.

4 EVALUATION

Oreo is evaluated against established clone detectors for recall, precision, and scalability, including harder-to-detect Twilight Zone clones. The experiments show strong detection of difficult clones and scalability to a very large Java dataset, although Oreo’s precision is below most compared tools.

  • 4 EVALUATION: Oreo is compared with SourcererCC, NiCad, CloneWorks, and Deckard, while several claimed Type-4 tools are excluded because implementations were unavailable.The evaluation focuses primarily on Type-3 detectors because Type-1 and Type-2 clones are relatively easy to detect.
  • Recall: Oreo performs better than every other tool on most clone categories, with especially large gains on moderately and weakly similar clones.On MT3 and WT3/T4 categories, Oreo detects one to two orders of magnitude more clone pairs than SourcererCC, CloneWorks, and NiCad.
  • Precision: 89.5% precision is reported for Oreo, below the precision of all compared tools except Deckard.NiCad has the highest reported precision at 99%, while Deckard has the lowest at 34.8%.
  • Scalability: Oreo’s scalability evaluation measures how two-level input partitioning and the Action Filter reduce candidate pairs before the metrics-based DNN stage.The experiment uses 1,000 random methods, a 55% Action Filter threshold, and 6 input partitions.
  • Run time and resource demands: 26 hours and 46 minutes were required for Oreo to process the entire IJaDataset, compared with 4 hours and 40 minutes for SourcererCC and 1 hour and 50 minutes for CloneWorks.The dataset contains 25,000 open-source projects, 3 million source files, and 250MLOC.
  • Conclusion: The combined experiments demonstrate that Oreo scales while detecting both easy clone categories and clones in the Twilight Zone.The recall, precision, and scalability evaluations jointly support this conclusion.

5 MANUAL ANALYSIS OF SEMANTIC CLONES

Manual examples show Oreo detecting semantically similar methods with weak syntactic overlap, while also exposing false positives caused by shared structural and action patterns.

  • The precision study included pairs that were difficult to classify and cases where syntactic similarity conflicted with semantic functionality.High syntactic similarity sometimes accompanied different functionality, and the reverse also occurred.
  • Action Filter identified semantic similarity between Spanish- and English-identifier methods through their library calls.The DNN model then recognized structural similarity while ignoring language differences.
  • Oreo detected clone pairs with semantically similar but syntactically weak methods, including different sorting implementations.Insertion Sort and Bubble Sort shared action tokens and nested-loop structure, although Oreo’s classification could be attributed to chance.
  • Two file-extension methods implemented the same functionality despite different variable names, statement positions, and an extra slash check.The authors were uncertain whether to classify the pair as WT3/T4 or MT3.
  • A false positive occurred because shared toString() and append() actions and similar loop and conditional structures produced a high semantic match.The methods performed hexadecimal conversion and integer-sequence generation, respectively.

6 RELATED WORK

Related work spans text-, token-, tree-, metrics-, graph-, semantic-, and machine-learning-based clone detection, with comparisons limited by incomplete reporting or scalability information in several studies.

  • Text-, token-, tree-, metrics-, and graph-based techniques are established categories of source-code clone detection.The cited approaches differ in their underlying code representations and analysis strategies.
  • NiCad, SourcererCC, and CloneWorks are identified as state-of-the-art tools for detecting clones up to Type-3.SourcererCC and CloneWorks combine token and index techniques, while NiCad uses syntactic pretty-printing with normalization and filtering.
  • Prior Type-4 techniques used semantic vectors or execution against random inputs, but reported precision and recall were unavailable for comparison.The described implementations targeted C clones.
  • A deep-learning study reported 93% precision on 398 files and 480 method-level pairs, but did not report standard-benchmark recall or scalability.The approach learned discriminating source-code features without supervision.
  • Other supervised approaches learned code representations or used AST and PDG features, while reporting gaps included unclear training data and unreported scalability.Oreo distinguishes itself from the latter approach through deep learning, different metrics, and a semantic filter instead of semantic features.

7 LIMITATIONS OF THIS STUDY

The study’s limitations concern language and method-size scope, tool-configuration dependence, and reduced applicability of the Action Filter to very small methods.

  • Training and evaluation used only methods from open-source Java projects.Adaptation to other languages is possible but requires careful consideration of the reported heuristics and software metrics.
  • The Action Filter may not work for simple small methods lacking calls to other methods or references to class properties.A 50-token minimum threshold excluded simpler methods in this study; method names or derivatives are proposed for future mitigation.
  • Clone-detection studies are affected by tool configuration, although the authors mitigated this risk by using configurations suggested by tool authors.

8 CONCLUSIONS AND FUTURE WORK

The paper concludes that Oreo combines information retrieval, machine learning, and metrics to scale clone detection while extending it toward harder Twilight Zone clones. Future work targets finer-grained models and ensemble-derived training data.

  • Oreo combines information retrieval, machine learning, and metric-based approaches for clone detection.Its components include an Action Filter, two-level input partitioning, and a Siamese deep neural network.
  • The two-level input partitioning strategy reduces candidate pairs while maintaining good recall.
  • Oreo was compared with four state-of-the-art tools on a standard benchmark and was demonstrated to be scalable and accurate.The authors report that it significantly pushes clone-detection boundaries toward harder-to-detect Twilight Zone clones.
  • Future work will examine finer-grained models and training with clones detected by an ensemble of clone-detection tools.The stated goal is to improve recall and precision for harder-to-detect semantic clones.
Loading 1806.05837v1…