符号执行研究综述 被引量：19

1

作者 叶志斌 严波 《计算机科学》 CSCD 北大核心 2018年第B06期28-35,共8页

符号执行作为一种重要的程序分析方法,可以为程序测试提供高覆盖率的测试用例,以触发深层的程序错误。首先,介绍了经典符号执行方法的原理;然后,阐述了基于符号执行发展形成的混合测试、执行生成测试和选择性符号执行方法,同时,对制约... 符号执行作为一种重要的程序分析方法,可以为程序测试提供高覆盖率的测试用例,以触发深层的程序错误。首先,介绍了经典符号执行方法的原理;然后,阐述了基于符号执行发展形成的混合测试、执行生成测试和选择性符号执行方法,同时,对制约符号执行方法在程序分析中的主要因素进行了分析,并讨论了缓解这些问题和提高符号执行可行性的主要方法;随后,介绍了当前主流的符号执行分析工具,并比较分析了其优缺点;最后,总结并讨论了符号执行的未来发展方向。 展开更多

关键词 符号执行 混合测试 执行生成测试 路径爆炸 约束求解

下载PDF 职称材料

函数摘要在Concolic测试方法中的应用 被引量：6

2

作者 安靖 钟金鑫 +1 位作者 魏更宇 杨义先 《北京邮电大学学报》 EI CAS CSCD 北大核心 2012年第1期24-27,共4页

在函数摘要的基础上提出了一种新的Concolic测试方法.该方法利用外部调用的函数摘要来避免多次测试外部调用引起的路径爆炸问题.在对外部调用进行Concolic测试后,将其返回结果和路径条件作为函数摘要.测试过程中调用同一外部调用时,该... 在函数摘要的基础上提出了一种新的Concolic测试方法.该方法利用外部调用的函数摘要来避免多次测试外部调用引起的路径爆炸问题.在对外部调用进行Concolic测试后,将其返回结果和路径条件作为函数摘要.测试过程中调用同一外部调用时,该方法用函数摘要替代展开测试,避免了传统Concolic测试过程对外部调用重复测试的问题,缓解了调用次数增多和调用深度增加引起的路径爆炸问题.原型系统的实验结果表明,随着测试对象中函数数量的增加,传统Concolic测试路径数量可能出现指数型增长,而该方法中测试路径数量基本保持线性增长. 展开更多

关键词 Concolic测试 符号执行 函数摘要 路径爆炸

原文传递

基于改进烟花算法的室内服务机器人路径规划 被引量：4

3

作者 王晓燕 牛晶 刘挺 《现代电子技术》 2022年第12期182-186,共5页

针对传统烟花算法进行室内服务机器人路径规划存在的随机性较大及易陷入局部最优等问题,文中提出一种在全局静态已知环境下的改进烟花算法(IFWA)。首先,在传统烟花算法(FWA)的基础上,IFWA将当前路径节点与上一路径点的位置信息作为适用... 针对传统烟花算法进行室内服务机器人路径规划存在的随机性较大及易陷入局部最优等问题,文中提出一种在全局静态已知环境下的改进烟花算法(IFWA)。首先,在传统烟花算法(FWA)的基础上,IFWA将当前路径节点与上一路径点的位置信息作为适用度函数,引入惩罚函数筛除落在障碍物区域的火花,降低子代火花的随机性,进一步减少路径代价;然后,针对FWA路径规划过程存在的局部最优问题,将非零因子β引入爆炸半径中,避免最优烟火花爆炸半径为0;最后,引入“八叉树”避障策略,以解决烟花算法路径规划中出现的路径穿过障碍物问题。通过Matlab进行IFWA、FWA与蚁群算法的对比仿真实验,结果验证了IFWA的可行性和优越性。该算法可避免出现随机性大及局部最优问题,能够有效提高室内服务机器人路径规划的效率。 展开更多

关键词 路径规划 改进烟花算法 室内服务机器人 惩罚函数 爆炸半径 避障策略 八叉树

下载PDF 职称材料

符号执行中的循环依赖分析方法 被引量：2

4

作者 刘杰 曹琰 +1 位作者 魏强 彭建山 《计算机工程》 CAS CSCD 2012年第22期24-27,33,共5页

