TGMM: 结合解析树与GPU的大规模多语言多粒度代码克隆检测

doi:10.19678/j.issn.1000-3428.0252041

摘要/Abstract

摘要：

针对现有代码克隆检测工具在多语言适配与大规模克隆分析方面存在的不足, 提出一种基于解析树和图形处理器(GPU)加速的大规模代码克隆检测方法——TGMM。该方法采用三级处理架构进行克隆分析: 首先, 根据各编程语言的词法与语法规则生成标准化解析树, 并从中提取满足特定粒度要求的子树; 其次, 通过对子树进行剪枝和语义等价转换, 实现子树的简化与非功能性差异的消除; 最后, 利用GPU并行构建全局后缀数组, 实现大规模代码块相似度的快速计算。实验环节从克隆检测效能和语言扩展性两个维度对TGMM进行了测试: 在公开的基准数据集BigCloneBench上, TGMM以97%的精确率显著优于对比的7种主流工具, 其执行时间较次优工具缩短50%以上, 同时保证召回率在各类克隆类型上与对比工具相当; 在语言拓展性测试中, TGMM成功解析22种主流编程语言中的19种。此外, 通过应用TGMM对GitHub排名前45的项目(涵盖9种编程语言)执行多粒度克隆分析, 揭示了不同语言在克隆分布密度上的显著差异, 并详细分析了其背后成因, 从而为软件维护提供了切实有效的参考依据。

关键词: 克隆检测, 多语言, 大规模, 图形处理器加速, 解析树

Abstract:

This study proposes TGMM, a large-scale code clone detection method based on parse trees and Graphics Processing Unit (GPU) acceleration, to address the limitations of existing tools in multilingual adaptation and large-scale analysis. The method employs a three-stage architecture for clone detection. First, it generates standardized parse trees based on lexical and syntactic rules of each programming language and then extracts subtrees that meet specific granularity requirements. Second, it simplifies these subtrees by pruning and eliminates nonfunctional differences through semantic equivalence transformations. Finally, it leverages GPUs to construct a global suffix array in parallel, enabling rapid similarity calculation of large-scale code blocks. The proposed method is evaluated in terms of clone detection efficiency and language scalability. On the public benchmark dataset BigCloneBench, TGMM achieves a precision of 97%, significantly outperforming seven mainstream tools compared, while reducing execution time by over 50% compared to the second-best tool and maintaining a recall rate similar to the compared tools across various clone types. In the language scalability test, TGMM successfully parses 19 out of 22 mainstream programming languages. Furthermore, by applying TGMM to conduct a multi-granularity clone analysis of the top 45 GitHub projects (covering nine programming languages), the study reveals significant differences in clone density across different languages, provides an in-depth analysis of the underlying causes, and thus offers practical and effective references for software maintenance.

Key words: clone detection, multilingual, large-scale, Graphics Processing Unit (GPU) acceleration, parse tree

叶宇航, 任潇宁, 吴月明. TGMM: 结合解析树与GPU的大规模多语言多粒度代码克隆检测[J]. 计算机工程, 2026, 52(9): 333-347.

YE Yuhang, REN Xiaoning, WU Yueming. TGMM: Large-scale Multilingual and Multi-Granularity Code Clone Detection Combining with Parse Tree and GPU[J]. Computer Engineering, 2026, 52(9): 333-347.

https://www.ecice06.com/CN/Y2026/V52/I9/333

图/表 10

图1 源代码解析和代码块提取

Fig.1 Source code parsing and code block extraction

图2 后缀树与后缀数组示例

Fig.2 An example for suffix tree and suffix array

图3 代码行数与运行时间及内存占用关系图

Fig.3 Relationship diagram between code lines, execution time, and memory usage

图4 9种编程语言的多粒度克隆分析

Fig.4 Multi-granularity clone analysis of nine programming languages

参考文献 40

