相关路径静态分析中协同式逆向推理方法 被引量：5

1

作者 郭曦 王盼 《软件学报》 EI CSCD 北大核心 2015年第1期1-13,共13页

相关路径生成,是程序动态分析中的一种重要方法.通过对目标执行路径的获取和分析来生成与其相关的近邻执行路径,在程序行为特征分析、编译优化和调试等研究方向有重要的作用.现有的方法主要通过改变路径节点序列来生成近邻的路径集合,... 相关路径生成,是程序动态分析中的一种重要方法.通过对目标执行路径的获取和分析来生成与其相关的近邻执行路径,在程序行为特征分析、编译优化和调试等研究方向有重要的作用.现有的方法主要通过改变路径节点序列来生成近邻的路径集合,由于缺乏关键节点的路径引导信息,导致生成大量冗余或者无效的路径集合.提出采用协同式逆向分析的近邻路径生成方法,针对目标路径的后置条件,采用逆向符号分析方法产生程序各个基本块的前置条件作为执行路径的引导信息.同时,通过调整距离因子k的取值,可以有针对性地生成与目标路径的编辑距离不超过k的近邻路径集合.实验结果表明:与现有方法相比,该方法在准确性和效率方面有明显的优势. 展开更多

关键词 逆向分析 近邻路径 最弱前置条件 符号执行

下载PDF 职称材料

基于k近邻最弱前置条件的程序多路径验证方法 被引量：5

2

作者 郭曦 王盼 +1 位作者 王建勇 张焕国 《计算机学报》 EI CSCD 北大核心 2015年第11期2203-2214,共12页

程序多路径验证方法是对软件性质进行发掘的重要方法之一,现有的验证方法主要通过求解路径条件或者自动构造不同的输入来触发生成不同的路径,从而分析程序中潜在的安全问题,但存在对路径条件不加选择地进行多路径扩展而生成缺乏针对性... 程序多路径验证方法是对软件性质进行发掘的重要方法之一,现有的验证方法主要通过求解路径条件或者自动构造不同的输入来触发生成不同的路径,从而分析程序中潜在的安全问题,但存在对路径条件不加选择地进行多路径扩展而生成缺乏针对性的路径的问题,另外由于路径条件过长而难以求解也限制了它的使用范围.该文提出基于k近邻最弱前置条件的程序多路径验证方法,该方法通过后向符号分析对程序调用图的构建过程进行改进,同时对指定的程序检测点生成最弱前置条件,并以该最弱前置条件为引导信息使用符号执行的方法在保证检测点可达的前提下有针对性地生成对程序性质进行验证的精简路径集合.实验结果表明,该方法可以提高程序验证的精度和准确性,并减少误报. 展开更多

关键词 程序验证 静态分析 最弱前置条件 符号执行 控制流图

下载PDF 职称材料

基于克雷格插值的反例理解方法 被引量：2

3

作者 黄宏涛 黄少滨 +1 位作者 陈志远 张涛 《吉林大学学报（理学版）》 CAS CSCD 北大核心 2013年第1期94-100,共7页

针对错误原因提取效率低的问题,提出一种利用克雷格插值对模型检测器产生的反例进行自动理解的方法.该方法首先从反例失效状态出发推导出其最弱前置条件,然后对初始状态与反例最弱前置条件进行不一致分析,能在线性时间内提取克雷格插值... 针对错误原因提取效率低的问题,提出一种利用克雷格插值对模型检测器产生的反例进行自动理解的方法.该方法首先从反例失效状态出发推导出其最弱前置条件,然后对初始状态与反例最弱前置条件进行不一致分析,能在线性时间内提取克雷格插值作为反例失效原因,产生的插值能直接用于定位错误事件.实验结果表明,基于克雷格插值的反例理解方法能显著提高反例理解速度,提高软件的调试效率,从而提升软件的可靠性和质量. 展开更多

关键词 模型检测 反例 反例理解 最弱前置条件 克雷格插值

下载PDF 职称材料

由规格说明到排序算法 被引量：2

4

作者 钟珞 《计算机技术与发展》 1992年第3期1-6,共6页

本文给出由程序的规格说明变换出程序的一种系统化方法的新概念.对规格说明进行不同的变换可得到不同的不变式形式.这些不变式通过计算最弱前置条件给出了多种相应算法的框架。本文以若干著名的排序算法例示了以上的概念和方法。

关键词 规格说明 变换 最弱前置条件 排序算法

下载PDF 职称材料

一种基于最弱前置条件的软件错误定位算法 被引量：2

5

作者 李雅 黄少滨 +2 位作者 李艳梅 迟荣华 郎大鹏 《电子学报》 EI CAS CSCD 北大核心 2019年第1期25-32,共8页

