浅谈代码相似性检测与图神经网络

代码相似性检测从对象上来划分可以分为基于源代码的相似性检测和基于二进制的相似性检测，其目的常用于代码检测、漏洞检测以及知识产权保护等。通常情况下，软件的源码比较难以获取，因此基于二进制代码的相似性检测技术能够适用的场景更加广泛。本文主要针对二进制代码的相似性做介绍。

最初Whale于1988年首次提出将代码相似性检测过程分为两个阶段：代码格式转换和相似度确定，后续的方法大多参考这一做法，大致过程可分为4个部分：代码预处理、中间表示转换、比较单元生成和度量算法匹配。

最初Whale于1988年首次提出将代码相似性检测过程分为两个阶段：代码格式转换和相似度确定，后续的方法大多参考这一做法，大致过程可分为4个部分：代码预处理、中间表示转换、比较单元生成和度量算法匹配。

（1） 代码预处理的目的是剔除部分与代码相似性无关的或影响较小的信息，同时规范和统一输入格式以便于处理，其操作通常包括：统一代码布局、去除无关字符（如空行、注释）、替换名称（如自定义函数名、数据名和通用寄存器名）、程序切片等。

（2） 中间表示转换的目的是在尽量不改变代码携带信息的前提下，提取感兴趣的信息（如字节流、字符串、可度量属性、控制流和数据流，以及代码的词法、语法和语义等），并将其转换成自动化程序可处理和比较的其他形式，该步骤一般借助于编译器、反编译器、程序分析器或自定义规则等进行转换。常见的中间表示形式有线性结构（字符串或序列）、树形结构（抽象语法树或XML文档等）、图形结构（控制流图或数据流图等）和其他非线性结构（多维特征向量或特征矩阵）。

（3） 比较单元生成是对代码或其中间表示进行切分或聚合，得到便于相似性度量的最小单元。常见的比较单元有字符串、标识符（Token）序列、特征向量、树的结点及其子树、图的节点及其子图等，也可以是中间表示本身。比较单元还可以分为固定粒度和自由粒度。针对固定粒度，如果粒度太大，那么检测的准确度会降低；如果粒度太小，那么检测的工作量会增加。自由粒度的实现难度较大。因此，在实际操作中需要根据中间表示的形式和任务目标选择合适的检测粒度。

（4） 度量算法匹配是根据不同形式的比较单元，采用与之相适应的相似性度量算法（如串搜索、向量距离计算、子树和子图的匹配、聚类等），度量检测对象之间的相似性。

图1 代码相似性检测总体模型

       除此之外，二进制代码相似性检测还有以下难题：跨编译器问题、跨编译优化配置问题以及跨指令架构问题。传统相似性检测方法由于多采用图形结构的中间表示，受限于图匹配算法的效率，只能选择在准确度和速度之间做平衡，对相似性度量算法效率的提升逐渐陷入瓶颈。近几年，越来越多的研究借助于深度神经网络技术突破了这一瓶颈。神经网络的优势在于不仅可以自动学习和筛选影响相似性的特征，还可以确定不同特征对相似性影响的大小，该方法的关键在于如何处理原始代码和选择哪种中间表示更利于神经网络的训练和学习，以及哪种神经网络模型更适合程序相似度模型的构建。

 （细节参考《二进制代码相似性检测技术综述》- 方磊、武泽慧、魏强）

        二进制代码逆向后函数天然地被表示为控制流图的形式（CFG，Control-Flow Graph）,控制流图本身也反应了程序丰富的本质信息，关键在于其本身就是一个图结构，也不再需要人为地去构建图结构。正如上一部分所述，传统的相似性检测方法受限于图匹配算法而陷入瓶颈，而近年来图神经网络的发展以及在各种复杂网络中的表现使得二进制代码检测的技术能进一步突破。

简单地介绍一下什么是图，图最重要的两个要素：节点（Node）和边(Edge)，节点表示研究对象的基本单元，边表示节点之间的关系，可以有方向也可以没有方向。在CFG中，基本块可以表示为节点，基本块和基本块之间的控制流则表示为边，显然CFG是一个有向图。

图2 控制流图

应用实例

《Order Matters: Semantic-Aware Neural Networks for Binary Code Similarity Detection》

       这篇文章为腾讯发表于2020年的AAAI上，是一篇比较新又比较经典的二进制代码检测文章。这篇文章综合了NLP、图神经网络的优势，把这些方法运用到了二进制代码相似性检测上，其模型如下：

图3 总体模型

       上一部分提到图可以分为节点和边，进一步图也包含了两个方面的信息，一个是节点的特征信息，另一个是图的结构信息，已经有论文证实忽略节点信息和结构信息的差异会对导致最终结果的不准确。因此，该模型将原始的CFG信息拆分为两边，上半部分是利用改进后的Bert以及图神经网络MPNN聚合节点特征信息，下半部分是利用CNN对邻接矩阵对结构信息进行提取，最终利用MLP把两部分拼接起来的信息进行学习，起到了注意力机制的效果。

       关于二进制相似性检测，现阶段的主流做法一是从特征提取上面做文章，比如近些年的NLP的发展；二是从检测模型出发，比如图的节点信息和结构信息的关系、图神经网络的发展。目前二进制相似性检测相关成果产出比较依赖于人工智能的技术发展，如何将前沿技术成果和安全实际问题结合和创新是现阶段代码相似性检测的主要面对问题。

扫码关注我们

每天有最新消息