1	AL-EKRAM R, KAPSER C, HOLT R, et al. Cloning by accident: an empirical study of source code cloning across software systems[C]//Proceedings of the 2005 International Symposium on Empirical Software Engineering. Washington D.C., USA: IEEE Press, 2005: 1-10.
2	ROY C K, CORDY J R. A survey on software clone detection research[EB/OL]. [2024-12-04]. https://www.researchgate.net/publication/277287260_A_Survey_on_Software_Clone_Detection_Research.
3	ROY C K , CORDY J R , KOSCHKE R . Comparison and evaluation of code clone detection techniques and tools: a qualitative approach. Science of Computer Programming, 2009, 74 (7): 470- 495. doi: 10.1016/j.scico.2009.02.007
4	MONDAL M, RAHMAN M S, SAHA R K, et al. An empirical study of the impacts of clones in software maintenance[C]//Proceedings of the IEEE 19th International Conference on Program Comprehension. Washington D.C., USA: IEEE Press, 2011: 242-245.
5	苏小红, 张凡龙. 面向管理的克隆代码研究综述. 计算机学报, 2018, 41 (3): 628- 651.
	SU X H , ZHANG F L . A survey for management-oriented code clone research. Chinese Journal of Computers, 2018, 41 (3): 628- 651.
6	乐乔艺, 刘建勋, 孙晓平, 等. 代码克隆检测研究进展综述. 计算机科学, 2021, 48 (11A): 509- 522.
	LE Q Y , LIU J X , SUN X P , et al. Survey of research progress of code clone detection. Computer Science, 2021, 48 (11A): 509- 522.
7	CORDY J R, ROY C K. The NiCad clone detector[C]//Proceedings of the IEEE 19th International Conference on Program Comprehension. Washington D.C., USA: IEEE Press, 2011: 219-220.
8	SAJNANI H, SAINI V, SVAJLENKO J, et al. SourcererCC: scaling code clone detection to big-code[C]//Proceedings of the IEEE/ACM 38th International Conference on Software Engineering (ICSE). Washington D.C., USA: IEEE Press, 2017: 1157-1168.
9	NAKAGAWA T, HIGO Y, KUSUMOTO S. NiL: large-scale detection of large-variance clones[C]//Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. New York, USA: ACM Press, 2021: 830-841.
10	ZHU W Q, YOSHIDA N, KAMIYA T, et al. MSCCD: grammar pluggable clone detection based on ANTLR parser generation[C]//Proceedings of the 30th IEEE/ACM International Conference on Program Comprehension. New York, USA: ACM Press, 2022: 460-470.
11	ZHAO J L, XIA K F, FU Y L, et al. An AST-based code plagiarism detection algorithm[C]//Proceedings of the 10th International Conference on Broadband and Wireless Computing, Communication and Applications (BWCCA). Washington D.C., USA: IEEE Press, 2015: 178-182.
12	ZOU Y, BAN B H, XUE Y X, et al. CCGraph: a PDG-based code clone detector with approximate graph matching[C]//Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering (ASE). Washington D.C., USA: IEEE Press, 2020: 931-942.
13	PARR T. ANTLR[EB/OL]. [2024-12-03]. https://www.antlr.org/.
14	ANTLR. grammars-v4[EB/OL]. [2024-12-03]. https://github.com/antlr/grammars-v4.
15	HUNT J W , SZYMANSKI T G . A fast algorithm for computing longest common subsequences. Communications of the ACM, 1977, 20 (5): 350- 353. doi: 10.1145/359581.359603
16	WANG Y K, YE Y H, WU Y M, et al. Comparison and evaluation of clone detection techniques with different code representations[C]//Proceedings of the IEEE/ACM 45th International Conference on Software Engineering (ICSE). Washington D.C., USA: IEEE Press, 2023: 332-344.
17	SEMURA Y, YOSHIDA N, CHOI E, et al. CCFinderSW: clone detection tool with flexible multilingual tokenization[C]//Proceedings of the 24th Asia-Pacific Software Engineering Conference (APSEC). Washington D.C., USA: IEEE Press, 2018: 654-659.
18	Queen's University at Kingston. The TXL programming language[EB/OL]. [2024-12-03]. https://www.txl.ca/txl-index.html.
19	JIANG L X, MISHERGHI G, SU Z D, et al. DECKARD: scalable and accurate tree-based detection of code clones[C]//Proceedings of the 29th International Conference on Software Engineering (ICSE'07). Washington D.C., USA: IEEE Press, 2007: 96-105.
20	AMME W, HEINZE T S, SCHÄFER A. You look so different: finding structural clones and subclones in Java source code[C]//Proceedings of the IEEE International Conference on Software Maintenance and Evolution (ICSME). Washington D.C., USA: IEEE Press, 2021: 70-80.
21	LEI M , LI H , LI J , et al. Deep learning application on code clone detection: a review of current knowledge. Journal of Systems and Software, 2022, 184, 111141. doi: 10.1016/j.jss.2021.111141
22	孙雪凯, 刘春玲, 蒋烈辉. 一种利用抽象语法树的源代码克隆检测模型. 信息工程大学学报, 2024, 25 (6): 667- 673.
	SUN X K , LIU C L , JIANG L H . A source code clone detection model using abstract syntax tree. Journal of Information Engineering University, 2024, 25 (6): 667- 673.
