Code Clone Detection Based on Program Vector Tree

doi:10.3778/j.issn.1673-9418.1910019

Abstract

Abstract:

Code cloning facilitates software development but also causes recurring bugs and software quality problems. Some types of code clones have very low similarity in literal, leading to difficulty of detection. Aiming at this pro-blem, this paper proposes one method of code clone detection based on the program vector tree. First, the feature representations of lexical units are extracted based on a statistical language model and the semantic similarities between different literal words are analyzed. Second, the abstract syntax tree (AST) of each program is extracted by syntactical analysis, and each AST is transformed into a program vector tree with each leaf node assigned a feature representation of the corresponding literal word. Finally, one weighted encoding mechanism is proposed for encoding each program vector tree into a fixed-sized vector, considering different weight information of nodes in the tree, and code fragments with similar vector representations are reported as code clones. Experimental results on BigClone-Bench, an existing large benchmark of real code clones, show that this method outperforms many prominent clone detection methods, including NiCad, Deckard, SourcererCC and Oreo, etc., in detecting Moderately Type-3 or Type-4 clones that have low similarity in literal, which verifies the validity of this method.

Key words: code clone, code clone detection, abstract syntax tree (AST), program vector tree

摘要：

代码克隆能够加速软件开发但是也会导致缺陷重复发生和软件质量问题。部分类型的代码克隆在字面上相似度低，导致识别困难。针对这一问题，提出一种基于程序向量树的代码克隆检测方法。首先，基于统计语言模型抽取词法单元的特征表示，分析不同字面单词之间的语义相似性；接着，通过语法分析提取程序的抽象语法树（AST），为叶子节点赋予对应字面单词的特征表示，将抽象语法树转化为程序向量树；最后，提出一种加权编码规则，在考虑区分不同树节点重要程度的基础上，将程序向量树编码为定长向量，而具有相似向量表示的代码片段被判定为代码克隆。实验结果表明，在真实代码克隆的大规模标准数据集BigCloneBench上，针对在字面上相似度较低的Moderately Type-3和Type-4类型克隆进行检测时，该方法均优于当前的主流方法，包括NiCad、Deckard、SourcererCC和Oreo等，证实了该方法的有效性。

关键词: 代码克隆, 代码克隆检测, 抽象语法树（AST）, 程序向量树