符号执行方法处理循环时存在路径爆炸的问题。为此,提出一种基于归纳变量的循环依赖分析方法。通过识别循环归纳变量及符号表达式,结合边界约束条件生成可达归纳变量分支的路径约束,并采用符号化映射方法分析嵌套循环归纳变量依赖问题,... 符号执行方法处理循环时存在路径爆炸的问题。为此,提出一种基于归纳变量的循环依赖分析方法。通过识别循环归纳变量及符号表达式,结合边界约束条件生成可达归纳变量分支的路径约束,并采用符号化映射方法分析嵌套循环归纳变量依赖问题,从而在不展开循环的情况下生成覆盖归纳变量分支的测试用例。对开源工具Libxml2进行实验,该方法能发现其中2个while循环所引发的数组访问越界错误。 展开更多

关键词 符号执行 路径爆炸 归纳变量 循环依赖 约束求解 嵌套循环

下载PDF 职称材料

基于输入约束的符号执行优化 被引量：2

5

作者 汪孙律 林渝淇 +1 位作者 杨秋松 李明树 《通信学报》 EI CSCD 北大核心 2019年第3期19-27,共9页

为了解决符号执行中路径爆炸、新路径发现率低等问题,提出了基于输入约束的符号执行(ICBSE)优化框架。该方法通过分析程序代码自动提取3类输入约束,随后使用这些约束引导符号执行更关注于核心功能代码。在KLEE中实现了上述优化框架,并对... 为了解决符号执行中路径爆炸、新路径发现率低等问题,提出了基于输入约束的符号执行(ICBSE)优化框架。该方法通过分析程序代码自动提取3类输入约束,随后使用这些约束引导符号执行更关注于核心功能代码。在KLEE中实现了上述优化框架,并对coreutils、binutils、grep、patch、diff这5个程序套件中的7个常用程序做了检测。ICBSE发现了7个之前未知的缺陷(KLEE只检测其中3个)。同时,ICBSE将指令行覆盖率、分支覆盖率分别提升了约20%,时间开销降低了约15%。 展开更多

关键词 符号执行 输入约束 路径爆炸 缺陷查找

下载PDF 职称材料

恶意代码的符号执行树分析方法 被引量：1

6

作者 钟金鑫 魏更宇 +1 位作者 安靖 杨义先 《重庆大学学报（自然科学版）》 EI CAS CSCD 北大核心 2012年第2期65-70,共6页

在恶意代码分析中,动态监测虚拟环境中的恶意代码行为是一种常用的方法。但是,由于可执行的路径分支众多,极易产生路径爆炸问题,造成某些可执行路径无法被覆盖,严重影响分析的全面性。为了解决恶意代码分析中路径爆炸问题,提出了一种基... 在恶意代码分析中,动态监测虚拟环境中的恶意代码行为是一种常用的方法。但是,由于可执行的路径分支众多,极易产生路径爆炸问题,造成某些可执行路径无法被覆盖,严重影响分析的全面性。为了解决恶意代码分析中路径爆炸问题,提出了一种基于符号执行树的恶意代码分析方法。通过构造符号执行树,引入汇聚节点,对恶意代码的执行路径进行约束求解,减少分析路径,从而缓解路径爆炸的影响,提高分析的全面性。恶意代码样本分析的实验表明,该方法能够有效地提升分析效率,同时拥有较小的时间复杂度。 展开更多

关键词 符号执行 路径爆炸 恶意代码分析 汇聚节点 二进制程序分析

下载PDF 职称材料

基于选择机制的实体间最信任路径发现方法

7

作者 周国强 曾庆凯 《北京工业大学学报》 CAS CSCD 北大核心 2010年第5期679-684,共6页

提出了一种基于选择机制的实体间最信任路径发现算法.该算法采用动态规划思想,同时利用乘关系特点和信息反馈,在计算信任路径过程中可过滤掉无关路径,解决了恶意实体干扰问题、信任路径数目爆炸问题以及回路问题.仿真结果显示,本算法能... 提出了一种基于选择机制的实体间最信任路径发现算法.该算法采用动态规划思想,同时利用乘关系特点和信息反馈,在计算信任路径过程中可过滤掉无关路径,解决了恶意实体干扰问题、信任路径数目爆炸问题以及回路问题.仿真结果显示,本算法能有效隔离恶意实体,同时具有通信量小,收敛性好的优点. 展开更多

关键词 信任网络 信任路径 路径爆炸 恶意实体

