Tgmm: Combining Parse Tree with Gpu for Scalable Multilingual and Multi-Granularity Code Clone Detection

Yuhang Ye, Yuekun Wang, Yinxing Xue, Yueming Wu, Yang Liu

TL;DR

This paper introduces TGMM, a novel tool that combines parse trees and GPU acceleration for scalable, multilingual code clone detection. TGMM achieves state-of-the-art precision and significantly faster execution times, making it a powerful solution for identifying code duplication across diverse programming languages and granularities.

What Problem Does This Paper Address?

Software development is increasingly complex, with code duplication (clones) being a common issue. These clones, while sometimes intentional, can lead to increased maintenance costs, bug propagation, and reduced understandability. Existing code clone detection tools often struggle to balance scalability (handling large codebases), multilingual support (working across different programming languages), and the ability to detect various types of clones (from exact copies to functionally similar code). Many tools excel at one aspect but falter in others, leaving a gap for a comprehensive solution. This paper aims to fill that gap by proposing a tool that addresses all three challenges simultaneously.

Methods

TGMM's core innovation lies in its hybrid approach:

  • Parse Tree Representation: Instead of relying solely on text or tokens, TGMM first parses source code into abstract syntax trees (ASTs). This tree structure captures the code's hierarchical organization, enabling the detection of more complex, semantically similar clones (Type-3 and Type-4).
  • GPU Acceleration: Processing ASTs can be computationally expensive. TGMM leverages GPUs to accelerate key operations, particularly the construction of suffix arrays from serialized AST node sequences. This significantly speeds up the detection process.
  • Multi-Granularity Support: TGMM allows users to define the granularity of code blocks to analyze, from entire files down to specific statements like loops or branches. This flexibility caters to different analysis needs.
  • ANTLR for Multilingualism: The tool utilizes ANTLR (ANother Tool for Language Recognition), a powerful parser generator, to handle diverse programming languages. By providing ANTLR grammar files, TGMM can theoretically support a vast number of languages.
  • Suffix Array and Three-Tuple Construction: ASTs are transformed into node sequences, then into suffix arrays. From these, "three-tuples" are generated, representing potential clone units. These are then processed and merged to identify clone pairs.

Datasets

  • BigCloneBench [21]: Used for evaluating recall and precision. This dataset is a subset of the IJaDataset-2.0, containing known clones in Java. It's noted that this dataset is also used by other state-of-the-art tools like ASTNN and TACC.
  • IJaDataset-2.0: Used for measuring execution time and scalability. This dataset was sampled to include codebases ranging from 10KLOC to 250 MLOC.
  • GitHub Repositories: For RQ3, the authors analyzed the clone distribution across nine popular languages by selecting the top five starred repositories for each language (excluding educational ones).
  • Rosetta Code: Used to ensure generalizability across languages by selecting solutions to common programming tasks.

Key Insights and Ideas

  • GPU is a Game-Changer for Tree-Based Detection: The paper demonstrates that GPU acceleration can make tree-based clone detection, which was previously too slow for large-scale analysis, a viable and efficient option. The speedup for suffix array generation is dramatic (nearly 1000x).
  • Parse Trees Offer Superior Precision: By analyzing code structure (ASTs) rather than just text or tokens, TGMM achieves significantly higher precision, meaning fewer false positives. This is attributed to considering structural information and requiring duplicated nodes to be non-discrete.
  • Multi-Granularity Analysis Reveals Language Differences: Analyzing clones at different levels (file, class, function, loop, branch) highlights distinct patterns across programming languages. For example, TypeScript shows high clone rates at the file level due to its design principles, while Python has many function-level clones driven by its functional programming features.
  • ANTLR's Grammar-Based Approach Enables Broad Language Support: The reliance on ANTLR's extensive grammar repository allows TGMM to support a wide array of languages, with the potential for even broader coverage by creating custom grammars.

Key Results

  • Performance: TGMM ranks first in execution time and precision among the compared state-of-the-art tools. Its recall is comparable to others.
  • Scalability: TGMM can handle large codebases, successfully completing clone detection on 250 MLOC in approximately 11 hours, significantly outperforming MSCCD which struggles with such large inputs.
  • Multilingual Support: TGMM perfectly supports 17 out of 30 popular languages tested, with partial support for 8 others.
  • Precision: TGMM achieves a perfect recall for Type-1/2 clones and high recall for Type-3/4 clones, with precision significantly outperforming other tools, especially for more complex clone types (MT3).
  • Speedup: GPU acceleration for suffix array generation is nearly 1000x faster than CPU. Sorting three-tuples on GPU is about 70x faster.

Limitations and Future Work

  • Grammar File Dependency: While ANTLR supports many languages, TGMM's multilingual capability is contingent on the availability of accurate grammar files. For languages lacking these, users would need to create or modify them.
  • Manual Precision Assessment: The paper notes that a standardized benchmark for measuring precision is lacking, and they relied on manual analysis by judges.
  • Type-4 Clone Detection: While TGMM aims to detect Type-3/4 clones, the paper acknowledges that detecting Type-4 clones (functionally similar but syntactically different) remains particularly challenging, often requiring semantic understanding beyond ASTs.
  • Future Work: The authors suggest that further research could explore more advanced semantic analysis techniques to improve Type-4 clone detection and potentially integrate TGMM with other tools for a more comprehensive software analysis suite.

Summary updated

Abstract

The rapid evolution of programming languages and software systems has necessitated the implementation of multilingual and scalable clone detection tools. However, it is difficult to achieve the above requirements at the same time. Most existing tools only focus on one challenge. In this work, we propose TGMM, a tree and GPU-based tool for multilingual and multi-granularity code clone detection. By generating parse trees based on user-provided grammar files, TGMM can extract code blocks at a specified granularity and detect Type-3 clones efficiently. In order to show the performance of TGMM, we compare it with seven state-of-the-art tools in terms of recall, precision, and execution time. TGMM ranks first in execution time and precision, while its recall is comparable to the others. Moreover, we analyzed the language extensibility of TGMM across 30 mainstream programming languages. Out of these, a total of 25 languages were supported, while the remaining five currently lack the necessary grammar files. Finally, we analyzed the clone characteristics of nine popular languages at five common granularities, hoping to inspire future researchers. The source code of TGMM is available at: https://github.com/TGMM24/TGMM.git.
BibTeX
@misc{ye2024tgmm,
  author = {Yuhang Ye and Yuekun Wang and Yinxing Xue and Yueming Wu and Yang Liu},
  title = {{Tgmm: Combining Parse Tree with Gpu for Scalable Multilingual and Multi-Granularity Code Clone Detection}},
  year = {2024},
  eprint = {2403.18202},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2403.18202},
}
Figure