admin 管理员组文章数量: 1086019
2024年4月30日发(作者：entryset转map)
Software Development
软件开发
•
面向海量目标源代码数据比对样本的源代码特征值提取算法
本文提出了在面向海量目标
摘
源代码数据比对样本场景下对软
要
件同源性检测技术提出的新的技
术挑战，同时，对目前已有的同
源性检测技术进行探讨，介绍了
一种源代码特征值提取算法来满
足检测需求，在此基础上对检测
系统进行了设计，并从检测准确
性、存储容量方面验证了算法的
实际效果和可行性。
【关键词】软件同源性检测 抽象语法树 特征
值提取算法
最近几年随着开源软件项目的数量与质
量的不断提升，越来越多的企业也开始倾向于
采取开源方案构建自己的软件系统。但在使用
开源软件项目的源代码过程中，企业也隐性地
承担了因为软件项目管理不善、程序员使用不
当等因素所引入的由开源软件许可证所带来的
法律风险。因此，对源代码进行同源性检测，
让软件企业了解其软件代码中包含的开源代
码成分，并分析这些开源代码可能带来的问题
（知识产权风险、安全漏洞风险等）是目前规
避上述风险的主要手段。然而，对于完成上述
目标的代码同源性检测将面临着巨大的技术挑
战——不仅需要解决如何在海量的开源项目中
提取并存储用于比对的源代码样本数据信息，
而且还需要达到快速、准确地完成针对被比对
软件源代码组成成分的检测任务。为解决以上
问题，本文将介绍一种面向海量目标源代码数
据比对样本的源代码特征值提取算法，能够基
本满足在存储容量与检测准确度、效率上的对
于源代码同源性检测的要求。本文中采用了
Java语言的开源项目及其源代码作为主要研究
对象，既具有代表性，同时也兼顾了实际应用
价值。
1 已有源代码同源性检测技术
1.1 基于文本的方法
将代码直接进行文本或字符串比较。将
程序代码当做文本进行分析，利用字符串匹配
算法将代码划分为一系列子串，然后对每个子
串进行哈希运算,并筛选出部分哈希值作为程
序指纹。
1.2 基于词法的方法
对源代码进行词法分析，将源代码按照某
种粒度转化成Token序列，通过检测Token序
文/刘帅
列中的重复序列来判定代码克隆。这类方法的
关键在于Token的提取和比较算法的设计, 筛
选的Token特征应当能够应对代码混淆，不能
被简单混淆破坏掉。
1.3 基于语法的方法
分为基于树的方法和基于度量的方法。
基于树的方法将代码变换为AST，并利用树
匹配算法对子树进行检测，但是树的创建和比
图1：Token替代效果示意图
较具有较高的时空复杂度，因此代码搜索效率
较低，这种子树搜索或节点间匹配的方法难以
应对代码重排及控制流混淆。因此，后续很多
研究是将AST转换成Token序列或字符串来
处理。
1.4 基于代码特征值方法
在面向海量目标源代码数据比对样本的
图2：结构属性多级聚类排序处理效果示意图
问题下，由BlackDuck提出了codeprint的概念，
代码切片的目的是为了对源代码选取一
其采用纯文本方案计算代码特征值，不仅实现
个合适的切分粒度，得到一系列的切片，最终
了快速检索，而且在一定程度上解决了对代码
为每个切片计算特征值，以细化比较的粒度，
进行修改导致精度失效的问题，但纯文本提取
从而更加有效的进行检索和分析。本算法采用
方案在故意修改源代码的情况下会导致相似度
以方法为粒度进行源代码的切片处理。
分析准确性不足，而且如果采用较细粒度来提
取特征值将耗费比较大的存储空间。另外，有
2.3 Token替代步骤
一种将AST后缀树各子节点作为特征值提取
借鉴成熟的Token替代方案，将通过对
依据的算法，大幅度提升了对于故意修改源代
AST进行分级处理后的各节点结构体相关内
码进行相似度分析的准确性，但很难将一颗完
容进行结构信息Token符号替代，将参数、变
整AST后缀树的所有子节点的结构进行哈希
量等名称按结构信息相关规则使用Token符号
计算后进行存储。
进行代替，以实现Token化，从而消除“人为
2 核心算法设计
修改类、变量、方法等名称但保持代码逻辑”
的干扰情况。Token替代算法的主要思想是利
从上一章节可以看出当前没有完全倾向
用AST对每个参数、变量在操作符两端出现
于面向海量目标源代码比对样本的同源性检测
的次数以及在关键Block节点出现的次数进行
技术，因此，本文提出了一种源代码特征值提
统计，并根据统计信息合成其Token化后的名
取算法，通过该算法能够对样本代码进行切片
称，处理后的效果如图1所示。
后的特征值计算，提取后的特征值能够基本满
足在存储容量与检测准确度、效率上的要求。
2.4 结构属性多级聚类排序处理步骤
算法基于AST，其核心思路是将AST转换为
每一个AST方法节点都是一棵子语法树，
纯文本内容，再将特征值的提取问题简化为处
筛选其AST各节点单元结构属性，根据排序
理海量文本去重的问题上来。下面将对每个算
策略，完成多级聚类排序处理，从而在打乱代
法步骤的具体实现进行详细说明：
码部分行顺序但实现相同逻辑的情况下，可以
2.1 消除代码噪音步骤
尽量得到一个相同的结果， 整个算法过程可
以简单地视为一个对所有Method子语法树下
该步骤实现识别并剔除代码中的噪声内
Block节点语法树内各个节点结构属性的聚类
容。有一些代码噪声很容易被有意的添加在代
后排序处理，并存储为对应的Struct结构体对
码片段中用于干扰检查结果，造成基于文本
象的过程。处理后的效果如图2所示。
或Token方法的源代码同源性检测结果精度降
低，如对目标源码中夹杂一些无用的声明。通
2.5 特征值计算步骤
过该过程将一些人为混入源代码中的无用代码
特征值计算将主要采用Simhash算法，并
片段过滤掉，从而达到消除噪音的目的。
在加权计算方面加以改造。Simhash是Google
2.2 代码切片步骤
用来处理海量文本去重的算法，可以得到局部
Electronic Technology & Software Engineering
电子技术与软件工程
• 25
软件开发
•
Software Development
表1：相似度查询表
海明距离
相似度
<=5
95%
<=10
80%
表2：相似度检测结果比对表
修改源代码方式
修改方法、方法内参数、变量名
调整声明顺序
混入代码
特征值算法
100%
100%
80%
Beyond Compare
48%
95%
78%
WinMerg
48%
95%
78%
TextDiff
48%
95%
78%
<=15
50%
<=20
25%
敏感的代码特征值。根据对普遍的Method节
点层数及计算后准确性的验证，哈希值长度选
取128位，权重一般可考虑取Method节点的
基数权重为10，子节点为父节点的70%，依
次计算。经过大量实验，当海明距离小于20时，
代码相似度较高，可参考以下相似度查询表（如
表1所示）。
3 检测系统设计
如图3所示，开源项目元数据采集系统
完成从开源社区采集源代码、元数据及许可证
等数据信息，实时对所获取数据进行处理分类，
进行代码特征值的分析与提取，并进行持久化
存储，为同源性检测提供必要的检索素材与条
件。代码同源性检测系统完成对待检测源代码
的代码组成成分与许可证风险进行检查。通过
对目标源代码的特征值和分组信息的提取完成
对海量代码特征值库的检索。
4 测试结果与分析
本次测试中使用从Github开源社区上下
载的开源代码进行算法的测试，测试内容主要
分为两部分，以验证算法可以基本满足面向海
量目标源代码数据比对样本场景下的代码同源
性检测需求。
4.1 准确性验证测试
随机选择一个Github开源项目
Tron(/tronprotocol/java-
tron)，将其包e中的
源代码文件中的getStorage方
法作为本次准确性验证的基准源代码样本。与
基于文本的三种比对工具Beyond Compare、
WinMerge和TextDiff进行比对，可以看到本
算法的准确性较高，结果如表2所示。
4.2 存储容量验证测试
同样使用Tron项目，将本算法在提取特
征值以及检索必要信息后的存储容量同源文件
与文本特征值提取算法进行比较，可以看到本
算法所占的存储容量相对较小，如图4所示。
图3：检测系统设计图
5 结束语
本文提出了一种源代码特征值提取算法
来满足面向海量目标源代码数据比对样本场景
下的同源性检测需求，在此基础上对检测系统
进行了设计，并使用该算法对构造的各种抄袭
类型进行检测并同工具检测与其他算法结果进
行比较，证明本算法可以应用到真实环境中并
具有一定的使用价值。
图4：存储容量对比图
[2]任颜珠.结合文本和抽象语法树比对的源
代码同源性鉴别系统的研究与设计[D].
北京.北京邮电大学,2011.
[3]李彦臣.基于后缀语法树的代码抄袭检
测研究[D].呼和浩特.内蒙古师范大
学,2010.
作者简介
刘帅（1983-），男，北京市人。大学本科学历。
中级工程师。主要研究方向为软件工程、软件
测试。
参考文献
[1]Schleimer, S.,Wilkerson, D. and
Aiken, Winnowing: Local Algorithms
for Document Fingerprinting[C]. In
SIGMOD, pages 76-85,2003.
作者单位
北方工业大学 北京市 100144
26 •
电子技术与软件工程
Electronic Technology & Software Engineering
版权声明：本文标题：面向海量目标源代码数据比对样本的源代码特征值提取算法 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1714464496a681309.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论