基于改进编辑距离和LCS的同源性检测技术

发布时间：2021-06-21 08:42

　　传统基于Token的同源性检测算法存在代码变体结构化信息定位困难、模块提取、识别能力差、同源性度量精度低的问题.为此,提出了一种基于改进编辑距离和LCS（longest common sequence）的结构化识别同源性检测技术.在编辑距离（edit distance）计算中,引入交换算子,提高模块内部同源性度量精度.在LCS算法中,引入相似模块度量的最小尺寸监测机制和代码行间最大动态相关性度量,提供代码结构边界划分、模块行关联、代码有效结构化信息抽取的能力.实验证明,该方法是一种有效的基于结构化信息的同源性检测技术,其随机抽样检测结果的准确率、召回率及F值均有较优表现,且稳定性较好. 

【文章来源】：北京理工大学学报. 2017,37(02)北大核心EICSCD

【文章页数】：7 页

【部分图文】：

图１基于Ｔｏｋｅｎ的源代码级同源性检测的处理流程Ｆｉｇ．１ＦｌｏｗｃｈａｒｔｏｆＴｏｋｅｎ－ｂａｓｅｄｓｏｕｒｃｅ－ｌｅｖｅｌｈｏｍｏｌｏｇｙｄｅｔｅｃｔｉｏｎ代码行摘要值计算模型及确保摘要值的唯一性是实

－ｗｉｎ３２，运用Ｊａｖａ语言实现．目前，该同源性检测软件可以针对多种程序语言进行检测，主要支持Ｃ、Ｃ＋＋、Ｃ＃、ｊａｖａ等语言．采用多线程并发批量检测模式，支持一对多、多对一、多对多检测．软件具有格式化输出功能，支持ｗｏｒｄ２００３模板的报告导出功能，将检测结果格式化为非结构化数据存储．作为有效性验证实验，软件参数设置为ｒｄｅｆ＝３，Ｗｉ＝４，Ｗｊ＝３．实验对象包括ｊａｖａ、Ｃ、Ｃ＋＋、Ｃ＃语言代码，软件界面如图４所示．图４本文算法检测结果Ｆｉｇ．４Ｒｅｓｕｌｔｓｏｆｔｈｉｓｐａｐｅｒａｌｇｏｒｉｔｈｍ本文引用了开源软件ｓｎｏｒｔ２．９．６．０中的ｓｎｏｒｔ．ｃ源文件，ｆｉｌｅｚｉｌｌａ－３．０．０中的ｄｉｒｅｃｔｏｒｙｃａｃｈｅ．ｃｐｐ源文件，ｈａｄｏｏｐ－０．２１．０中的ｈｄｆｓ＿ｔｅｓｔ．ｃ源文件，ｔｏｍｃａｔ－８．０．３的ＷｓＷｅｂＳｏｃｋｅｔＣｏｎｔａｉｎｅｒ．ｊａｖａ源文件，Ｎｐｇｓｑｌ－２．１．１中的ＬｉｎｑＢｒｉｄｇｅ－１．３．ｃｓ源文件作为同源性检测的基准文件．在指定结构化模块范围内，随机选择变种位置，并基于Ｃ语言脚本产生３种场景的代码变种，形成检测样本对．实验中，共计产生了５０个样本对，并自动记录各样本的变种位置．由于ＣＣＦｉｎｄｅｒ［１２］是基于Ｔｏｋｅｎ的源代码级同源性检测的典型应用工具，在业内的认知度也较高，因此采用此工具作为实验比对对象．实验通过１７２北京理工大学学报第３７卷

ＤＲＮＲＭ×１００％，（１０）式中：Ｒ为召回率；ＮＤＲ为正确检测出的变种模块的行数；ＮＲＭ为实际变种模块的行数．准确率为Ｐ＝ＮＤＲＮＤＭ×１００％，（１１）式中：Ｐ为准确率；ＮＤＭ为检测出的变种模块的行数．此外，作为召回率和准确率的调和平均值，Ｆ值定义为Ｆ＝２ＲＰＲ＋Ｐ．（１２）分别对５０对样本进行了同源性检测，并记录了检测结果的召回率、准确率以及Ｆ值，分别如图５、图６、图７所示．图５召回率情况Ｆｉｇ．５Ｃａｓｅｏｆｒｅｃａｌｌ图６准确率情况Ｆｉｇ．６Ｃａｓｅｏｆｐｒｅｃｉｓｉｏｎ从实验结果可以看出，本文算法具有较高的有效性和稳定性．表１给出了５０次实验的统计结果，本文算法的召回率、正确率和Ｆ值的均值分别为９２．８３％、９０．５５％和０．８９，均高于ＣＣＦｉｎｄｅｒ的３３．８４％、３０．９７％和０．３２，说明算法具有较高的有图７Ｆ值情况Ｆｉｇ．７ＣａｓｅｏｆＦｖａｌｕｅｓ效性．本文算法召回率、正确率和Ｆ值的方差分别为７．５１％、４．０４％和８．９７×１０－４，分别小于ＣＣＦｉｎｄｅｒ的１９．８６％、５９．９７％和２．００×１０－３，说明算法具有较好的稳定性．本文算法召回率、正确率和Ｆ值的最大值分别为９７．３６％、９４．２４％和０．９７，最小值分别为８８．６４％、８６．６８％和０．８５，处于较高水平．同时，整体上看，本文算法召回率要略高于正确率，说明算法本身产生的误检率要略高于漏检率，但相差


本文编号：3240362