基于抽象解释的非函数依赖不变量的检测方法

不变量的检测是提高软件质量的一种有效方法.针对传统静态检测方法可能带来无效的不变量、缺失不变量等缺陷,文中提出一种以抽象解释理论为基础的非函数依赖不变量的静态检测方法.首先利用词法语法分析得到抽象语法树,然后将抽象语法树转化成抽象域图,接着对抽象域图进行抽象执行得到程序中可执行的路径,最后依据定义的非函数依赖不变量表现形式对可执行路径分析得到程序中潜在的非函数依赖不变量.同时通过一个 C 程序为例对该方法进行验证说明     

C程序控制流程模型的提取技术与实现

控制流图描述了函数执行时可能采取的执行路径。绝大多数静态分析工具都在抽象语法树之上生成控制流图并据此对程序的运行行为进行分析。在模型检测过程中,提取正确的控制流图是构建系统模型的关键。在分析C程序的抽象语法树和控制结构的基础上,设计并实现了程序控制流图提取的算法,并分析了算法的正确性。基于提取的控制流程,可对C程序的某些性质进行模型检验。     

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

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

基于抽象解释的可执行代码值范围分析

阐述可执行代码抽象存储空间模型的概念并给出程序运行时刻环境抽象表示技术。通过抽象解释静态逼近程序不动点语义的理论保证二进制代码数据流分析的正确性以及可计算性。基于抽象解释和单调数据流框架提出一种自动分析可执行代码变量取值范围的方法及自动获取程序循环最大迭代次数和不可执行路径,并给出数据流分析实例。     

基于过程蓝图的静态代码控制流生成算法

对非结构化的程序代码进行理解分析对代码理解能力不强的测试人员存在一定难度。为了减轻静态代码分析的难度,本文首先采用程序切片算法将程序进行预处理,利用过程蓝图对代码进行可视化操作形成程序的中间表示形式抽象语法树。然后对其构造和特点进行研究,提出抽象语法树的遍历算法。通过该算法得到程序的控制流图。最后,利用控制流图和控制树,对静态代码进行高效的控制流分析,监测这些代码是否满足安全性、可靠性等方面的指标,为检测和处理软件缺陷降低成本。     

基于JavaCC的抽象语法树的构建与实现

抽象语法树(abstract syntax tree,AST)作为程序一种重要的中间表示形式,在代码分析领域中有着广泛的应用。如何针对Java程序生成其抽象语法树是在进行代码静态分析前必不可少的工作。分析抽象语法树的构建算法,通过JavaCC解析工具完成对Java文件抽象语法树的构建,该方法可实现代码树状形式的可视化呈现。     

一种C程序内存访问缺陷自动化检测方法研究

符号执行是目前较为行之有效的软件缺陷自动化检测方法,计算代价昂贵与程序执行路径爆炸是两个影响其性能的关键问题.提出了一种针对C语言程序内存访问缺陷的符号执行检测方法,该方法可通过自动化构造的测试用例发现程序内部的内存访问缺陷,如缓冲区溢出、跨界访问和指针异常等.使用符号跟踪缓冲区长度的方法,一方面减少了符号变量的数量,另一方面由此精确抽象C语言库中字符串操作函数的行为,解决了符号执行过程间函数调用的步进问题;使用动态切片的方法,裁减路径探索过程中的冗余路径,从而解决在程序内部路径搜索时发生的路径爆炸问题.实验表明,提供的检测方法不但可行,而且验证代价较小,具有较强的实用性.     

基于GCC的符号执行工具

静态分析和符号执行是发现源代码缺陷和提高源代码质量的两种有效方式。然而,这两种技术都面临各自的问题,静态分析误报率较高和符号执行一直面临着路径爆炸难题。为了减少静态分析和符号执行的这些限制,本文构建了一个称为ABARZER-SE的工具,它是第一个基于GCC结合符号执行和静态分析的源代码检测工具。ABAZER-SE由两个阶段组成,第一阶段是通过符号执行获取可行性路径,第二阶段应用静态分析技术对可行性路径分析找到源代码中缺陷。实验结果表明该工具具有可行性、有效性和可扩展性。     

软件漏洞静态检测模型及检测框架

软件漏洞静态分析是信息安全领域的重点研究方向,如何描述漏洞及判别漏洞是漏洞静态分析的核心问题。提出了一种用于描述和判别漏洞的漏洞静态检测模型。首先对软件漏洞的属性特征进行形式化定义,并对多种软件漏洞和其判定规则进行形式化描述;其次,针对传统的路径分析存在的状态空间爆炸问题,提出了一个新的程序中间表示——漏洞可执行路径集,以压缩程序状态空间。在该模型的基础上,设计了一个基于漏洞可执行路径集的软件漏洞静态检测框架,利用定义的漏洞语法规则求解漏洞可执行路径集上的漏洞相关节点集,利用漏洞判定规则对漏洞相关节点集进行判别得出漏洞报告。实验分析验证了该漏洞检测模型的正确性和可行性。     