ZENG Jie, BEN Kerong, ZHANG Xian, LI Xiaowei, ZHOU Quan. Code Clone Detection Based on Program Vector Tree[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(10): 1656-1669.

曾杰，贲可荣，张献，李晓伟，周全. 基于程序向量树的代码克隆检测[J]. 计算机科学与探索, 2020, 14(10): 1656-1669.

References

[1] Rattan D, Bhatia R, Singh M. Software clone detection: a syste-matic review[J]. Information & Software Technology, 2013, 55(7): 1165-1199.
[2] Islam J F, Mondal M, Roy C K. Bug replication in code clones: an empirical study[C]//Proceedings of the 2016 IEEE Inter-national Conference on Software Analysis, Evolution, and Reen-gineering, Suita, Mar 14-18, 2016. Piscataway: IEEE, 2016: 68-78.
[3] Li Z M, Lu S, Myagmar S, et al. CP-Miner: a tool for finding copy-paste and related bugs in operating system code[C]//Proceedings of the 6th Symposium on Operating System Design and Implementation, San Francisco, Dec 6-8, 2004. Berkeley: USENIX Association, 2004: 289-302.
[4] Jang J Y, Agrawal A, Brumley D. ReDeBug: finding unpatched code clones in entire os distributions[C]//Proceedings of the 2012 IEEE Symposium on Security and Privacy, San Fran-cisco, May 20-23, 2012. Piscataway: IEEE, 2012: 48-62.
[5] Kim S, Woo S, Lee H, et al. VUDDY: a scalable approach for vulnerable code clone discovery[C]//Proceedings of the 2017 IEEE Symposium on Security and Privacy, San Jose, May 22-26, 2017. Washington: IEEE Computer Society, 2017: 595-614.
[6] Bellon S, Koschke R, Antoniol G, et al. Comparison and evaluation of clone detection tools[J]. IEEE Transactions on Software Engineering, 2007, 33(9): 577-591.
[7] Svajlenko J, Islam J F, Keivanloo I, et al. Towards a big data curated benchmark of inter-project code clones[C]//Proceed-ings of the 30th IEEE International Conference on Software Maintenance and Evolution, Victoria, Sep 29-Oct 3, 2014. Washington: IEEE Computer Society, 2014: 476-480.
[8] Saini V, Farmahinifarahani F, Lu Y, et al. Oreo: detection of clones in the twilight zone[C]//Proceedings of the 2018 ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineer-ing, Lake Buena Vista, Nov 4-9, 2018. New York: ACM, 2018: 354-365.
[9] Cordy J R, Roy C K. The NiCad clone detector[C]//Proceed-ings of the 19th International Conference on Program Com-prehension, Kingston, Jun 22-24, 2011. Washington: IEEE Com-puter Society, 2011: 219-220.
[10] Kamiya T, Kusumoto S, Inoue K. CCFinder: a multilingui-stic token-based code clone detection system for large scale source code[J]. IEEE Transactions on Software Engineering, 2002, 28(7): 654-670.
[11] Jiang L X, Misherghi G, Su Z D, et al. Deckard: scalable and accurate tree-based detection of code clones[C]//Proc-eedings of the 29th International Conference on Software Engineering, Minneapolis, May 20-26, 2007. Washington:IEEE Computer Society, 2007: 96-105.
[12] Sajnani H, Saini V, Svajlenko J, et al. SourcererCC: scaling code clone detection to big-code[C]//Proceedings of the 38th International Conference on Software Engineering, Austin, May 14-22, 2016. New York: ACM, 2016: 1157-1168.
[13] Whale G. Plague: Plagiarism detection using program struc-ture[M]. Sydney: University of New South Wales, 1988.
[14] Tufano M, Watson C, Bavota G, et al. Deep learning simi-larities from different representations of source code[C]//Pro-ceedings of the 15th International Conference on Mining Software Repositories, Gothenburg, May 28-29, 2018. New York: ACM, 2018: 542-553.
[15] Baker B S. On finding duplication and near-duplication in large software systems[C]//Proceedings of the 2nd Conference on Reverse Engineering, Toronto, Jul 14-16, 1995. Washington: IEEE Computer Society, 1995: 86-95.
[16] Baxter I D, Yahin A, De Moura L M D, et al. Clone detec-tion using abstract syntax trees[C]//Proceedings of the 1998 International Conference on Software Maintenance, Bethesda, Nov 16-19, 1998. Washington: IEEE Computer Society, 1998: 368-377.
[17] Yamaguchi F, Lottmann M, Rieck K. Generalized vulnera-bility extrapolation using abstract syntax trees[C]//Proceed-ings of the 28th Annual Computer Security Applications Con-ference, Orlando, Dec 3-7, 2012. New York: ACM, 2012: 359-368.
[18] Liu C, Chen C, Han J W, et al. GPLAG: detection of soft-ware plagiarism by program dependence graph analysis[C]//Proceedings of the 12th ACM SIGKDD International Con-ference on Knowledge Discovery and Data Mining, Phila-delphia, Aug 20-23, 2006. New York: ACM, 2006: 872-881.
[19] Li J Y, Ernst M D. CBCD: cloned buggy code detector[C]//Proceedings of the 34th International Conference on Soft-ware Engineering, Zürich, Jun 2-9, 2012. Washington: IEEE Computer Society, 2012: 310-320.
[20] Zou D Q, Qi H C, Li Z, et al. SCVD: a new semantics-based approach for cloned vulnerable code detection[C]//LNCS 10327: Proceedings of the 14th International Conference on Detection of Intrusions and Malware & Vulnerability Assessment, Bonn, Jul 6-7, 2017. Berlin, Heidelberg: Springer, 2017: 325-344.
[21] Mayrand J, Leblanc C, Merlo E. Experiment on the auto-matic detection of function clones in a software system using metrics[C]//Proceedings of the 1996 International Conference on Software Maintenance, Monterey, Nov 4-8, 1996. Wash-ington: IEEE Computer Society, 1996: 244.
[22] 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 Soft-ware Engineering, Singapore, Sep 3-7, 2016. New York: ACM, 2016: 87-98.
[23] Socher R, Pennington J, Huang E H, et al. Semi-supervised recursive autoencoders for predicting sentiment distributions[C]// Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, Edinburgh, Jul 27-31, 2011: 151-161.
[24] Svajlenko J, Roy C K. Evaluating clone detection tools with BigCloneBench[C]//Proceedings of the 2015 IEEE Interna-tional Conference on Software Maintenance and Evolution, Bremen, Sep 29-Oct 1, 2015. Washington: IEEE Computer Society, 2015: 131-140.
[25] Chen Q Y, Li S P, Yan M, et al. Code clone detection: a literature review[J]. Journal of Software, 2019, 30(4): 962-980.陈秋远, 李善平, 鄢萌, 等. 代码克隆检测研究进展[J]. 软件学报, 2019, 30(4): 962-980.
[26] Guo Y, Chen F H, Zhou M H. Code clone detection method for large-scale source code[J]. Journal of Frontiers of Com-puter Science and Technology, 2014, 8(4): 417-426. 郭颖, 陈峰宏, 周明辉. 大规模代码克隆的检测方法[J]. 计算机科学与探索, 2014, 8(4): 417-426.
[27] Livieri S, Higo Y, Matushita M, et al. Very-large scale code clone analysis and visualization of open source programs using distributed CCFinder: D-CCFinder[C]//Proceedings of the 29th International Conference on Software Engineering, Minneapolis, May 20-26, 2007. Washington: IEEE Computer Society, 2007: 106-115.
[28] Indyk P, Motwani R. Approximate nearest neighbors: tow-ards removing the curse of dimensionality[C]//Proceedings of the 30th Annual ACM Symposium on Theory of Compu-ting, Dallas, May 23-26, 1998. New York: ACM, 1998: 604-613.
[29] Fu C, Xiang C, Wang C, et al. Fast approximate nearest nei-ghbor search with the navigating spreading-out graph[J]. Pro-ceedings of the VLDB Endowment, 2019, 12(5): 461-474.
[30] Fu C, Cai D. Efanna: an extremely fast approximate nearest neighbor search algorithm based on KNN graph[J]. arXiv:1609.07228, 2016.
[31] Svajlenko J, Roy C K. BigCloneEval: a clone detection tool evaluation framework with BigCloneBench[C]//Proceedings of the 2016 IEEE International Conference on Software Main-tenance and Evolution, Raleigh, Oct 2-10, 2016. Washington: IEEE Computer Society, 2016: 596-600.
[32] Mikolov T, Chen K, Corrado G, et al. Efficient estimation of word representations in vector space[J]. arXiv:1301.3781, 2013.
[33] Svajlenko J, Roy C K. CloneWorks: a fast and flexible large-scale near-miss clone detection tool[C]//Proceedings of the 39th International Conference on Software Engineer-ing, Buenos Aires, May 20-28, 2017. Washington: IEEE Com-puter Society, 2017: 177-179.
[34] Maaten L V D, Hinton G. Visualizing data using t-SNE[J]. Journal of Machine Learning Research, 2008, 9(11): 2579-2605.