符号执行，从漏洞扫描到自动化生成测试用例
ThoughtWorks安全团队曾经在可信Frimware领域做了一些探索和研究。背景大概是这样的：整车制造过程中，常常会引入供应商的部分设备，如车载娱乐系统，但是出于知识产权的原因，这些供应商很难提供完整的源码给整车制造方，因此二进制的固件就成了整车制造环节中的安全隐患，各种漏洞都可能被供应商的零部件引入，存在于车载系统之中，随时可能被攻击者利用而影响整车的安全性。
为了探测二进制程序中的漏洞，经过一段时间的探索和研究后，把核心技术锁定到了符号执行，利用该技术帮客户搭建了一套自动化的二进制漏洞扫描平台。并且，在后来不断的研究中，我们发现，符号执行也可以用来自动化生成测试用例，为我们更加全面的编写测试用例, 带来新的思路。
Wikipedia上对符号执行的解释：是一种程序分析技术，其可以通过分析程序来得到让特定代码区域执行的输入。使用符号执行分析一个程序时，该程序会使用符号值作为输入，而非一般执行程序时使用的具体值。在达到目标代码时，分析器可以得到相应的路径约束，然后通过约束求解器来得到可以触发目标代码的具体值。
讲的比较绕，举个通俗的例子来说明：假设程序现在是一个王者荣耀中的英雄，这个英雄经过一定的出装就会有一定的战力(攻速，物理伤害，防御等)，符号执行的技术就是，给出了一个英雄的战力，可以反推出什么样的出装可以达到这样的战力。
再举个实际的代码例子来说明符号执行:
假设当t<x时，是我们程序的漏洞，我们要使用符号执行判断是否有达到t<x这个分支的可能。符号执行的方法就是在给定的时间内，生成一组输入，以尽可能多的探索所有的执行路径，在分析时，该程序会使用符号值作为输入，而非具体的值，去探索每一条分支。比如该程序在符号执行完后，会生成如下类似的方程组：
接下来，符号执行会通过约束求解，去分析上述的每条路径，通过约束求解分析得，如上的两条路径在任何情况下都不可能达到t<x这个分支。约束求解可以简单的理解为解方程，有很多开源的约束求解器，比如Z3。
那我们是如何把符号执行运用在自动化漏洞扫描的场景上？
首先要说明的是，我们要扫描的对象是Linux kernel，对于kernel来说有很多已知的CVE漏洞，我们的任务就是去发现二进制的kernel上是否存在这些CVE漏洞。思路如下：
通过一些简单的逆向，得到该内核的版本。
有了内核版本，就可以得到内核的源码，以及该内核版本对应的所有CVE漏洞和补丁。
给内核源码打上所有的CVE补丁，在二进制层面diff前后的补丁，对每个补丁提取唯一的特征（漏洞指纹）。
用漏洞指纹与目标kernel进行对比，扫描得到最终的漏洞列表。
由上述可知，提取漏洞的唯一特征是最重要的一步，接下来介绍如何使用符号执行来提取漏洞指纹。
首先介绍两个基本的概念BB(basic block)和CFG(control flow graph):BB是指从汇编的角度来看程序，一段连续的汇编指令就是一个BB，这段连续的汇编仅仅包含一个入口和一个出口，换句话说，BB内部不会有分支和跳转。由此我们可以得出，一个程序，是由一堆的bb组成的，它们之间有复杂的调用和跳转关系，最终形成了一张图，这个图就是CFG。例如下图是一个简单的CFG：
有了这两个概念，我们就可以对漏洞进行唯一的特征描述了。
漏洞指纹特征
由上面可知，CFG其实表示了一段程序执行的所有路径，而符号执行的第一步就是去探索所有的执行路径。如果您了解过内核的CVE漏洞，就会发现内核很大一部分的CVE漏洞补丁，就是在一些关键的代码上加了一些if分支和判断。例如CVE-2019-19252的补丁如下：
该补丁只是在vcs_write的函数中添加了一个if判断，对于这类补丁，在使用符号执行生成CFG的时候，前后肯定会出现一个明显的差异，因为多了一个分支，整个的程序流图也就多了一个分支。对于这种类型的补丁，使用CFG就可以作为漏洞的特征，通过对比发现，前后的CFG不一样，就说明漏洞存在。
那么，仅仅通过CFG是否就可以唯一的确定这个漏洞吗？请看下面的CVE-2019-8956的例子：
对于这种漏洞补丁，没有分支上的增减，只是改变了一个函数的入参个数，那么补丁前后的CFG可能是一样的，所以我们就不能仅仅通过CFG来判断补丁是否存在，必须加上在语义上的分析，语义即这个参数对函数的整体影响。这就引出了符号执行的另一步：约束求解，前面我们提到符号执行会对所有路径形成类似方程组的概念，然后使用约束求解器求出到达每个路径的解的集合。如果其中某些变量发生了改变，其最终的解一定是不一样的，以此作为漏洞标识的另一个特征。
漏洞扫描总结
所以最终，我们是采用符号执行从CFG和语义分析两个维度来唯一的确定一个漏洞的特征，然后用这个唯一的特征去目标的kernel中对比。以此来确定补丁是否已经存在。这个就是我们检测二进制漏洞的关键技术，大致流程如下图：
在整个过程中，我们会使用开源的符号执行引擎和约束求解器，比如Angr和Z3。
前面是符号执行在漏洞提取和扫描的一个案例，除此之外，符号执行在漏洞挖掘，CTF等方面也有比较广泛的应用。例如如下程序是我用Ghidra逆向的一道CTF的题目：
可以发现，其核心关键是去破解这个加解密的算法（异或，加减等操作），如果人工逆向，可能需要很长时间的推算和尝试，而符号执行则可以自动的去不断尝试每个路径的解，直到算出一个自己需要的值。有兴趣的读者，可以使用angr和z3去做一下这个CTF的破解，非常容易，这里不再赘述。需要说明的是，在破解和CTF中，符号执行往往和IDA/Ghidra等工具来配合使用。
另一方面是在测试领域，在单元测试中代码覆盖率往往被用于评估代码的测试充分性水平，在软件工业界，人工设计测试用例的方法被广泛使用，即依靠人对程序代码的理解设计测试用例，但对应的人力成本很高，有时候为了降低人力成本且提高自动化程度，随机测试的方法也被常常使用，但一般只能检测到有限的程序行为，容易遗漏软件错误。
在单元测试中，常用的白盒测试的充分性准则大多属于基于控制流的覆盖准则，如语句覆盖，分支覆盖和MC/DC覆盖等。而测试准则的选取一般根据实际的测试需求而确定，比如，传统软件的测试一般要求实现尽可能高的语句覆盖和分支覆盖，而对于航天，轨交等控制软件一般要求代码满足100%的分支覆盖。而这种同时实施多种测试标准的需求，进一步加大了单元测试的工作量和难度， 使得单元测试在实际软件开发中往往被忽略，最终导致软件缺陷没有在早期被及时发现。
而符号执行的特点是会尽可能的遍历每条路径，每一次符号执行的结果等价于大量的测试案例。符号执行为软件的各种情况自动生成了有效的输入，覆盖率高，可以更加容易检测到程序是否存在缺陷和错误。所以，其实我们可以运用符号执行生成测试用例。
目前学术界有不少的论文研究如何使用符号执行自动化生成更好的测试用例。也有一些有意思的demo，可以让您体验：
C语言：https://github.com/Sajed49/C-Path-Finder
Java语言：https://github.com/kaituo/sedge
以上是我们对符号执行的一些探索，欢迎您与我们一起进行更加深入的研究。随着大家对安全的越来越重视，基于符号执行的漏洞扫描，自动测试，fuzz测试等越来越受到人们的重视。2019年美国《国防法》National Defense Act的H.R.5515—517 就推荐使用二进制分析和符号执行工具来增强关键软件系统的安全。目前，ThoughtWorks安全团队正在积极探索符号执行在安全领域的威力，通过自动生成测试用例，再结合模糊测试（fuzz）工具，集成到DevOps的环境中，在整个软件的开发周期内持续的发现安全漏洞，为软件安全保驾护航。
- 相关阅读 -
点击【阅读原文】可至洞见网站查看原文&绿色字体部分的相关链接。
本文版权属ThoughtWorks公司所有，如需转载请在后台留言联系。