一种支持多线程程序的符号执行技术

符号执行是一种实用的验证程序中是否包含某类错误的技术,具有0误报率的优点,但是主流的执行工具并不支持分析多线程程序。本文对已有的多线程程序的符号执行工具进行分析,发现存在的问题有：1）有些工具性能好,但是不支持外部库,实用性很差;2）有些工具支持外部库函数,但是版本老,难以更新和维护,无法检查减法溢出、乘法溢出、移位溢出等基本类型的bug。本文基于最主流的符号执行工具KLEE设计并实现支持多线程程序的符号执行工具——MTSE（Multi-Thread Symbolic Execution）。MTSE支持libc和libc++库,并且相对于已有的同类工作Cloud9,MTSE可以多查找出约50%的程序缺陷,并且指令覆盖率和分支覆盖率上均有约30%的提升。     

基于多线程并行的符号执行引擎设计与实现

符号执行作为一种高效的测试生成技术,被广泛应用于软件测试、安全分析等领域. 然而,由于程序中的执行路径数量随着分支数量的增加而指数级上升,符号执行往往无法在大规模程序上进行高效执行,缺乏可扩展性. 已有的基于多进程的并行化方法具有较大的额外通信开销,并且缺乏对现有约束求解优化技术的利用. 提出了基于多线程并行处理模型的符号执行加速方法. 具体来讲,为解决并行符号执行中的不同工作节点负载不平衡问题,设计了不需要中间节点参与的工作窃取算法. 为充分利用现有约束求解优化技术,提出了让不同工作节点共享约束求解信息的加速求解方法. 基于符号执行引擎（KLEE）实现了多线程并行化符号执行方案,从而形成多线程并行化符号执行引擎（PKLEE）. 实验验证表明,在穷尽执行路径场景下,KLEE平均耗时是在给定8个线程下PKLEE的3~4倍;在同样的时间内,PKLEE执行的有效工作负载平均是KLEE的3倍.

     

基于性质制导符号执行的Linux驱动程序缺陷检测研究

驱动程序是操作系统的重要组成部分。驱动程序运行于内核态,其可靠性对于操作系统的安全可靠非常关键。针对Linux驱动程序,研究基于符号执行的驱动程序缺陷自动检测方法。提出了基于性质制导符号执行的Linux驱动程序缺陷检测框架,以及多性质制导的符号执行方法,支持针对多个缺陷性质的快速缺陷检测。在LLVM和KLEE的基础上实现了提出的框架和方法,并在实际的Linux驱动程序上开展了初步实验。实验效果表明了所提方法和检测框架的有效性和高效性。     

基于求解开销预测的符号执行搜索策略研究

符号执行中约束求解所占的时间比例非常高.同时,不同复杂度约束的求解时间开销差距悬殊,这一现象在对包含复杂数值计算的程序进行符号执行时尤为明显.在指定时间内求解更多约束有利于覆盖更多语句和探索更多路径.为此,提出了基于求解开销预测的符号执行搜索策略.基于实验总结出了度量约束复杂度的经验公式,并结合约束的历史求解开销来预测当前的求解开销,从而在符号执行过程中优先探索求解开销较小的路径.在KLEE中实现了上述搜索策略,并对GNU科学计算库(GSL)中的12个模块进行了实验.实验结果表明,相比现有搜索策略,提出的搜索策略在保证语句覆盖率的同时,可以探索更多的路径(平均24.34%提高);而且,在相同时间内,可以查找出更多的软件缺陷,同时查找出相同缺陷的时间开销平均降低了44.43%.     

Unit Test Data Generation for C Using Rule-Directed Symbolic Execution

Unit testing is widely used in software development. One important activity in unit testing is automatic test data generation. Constraint-based test data generation is a technique for automatic generation of test data, which uses symbolic execution to generate constraints. Unit testing only tests functions instead of the whole program, where individual functions typically have preconditions imposed on their inputs. Conventional symbolic execution cannot detect these preconditions, let alone converting these preconditions into constraints. To overcome these limitations, we propose a novel unit test data generation approach using rule-directed symbolic execution for dealing with functions with missing input preconditions. Rule-directed symbolic execution uses predefined rules to detect preconditions in the individual function, and generates constraints for inputs based on preconditions. We introduce implicit constraints to represent preconditions, and unify implicit constraints and program constraints into integrated constraints. Test data generated based on integrated constraints can explore previously unreachable code and help developers find more functional faults and logical faults. We have implemented our approach in a tool called CTS-IC, and applied it to real-world projects. The experimental results show that rule-directed symbolic execution can find preconditions (implicit constraints) automatically from an individual function. Moreover, the unit test data generated by our approach achieves higher coverage than similar tools and efficiently mitigates missing input preconditions problems in unit testing for individual functions.

     

基于符号执行与模糊测试的混合测试方法

