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

Authors:

Zeping Yu,1∗ Rui Cao,1∗ Qiyi Tang,1 Sen Nie,1 Junzhou Huang,2 Shi Wu1† 1Tencent Security Keen Lab, Shanghai, China
2Tencent AI Lab, Shenzhen, China
{zepingyu, ruicho}@foxmail.com, {dodgetang, snie, joehhuang, shiwu}@tencent.com

Conference: AAAI2020

Institution：腾讯科恩实验室

标题、摘要和图表

1. 标题

任务名称：Binary Code Similarity Detection

主要方法：Semantic-Aware Neural Networks

关键feature：Order

即这篇文章利用了语义信息但神经网络来做二进制代码相似度的检测，提出了考虑Order的新方法。

2. 摘要

Topic：二进制代码检测是在不获取源代码的情况下，得到二进制函数之间的相似性，这是计算机安全方面的一个重要任务。

Problem：传统的方法通常使用图匹配算法（graph matching algorithms），这往往会非常的慢而且准确率不高。

Idea：

• 来源：
  • 目前基于神经网络的方法获得很大的提升
  • 二进制函数首先表示成控制流图（CFG），然后通过图神经网络（GNN）来获取相应的编码
• 间隙：
  • 尽管这些方法高效且有用，但不能充分的捕捉二进制代码的语义信息
• 新的思路：
  • 使用semantic-aware neural networks来获取捕捉其中的语义信息

Concrete Work：

• 使用BERT在 one token-level，one block-level， two graph-level 任务上来对二进制代码预训练
• 发现了CFG节点之间的顺序对图的相似性检测也很重要，使用了CNN抽取邻接矩阵（adjacency matrices ）的节点顺序信息

Result：

• 在4个数据集上做实验
• 结果达到了SOTA

3. 图表

图1: 一个控制流图（CFG）和其中被人工选择的块特征的例子

图1中的左边是一个CFG的例子，之前的工作中，Gemini (Xu et al. 2017) 将其转换为一个属性化的CFG，在每个块中均具有手动选择特征(右)。然后使用Structure2vec (Dai, Dai, and Song 2016) 来产生图的embedding。最终计算二进制函数之间的相似度。

图2: 在不同平台上 (x86-64 & ARM) 函数“ _freading”两个CFG和它们的邻接矩阵

本文尝试设计一个结构抽取CFG节点之间的顺序信息。图2中展示了同一个函数在不同平台上的CFG，可以看出两个CFG之间是非常类似的，他们的邻接矩阵是非常像的，所以这篇文章使用了CNN来抽取其中的节点顺序信息。

图3: 模型的整体结构，主要包括3个部分：语义抽取模型，结构抽取模型，顺序抽取模型。

semantic-aware

• 采用CFG作为输入，使用BERT来预训练token和block的embedding

structural-aware

• 使用具有GRU更新函数的MPNN来计算图的语义和结构的embedding

order-aware

• 使用CFG的邻接矩阵作为输入，使用CNN来计算图顺序的embedding

最终链接输出的embedding并计算图最终的分布。

图4: 针对MLM, ANP, BIG and GC共4个任务的BERT

MLM：Masked language model

ANP：Adjacency node prediction

BIC：block inside graph

GC：graph classification

其中MLM和ANP是和BERT的原论文中相似的两个任务。MLM是一个token-level的任务，对block中的token进行mask操作并进行预测，和语言模型的方式相同。ANP任务是一个block-level的任务，虽然控制流图没有NLP领域中的语言顺序，但控制流图是一个有向图，也有节点的拓扑顺序，我们将控制流图中的所有相邻节点提取出来，当作相邻的“句子”。这些相邻的block pair作为ANP任务的正例，并随机选择同图内不相邻的block pair作为负例。

为了获得更多的graph-level的信息，我们加入了两个辅助的graph-level任务BIG和GC。BIG和ANP的方式类似，区别是pair的正负例选择方式不同。BIG任务的目的是让模型判断两个block是否在同一个图中，希望模型可以尽可能地学到此信息，从而对graph-level task有帮助。因此，在BIG任务中同图的block pair为正例，不同图的block pair为负例。GC为graph-level的block分类任务，在我们的场景中，在不同平台、不同编译器、不同优化选项的条件下，得到的block信息有所不同，我们希望模型可以让block embedding中包含这种信息。GC对block进行分类，判断block属于哪个平台，哪个编译器，以及哪个优化选项。

图5: 3个图和它们的邻接矩阵

