基于SMT求解器的路径敏感程序验证

随着软件规模的不断扩大以及复杂度的不断增长,人们越来越关注软件的可信性问题.验证程序是否满足断言所描述的性质,是保证软件可信性的一种常见方法.路径敏感的程序验证由于不可能遍历所有的路径,需要合并路径信息,因此造成精度上的损失.提出一种基于SMT求解器的路径敏感程序验证方法,在保证精确度的前提下,有效减少路径搜索空间.其基本思想是,利用最大强连通分量压缩循环路径,然后根据目标断言对控制流图进行切片.使用一种布尔表达式方法对路径空间进行抽象,结合抽象解释和符号执行技术对路径进行验证.结合F-Soft平台和Z3工具对该方法进行了实验验证,结果表明,该方法在验证的精确度和效率上都有较好的效果.     

基于协议状态机遍历的模糊测试优化方法

针对现有的协议模糊测试技术存在报文重复交互、输入盲目等问题,提出一种基于协议状态迁移遍历的模糊测试优化方法。该方法将协议状态迁移遍历问题转化为中国邮路问题,求解遍历所有协议状态迁移的最短路径,并依据该最短路径对各个状态迁移进行测试。在测试过程中,通过分析协议实体在执行测试用例后的响应报文,动态调整后续的报文输入,进而避免无效交互。同时利用UIO序列判断协议实体状态是否发生异常迁移,及时检测协议逻辑漏洞。实验结果表明,该模糊测试优化方法可以显著提高测试效率与漏洞挖掘能力。     

面向Android应用的静态污点分析结果的正确性验证

应用静态污点分析检测Android应用的隐私泄露漏洞会产生许多虚警，为此提出一种上下文敏感、路径敏感和域敏感的半自动程序分析方法，仅需遍历少量执行路径即可判定漏洞是否虚警。首先，运行插桩后的应用来获得一条覆盖Source和Sink的种子Trace。然后，应用基于Trace的污点分析方法来验证Trace中是否存在污点传播路径，是则表明漏洞真实存在；否则进一步收集Trace的条件集合和污点信息，结合活变量分析和基于条件反转的程序变换方法设计约束选择策略，以删除大部分与污点传播无关的可执行路径。最后，遍历剩余执行路径并分析相应Trace来验证漏洞是否虚警。基于FlowDroid实现原型系统，对DroidBench的75个应用和10个真实应用进行验证，每个应用平均仅需遍历15.09%的路径，虚警率平均降低58.17%。实验结果表明该方法可以较高效地减少静态分析结果的虚警。     

基于可满足性模理论求解器的程序路径验证方法

针对程序中因存在路径条数过多或复杂循环路径而导致路径验证时的路径搜索空间过大,直接影响验证的效率和准确率的问题,提出一种基于可满足性模理论（SMT）求解器的程序路径验证方法。首先利用决策树的方法对复杂循环路径提取不变式,构造无循环控制流图（NLCFG）;然后通过基本路径法对控制流图（CFG）进行遍历,提取基本路径信息;最后利用SMT求解器作为约束求解器,将路径验证问题转化为约束求解问题来进行处理。与同样基于SMT求解器的路径验证工具CBMC和FSoft-SMT相比,该方法在对测试集程序的验证时间上比CBMC降低了25%以上,比FSoft-SMT降低了15%以上;在验证精度上,该方法有明显的提升。实验结果表明,方法可以有效解决路径搜索空间过大的问题,同时提高路径验证的效率和准确率。     

路径模糊:一种有效抵抗符号执行的二进制混淆技术

符号执行能够对软件的路径分支信息进行收集和形式化表示,然后通过路径可达性推理得到软件行为同用户输入、网络输入等外部执行环境间的依赖关系.这些依赖关系已被广泛地应用到漏洞发掘、代码复用、协议分析等领域.该逆向分析技术也可被黑客用于软件破解、篡改和盗版等,对软件知识产权的保护带来了新的威胁.提出了一种新的基于路径模糊的软件保护方法以抵抗基于符号执行的逆向分析:利用条件异常代码替换条件跳转指令来隐藏程序的路径分支信息,使用不透明谓词技术引入伪造的路径分支来弥补程序在统计属性上的差异,并对路径模糊技术的强度、弹性和开销进行了分析.实验结果表明路径模糊技术能保护各类路径分支条件,有效减少路径分支信息的泄露,抵抗基于符号执行的逆向分析.     

面向未解释程序的合作验证方法

未解释程序的验证问题通常是不可判定的,但是最近有研究发现,存在一类满足coherence性质的未解释程序,其验证问题是可判定的,并且计算复杂度为PSPACE完全的.在这个结果的基础上,一个针对一般未解释程序验证的基于路径抽象的反例抽象精化（CEGAR）框架被提出,并展现了良好的验证效率.即使如此,对未解释程序的验证工作依然需要多次迭代,特别是利用该方法在针对多个程序验证时,不同的程序之间的验证过程是彼此独立的,存在验证开销巨大的问题.本文发现被验证的程序之间较为相似时,不可行路径的抽象模型可以在不同的程序之间复用.因此,本文提出了一个合作验证的框架,收集在验证过程中不可行路径的抽象模型,并在对新程序进行验证时,用已保存的抽象模型对程序进行精化,提前删减一些已验证的程序路径,从而提高验证效率.此外,本文通过对验证过程中的状态信息进行精简,对现有的基于状态等价的路径抽象方法进行优化,以进一步提升其泛化能力.本文对合作验证的框架以及路径抽象的优化方法进行了实现,并在两个具有代表性的程序集上分别取得了2.70x和1.49x的加速.     