软件测试是保障软件质量的常用方法,如何获得高覆盖率是测试中十分重要且具有挑战性的研究问题.模糊测试与符号执行作为两大主流测试技术已被广泛研究并应用到学术界与工业界中,这两种技术都具有一定的优缺点：模糊测试随机变异生成测试用例并动态执行程序,可以执行并覆盖到较深的分支,但其很难通过变异的方法生成覆盖到复杂条件分支的测试用例.而符号执行依赖约束求解器,可以生成覆盖复杂条件分支的测试用例,但在符号化执行过程中往往会出现状态爆炸问题,因此很难覆盖到较深的分支.有工作已经证明,将符号执行与模糊测试相结合可以获得比单独使用模糊测试或者符号执行更好的效果.分析符号执行与模糊测试的优缺点,提出了一种基于分支覆盖将两种方法结合的混合测试方法——Afleer,结合双方优点从而可以生成具有更高分支覆盖率的测试用例.具体来说,模糊测试（例如AFL）为程序快速生成大量可以覆盖较深分支的测试用例,符号执行（例如KLEE）基于模糊测试的覆盖信息进行搜索,仅为未覆盖到的分支生成测试用例.为了验证Afleer的有效性,选取标准程序集LAVA-M以及实际项目oSIP作为评测对象,以漏洞检测能力以及覆盖能力作为评测指标.实验结果表明：（1）在漏洞检测能力上,Afleer总共可以发现755个漏洞,而AFL仅发现1个;（2）在覆盖能力上,Afleer在标准程序集上以及实际项目中都有不同程度的提升.其中,在oSIP中,Afleer比AFL在分支覆盖率上提高2.4倍,在路径覆盖率上提升6.1倍.除此之外,Afleer在oSIP中还检测出一个新的漏洞.     

基于目标制导符号执行的静态缓冲区溢出警报自动确认技术

缓冲区溢出漏洞是一类严重的安全性缺陷。目前存在动态测试和静态分析技术来检测缓冲区溢出缺陷:动态测试技术的有效性取决于测试用例的设计,而且往往会引入执行开销;静态分析技术及自动化工具已经被广泛运用于缓冲区溢出缺陷检测中,然而静态分析由于采取了保守的策略,其结果往往包含数量巨大的误报,需要通过进一步人工确认来甄别误报,但人工确认静态分析的结果耗时且容易出错,严重限制了静态分析技术的实用性。符号执行技术使用符号代替实际输入,能系统地探索程序的状态空间并生成高覆盖度的测试用例。本文提出一种基于目标制导符号执行的静态缓冲区溢出警报确认方法,使用静态分析工具的输出结果作为目标,制导符号执行确认警报。我们的方法分为3步:首先在过程间控制流图中检测静态分析警报路径片段的可达性,并将可达的警报路径片段集合映射为用于确认的完整确认路径集合;其次在符号执行中通过修剪与溢出缺陷疑似语句无关的路径,指导符号执行沿特定确认路径执行;最后在溢出缺陷疑似语句收集路径约束并加入溢出条件,通过约束求解的结果,对静态分析的警报进行分类。基于上述方法我们实现了原型工具BOVTool,实验结果表明在实际开源程序上BOVTool能够代替人工减少检查59.9%的缓冲区溢出误报。     

Symbolic Cache Analysis for Real-Time Systems

Caches impose a major problem for predicting execution times of real-time systems since the cache behavior depends on the history of previous memory references. Too pessimistic assumptions on cache hits can obtain worst-case execution time estimates that are prohibitive for real-time systems. This paper presents a novel approach for deriving a highly accurate analytical cache hit function for C-programs at compile-time based on the assumption that no external cache interference (e.g. process dispatching or DMA activity) occurs. First, a symbolic tracefile of an instrumented C-program is generated based on symbolic evaluation, which is a static technique to determine the dynamic behavior of programs. All memory references of a program are described by symbolic expressions and recurrences and stored in chronological order in the symbolic tracefile. Second, a cache hit function for several cache architectures is computed based on a cache evaluation technique. Our approach goes beyond previous work by precisely modelling program control flow and program unknowns, modelling large classes of cache architectures, and providing very accurate cache hit predictions. Examples for the SPARC architecture are used to illustrate the accuracy and effectiveness of our symbolic cache prediction.     

模型学习与符号执行结合的安全协议代码分析技术

符号执行技术从理论上可以全面分析程序执行空间,但对安全协议这样的大型程序,路径空间爆炸和约束求解困难的局限性导致其在实践上不可行。结合安全协议程序自身特点,提出用模型学习得到的协议状态机信息指导安全协议代码符号执行思路;同时,通过将协议代码中的密码学逻辑与协议交互逻辑相分离,避免了因密码逻辑的复杂性导致路径约束无法求解的问题。在SSH协议开源项目Dropbear上的成功实践表明了所提方法的可行性;通过与 Dropbear 自带的模糊测试套件对比,验证了所提方法在代码覆盖率与错误点发现上均具有一定优势。     