错误定位是软件调试中非常耗时费力的活动之一,自动错误定位技术可以有效地提高调试效率,降低调试成本.基于最弱前置条件的错误定位技术,首先计算出程序需要满足的最弱前置条件,并为其构造错误分析图;然后在错误分析图上依照失败测试用... 错误定位是软件调试中非常耗时费力的活动之一,自动错误定位技术可以有效地提高调试效率,降低调试成本.基于最弱前置条件的错误定位技术,首先计算出程序需要满足的最弱前置条件,并为其构造错误分析图;然后在错误分析图上依照失败测试用例进行初始化标记;最后限定分析图的输入和输出,自顶向下再次对其进行标记,找到冲突的结点,从而进行错误定位.实验结果表明,相对于其它方法,文中提出的方法能有效地提高程序错误定位的效率,使得调试人员只需检查更少的语句即可找到出错的位置. 展开更多

关键词 调试 错误定位 最弱前置条件 反例理解

下载PDF 职称材料

基于最弱前置条件的静态分析误报消除技术 被引量：1

6

作者 陈杰 《计算机工程与应用》 CSCD 2012年第33期1-4,33,共5页

针对程序静态分析技术误报过多的问题,提出一种基于最弱前置条件的静态分析误报消除方法。根据不同的软件安全性质,从目标状态出发,以需求驱动的方式得到过程起始位置的最弱前置条件,判断该条件公式的可满足性来消除误报。将该方法实例... 针对程序静态分析技术误报过多的问题,提出一种基于最弱前置条件的静态分析误报消除方法。根据不同的软件安全性质,从目标状态出发,以需求驱动的方式得到过程起始位置的最弱前置条件,判断该条件公式的可满足性来消除误报。将该方法实例化来消除静态分析工具检测数组访问越界和空指针解引用的误报,实验结果表明该方法是有效且实用的。 展开更多

关键词 静态分析 误报消除 最弱前置条件 数组访问越界 空指针解引用

下载PDF 职称材料

基于动态协同双向映射的相似执行路径生成方法 被引量：1

7

作者 郭曦 王盼 《电子学报》 EI CAS CSCD 北大核心 2014年第11期2168-2173,共6页

相似执行路径的生成是代码分析和检测的基础性工作之一,现有的方法通常以程序的行为序列或结构为分析对象,通过改变关键谓词的取值等方法来进行分析,但由于缺乏必要的引导信息导致生成的相似路径的有效性较低,另外由于路径的谓词集合较... 相似执行路径的生成是代码分析和检测的基础性工作之一,现有的方法通常以程序的行为序列或结构为分析对象,通过改变关键谓词的取值等方法来进行分析,但由于缺乏必要的引导信息导致生成的相似路径的有效性较低,另外由于路径的谓词集合较长而难以求解也降低了分析的精度.提出基于动态协同双向映射的分析方法,通过对程序控制流图的表示形式进行扩展,结合后向符号分析的方法生成候选路径的最弱前置条件,并以此为引导信息使用编辑距离的方法通过改变距离因子的取值来生成有针对性的相似路径集合.实验结果表明,与现有的方法相比,该方法的准确性和效率有明显的优势. 展开更多

关键词 静态分析 控制流图 最弱前置条件 相似执行路径

下载PDF 职称材料

一种基于符号执行的测试用例生成方法

8

作者 郑华利 刘钊远 田野 《计算机与数字工程》 2019年第9期2327-2331,共5页

针对符号执行中存在的路径爆炸问题,提出一种冗余路径删除方法,该方法利用Hoare逻辑中的后置条件引导符号执行以生成有效的测试用例。首先利用最弱前置条件来计算已探索的路径,然后通过后置条件引导符号执行以识别程序中多个共享的路径... 针对符号执行中存在的路径爆炸问题,提出一种冗余路径删除方法,该方法利用Hoare逻辑中的后置条件引导符号执行以生成有效的测试用例。首先利用最弱前置条件来计算已探索的路径,然后通过后置条件引导符号执行以识别程序中多个共享的路径后缀,并在测试用例生成时进行消除。最后通过对多个基准程序进行实验,结果表明论文方法在一定程度上能够减少程序的路径探索数目和执行时间,削弱了符号执行中的路径爆炸问题。 展开更多

关键词 符号执行 路径爆炸 后置条件 最弱前置条件

下载PDF 职称材料

基于最弱前置条件的程序正确性分析

9

作者 郭莎莎 侯春燕 王劲松 《高技术通讯》 EI CAS 北大核心 2019年第6期556-563,共8页

随着软件的不断更新迭代,软件正确性检测的必要性愈加凸显,软件正确性检测的处理时间直接决定软件的维护成本。动态测试的断言编写和静态分析的符号执行均针对程序正确性进行优化完善,但分析结果易出现路径缺失甚至错误无法识别等问题... 随着软件的不断更新迭代,软件正确性检测的必要性愈加凸显,软件正确性检测的处理时间直接决定软件的维护成本。动态测试的断言编写和静态分析的符号执行均针对程序正确性进行优化完善,但分析结果易出现路径缺失甚至错误无法识别等问题。现有验证方法在路径扩展时易生成较多无用路径,且针对性不强,因此有必要研究一种更为可靠的方案。本文采用最弱前置条件对软件可行性加以分析,对程序执行语义正确建模,使用程序切片技术预处理程序代码,并根据层级结构存储节点及其子程序。实验结果表明,该方法可以有效减小静态分析对程序状态抽象操作带来的验证精度损耗,且能够遍历求解出程序的所有可能路径,并通过分组标出条件表达式的结论真假值,以此验证路径正确性,同时可对高复杂的程序代码进行有效的正确性分析。 展开更多