23	吕泉润, 谢春丽, 万泽轩, 等. 基于对比学习的跨语言代码克隆检测方法. 计算机应用研究, 2024, 41 (7): 2147- 2152.
	LÜ Q R , XIE C L , WAN Z X , et al. Contrastive learning based cross-language code clone detection. Application Research of Computers, 2024, 41 (7): 2147- 2152.
24	SUN W D. Using GPU to accelerate suffix array construction[C]//Proceedings of the 7th International Conference on Biomedical Engineering and Informatics. Washington D.C., USA: IEEE Press, 2015: 677-682.
25	SVAJLENKO J, ISLAM J F, KEIVANLOO I, et al. Towards a big data curated benchmark of inter-project code clones[C]//Proceedings of the IEEE International Conference on Software Maintenance and Evolution. Washington D.C., USA: IEEE Press, 2014: 476-480.
26	Ambient Software Evolution Group. IJaDataset-2.0[EB/OL]. [2024-12-03]. https://1drv.ms/u/s!AhXbM6MKt_yLj_tk29GJnc9BKoIvCg?e=oVTVJm.
27	WANG P C, SVAJLENKO J, WU Y Z, et al. CCAligner: a token based large-gap clone detector[C]//Proceedings of the IEEE/ACM 40th International Conference on Software Engineering (ICSE). Washington D.C., USA: IEEE Press, 2018: 1066-1077.
28	KAMIYA T . CCFinderX: an interactive code clone analysis environment. Singapore: Springer, 2021.
29	GÖDE N, KOSCHKE R. Incremental clone detection[C]//Proceedings of the 13th European Conference on Software Maintenance and Reengineering. Washington D.C., USA: IEEE Press, 2009: 219-228.
30	SVAJLENKO J, ROY C K, CORDY J R. A mutation analysis based benchmarking framework for clone detectors[C]//Proceedings of the 7th International Workshop on Software Clones (IWSC). Washington D.C., USA: IEEE Press, 2013: 8-9.
31	KRUTZ D E, LE W. A code clone oracle[C]//Proceedings of the 11th Working Conference on Mining Software Repositories. New York, USA: ACM Press, 2014: 388-391.
32	CARBONNELLE P. PYPL[EB/OL]. [2024-12-03]. https://pypl.github.io/PYPL.html.
33	Rosetta Code Contributors. Rosetta code[EB/OL]. [2024-12-03]. https://rosettacode.org/wiki/Rosetta_Code.
34	LI L Q, FENG H, ZHUANG W J, et al. CCLearner: a deep learning-based clone detection approach[C]//Proceedings of the IEEE International Conference on Software Maintenance and Evolution (ICSME). Washington D.C., USA: IEEE Press, 2017: 249-260.
35	ZHANG J, WANG X, ZHANG H Y, et al. A novel neural source code representation based on abstract syntax tree[C]//Proceedings of the IEEE/ACM 41st International Conference on Software Engineering (ICSE). Washington D.C., USA: IEEE Press, 2019: 783-794.
36	CHOI E, FUKE N, FUJIWARA Y, et al. Investigating the generalizability of deep learning-based clone detectors[C]//Proceedings of the IEEE/ACM 31st International Conference on Program Comprehension (ICPC). Washington D.C., USA: IEEE Press, 2023: 181-185.
37	LIU C Y, LIN Z Q, LOU J G, et al. Can neural clone detection generalize to unseen functionalities[C]// Proceedings of the 36th IEEE/ACM International Conference on Automated Software Engineering (ASE). Washington D.C., USA: IEEE Press, 2022: 617-629.
38	Google Code Jam dataset[EB/OL]. [2024-12-03]. https://www.kaggle.com/datasets/jur1cek/gcj-dataset.
39	WHITE M, TUFANO M, VENDOME C, et al. Deep learning code fragments for code clone detection[C]// Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering (ASE). Washington D.C., USA: IEEE Press, 2016: 87-98.
40	FENG S Y, SUO W Q, WU Y M, et al. Machine learning is all you need: a simple token-based approach for effective code clone detection[C]//Proceedings of the IEEE/ACM 46th International Conference on Software Engineering (ICSE). Washington D.C., USA: IEEE Press, 2024: 2745-2757.

