基于参数约束的分支覆盖符号执行优化算法

软件质量检测常用的方法是软件测试,符号执行作为主流的测试技术已被广泛应用于学术界与工业界中。但是随着程序规模的增大和函数调用的增加,因某些路径约束条件的特殊性,而难以生成正确的测试用例,从而导致符号执行不能对所有路径做到全覆盖。为了提高符号执行在特殊约束条件对路径的覆盖率等问题,本文提出了基于参数约束的符号执行优化算法。首先,该算法通过搜索收集程序代码中函数的特殊参数,然后利用这些特殊参数作为约束条件,最后将约束条件添加到路径的约束集中。该算法使符号执行生成的测试用例更加精确,从而实现覆盖特殊约束条件下的路径分支,以提高符号执行的精确性和路径覆盖率。在开源符号执行平台CREST中实验并验证上述优化算法,验证及测试结果表明本文提出的算法能够提高符号执行在特殊约束条件下对路径的覆盖率。     

SymFuzz:一种复杂路径条件下的漏洞检测技术

当前漏洞检测技术可以实现对小规模程序的快速检测,但对大型或路径条件复杂的程序进行检测时其效率低下。为实现复杂路径条件下的漏洞快速检测,文中提出了一种复杂路径条件下的漏洞检测技术SymFuzz。SymFuzz将导向式模糊测试技术与选择符号执行技术相结合,通过导向式模糊测试技术对程序路径进行过滤,利用选择符号执行技术对可能触发漏洞的路径进行求解。该技术首先通过静态分析获取程序漏洞信息;然后使用导向式模糊测试技术,快速生成可以覆盖漏洞函数的测试用例;最后对漏洞函数内可以触发漏洞的路径进行符号执行,生成触发程序漏洞的测试用例。文中基于AFL与S2E等开源项目实现了SymFuzz的原型系统。实验结果表明,SymFuzz与现有的模糊测试技术相比,在复杂路径条件下的漏洞检测效果提高显著。     

基于蚁群算法的猜测符号执行的路径搜索

符号执行作为一种基本的程序分析技术,已被广泛应用于软件测试领域。研究表明,即使在现有的查询优化技术的支持下,约束求解也仍然是符号执行中最耗时的部分。猜测符号执行的思想是将多次约束求解合并成一次求解,从而减少约束求解消耗的时间。但是,猜测的成功率受猜测深度和路径搜索方向的影响,尤其是路径搜索的方向在较大程度上决定了整体猜测的成功率。因此,引导路径搜索向成功率高的方向进行,对提高猜测符号执行的整体效率至关重要。在猜测符号执行的路径搜索过程中引入蚁群算法,根据节点条件信息初次确定分支路径的权重,在多次迭代中根据分支路径的覆盖情况更新权重,通过权重决定路径搜索的方向。实验表明,该方法有效提升了猜测符号执行的效率。     

面向软件脆弱性的并行检测系统相关技术研究与实现

软件脆弱性作为信息安全问题的根源之一,对信息安全构成了严重威胁。当前,普遍使用的符号执行技术受限于运算复杂度和计算能力,无法实现大规模应用。为此课题组提出了基于动态符号执行的软件脆弱性并行检测系统。并行调度是软件脆弱性并行检测系统的关键技术之一,与系统的检测效率紧密相关。本文提出了基于节点状态的子系统调度算法和基于路径广度优先遍历的任务调度算法,分别实现了并行系统的子系统调度和任务调度。两个算法在实现上简单易行,并且具有很高的效率。本文对具体编程的细节进行了介绍和分析。     

志愿者计算平台中的监控系统设计与实现

描述了志愿者计算平台P2HP的监控系统设计与实现技术,该监控系统的功能采用多个节点来完成,克服了单一节点失效问题。采用对象序列化技术和远端过程调用技术进行任务和子任务的处理,可以使应用程序跨平台运行,使P2HP平台更加有利于聚集异构环境下的计算资源。通过定义各个角色节点间的消息通信协议格式,采用消息通信机制对本组的监控服务器节点、下属的调度服务器节点和分布式应用程序进行监控。测试结果表明,该监控系统提供了平台和应用监控、节点管理、任务和子任务的处理等完善的功能。     

基于动态符号执行的二进制程序缺陷发现系统

以对二进制程序进行自动化缺陷发现为目标, 基于软件虚拟机的动态二进制翻译机制和污点传播机制, 对符号计算需要关注的程序运行时语义信息提取、中间语言符号计算等机制进行了研究, 改进了传统动态符号执行的路径调度部分, 分析了程序缺陷的符号断言表达形式, 构建了一个在线式的动态符号执行系统检测二进制程序中的缺陷。实验验证了该方法在实际程序缺陷发现中的有效性。     

函数调用路径测试用例自动生成的方法研究

测试用例自动生成是软件测试自动化中最为关键的组成部分之一,符号执行作为一种程序分析方法,以其可提供高覆盖率测试用例的优势被广泛应用其中,但路径爆炸和约束求解问题很大程度制约了符号执行技术在现实程序分析中的应用。将研究粒度由语句提升至函数,利用抽象语法树和字节码序列提取到的函数关键信息和控制信息得到函数调用关系模型,设计算法生成函数调用路径（函数调用路径表示程序从开始到结束之间函数的调用或执行序列）。该方法不仅减少了测试路径数目缓解了路径爆炸问题,还有效解决了控制条件中存在函数导致符号表达式难求解的问题。实验结果表明该方法可优化测试路径集,在不降低覆盖率的前提下减少测试用例数量。     

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

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

