Page 327 - 《软件学报》2021年第7期

李玫 等:面向代码相似性检测的相似哈希改进方法 2245

将最终生成一个字符串或一个二进制数,也就是计算对象的指纹值.两个指纹之间的比较相当于两个二进制数
之间的比较,与两段源代码之间直接两两比较相比,效率得到了大幅提升.在构建大规模代码库时,采用将输入
代码转化为指纹后入库的方法也能够节省存储空间,便于索引的建立.如图 1 所示,左侧为输入的待测代码文件,
右侧分别展示了其对应的 MD 5 指纹值、改进前后的相似哈希指纹值.

Fig.1 Examples of fingerprints
图 1 指纹生成示例

MD 5 消息摘要算法(MD 5 message-digest algorithm)即是一种常用的指纹生成方法,能够将输入内容视作
一串长字符串,在进行一系列填充、不可逆变化等操作后生成一个独特的散列值.在代码漏洞检测领域,MD 5 可
用于代码文件以及函数的指纹生成.漏洞代码同源检测工具 VUDDY [13] 通过 MD 5 对代码进行降维映射,因此能
够在大规模代码上具有良好的效率.VUDDY 将程序中的函数提取出来,进行抽象化和正则化的处理(包括对变
量名、参数名、数据类型的重命名等),然后通过 MD 5 算法生成每一个函数对应的指纹,在漏洞代码指纹库中
查找是否有相同的指纹,并以此为索引找到工程包含的相关漏洞信息.
传统哈希算法,如 MD 5 在本质上是将原始内容尽量均匀而随机地映射为一个指纹值,只能判断输入双方
是否相同,而无法衡量两者相似的程度,因此在应用场景上具有局限性.即便只对输入内容修改一个空格,传统
哈希算法也将产生截然不同的指纹值,而局部敏感哈希 LSH(locality sensitive hashing) [14] 就能够很好地解决
这一问题.
Charikar 等人 [15] 提出的相似哈希(simhash)算法是一种局部敏感哈希算法,它能够在将文件降维成一个指纹
值的同时保留文档的特性.只需比较两个文件指纹的海明距离(Hamming distance) [16] ,就能高速、便捷地衡量文
件之间的相似程度.谷歌公司的 Manku 等人 [17] 将相似哈希用于海量相似网页去重,将每个网页转化为一个 64
位的指纹值,构建一个数十亿量级的指纹库并取得了良好的实验结果.
由于相似哈希相似检索的快速性,它在很多领域均有应用.Xu 等人 [18] 将其用于分布式环境下的推荐系统
中,将用户的服务信息转换为相似哈希指纹,既保护了不同云平台的用户信息隐私,又提高了推荐系统的效率和
可扩展性.Rezaeian 等人 [19] 利用相似哈希进行俄语文件中剽窃内容的检索,使用 N grams 方法将文件转换为一
组连续的字符串,并将它们作为相似哈希计算的特征.
在代码分析领域,同样也有相似哈希的相关应用.王勇等人 [20] 将相似哈希用于安卓恶意应用程序的检测,运
用动态分析和静态分析相结合的方法获取了多维度特征,并通过信息增益的方法进行筛选.另外,他们还提出了
基于 simhash 算法的特征融合方法,将特征进行降维,通过对权重进行调节的方式解决了特征维度不平衡的问
[6]
题.Uddin 等人 [21,22] 曾将相似哈希和经典克隆检测工具 Nicad 两种方法相结合提出了一种新的 SimCad 代码克
隆簇聚类工具,主要用于对一个大型软件系统内部源代码进行检测,获得多组相似代码以及克隆簇.SimCad 将
每个代码文件切分为代码段,对其进行格式化和标准化处理后转换为 simhash 指纹,同时建立索引.最后使用
DBSCAN 聚类算法对结果进行聚类,获得代码克隆簇.他们还提出了 Simcad 的双层索引策略,第 1 层中根据代