[1]	郝冠一, 孙靖超. 多模态虚假信息检测综述[J]. 计算机工程, 2026, 52(9): 64-80.
[2]	何添翼, 曹海燕, 吉杨锐, 许方敏. 基于单纯形法的无网格超大规模MIMO信道估计[J]. 计算机工程, 2025, 51(9): 379-386.
[3]	周炫锦, 蔡刚, 黄志洪. 支持FPGA动态重构的RISC-Ⅴ扩展指令集设计与实现[J]. 计算机工程, 2025, 51(5): 229-238.
[4]	江子锐, 梁辰, 张子龙, 王奕森. 一种面向异构固件的高效靶向分析技术[J]. 计算机工程, 2025, 51(11): 171-185.
[5]	林紫晴, 李泽鹏, 刘耿耿. 先进通孔柱技术下高性能层分配算法[J]. 计算机工程, 2025, 51(11): 204-214.
[6]	王景熠, 朱予涵, 周茹平, 刘耿耿. 基于动态粒子群优化的X结构Steiner最小树算法[J]. 计算机工程, 2024, 50(9): 226-234.
[7]	王彬, 张娇, 李薇, 王晓帆, 金海燕. 面向大规模优化问题的精英贡献两阶段动态分组算法[J]. 计算机工程, 2024, 50(7): 154-163.
[8]	郑娟毅, 张庆珏, 董嘉豪, 郭梦月, 杨溥江. 一种深度学习的波束空间信道估计算法[J]. 计算机工程, 2024, 50(5): 298-305.
[9]	侯钰涛, 阿布都克力木·阿布力孜, 史亚庆, 马依拉木·木斯得克, 哈里旦木·阿布都克里木. 面向"一带一路"的低资源语言机器翻译研究[J]. 计算机工程, 2024, 50(4): 332-341.
[10]	李贵勇, 高馨雨, 于晓娜. 毫米波非正交多址接入的节能资源分配[J]. 计算机工程, 2024, 50(12): 194-199.
[11]	王晓峰, 于卓, 赵健, 曹泽轩. 大规模图例的最大团问题算法分析[J]. 计算机工程, 2022, 48(6): 182-192,199.
[12]	丁青锋, 徐梦引, 石辉, 李怡浩, 杨倩. 基于ADC精度与AP选择的去蜂窝系统能效均衡方法[J]. 计算机工程, 2022, 48(11): 192-200.
[13]	霍占强, 刘玉洁, 付苗苗, 乔应旭. 基于卷积神经网络的直线描述方法研究[J]. 计算机工程, 2021, 47(5): 251-259.
[14]	黄宁, 刘渊, 王晓锋. 基于交互式流量回放的用户行为仿真技术[J]. 计算机工程, 2021, 47(10): 103-110.
[15]	张冬梅, 陈永乐, 杨玉丽. 基于分层特征的代码克隆检测方法[J]. 计算机工程, 2021, 47(10): 125-131.

选择文件类型/文献管理软件名称

选择包含的内容