一种面向跨架构漏洞挖掘的符号执行引擎优化方法

摘要

本发明公开一种面向跨架构漏洞挖掘的符号执行引擎优化方法，该方法利用活跃变量分析技术和符号表达式预生成技术分别得到路径上每个基本块的活跃输出变量和输入输出变量间关系等基本块摘要信息，并由此构建摘要执行引擎，依据基本块摘要信息对基本块进行快速符号执行。该方法基于基本块摘要的分析来进行优化，具有平台无关性，且能够显著提高符号执行引擎的速度。

说明书

技术领域

本发明涉及计算机软件漏洞挖掘领域，具体涉及一种面向跨架构漏洞挖掘的符号执行引擎优化方法。

背景技术

在计算机软件漏洞挖掘方面，符号执行已经变得越来越流行，但在分析较复杂程序时，符号执行在应用领域、可扩展性和性能优化等方面仍面临着一些挑战。符号执行技术使用符号执行引擎对程序进行模拟执行。Yun等人指出符号执行引擎的性能是影响符号执行可扩展性的一个主要因素。目前针对架构类型多样的物联网设备，为了实现跨架构程序分析，符号执行引擎通常基于中间表示(Intermediate Representation，IR)进行实现，然而，现有的基于IR的符号执行引擎通常以基本块作为基本执行单元，需要对频繁执行的基本块进行大量重复分析，从而大大影响了符号执行引擎的性能。

发明内容

针对现有技术的不足，本发明提出一种面向跨架构漏洞挖掘的符号执行引擎优化方法，通过基本块摘要对基本块进行抽象，利用基本块摘要信息避免对基本块进行重复分析。具体技术方案如下：

一种面向跨架构漏洞挖掘的符号执行引擎优化方法，该方法包括如下步骤：

步骤一：对程序进行插桩，记录程序的执行流以及数据流；

步骤二：分别进行活跃变量分析和符号表达式预生成，得到基本块的摘要信息；

所述的活跃变量分析具体为：以执行路径为输入，得到所有的基本块，并根据所述数据流跟踪的结果得到基本块中定义和使用的变量集合，然后按照程序控制流的反方向依次遍历每个基本块，计算得到基本块的入口活跃变量集合和出口活跃变量集合；然后对基本块内定义的变量集合与基本块出口的活跃变量集合取交集，得到基本块的活跃输出变量集合；

所述的符号表达式预生成具体为：根据所述执行流跟踪的结果对执行路径上的基本块的执行频次进行统计，筛选出执行频次较高的基本块；对执行频次较高的基本块进行符号表达式预生成，得到基本块中符号值到输入变量之间的映射以及输出变量到符号表达式之间的映射；

所述的基本块的活跃输出变量、符号值到输入变量之间的映射以及输出变量到符号表达式之间的映射构成基本块的摘要信息；

步骤三：在执行引擎中构建摘要执行引擎，当基本块涉及符号数据时，优先使用摘要执行引擎对该基本块进行执行，具体为根据基本块的摘要信息进行快速符号执行，如果失败则顺序尝试其它可用的引擎；当基本块不涉及符号数据时则直接顺序尝试所有可用的引擎；当有一个执行引擎成功执行时，执行结束；最终得到执行路径的约束；

步骤四：根据执行引擎得到的路径约束，利用约束求解器求解变量值。

进一步地，所述的活跃变量具体为：对于特定的执行路径path、其上的变量x和执行路径上的某个基本块B，判断在路径path中基本块B出口之后是否会引用x的值，如果是，则说明在该path中变量x在B点是活跃变量，否则变量x在B点是非活跃变量。

进一步地，所述的步骤二中的基本块的活跃输出变量集合计算公式如下：