下载PDF 职称材料

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

8

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

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

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

下载PDF 职称材料

一种针对格式文件的符号执行优化方法

9

作者 汪孙律 杨秋松 李明树 《电子学报》 EI CAS CSCD 北大核心 2020年第12期2417-2424,共8页

为了解决符号执行中路径爆炸、新路径发现率低等问题,提出了针对文件格式数据块约束的符号执行分析方法(FFCBSE,File Format Constraint Based Symbolic Execution)优化框架.文件格式信息的缺失会影响符号执行的效率以及测试用例生成,... 为了解决符号执行中路径爆炸、新路径发现率低等问题,提出了针对文件格式数据块约束的符号执行分析方法(FFCBSE,File Format Constraint Based Symbolic Execution)优化框架.文件格式信息的缺失会影响符号执行的效率以及测试用例生成,该方法通过分析程序代码自动分析程序读取的格式文件数据块之间的依赖关系并建立相关约束,随后使用这些约束引导符号执行更关注于核心功能代码区域.在KLEE中实现了上述优化框架,并对Tcpdump、Readelf、Elfdump、File、Zlib等7个常用文件处理程序做了检测.和KLEE以及DASE相比,FFCBSE发现了13个之前未知的缺陷,在指令覆盖率和分支覆盖率有10%~225%不同程度的提升. 展开更多

关键词 符号执行 文件格式 路径爆炸 缺陷查找

下载PDF 职称材料

矿井瓦斯/空气预混气体爆燃的激光纹影测试系统设计 被引量：16

10

作者 胡洋 尹尚先 +2 位作者 ARNTZENJ.Bj?rn 朱建芳 李雪冰 《光学精密工程》 EI CAS CSCD 北大核心 2019年第5期1045-1051,共7页

为了准确地获取矿井瓦斯/空气预混气体爆燃流场的内部微观结构信息,能够从基元反应层面认识爆燃流场的演化过程以及惰性介质阻燃剂抑制作用的机理,在已经建成的中尺度激波管道上继续搭建高速激光纹影测试系统,结合实验室几何空间约束条... 为了准确地获取矿井瓦斯/空气预混气体爆燃流场的内部微观结构信息,能够从基元反应层面认识爆燃流场的演化过程以及惰性介质阻燃剂抑制作用的机理,在已经建成的中尺度激波管道上继续搭建高速激光纹影测试系统,结合实验室几何空间约束条件,提出纹影测试系统'Z'字型光路的设计方案。以激光纹影系统代替传统的压力火焰测试系统,将爆燃流场的研究重心从宏观的单一点源信息向微观的多重结构信息转化。研究表明,在60,100,125,212ms时火焰阵面的化学反应变强,伴随着产生了冲击波,在75ms左右火焰发生断裂,该点处的压力下降,325ms火焰阵面扫过该测点以后,压力迅速下降。该结果为寻求预混气体爆燃高速摄影、压力火焰速度测试手段之外的方法提供了新的研究思路。 展开更多

关键词 激光纹影 激波管 光路设计 瓦斯爆燃 阻燃抑爆

下载PDF 职称材料

基于精英反向学习的烟花爆炸式免疫遗传算法 被引量：6

11

作者 韩江 闵杰 《合肥工业大学学报（自然科学版）》 CAS 北大核心 2020年第4期433-437,共5页

针对移动机器人的路径规划中存在的避障和路径搜索等问题,文章提出了一种基于精英反向学习(elite opposition-based learning,EOBL)的烟花爆炸式免疫遗传算法(fireworks explosive immune genetic algorithm,FEIGA)。在FEIGA算法的基础... 针对移动机器人的路径规划中存在的避障和路径搜索等问题,文章提出了一种基于精英反向学习(elite opposition-based learning,EOBL)的烟花爆炸式免疫遗传算法(fireworks explosive immune genetic algorithm,FEIGA)。在FEIGA算法的基础上,引入EOBL机制扩大全局搜索,即在进行爆炸操作时,对当前最佳个体执行反向学习,生成其搜索边界内的反向搜索种群,引导算法向包含全局最优的解空间逼近,以提高算法的平衡和探索能力。函数优化结果表明,与其他算法相比,EOBL-FEIGA收敛速度更快,搜索精度更高,有效地解决了免疫遗传算法(immune genetic algorithm,IGA)存在的局部搜索能力弱、易早熟收敛的问题,克服了FEIGA算法易陷入局部最优解的不足。路径规划结果表明,在不同的复杂环境下,EOBL-FEIGA能实现机器人的最优路径搜索和避障,有较强的搜索能力和鲁棒性。 展开更多