标签约束可达查询的高效处理方法

基于标签约束的可达性查询s→\\-Lt用于回答给定图中顶点s到顶点t是否存在路径标签属于L的有向路径.针对现有方法索引构建时间长、索引规模大、查询效率低的问题,首先基于k个点构建双向路径标签索引,并提出相应的优化措施减小索引规模,以此来加速可达查询的处理速度.由于其索引没有完全覆盖可达查询,虽然索引规模小,但仍然无法避免查询过程中的图遍历操作.为此,进一步提出覆盖所有可达信息的双向路径标签索引,基于该索引,查询处理时可以完全避免图上的遍历操作.最后,基于多个真实数据集进行测试,实验结果从索引大小、索引构建时间和查询响应时间方面验证了所提方法相对现有方法具有索引规模小、索引时间短且查询响应快的优势.     

渐进式约束扩展的机械臂运动规划算法

为了保证冗余机械臂带约束运动规划时的路径连续性,针对目前的直接插值和连续插值方法潜在的约束失效和路径失效问题,提出渐进式约束扩展的快速搜索随机树算法（PCE-RRT）。该算法在进行搜索树扩展时引入了一种渐进式约束扩展方法,该方法使用带有最近点信息的逆运动学计算策略,可以在保证任务约束的情况下迭代缩短最近点和扩展点的距离,让每一次扩展都能够保证搜索树的约束性和连续性。PCE-RRT可以使最终生成的搜索树很好地贴合于约束流形子空间,且树上任意两个相连节点都能满足连续条件。通过仿真实验对算法进行验证,实验结果表明该算法能够为机械臂带约束运动规划问题提供同时满足约束性和连续性条件的路径解。     

基于模型检测的多轮FR协议验证

随着网络的大规模应用,越来越多的协议在并发环境中执行,时间也成为协议中一个重要因素.本文对公平交换协议Franklin/Reiter协议加入了时间因素,用时间自动机对其建模,并用自动验证工具UPPAAL验证了单轮协议的性质.重点验证了并发环境中多轮协议的执行情况,最后给出了协议在多轮情况下正常执行需满足的条件.     

一种新的电子商务协议分析方法

基于卿-周逻辑给出了一些新的逻辑推理规则,并提出了一种扩展的通信有限状态自动机,用于分析电子商务协议的安全性质.该方法可描述协议参与者的行为与知识,且无需人为地引入初始假设.对扩展模型抽象并修改后,还可验证其它一些与加密、签名消息无关的性质.利用该方法分析了匿名可恢复的公平交换协议,发现其满足有效性、公平性、可追究性,但不满足匿名性,并用UPPAAL验证了协议的公平性、活性与时效性等.     

用于克服程序状态空间爆炸的条件化预处理

提出用条件化技术对程序进行预处理的方案，以克服软件模型检测中状态空间爆炸问题。以程序性质公式中蕴涵式的前件作为约束条件，通过对程序符号化执行后各控制点的路径条件进行逻辑推理，删除那些对性质检测无关的语句。理论分析和实验结果表明，条件化可以有效缩减程序状态空间，并且满足软件模型检测对状态缩减的安全性要求。     

基于CPN模型的REST服务架构标准特征验证方法研究

当前REST服务架构广泛应用于大规模、可扩展的分布式Web系统中,若应用REST服务架构时不遵循其标准特征,则可能导致基于REST服务架构的Web系统出现性能下降、可扩展性低等问题。因此,实现基于REST服务架构的Web系统前,需要对该系统设计是否满足REST服务架构标准特征进行验证,以提升基于REST服务架构的Web系统的研发质量。提出一种基于CPN模型的REST服务架构标准特征验证方法,即对REST服务架构的五个标准特征约束进行CPN建模,并使用模型状态空间执行路径同步匹配的验证方法,以应用系统的CPN模型和标准特征约束的CPN模型为基础,对模型状态空间中的各自执行路径进行同步匹配,若路径可同步执行完毕,则说明该应用系统满足该REST标准特征约束。以基于REST服务架构的课程管理Web系统为例,验证上述方法的可用性和有效性。实验结果表明,本文所提验证方法可以有效确认基于REST服务架构的Web应用系统设计是否符合REST服务架构的标准特征约束,并在不符合标准特征约束时提供直观、可行的执行数据,便于后续完成应用系统设计缺陷定位及修正。     

路径测试中基本路径集的自动生成

路径测试是一种重要的白盒测试技术,具有较高的故障覆盖率。基本路径集覆盖了程序中所有语句和分支,该文测试了基本路径集中的路径,在测试资源有限的情况下得到较好的测试效果,并提出了基于图的深度优先搜索的基本路径集的生成方法,该算法采用的生成子路径的方法可以有效地减少路径生成过程中的搜索过程,提高路径生成的效率。 关键词：     