OUT[B

IN[B

DEF[B

ACT[B

其中，n表示基本块的数目，IN[B

进一步地，所述符号表达式预生成过程中，为了获取基本块的输入变量，使用了延迟初始化技术，即在变量第一次被读取时，为该变量赋予一个新的符号值，并建立符号值到输入变量之间的映射关系；同时，当更新状态中的目标操作数为变量或寄存器时，则说明该目标操作数是输出变量，建立输出变量到符号表达式之间的映射。

进一步地，所述的步骤三中，根据基本块的摘要信息进行快速符号执行具体为更新符号状态中活跃输出变量的值，详细过程为：对于基本块中每个输出变量，首先判断其是否为活跃输出变量，如果不是，则不对其进行更新；如果是，则将该活跃输出变量的符号表达式中的输入变量的符号值替换为该输入变量的实际符号表达式，即更新操作。

本发明的有益效果如下：

本发明提出的面向跨架构漏洞挖掘的符号执行引擎优化方法，该方法利用活跃变量分析技术和符号表达式预生成技术分别得到路径上每个基本块的活跃输出变量和输入输出变量间关系等基本块摘要信息，并由此构建摘要执行引擎，依据基本块摘要信息对基本块进行快速符号执行。通过这种方法的优化，使得符号执行引擎在CGC测试集上的速度相较于最新的二进制动态符号执行工具angr平均提高了45.35％，同时利用该符号执行引擎与模糊测试工具AFL构建的漏洞挖掘工具Hybrid Fuzz(一类结合符号执行和模糊测试的漏洞挖掘工具)，能够比现有的同类工具发现更多的漏洞，同时在不同架构的设备中都能挖掘到新的未公开的漏洞。

附图说明

图1为本发明的面向跨架构漏洞挖掘的符号执行引擎优化原型工具示意图，其中，具有深色底色的模块为优化模块。

图2为本发明的符号执行引擎优化方法涉及到的各个功能模块的示意图。

具体实施方式

下面根据附图和优选实施例详细描述本发明，本发明的目的和效果将变得更加明白，应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

如图1所示，本发明的面向跨架构漏洞挖掘的符号执行引擎优化方法，包括如下步骤：

步骤一：对程序进行插桩，记录程序的执行流以及数据流；作为其中一种实施方式，插桩模块基于QUME平台实现；除了常规的记录程序的执行流外，还通过对TCG解释器(Tiny Code Interpreter)进行修改增加了对数据流的跟踪，以此记录程序的寄存器和内存操作。

步骤二：分别进行活跃变量分析和符号表达式预生成，得到基本块的摘要信息；其中，活跃变量的粒度为字节；

本发明采用了活跃变量分析来获取基本块的活跃输出变量。在本发明中，活跃变量的定义是对于特定的执行路径path，变量x和执行路径上的某个基本块B，判断在路径path中基本块B出口之后是否会引用x的值。如果是，就说明在该path中x在B点是活跃变量，否则 x在B点是非活跃变量。活跃变量分析算法以执行路径为输入，通过路径可以得到所有的基本块，最后以基本块到活跃输出变量的映射作为输出。活跃变量分析按照程序控制流的反方向依次遍历每个基本块，通过数据流跟踪得到基本块中定义和使用的变量集合，并计算入口活跃变量集合和出口活跃变量集合，基本块的活跃输出变量即为基本块内定义的变量集合与基本块出口活跃变量集合的交集。基本块的活跃输出变量的计算公式如下：

OUT[B

IN[B

DEF[B

ACT[B

其中，n表示基本块的数目，IN[B

其中公式(1)的含义为某个基本块出口的活跃变量集合与下一个基本块入口的活跃变量集合相等。公式(2)的含义为最后一个基本块出口的活跃变量集合为空。公式(3)的含义为一个变量要在基本块入口处活跃，需要满足以下两个条件中的一个：一是它在基本块中没有被赋值之前就被使用；二是在基本块出口处活跃且基本块内没有对该变量进行赋值。公式 (4)的含义为基本块内定义的变量集合为基本块中进行赋值的变量集合减去基本块中赋值之前就被使用的变量集合。公式(5)的含义为基本块的活跃输出变量为基本块中定义的变量集合和基本块的出口的活跃变量集合的交集。

本发明采用了符号表达式预生成技术来获取基本块输出变量和输入变量之间的关系。基本块内未写入就被读取的内存和寄存器都可以当作基本块的输入变量，基本块内写入的内存和寄存器都可以当作基本块的输出变量。符号表达式预生成算法以基本块为输入，最后输出符号值到输出变量的映射以及输出变量到符号表达式的映射。符号表达式预生成的主要功能是将所有输入变量当作符号值，然后用这些符号值生成输出变量的符号表达式。具体为：利用延迟初始化技术获取基本块的输入变量，并同时得到其符号值与输入变量之间的映射；通过更新输出变量的符号表达式得到基本块中输出变量到符号表达式之间的映射；

所述的基本块的活跃输出变量、符号值到输入变量之间的映射以及输出变量到符号表达式之间的映射构成基本块的摘要信息。

步骤三：在执行引擎模块中构建新的摘要执行引擎，即SimEngineSummary，则整个执行引擎模块除了包括angr中的SimEngineFailure、SimEngineSyscall、SimEngineHook、SimEngineUnicorn、SimEngineVEX引擎外，还包含了新的摘要执行引擎SimEngineSummary，如图2所示。

利用执行引擎中的多个引擎对基本块进行各种处理，当基本块涉及符号数据时，优先尝试使用SimEngineSummary引擎，SimEngineSummary根据是否存有该基本块的摘要信息来判断SimEngineSummary引擎是否能处理。如果能，摘要执行引擎会根据摘要信息更新符号状态中活跃输出变量的值，最终得到一个新的输出状态，其过程中会遍历每一个活跃输出变量并将预生成的符号表达式中的符号值替换为输入符号状态中的输入变量的实际表达式。

当基本块不涉及符号数据时，将顺序执行SimEngineFailure、SimEngineSyscall、SimEngineHook、SimEngineUnicorn、SimEngineVEX引擎，即，

当输入状态已经无法继续运行时，SimEngineFailure引擎将抛出异常或者终止运行；

当输入状态即将执行一条系统调用指令时，SimEngineSyscall引擎将会执行；

当待执行基本块被挂钩时，SimEngineHook引擎将会执行；

当待执行的基本块不涉及符号数据时，SimEngineUnicorn引擎将会执行；

当其它引擎都无法处理时，SimEngineVEX引擎将会执行。

引擎模块会顺序尝试每一个引擎直到成功执行；当有一个执行引擎成功执行时，即结束对该基本块的执行。

步骤四：利用约束求解器对执行路径的约束求解变量值。

下面将首先列举使用符号执行引擎优化原型工具B

AFL的变异算法中存在两种变异模式(确定性模式和非确定性模式)，因此为AFL分配了2个模糊测试实例来测试二进制文件，同时为Driller、DigFuzz、B

程序输入选择测试集中提供的POV(Proof of Vulnerbility)，因为测试集中的POV文件是对应程序编写者写的，往往比较接近漏洞代码，而漏洞代码通常位于深层代码路径，因此POV 往往具有良好的代码覆盖率。

最终，在经过相同时间后，B

同样，B

最后，在CGC测试集的120个二进制程序上，我们将B

本领域普通技术人员可以理解，以上所述仅为发明的优选实例而已，并不用于限制发明，尽管参照前述实例对发明进行了详细的说明，对于本领域的技术人员来说，其依然可以对前述各实例记载的技术方案进行修改，或者对其中部分技术特征进行等同替换。凡在发明的精神和原则之内，所做的修改、等同替换等均应包含在发明的保护范围之内。