基于k-最近邻聚类功能等价重复代码检测方法地研究.pdf

国内图书分类号: 学校代码: 10213 国际图书分类号: 681 密级:公开工学硕士学位论文基于 K- 最近邻聚类的功能等价的重复代码的检测方法研究硕士研究生: 孔丹丹导师: 苏小红教授申请学位: 工学硕士学科: 计算机科学与技术所在单位: 计算机科学与技术学院答辩日期: 2012 年 6 月授予学位单位: 哈尔滨工业大学 Classified Index: .: 681 Dissertation for the Master Degree in Engineering RESEARCH ON DETECTION OF FUNCTIONALLY EQUIVALENT CODE FRAGMENTS VIA K NEAREST NEIGHBOR ALGORITHM Candidate : Kong Dandan Supervisor : Prof. Su Xiaohong Academic Degree Applied for : Master of Engineering Speciality : Computer Science and Technology Affiliation : School puter Science and Technology Date of Defence : June, 2012 Degree-Conferring-Institution : Harbin Institute of Technology 哈尔滨工业大学工学硕士学位论文 I 摘要软件的高质量、高可靠性是系统开发和维护工作的一个不可或缺的重要方面, 重复代码(也称为克隆代码)检测则是保证软件的高质量和高可靠性的一项重要任务。在软件系统中,重复代码的存在使代码量增大,软件系统架构变得比较臃肿,导致软件系统的维护存在一定的困难。而功能等价的重复代码作为重复代码的一种,因为涉及到复杂的程序语义分析,目前还缺少有效的检测方法。针对目前方法存在的不足,本文提出了基于 K- 最近邻聚类算法的功能等价的重复代码的检测方法。本文方法首先对源程序进行词法分析和语法分析分别建立抽象语法树 AST 和控制依赖图 CDG , 并在此基础上进行特定的数据流分析得到函数语句中变量的定值-使用信息集合,然后利用 K- 最近邻聚类方法获取得到功能独立的易于提取的代码片段,并在识别得到代码片段的输入变量和输出变量的基础上,对代码片段进行过程提取,将不能编译的代码片段转换为能够编译执行的函数,接下来为函数的输入变量实现自动随机赋值,最后对函数执行动态测试并根据输出变量的结果对函数进行分类,由此将代码片段划分到不同的集合中,得到功能等价的代码片段集合。本文使用学生在 C 语言课程作业中提交的程序和 Simens 开源代码对基于 K- 最近邻聚类的功能等价的重复代码的检测模型进行了测试,并且与参考文献中的利用滑动窗口方法获取候选代码片段的方法进行了对比,证明本文中的方法能够以较低的时间复杂度获取功能内聚的代码片段,然后从获取的代码片段中进一步检测得到功能等价的重复代码。关键字:重复代码;功能等价; K- 最近邻聚类算法;自动随机赋值;动态测试哈尔滨工业大学工学硕士学位论文 II Abstract It is an indispensable important aspect to insure the high quality and high reliability of software in system development and main tenance work. It is an important task to detect code clone to insure the high qual ity and high reliability of software. The presence of code clone increases the amount of code in software system, and makes the software system architecture more bloated and there existing some difficulties to maintain. Because of functionally equivale nt duplicated code plicated procedure semantic analysis, this kin