结合静态分析与动态符号执行的软件漏洞检测方法

动态符号执行是近年来新兴的一种软件漏洞检测方法,它可以为目标程序的不同执行路径自动生成测试用例,从而获得较高的测试代码覆盖率。然而,程序的执行路径很多,且大部分路径都是漏洞无关的,通常那些包含危险函数调用的路径更有可能通向漏洞。提出一种基于静态分析的有导动态符号执行方法,并实现了一个工具原型SAGDSE。该方法通过静态分析识别目标程序中调用危险函数的指令地址,在动态符号执行过程中遇到这些指令地址时收集危险路径约束,再通过约束求解生成走危险路径的测试用例,这些测试用例将更可能触发程序漏洞。实验结果表明了该方法的有效性。     

面向危险操作的动态符号执行方法

针对缺陷检测的需求,提出了面向危险操作的动态符号执行方法.依据所关注的缺陷类型,定义危险操作及危险操作相关路径,通过计算覆盖不同上下文中危险操作的能力,协助动态符号执行选择高效初始输入,并利用危险操作相关信息引导测试流程.缺陷检测成为定位待测程序内危险操作以及对危险操作相关路径进行检测的过程.实现了面向Linux平台二进制可执行程序的原型系统CrashFinder,实验结果表明,该方法能够更快地发现更多缺陷.     

基于混合输入的环境交互问题研究

针对软件安全测试中静态符号执行技术难以处理环境交互的问题, 提出了一种基于混合输入的符号执行方法。首先, 定义了程序执行的一致性模型, 系统化地分析了符号执行与实际执行的逼近问题; 接着, 提出了符号执行与具体执行的转换方法及维护一致性的启发式策略; 最后, 通过区分可求解约束和复杂约束条件, 提出了具体值和符号值混合代入法化简复杂约束的路径求解算法。实验结果表明该方法在处理环境交互问题上的可行性和有效性, 扩展了静态符号执行的能力。     

An analysis on secure coding using symbolic execution engine

Business’ dependency on a software or computer program is getting higher. In such an environment, eliminating security vulnerabilities have become increasingly important and difficult as programs are more complicated and have greater impacts on businesses. We analyzed the security vulnerabilities of code using a symbolic execution engine that tracks data which would kill or might make the program vulnerable. We also present smart fuzzing using the data from the symbolic execution engine, an effective software vulnerability-finding testing that automatically generates inputs that crash or penetrate the program. By using symbolic execution engine, we can produce the automatically-generated data that are strong against vulnerability issues. In the case when program verification tools fail to verify a program, either the program is buggy or the report is a false alarm. In this case, the burden is put on users in manually classifying the report, which is a time-consuming, error-prone task and it does not utilize facts already proven by the analysis. We present a new technique for assisting users in classifying error reports. Our technique computes small, relevant queries presented to a user, which capture exact information that the analysis misses to either discharge or validate the error. In this paper, a methodology proper to detecting the security vulnerability is suggested by engrafting the symbol-based engine into the secure coding. Also, its effect was verified through the security vulnerability inspection test using the suggested symbolic execution engine. A notion of symbolically executing the program has been presented, which is closely related to the normal notion of program execution. It offers the advantage that one symbolic execution may represent a large, usually infinite, class of normal executions. This can be used for great advantages in the program inspecting and debugging.     

A survey of new trends in symbolic execution for software testing and analysis

Symbolic execution is a well-known program analysis technique which represents program inputs with symbolic values instead of concrete, initialized, data and executes the program by manipulating program expressions involving the symbolic values. Symbolic execution has been proposed over three decades ago but recently it has found renewed interest in the research community, due in part to the progress in decision procedures, availability of powerful computers and new algorithmic developments. We provide here a survey of some of the new research trends in symbolic execution, with particular emphasis on applications to test generation and program analysis. We first describe an approach that handles complex programming constructs such as input recursive data structures, arrays, as well as multithreading. Furthermore, we describe recent hybrid techniques that combine concrete and symbolic execution to overcome some of the inherent limitations of symbolic execution, such as handling native code or availability of decision procedures for the application domain. We follow with a discussion of techniques that can be used to limit the (possibly infinite) number of symbolic configurations that need to be analyzed for the symbolic execution of looping programs. Finally, we give a short survey of interesting new applications, such as predictive testing, invariant inference, program repair, analysis of parallel numerical programs and differential symbolic execution.     

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

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

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

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

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

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

基于符号执行的底层虚拟机混淆器反混淆框架

针对Miasm反混淆框架反混淆后的结果是一张图片,无法反编译恢复程序源码的问题,在对底层虚拟机混淆器（OLLVM）混淆策略和Miasm反混淆思路进行深入学习研究后,提出并实现了一种基于符号执行的OLLVM通用型自动化反混淆框架。首先,利用基本块识别算法找到混淆程序中有用的基本块和无用块;其次,采用符号执行技术确定各个有用块之间的拓扑关系;然后,直接对基本块汇编代码进行指令修复;最后,得到一个反混淆后的可执行文件。实验结果表明,该框架在保证尽量少的反混淆用时前提下,反混淆后的程序与未混淆源程序的代码相似度为96.7%,能非常好地实现x86架构下C/C++文件的OLLVM反混淆。