基于条件值的C/C++预处理测试算法

传统C/C++代码的预处理分析利用符号执行推断预处理中自由变量条件表达式的值,但是该算法的时间复杂度是指数型的.为降低时间复杂度,提出一种快速符号执行算法.源代码通过词法分析器得到顶处理变量和路径条件,为预处理变量建立节点,把路径条件转化为条件表达式,通过符号执行算法将两者整合为条件值c-value的形式,最终显示预处...     

基于符号化执行的Fuzzing测试方法

设计并实现一种基于符号化执行的Fuzzing测试方法。通过代码插装,在程序执行过程中收集路径约束条件,依据一定的路径遍历算法生成新路径约束条件并进行求解,构造可以引导程序向新路径执行的输入测试数据。提出一种改进的污点分析机制,对路径约束条件进行简化,提高了代码覆盖率和漏洞检测的效率。     

一种基于程序功能标签切片的制导符号执行分析方法

提出了一种基于程序功能标签切片的制导符号执行分析方法OPT-SSE.该方法从程序功能文档提取功能标签,利用程序控制流分析,建立各功能标签和程序基本块的映射关系,并根据功能标签在程序执行中的顺序关系生成功能标签执行流.针对给定的代码目标点,提取与之相关的功能执行流切片,根据预定义好的功能标签流制导规则进行符号执行分析,在路径分析过程中,及时裁剪无关的功能分支路径以提升制导效率.通过对不同的功能标签流进行分离制导符号执行分析,可避免一直执行某复杂循环体的情形,从而提高对目标程序的整体分支覆盖率和指令覆盖率.实验结果表明,通过对binutils、gzip、coreutils等10个不同软件中的20个应用工具上的分析,OPT-SSE与KLEE提供的主流搜索策略相比,代码目标制导速度平均提升到4.238倍,代码目标制导成功率平均提升了31%,程序指令覆盖率平均提升了8.95%,程序分支覆盖率平均提升了8.28%.     

Modeling Control Speculation for Timing Analysis

The schedulability analysis of real-time embedded systems requires worst case execution time (WCET) analysis for the individual tasks. Bounding WCET involves not only language-level program path analysis, but also modeling the performance impact of complex micro-architectural features present in modern processors. In this paper, we statically analyze the execution time of embedded software on processors with speculative execution. The speculation of conditional branch outcomes (branch prediction) significantly improves a program's execution time. Thus, accurate modeling of control speculation is important for calculating tight WCET estimates. We present a parameterized framework to model the different branch prediction schemes. We further consider the complex interaction between speculative execution and instruction cache performance, that is, the fact that speculatively executed blocks can generate additional cache hits/misses. We extend our modeling to capture this effect of branch prediction on cache performance. Starting with the control flow graph of a program, our technique uses integer linear programming to estimate the program's WCET. The accuracy of our method is demonstrated by tight estimates obtained on realistic benchmarks.     

面向智能合约漏洞检测的改进符号执行研究

由于区块链不可窜改的特性,部署到区块链上的智能合约不可更改.为了提高合约的安全性,防止智能合约出现整数溢出、短地址攻击、伪随机等问题,在合约部署之前需对合约进行漏洞检测.针对智能合约的整数溢出漏洞利用符号执行进行分析研究,对现有符号执行方法进行调查发现检测速度较慢,从而提出一种自底向上求解约束的改进符号执行方法,并结合深度优先与广度优先进行路径选择从而提高符号执行的代码覆盖率.实验结果表明,改进符号执行在选取的100份含溢出漏洞的智能合约中检测正确率达84％,平均检测效率提高了20％,在中等规模智能合约中检测效率提升显著,检测结果正确率较高.     

基于代码移动的二进制程序控制流混淆方法

代码混淆技术常被用于软件保护领域和恶意代码对抗分析.传统的代码混淆技术会使逆向分析者获得程序的全部二进制代码,因此存在一定的安全性问题.为缓解这一问题,提出了一种基于代码移动的二进制程序控制流混淆方法,将程序的重要控制逻辑代码移动至逆向分析者不可控的可信实体,以使本地代码控制流信息部分缺失,从而使得程序的关键行为无法通过推理获知;利用包含无初始意义操作数的非条件跳转指令替代条件跳转指令隐藏路径分支的分支条件和目标地址,以增大收集程序路径信息的难度.对该控制流混淆方法从强度、弹性和开销3个指标进行了技术评价.将所提混淆方法用于6个恶意软件触发条件的混淆并对混淆之后的恶意代码进行逆向分析实验,结果表明该混淆方法能够较好地抵抗基于静态分析和符号执行的逆向分析方法.     