基于形式源级转换的可执行规格说明技术

本文提出一种新的可执行规格说明实现技术,它利用源级转换思想把规格说明直接转换成程序设计语言程序,且这种源级转换基于形式定义的规则与基于规范抽象语法树,该技术及相应的支持系统支持速成原型技术,具有支持系统开发工作量小、易保证正确性、开发代价低且开发周期短等特点,能较好地达到速成原型的效果。     

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

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

程序状态条件合并中变量隐式关联分析方法

程序分析的主要目标是对程序的性质进行研究,符号执行作为目前主流的分析方法在生成高效的测试用例集或提高路径覆盖率等方面发挥着重要的作用,其中路径条件表达式的提取以及约束求解是路径分析过程中的关键步骤.现有的路径分析方法普遍存在约束求解效率不高而导致的路径覆盖率较低的问题.由于符号执行引擎所采用的搜索策略不尽相同,在符号执行分析过程中存在状态合并的过程,该抽象过程可能导致产生不正确的测试用例.以提高路径分析效率为目标,提出一种高效的程序分析方法：首先对传统的符号执行树的表示方法进行改进,提取不同路径共享的符号表达式和路径约束条件以提高符号执行过程中状态合并的效率,然后采用隐式关联分析方法,产生逆向分析中的依赖条件集合,并给出基于依赖条件重构的算法以提高路径覆盖率.实验结果表明：相对于传统的状态合并以及符号执行方法,该方法有更为高效的状态合并效率以及更高的路径约束条件分析精度.     

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

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

基于语法树和JavaCC的程序题自动评分系统

为了提高程序题自动评分的准确性,及解决传统评分方法无法从语法结构和语义角度衡量错误的学生程序与正确答案之间的相似度,提出了一种基于抽象语法树匹配的程序题自动评分方法。文中以JavaCC技术为核心,首先通过词法分析、语法分析和语义分析生成错误列表和抽象语法树的中间表示,然后通过语法树切片匹配得分,最后和错误列表结合给出评分结果。文中详细论述了各个模块的设计方法,着重讨论了抽象语法树生成并匹配的细节,设计并实现了一个传统方法与语义分析结合的C＋＋程序题自动评分系统。通过对实际考试的结果进行实验,进而验证了该系统的实用性与有效性。     

采用图遍历算法的服务端请求伪造漏洞检测

针对基于PHP语言开发的Web应用系统,提出了一种基于图遍历算法的服务端请求伪造漏洞检测和利用方法。通过构建抽象语法树,获取每个文件的数据流信息,进而利用数据流中的传递依赖关系构造全局的代码属性图,使用图遍历算法对生成的代码属性图进行污点分析,得到污点变量的代码传递依赖路径图,最后使用约束求解的方法对路径图中的经过函数信息进行漏洞检测并生成可利用的攻击向量。实验结果表明,这种检测方式相较于传统的静态审计方法能够很好地发现服务端请求伪造漏洞,并能够自动化生成可绕过的攻击向量。     

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

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

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

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

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

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

可执行规范技术

本文简要介绍了可执行规范技术。可执行规范在软件工程过程的早期就能发现错误，随着形式化规范研究的发展，它越来越受到重视。ＸＹＺ系统是唐稚松教授提出并领导实现的。该系统的核心是序列化时序逻辑语言（ＴＴＬ ＸＹＺ／Ｅ语言），该语言能在同一框架之中表示动态涵义（可执行命令）与静态语义（前后断言规范），并可混合在一程序中出现。用这种混合出现的程序，就能表示出由完全抽象的规范到可有效执行的程序之间平滑过渡的过     

基于JavaCC的抽象语法树生成错误处理技术研究

随着C++语言标准的不断演进,词法语法解析工具如JavaCC等对于很多扩充的新特性以及复杂的语法结构不能做到完全支持,这可能会导致抽象语法树生成错误且不完整;针对这一问题,提出一个针对抽象语法树生成错误的处理框架;首先,通过对JavaCC的扩充,实现一套可以解析C++语言的词法语法分析器,生成抽象语法树并记录报错行;其次,根据报错行寻找所在函数区间即不支持或不匹配的语法片段;最后,通过注释函数区间的方式来跳过不支持或不匹配的语法片段进行错误处理并迭代生成抽象语法树;实验结果表明,对抽象语法树生成进行错误处理后可以更全面的分析代码,抽象语法树完成率上升37.8%,分析行数提高3.9倍。