为什么使用CNN模型呢？ 首先考虑图6中的三个图（节点中无语义信息），以及它们的邻接矩阵。这三个图非常相似，每个图中都有一个三角形特征（图a的节点123，图b的节点234，图c的节点134），这个特征体现在它们的邻接矩阵中。

首先对比图a和图b，与图a相比，图b加入了节点1，节点顺序依次后移一位，但三角形特征中三个节点的顺序还是连续的，这个特征在邻接矩阵中可以看到，这个1-1-0-1的2*2矩阵仍然存在。CNN在训练集中看过很多这种样例后，可以学习到这种平移不变性。

再看图c，加入了节点2，打破了原有三角形的节点顺序，但在邻接矩阵中我们可以看到它实际上是把原来的22矩阵放大成了33矩阵，当我们移除第二行和第二列时，仍然可以得到一个1-1-0-1的2*2矩阵。这与图像中的image scaling类似，CNN在训练集中包含足够多样例的情况下，也是可以学到这种伸缩不变性的。

图6: 4个CFG中关于block的聚类
使用K-means算法对block的embedding结果进行聚类，发现不同的CFG倾向于颜色不同，而同一类别的内部颜色倾向于相同。可视化的方式展示了在BERT中的两个graph-level的任务是有效果的。

表1: 数据集的基本信息

任务1是跨平台二进制代码检测任务，在任务1中，包含了O2和O3两种数据集，分别表示在gcc编译器上进行O2和O3两种优化选项的结果。

任务2是图的分类任务，包好了两个在不同平台上编译的代码，在每一个数据集中包含了不同优化选项的数据，期望能够根据图的embedding结果对优化选项结果进行分类。

表2和表3: 任务1和任务2的实验结果

表中第一个分块是整体模型，包括graph kernel，Gemini以及MPNN模型。第二个分块是semantic-aware模块的对比实验，分别使用了word2vec，skip thought，以及BERT，其中BERT2是指原始BERT论文中的两个task（即MLM和ANP），BERT4是指在此基础上加入两个graph-level task（BIG和GC）。第三个分块是对order-aware模块的对比实验，基础CNN模型使用3层CNN以及7、11层的Resnet，CNN_random是对训练集中控制流图的节点顺序随机打乱再进行训练，MPNN_ws是去除控制流图节点中的语义信息（所有block向量设为相同的值）再用MPNN训练。最后是本文的最终模型，即BERT+MPNN+Resnet。

引言、结论与公式

1、 引言

二进制代码相似性检测被用来计算两个二进制函数之间的相似程度。在计算机安全方面具有很多应用，包括代码克隆检测，漏洞发现和恶意软件检测等。

Previous work

传统的方法使用图匹配性算法来做的，但传统方法速度很慢，效果很差，难以被应用。

由于神经网络的发展，目前也有基于神经网络的办法，对于二进制代码相似性检测提升了很多。

Gemini：

• 每个block中的block转化为人工选择的特征（一个特征向量具有8个计算值）
• 使用Structure2vec生成图的embedding
• 使用Siamase架构
  • Siamase架构使用两个相同的图嵌入网络，输出的embedding计算余弦相似度

Weakness

但是二进制代码中的很多特性并没有被神经网络模型考虑到

• 原来的embedding是人工选择特征进行计算得到的
• 么有有考虑到CFG中的节点顺序信息

Work

• semantic-aware modeling
  • BERT of 4 tasks
• structural-aware modeling
  • MPNN
• order-aware modeling
  • CNN

contributions

• a general framework to learn graph em- beddings of CFGs
• BERT of 4 tasks
• the node order is useful
• better performance than the previous methods

2、结论

本文提出了一个新的模型，用于解决二进制代码分析的问题。本文的模型中包含semantic-aware模块，structural-aware模块以及order-aware模块。我们观察到语义信息和节点顺序信息都是控制流图重要的特征。我们使用BERT预训练模型提取语义信息，并使用CNN模型提取节点顺序信息。实验结果表明，本文提出的模型与之前最优的模型相比，取得了更好的效果。

3、公式

Structural-aware 模块：经过BERT预训练后，使用MPNN计算控制流图的graph semantic & structural embedding。MPNN有三个步骤：message function（M），update function（U）以及readout function（R）。具体步骤如公式2-公式4所示。

其中G代表整个图，v代表节点，N(v)代表v的邻居节点。在本文的场景中，节点即是控制流图中的block，图即是经过预训练后表示成block向量的控制流图。本文在message步骤使用MLP，update步骤使用GRU，readout步骤使用sum，如公式5-公式7所示。