基于污点指针的二进制代码缺陷检测

污点指针严重影响二进制代码数据流和控制流的安全。为此,提出一种二进制代码缺陷检测方法。引入指针污点传播规则,结合路径约束条件和边界约束条件得到缺陷引发条件,构造能够引发4类污点指针代码缺陷的输入数据。在Linux系统下实现ELF二进制代码缺陷检测工具,测试结果表明,该方法能降低测试用例生成数量,并发现Linux系统工具的1个虚函数调用控制缺陷和2个指针内存破坏缺陷。     

基于符号执行和N-scope复杂度的代码混淆度量方法

代码混淆可有效对抗逆向工程等各类MATE攻击威胁,作为攻击缓和性质的内生安全技术发展较为成熟,对代码混淆效果的合理度量具有重要价值。代码混淆度量研究相对较少,针对代码混淆弹性的度量方法与泛化性、实用性度量方法相对缺乏。符号执行技术广泛应用于反混淆攻击,其生成遍历程序完整路径输入测试集的难度可为混淆弹性度量提供参考,然而基于程序嵌套结构的对抗技术可显著降低符号执行效率,增加其混淆弹性参考误差。针对上述问题,提出结合符号执行技术和N-scope复杂度的代码混淆度量方法,该方法首先基于程序符号执行时间定义程序混淆弹性;其次提出适配符号执行的N-scope复杂度,定义程序混淆强度同时增强符号执行对多层嵌套结构程序的混淆弹性度量鲁棒性;进而提出结合动态分析与静态分析的混淆效果关联性分析,通过对程序进行符号执行与控制流图提取量化混淆效果。面向C程序构建了该度量方法的一种实现框架并验证,实验对3个公开程序集及其混淆后程序集约4 000个程序进行混淆效果度量,度量结果表明,提出的度量方法在较好地刻画混淆效果的同时拥有一定的泛化能力与实用价值;模拟真实混淆应用场景给出了该度量方法的使用样例,为混淆技术使...     

基于抽象符号表的内存模型

符号执行技术在软件测试和程序验证中发挥着重要作用。如何抽象和处理程序中各种数据类型和语法成分是符号执行必须解决的问题。本文提出抽象符号表的概念,以及基于抽象符号表建模内存的方法。抽象符号表记录可寻址对象的名称、类型、抽象地址和符号值,是一种简单、精确的内存抽象机制。内存模型是所有使用符号执行的技术的前提,本文系统给出了一个面向符号执行的内存模型。基于抽象符号表的内存模型能够统一处理各种数据类型和语法成分,包括函数和类,能够直接处理指针别名问题,不需要额外的别名分析算法。经过一些性能优化处理,基于抽象符号表的内存模型具有较好的性能。     

Worst‐case execution time analysis for a Java processor

In this paper, we propose a solution for a worst‐case execution time (WCET) analyzable Java system: a combination of a time‐predictable Java processor and a tool that performs WCET analysis at Java bytecode level. We present a Java processor, called JOP, designed for time‐predictable execution of real‐time tasks. The execution time of bytecodes, the instructions of the Java virtual machine, is known to cycle accuracy for JOP. Therefore, JOP simplifies the low‐level WCET analysis. A method cache, which fills whole Java methods into the cache, simplifies cache analysis. The WCET analysis tool is based on integer linear programming. The tool performs the low‐level analysis at the bytecode level and integrates the method cache analysis. An integrated data‐flow analysis performs receiver‐type analysis for dynamic method dispatches and loop‐bound analysis. Furthermore, a model checking approach to WCET analysis is presented where the method cache can be exactly simulated. The combination of the time‐predictable Java processor and the WCET analysis tool is evaluated with standard WCET benchmarks and three real‐time applications. The WCET friendly architecture of JOP and the integrated method cache analysis yield tight WCET bounds. Comparing the exact, but expensive, model checking‐based analysis of the method cache with the static approach demonstrates that the static approximation of the method cache is sufficiently tight for practical purposes. Copyright © 2010 John Wiley & Sons, Ltd.     

形状分析符号执行引擎中的状态合并

符号执行技术以其良好的精确度控制和代码覆盖率被广泛应用于静态程序分析和高覆盖率测试用例自动生成。 符号执行 在分析程序时,以模拟真实的程序执行过程的方式分析程序的数据流和控制流信息,并检查程序可能出现的所有状态,得到程序的分析结果。高精确度和高覆盖率要求对程序状态描述具体而完备,这会导致符号执行过程中常见的状态爆炸问题。首先提出在不同的执行路径上对具体内存状态进行合并的算法,然后对内存模型进行适度的抽象,扩大状态合并算法的适用范围,最后讨论状态合并所带来的实际效果,并提出了状态合并的优化解决方案。所提出的算法在符号执行引擎ShapeChecker上实现,并取得了良好的实验结果。