关键词 移动机器人 路径规划 精英反向学习(EOBL) 烟花爆炸算法 免疫遗传算法(IGA)

下载PDF 职称材料

煤矿井下避灾路径规划研究综述 被引量：4

12

作者 于丹 颜伟 《中国煤炭》 2022年第2期40-47,共8页

路径规划是煤矿井下灾害事故的热门研究之一,能够有效避免重大人员伤亡。针对矿井瓦斯爆炸、火灾、水灾3种煤矿井下灾害事故,从不同因素对巷道通行能力的影响、最优避灾路径规划模型构建以及求解避灾路径的算法3方面进行了总结研究。结... 路径规划是煤矿井下灾害事故的热门研究之一,能够有效避免重大人员伤亡。针对矿井瓦斯爆炸、火灾、水灾3种煤矿井下灾害事故,从不同因素对巷道通行能力的影响、最优避灾路径规划模型构建以及求解避灾路径的算法3方面进行了总结研究。结果表明:巷道类型、坡度、局部障碍物数目、风速风向及CO等有毒有害气体、高温、烟雾浓度、水位高度等为影响巷道通行能力的主要因素;最优避灾路径规划模型构建主要以路径权值最短为原则;求解避灾路径所用的算法以Dijkstra算法为主。最后以矿井水灾为背景,使用Dijkstra算法实例分析了五沟煤矿1035工作面的最优逃生路径。 展开更多

关键词 避灾路径 瓦斯爆炸 火灾事故 水灾事故 避灾路径规划 DIJKSTRA算法

下载PDF 职称材料

基于外卖配送路径优化的问题研究 被引量：4

13

作者 高文强 姜冠杰 《信息通信》 2018年第5期20-22,共3页

外卖配送是当今一种新型行业,只有对配送路径的各方面进行优化,才能提高配送效率,降低成本,保证配送安全,增加收益。文章以食品外卖配送为例,研究分析如何基于烟花算法解决在安全性下外卖配送路径优化的问题,算法流程涉及应用C语言进行... 外卖配送是当今一种新型行业,只有对配送路径的各方面进行优化,才能提高配送效率,降低成本,保证配送安全,增加收益。文章以食品外卖配送为例,研究分析如何基于烟花算法解决在安全性下外卖配送路径优化的问题,算法流程涉及应用C语言进行了编程运算。论文首先介绍了外卖配送路径优化的问题的产生,然后详细的介绍了烟花算法的原理,包括其爆炸和变异的原理。论文最后以C语言程序的结果为基础,对烟花算法中一些主要参数进行了分析,有效地解决了算法中存在的不足。从而实现了基于烟花算法对外卖配送路径优化问题的求解和编程。 展开更多

关键词 外卖配送 路径优化问题 烟花算法 粒子群最优化 路径优化 高斯变异火花

下载PDF 职称材料

基于CPN的程序测试用例生成方法的研究

14

作者 郑文艳 《计算机工程与应用》 CSCD 2014年第11期39-45,共7页

采用成熟的建模仿真工具CPN tools不仅仅对程序设计语言的三种基本结构进行了建模,而且对并行程序中的并行结构也进行了建模和仿真。在不针对某些具体语言比如C语言的情况下,提出了生成测试用例的新方法,该方法对具备三种基本结构特性... 采用成熟的建模仿真工具CPN tools不仅仅对程序设计语言的三种基本结构进行了建模,而且对并行程序中的并行结构也进行了建模和仿真。在不针对某些具体语言比如C语言的情况下,提出了生成测试用例的新方法,该方法对具备三种基本结构特性的所有程序都具有普遍适用性。对具有并行结构的程序通过化简寻找测试路径。最后在生成测试用例之后,又利用CPN tools对所获得的测试用例进行选择和评价,最终确定合适的测试用例,不仅能够保证获取的测试路径是完整的而且是最优的。 展开更多

关键词 程序测试 颜色PETRI网 强连通图 测试路径 并行结构 状态空间 状态空间爆炸

下载PDF 职称材料