Publication Type
Conference Proceeding Article
Version
acceptedVersion
Publication Date
2-2020
Abstract
Clone detection on large code repository is necessary for many big code analysis tasks. The goal is to provide rich information on identical and similar code across projects. Detecting near-miss code clones on big code is challenging since it requires intensive computing and memory resources as the scale of the source code increases. In this work, we propose SAGA, an efficient suffix-array based code clone detection tool designed with sophisticated GPU optimization. SAGA not only detects Type-l and Type-2 clones but also does so for cross-project large repositories and for the most computationally expensive Type-3 clones. Meanwhile, it also works at segment granularity, which is even more challenging. It detects code clones in 100 million lines of code within 11 minutes (with recall and precision comparable to state-of-the-art approaches), which is more than 10 times faster than state-of-the-art tools. It is the only tool that efficiently detects Type-3 near-miss clones at segment granularity in large code repository (e.g., within 11 hours on 1 billion lines of code). We conduct a preliminary case study on 85,202 GitHub Java projects with 1 billion lines of code and exhibit the distribution of clones across projects. We find about 1.23 million Type-3 clone groups, containing 28 million lines of code at arbitrary segment granularity, which are only detectable with SAGA. We believe SAGA is useful in many software engineering applications such as code provenance analysis, code completion, change impact analysis, and many more.
Keywords
big code, clone detection, GPU acceleration, near-miss clone, segment clone
Discipline
Information Security | Software Engineering
Research Areas
Software and Cyber-Physical Systems
Publication
2020 27th IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER): Ontario, London, February 18-21: Proceedings
First Page
272
Last Page
283
ISBN
9781728151434
Identifier
10.1109/SANER48275.2020.9054832
Publisher
IEEE Computer Society
City or Country
Los Alamitos, CA
Embargo Period
5-31-2021
Citation
LI, Guanhua; WU, Yijian; ROY, Chanchal K.; SUN, Jun; PENG, Xin; ZHAN, Nanjie; HU, Bin; and MA, Jingyi.
SAGA: Efficient and large-scale detection of near-miss clones with GPU acceleration. (2020). 2020 27th IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER): Ontario, London, February 18-21: Proceedings. 272-283.
Available at: https://ink.library.smu.edu.sg/sis_research/5976
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1109/SANER48275.2020.9054832