Predicting program execution times by analyzing static and dynamic program paths

This paper describes a method to predict guaranteed and tight deterministic execution time bounds of a sequential program. The basic prediction technique is a static analysis based on simple timing schema for source-level language constructs, which gives accurate predictions in many cases. Using powerful user-provided information, dynamic path analysis refines looser predictions by eliminating infeasible paths and decomposing the possible execution behaviors in a pathwise manner. Overall prediction cost is scalable with respect to desired precision, controlling the amount of information provided. We introduce a formal path model for dynamic path analysis, where user execution information is represented by a set of program paths. With a well-defined practical high-level interface language, user information can be used in an easy and efficient way. We also introduce a method to verify given user information with known program verification techniques. Initial experiments with a timing tool show that safe and tight predictions are possible for a wide range of programs. The tool can also provide predictions for interesting subsets of program executions.This research was supported in part by the Office of Naval Research under grant number N00014-89-J-1040.     

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

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

基于延后策略的动态多路径分析方法

多路径分析是弥补传统动态分析方法的不足、对可执行程序全面分析的重要方法之一.现有多路径方法主要采用随机构造或者根据路径条件构造输入进行路径触发,这两者均存在路径分析不全面和缺乏针对性的问题.文中通过对路径条件分析,确定了检测条件的基本组成元素,提出了弱控制依赖和路径引用集的概念和计算规则,并以此为基础提出一种延后策略的多路径分析方法.在程序分析过程中,对特定的程序检测点和检测点条件,有针对性地进行路径筛选,从语义上进行路径表达式简化,在保证检测点可达和检测表达式具有相同构造形式的前提下,简化检测表达式,减少分析路径的数量.对7款恶意软件的分析实验结果表明,该方法提高了分析效率和准确性.     

基于运行特征监控的代码复用攻击防御

针对代码复用的攻击与防御已成为网络安全领域研究的热点,但当前的防御方法普遍存在防御类型单一、易被绕过等问题.为此,提出一种基于运行特征监控的代码复用攻击防御方法RCMon.该方法在分析代码复用攻击实现原理的基础上定义了描述程序正常运行过程的运行特征模型RCMod,并提出了验证程序当前运行状态是否满足RCMod约束规则的安全验证自动机模型.实现中,通过直接向目标程序中植入监控代码,使程序运行到监控节点时自动陷入,并由Hypervisor实现运行特征库的构建和安全验证.实验结果表明,RCMon能够有效地防御已知的绝大部分代码复用攻击,平均性能开销约为22%.     

CPBPV: a constraint-programming framework for bounded program verification

This paper studies how to verify the conformity of a program with its specification and proposes a novel constraint-programming framework for bounded program verification (CPBPV). The CPBPV framework uses constraint stores to represent both the specification and the program and explores execution paths of bounded length nondeterministically. The CPBPV framework detects non-conformities and provides counter examples when a path of bounded length that refutes some properties exists. The input program is partially correct under the boundness restrictions, if each constraint store so produced implies the post-condition. CPBPV does not explore spurious execution paths, as it incrementally prunes execution paths early by detecting that the constraint store is not consistent. CPBPV uses the rich language of constraint programming to express the constraint store. Finally, CPBPV is parameterized with a list of solvers which are tried in sequence, starting with the least expensive and less general. Experimental results often produce orders of magnitude improvements over earlier approaches, running times being often independent of the size of the variable domains. Moreover, CPBPV was able to detect subtle errors in some programs for which other frameworks based on bounded model checking have failed.     

Dynamic method for software test data generation

Test data generation in program testing is the process of identifying a set of test data which satisfies a given testing criterion. Existing pathwise test data generators proceed by selecting program paths that satisfy the selected criterion and then generating program inputs for these paths. One of the problems with this approach is that unfeasible paths are often selected; as a result, significant computational effort can be wasted in analysing those paths. In this paper, an approach to test data generation, referred to as a dynamic approach for test data generation, is presented. In this approach, the path selection stage is eliminated. Test data are derived based on the actual execution of the program under test and function minimization methods. The approach starts by executing a program for an arbitrary program input. During program execution for each executed branch, a search procedure decides whether the execution should continue through the current branch or an alternative branch should be taken. If an undesirable execution flow is observed at the current branch, then a real-valued function is associated with this branch, and function minimization search algorithms are used to locate values of input variables automatically, which will change the flow of execution at this branch.     

基于程序运行形式化分析的软件故障监控技术

关键软件要求极高的可靠性和安全性,然而当前的技术途径尚不能完全消除软件故障——软件测试不能保证软件正确性,模型检查等形式化验证技术也存在着诸多局限。文章提出了基于监控程序运行途径来捕获软件故障和验证程序性质正确性,构建了基于程序运行形式化分析的软件故障监控（SFMRFA）模型,在监控逻辑表达、程序插桩、multi-agent设计等关键技术的基础上开发计算机辅助工具来监控、分析和引导程序执行,使软件运行当中可测、可控,避免软件失效。