关键词 程序正确性 最弱前置条件 静态分析 路径扩展 程序切片技术

下载PDF 职称材料

面向二进制程序的空指针解引用错误的检测方法

10

作者 傅玉 邓艺 +3 位作者 孙晓山 程亮 张阳 冯登国 《计算机学报》 EI CSCD 北大核心 2018年第3期574-587,共14页

空指针解引用是C/C++程序中常见的一类程序错误,它可让攻击者旁路安全机制或窥探操作系统敏感信息,一直是计算机安全领域的重要研究课题之一.目前已有很多(自动)分析工具对其进行检测,然而它们都在源代码层面上进行检测.大量的商业软件... 空指针解引用是C/C++程序中常见的一类程序错误,它可让攻击者旁路安全机制或窥探操作系统敏感信息,一直是计算机安全领域的重要研究课题之一.目前已有很多(自动)分析工具对其进行检测,然而它们都在源代码层面上进行检测.大量的商业软件不公开源代码,因此基于源代码的工具无法对这类软件中空指针解引用进行检测.此外,一些空指针解引用无法在源代码层面检测,因为这些缺陷由编译选项和编译优化不当引入.因此进行基于二进制的空指针解引用检测非常必要.基于二进制的空指针解引用检测的一个优势是可以包含库函数的代码,而基于源代码的分析通常采用人工构造的库函数摘要,从而影响检测的准确性和召回率.该文首次提出并实现了面向二进制程序的空指针解引用静态检测工具NPtrChecker,直接接受二进制程序进行分析,并给出代码中出现空指针的来源和解引用的位置以及对应的路径条件.在二进制上进行空指针解引用检测的一个重要难点是二进制程序中缺少指针类型、结构体类型等相关数据类型信息.如果缺乏这类信息,会导致分析结果的准确率大大降低.但是从二进制中恢复类型、数据结构本身是非常困难的问题.针对上述问题,我们提出了一种内存模型,区分来自同一数据结构的不同域的引用,实现了针对空指针解引用检测的域敏感指针分析.为了进一步提高分析的准确率,文章在此基础上设计实现了一套基于函数摘要的上下文敏感的数据流分析算法.此外,工具采用最弱前置条件对数据流分析结果进行验证,检查从指针来源到解引用点的路径条件是否可以被满足,以降低误报率.我们应用NPtrChecker分析了SPEC2000中的11个程序,总共报告了37个可疑空指针解引用,通过人工确认,其中22个是真实的程序错误.相对于Saturn报告的92个,仅13个为真;LUKE报告的3个 展开更多

关键词 空指针解引用检测 静态程序分析 二进制程序分析 最弱前置条件 数据流分析

下载PDF 职称材料

一种基于单条程序执行路径的错误定位方法

11

作者 周艺 易秋萍 +1 位作者 刘剑 淮晓永 《计算机系统应用》 2014年第10期112-118,共7页

当程序在测试中发生错误时,将形成一条错误的程序执行路径,程序员将会花费很多精力去检测程序代码和定位最终的程序错误.提出一种基于单条程序执行路径的错误定位方法,该方法通过对程序进行反向执行,计算出多个最弱前置条件及其相对应... 当程序在测试中发生错误时,将形成一条错误的程序执行路径,程序员将会花费很多精力去检测程序代码和定位最终的程序错误.提出一种基于单条程序执行路径的错误定位方法,该方法通过对程序进行反向执行,计算出多个最弱前置条件及其相对应的疑似错误语句集,并生成错误定位树,来辅助程序员进行快速错误定位.对西门子测试数据集进行的实验表明了该方法具有良好的效果. 展开更多

关键词 错误定位 最弱前置条件 可满足性理论 动态分析 自动化测试

下载PDF 职称材料

量子最弱自由前置条件的交换性及其性质 被引量：4

12

作者 雷红轩 席政军 李永明 《软件学报》 EI CSCD 北大核心 2013年第5期933-941,共9页

首先给出了量子最弱自由前置条件(weakest liberal precondition,简称wlp)wlp(A,B,C)-可交换的定义,研究了wlp(A,B,C)-可交换的充分必要条件;其次,得到了wlp不是良好的谓词转换,验证了wlp是比量子最弱前置条件(weakest precondition,简... 首先给出了量子最弱自由前置条件(weakest liberal precondition,简称wlp)wlp(A,B,C)-可交换的定义,研究了wlp(A,B,C)-可交换的充分必要条件;其次,得到了wlp不是良好的谓词转换,验证了wlp是比量子最弱前置条件(weakest precondition,简称wp)更弱的谓词转换,揭示了wlp和wp的本质区别;最后证明了wlp的序列合成、并行合成和块结构等性质. 展开更多

关键词 量子谓词 超算子 量子最弱自由前置条件 交换

下载PDF 职称材料