王学1，李学新1，周智鹏1，袁耀文2
（1.清华大学计算机科学与技术系，北京 100084；2. 解放军95837部队,北京 100093）
摘 要：S2E是一款开源的基于Qemu虚拟机并结合KLEE以及LLVM的软件安全测试平台，其主要优越性体现为：支持全系统控制；支持多平台分析；支持多核以提高分析效率。分析研究该平台，对
软件测试、漏洞挖掘都具有现实意义。S2E的成功得益于对符号执行、动态二进制翻译和虚拟机技术的
运用。文章着重介绍S2E的架构，插件的使用实例，并结合实例分析S2E的并行性能。
关键词：S2E；软件测试；漏洞挖掘；Qemu虚拟机；并行性能分析
中图分类号：TP393.08 文献标识码：A 文章编号：1671-1122（2012）07-0016-04
Analysis of the Software Testing Platform: S2E
WANG Xue1, LI Xue-xin1, ZHOU Zhi-peng1, YUAN Yao-wen2
( 1.Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China;
2. Unit 95837, Beijing 100093, China )
Abstract: The S2E is an open source software testing platform which based on Qemu virtual machine, KLEE and LLVM. It’s major advantaged abilities as follow: whole system control, multiplatform analyze and run with
multicore. It’s very meaningful for software testing and vulnerability exploitation to analyze this platform.
Key words: selective symbolic execution; software testing; vulnerability exploitation; qemu; performance analysis
doi：10.3969/j.issn.1671-1122.2012.07.004
S2E测试平台及并行性能分析
作者简介：王学（1983-），男，陕西，硕士研究生，主要研究方向：信息安全、普适计算;李学新（1984-），男，河南，硕士研究生，主要研究方向：普适计算、网络安全；周智鹏（1983-），男，山西，硕士研究生，主要研究方向：普适计算、网络安全;袁耀文（1974-），男，湖南，工程师, 硕士,主要研究方向：系统架构、网络安全。
0 引言
软件测试、分析和漏洞挖掘技术是软件设计和安全人员一直关注的问题。如何能够更准确、更高效地发现软件中的潜在问题是研究人员关注的焦点。在软件测试、分析和漏洞挖掘的过程中，人们提出了许多技术方法，并与其他技术相结合，从而能够更好地发现和解决问题。比如，软件测试技术与虚拟机技术的结合，使软件测试迈向了全系统级测试的层次。
1 S2E技术应用
符号执行技术是Robert S.Boyer和James C.King[1,2]等人于上世纪七十年代提出的。其基本思想是先对程序的每条路径生成路径条件，然后求解该条件并得到能够使程序执行对应路径的输入数据。
S2E是选择性符号执行[3]的英文缩写，由瑞士洛桑理工大学的Vitaly Chipounov，Vlad Georgescu等人于2009年提出并发展至今。其核心思想是对我们所关心的目标代码层实施符号执行，比如库函数，而对系统内核函数和其他应用函数的调用实施单路径的具体执行（参见图1）。选择性符号执行将目标程序看作可执行路径
叠加的程序，将具体值的单路径执行和符号值的多路径执行同时
进行，通过具体值执行与符号值执行之间的无缝切换，来达到我
们对目标代码层实现全路径符号执行的目的。这样便极大的提高
了软件测试、分析和漏洞挖掘的效率，有效解决了路径爆炸问题。
我们就图1解析如下：
程序app由concrete（具体执行）开始自上而下执行，进入
我们所关心的lib库函数时，我们使其symbolic（符号化执行），
当程序离开lib库进入内核kernel时，我们使其具体执行，如此图 1 选择性符号执行示意图[4]
17
反复，核心只有一个，即：对我们所关心的代码、函数或程序片段（如闭源的程序只能获取二进制内容时），使其符号化执行；对我们所不关心的部分，使其具体执行[5-6]。详细转化过程分为以下两种：
1）具体执行至符号执行的转化：具体值继续独立执行；符号值开始符号执行，转换时可对符号值加约束条件，也可不加约束条件（由一致性模型进行处理：主要根据路径覆盖率和时间开销的不同进行权衡）。
2）符号执行到具体执行的转换：将具体执行的结果返回到具体执行域，从而保证该路径的一致性；
符号值转换为具体值：(如x = i;)
（1）如果被调用的符号参数在具体执行时没有被访问，则该符号参数并不改变，x = i ；
（2）如果被调用的符号参数在具体域中被访问，则随机选择一个具体值代替符号值，并将该具体值作为符号参数的软约束添加到约束集合(x = i; x = 5;)，当由于具体化而导致有效路径丢失时（过度约束）执行回溯，重新选择具体值，直到满足约束条件或选择超时（在不同一致性模型中，对软约束和硬约束问题的处理有所差异）。
2 S2E 的架构
S2E 是基于QEMU、KLEE 和LLVM [7-10]，能够进行软件测试、漏洞挖掘的开源平台。其架构图如图2所示。
图 2 S2E的架构[4]
1） LLVM 用来进行动态二进制翻译；2）KLEE 用来进行符号执行；3）QEMU 用来运行目标程序。
从图2我们可以清晰地看到，从上到下依次为：应用程序→库函数→操作系统内核或驱动，他们都运行在S2E 架构之上。该架构由以下三层组成：
1）动态二进制翻译器：根据需要将客户机器码翻译为具体模式的主机器码或符号模式的LLVM 字节码；2）执行引擎：以主机CPU 执行具体模式数据或者以KLEE 执行符号数据；3）共享状态描述：各种虚拟的设备来支持上述两层所描述的工作。
在这个架构的两侧，分布着选择接口和分析接口。左侧的选择接口支持用户自定义的和S2E 自开发的选择器，右侧的分
析接口与之类似，也支持用户自定义的以及S2E 自开发的分析器。这些选择器和分析器均以插件的形式存在，具备很好的扩展性。
3 S2E 的插件系统分析
S2E 现有插件分为以下五类: OS Event Monitors, Execution Tracers, Selection Plugins, Analysis Plugins, Miscellaneous Plugins。
3.1 OS Event Monitors
依赖以下插件来检测模块的加载/卸载和目标模块的执行：1）Windows Monitor ：实现Windows 操作系统下模块和进程加载/卸载的检测，该插件捕获特定的内核函数调用来检测这些事件;2） Raw Monitor ：检测特定目标模块的加载或卸载，用于一个没有插件的新操作系统来自动提取信息，也可以用于分析原始代码，如BIOS 固件等；3）Module Execution Detector ：获取目标模块在内存中的位置，当程序执行进入或者离开目标模块时负责发送信号给其他的插件。
3.2 Execution Tracers
执行追踪器，这些插件记录在执行期间的各类多路径信息，这些信息可由离线分析工具处理：
1）Excution Tracer ：一个主要的跟踪插件，将二进制跟踪文件保存在s2e-last/ExecutionTracer.dat 中。默认情况下，该插件在程序执行发生分叉时，调用程序计数器，这使得离线分析工具可以重建执行树，并提供每个路径的分析；2）Module Tracer ：记录Module Execution Detector 插件中指定的模块加载事件，依赖于Execution Tracer、Module Execution Detector ；3）Test Case Generator ：记录程序执行过程中跟踪的每个终止路径的具体输入值，依赖于Excution Tracer ；4）Translation Block Tracer ：记录程序执行过程中所有的翻译块，记录信息包含每个块的起始地址及执行前后CPU 寄存器的内容，依赖于Execution Tracer、Module Execution Detector ；5）Instruction Counter ：记录模块内感兴趣的执行路径执行的指令数，依赖于Excution Tracer。
3.3 Selection Plugins
选择性插件，主要用于指定注入符号值的位置、选择执行的路径：
1）Annotation ：拦截任意指令和函数的调用或返回，并写Lua 脚本来操作执行状态，杀死路径等；2）Base Instructions ：该插件用于实现各种定制指令，从客户机操作系统内来控制符号执行的行为；3）Code Selector ：禁用目标模块以外的分支；4）Edge Killer ：寻找执行程序序列的计算器，当序列发生时，杀死所有路径
；5）State Manager ：通过实施执行障碍的概念，多步分割路径探索。一个障碍是用户定义的代码位置，当一个路径到达障碍时，State Manager 暂停；当所有的路径到达障碍或者发生超时，State Manager 杀死除一
个以外所有的路径，然后继续执行剩下的路径。State Manager
用于探索有多个入口点的模块的执行路径（库或者设备驱动）；
6）Symbolic Hardware：实现符号PCI和ISA设备以及符号中
断和DMA。
3.4 Analysis Plugins
分析插件：CacheSim：实现多路缓存探查器。
3.5 Miscellaneous Plugins
其余插件：1）Function Monitor:捕捉机器指令的调用和返回，
并调用相应的处理程序；2）Host Files：s2eget插件的配置文件，
用于快速便捷的在Host主机与Guest机器之间传输文件。
4 S2E使用实例
说明：以下实例均以S2E v1.1、Ubuntu10.10 64位系统为
基础环境。
实例一：Windows Monitor插件使用实例
该例旨在监控WindowsXPSP3系统下的notepad.exe进程：
首先，我们需要配置S2E的配置文件，lua格式，此处命
名为notepad.lua，内容如下：
其次，运行S2E版本的Qemu虚拟机（已将WindowsXP
SP3安装在虚拟机），命令如下：
再次，在虚拟机WindowsXPSP3系统内打开notepad程序，
则虚拟机外部的终端即可监控到notepad进程，其运行状态、
加载时间等信息保存在S2E同级目录的s2e-last文件夹中的各
个文件内。
实例二：并行分析实例
待分析的程序TestApp.c片段：该程序主要将我们自定义
的输入值符号化执行，并支持多线程。
以单线程运行TestApp.c：
以多线程运行TestApp.c：
为了比较以不同线程运行时的性能，我们分别在以下两
种配置的机器上运行TestApp.c：
Intel Core i3 330M 2.13GHz 4Cores/2G内存/笔记本（下文
以“4核i3”表述）
Intel Xeon E5606 2.13GHz 8Cores/12G内存/服务器（下文
以“8核Xeon”表述）
图3给出了在单核、4核以及8核上运行TestApp.c的性
能图示。从图上我们能够直观地看到：
以单核运行时，4核i3与8核Xeon的耗时基本持平，大
约为20秒；
以4核运行时，4核i3与8核Xeon的耗时也基本持平，
分别为62与65秒；
当以8核运行时，8核Xeon的耗时大约为64秒。
由此，我们产生了疑问：同一实例单核运行时，耗时20
多秒；4核运行时，耗时不降反升，为60多秒；8核运行时，
耗时比4核运行时亦无显著降低。
图 3 多核性能简明分析
通过阅读并调试S2E源代码，我们初步发现：
19
如果目前空余的CPU 核数为x，S2E 则为每条路径分支自动创建新线程，由Core Plugin 函数发出onProcessFork 信号，使与之相关的plugins 能够对其信号进行响应，直到这x 个CPU 核全部被使用为止；
如果待执行的路径数为y，且y 小于x 时，S2E 则创建y 个与待执行路径对应的线程；
在多核运行模式下，为了确保执行结果的一致性，各个有路径依赖关系的线程之间需要等待，有的甚至会超时，这会导致耗时明显增加。
而更深层次的原因有待进一步研究。
5 S2E 的技术优势以及目前面临的问题
S2E 的优势主要体现在以下几方面：1）支持系统级的控制分析；2）支持多平台的分析；3）支持多核多线程以提高分析效率。经实验测试，S2E 目前存在如下问题：1）不支持分布式内存，即不能在集群上并行；2）在共享内存模式下，相同实例以单线程运行耗时仅为20多秒，而以多线程（如4线程或8线程）运行耗时却超过1分钟。
6 结束语
本文简要介绍了S2E 这种基于Qemu 虚拟机、KLEE 及LLVM 的软件测试平台。分析了S2E 各类插件的主要功能，并结合实例分析了S2E 的并行性能，进一步总结了S2E 的优势以及目
前面临的问题。这有助于提高人们对这种支持全系统控制、多平台分析、多核运行的软件测试平台的理解和运用。 （责编 杨晨）
参考文献：
[1] Robert S. Boyer, Bernard Elspas, Karl N. Levitt SELECT--a formal system for testing and debugging programs by symbolic execution[C]. Proceedings of the International Conference on Reliable Software, page 234-245,1975.
[2] JC King. Symbolic execution and program testing[C]. Communications of the ACM, Volume 19 Issue 7, July 1976.
[3] V Chipounov. S2E: A platform for in-vivo multi-path analysis of software systems[C]. ASPLOS '11 Volume 46 Issue 3, March 2011.[4] V Chipounov. The S2E Platform: Design, Implementation, and Applications[C]. ACM Transactions on Computer Systems, Vol. 30, No. 1, Article 2, February 2012.
[5] M Sutton. Fuzzing:Brute Force Vulnerability Discovery[M]. 2007.
[6] T Wang. TaintScope:A checksum-aware directed fuzzing tool for automatic software vulnerability detection[C]. 2010 IEEE Symposium on Security and Privacy, May 16-May 19, 2010.
[7] F. Bellard. QEMU, a fast and portable dynamic translator[C]. In USENIX Annual Technical Conf., 2005.
[8] C. Cadar, D. Dunbar, D. R. Engler. KLEE: Unassisted and automatic generation of high-coverage tests for complex systems programs[C]. In Symp. on Operating Systems Design and Implementation, 2008.
[9] Tao Xie. Fitness-Guided Path Exploration in Dynamic Symbolic Execution[C]. Dependable Systems & Networks, 2009.[10] LLVM[EB/OL]. https://www.doczj.com/doc/b14211388.html,/.
一、会议背景
“卓越工程师教育培养计划”（简称“卓越计划”）是贯彻落实《国家中长期教育改革和发展规划纲要（2010-2020 年）》和《国家中长期人才发展规划纲要（2010-2020 年）》的重大改革项目，旨在培养造就一大批创新能力强、适应经济社会发展需要的高质量各类型工程技术人才，对促进高等教育面向社会需求培养人才、全面提高工程教育人才培养质量具有十分重要的示范和引导作用。
应广大开设卓越工程计划高校的要求，由教育部高等学校电子信息科学与工程类专业教学指导分委员会指导，国内十多家大学联合主办的2012 年卓越工程师教育交流研讨会定于2012 年7 月30 日至8 月1 日在河北秦皇岛召开，会议届时将围绕卓越工程师人才培养展开广泛深入的研讨和交流。组委会将邀请知名高校卓越工程师专业建设专家教授，国家级工程教育中心建设负责人，IEEE、IET 等国际工程教育认证机构专家等做主题报告。为加强会议期间的交流，会议将正式出版论文集一本（有ISBN 号），论文集除收录教师专家撰写的文章外，还将收录专家发言PPT、典型高校卓越工程师计划的培养方案和卓越工程师其他材料。会议支持媒体为《信息网络安全》杂志。
组委会建议所有参会单位至少有1 名参会代表作一个20 分钟左右的交流报告，用来介绍本单位卓越工程师计划推进情况及经验，组委会热忱欢迎大家踊跃参加会议。
二、参会对象
全国已审批卓越工程师教育和计划申请卓越工程师教育高校专业建设负责人和骨干教师、教务以及学生就业指导部门负责人。参会代表将获得国内卓越工程师相关资料。
三、会议地点
东北大学秦皇岛分校北戴河培训中心，位于东北大学秦皇岛分校北戴河校区院内，南距北戴河国际俱乐部、北距野生动物园均一百米，东临沙软潮平大海。
四、参会费用
980 元/人，住宿统一安排，费用自理。会议期间正值秦皇岛旅游旺季，需住宿的代表请提前报名注册，以便组委会提前安排住宿。住宿费用标准为每个标间300 元每天。
五、联系方式
会议网站：https://www.doczj.com/doc/b14211388.html,/E-mail: xueqiong@https://www.doczj.com/doc/b14211388.html,
电话：157******** 联系人：薛老师，董老师
2012年卓越工程师教育交流研讨会组委会
北京邮电大学信息安全中心
2012 年卓越工程师教育交流研讨会邀请函