基于分支混淆算法的符号执行技术

符号执行是静态分析中的一项常用技术,数组元素混淆问题是限制符号执行本身性能的关键因素之一。通过分析数组混淆实质,提出了一种分支混淆算法,利用边混淆边符号执行的策略,可以处理较为复杂的数组问题。该策略使用实时的约束求解,及时地剪除不可达的混淆分支。结合符号执行和约束求解技术,开发了基于分支混淆算法的工具原型ASym。初步实验表明,利用分支混淆算法可以处理具有分支结构的数组混淆问题,避免延迟替换出现的数组语义误差,且在很大程度上缩减了分支数量,提高执行效率。     

基于结点间距离统计的无向无权图同构判别

按照同构图的定义判断两个图是否同构,最坏情况下其时间复杂度是O(N!),当结点数N比较大时,计算速度非常慢,针对该问题,提出一种通过统计结点间距离和按照距离分层,计算同层结点间的关联边数以及关联结点数来研究图中各结点差异的算法,该算法可以给出两个图的结点间可能的对应关系.如果两个图的结点距离数组及对应结点的层结点关联数组不能一一对应,其时间复杂度仅为O(N4),否则,根据结点间可能的对应关系,避免遍历所有结点序号的交换,计算量可以成倍地下降.     

基于分布函数的WCET快速估计

在实时软件系统中,软件时间性能的分析与评估技术是一个重要的课题,然而随着CPU的结构越来越复杂,采用传统的模拟底层硬件执行的方法越来越困难。而基于分布函数的最坏执行时间(Worst Case Execution Time,WCET)估计方法从概率角度出发,可以绕过复杂的底层硬件建模,估计程序的最坏执行时间。首先对TI TMS320C6713 DSP汇编代码进行基本块的划分,以基本块为结点构建程序流图;然后用贝塔分布模拟每条指令的运行时间并采用改进的计划评审技术(Program Evaluation and Review Technique,PERT)确定贝塔分布相关参数,指令叠加后用正态分布模拟每个基本块的执行时间;最后利用基于路径的方法得到整个程序的最坏执行时间。实验结果表明此方法是可行的和合理的。     

基于STN的计划执行过程时间冲突检测与消解*

计划执行过程中,各种不确定因素常常引起时间约束的违背.为维护计划的时间一致性,利用STN表示时间约束,分析了由于活动的提前或延迟导致的两种时间冲突,给出了冲突判定定理,在此基础上通过松弛冲突路径上某些约束来消解冲突;最后通过一个计划案例的仿真验证了本方法能够有效检测和消解执行过程中的时间冲突.     

面向热点代码的路径搜索方法研究

程序测试研究表明代码安全缺陷聚集于热点代码。提出一种面向热点代码的路径搜索方法,在程序CFG(controlflow graph)图上搜索分支语句与热点代码之间的最短路径,采用符号执行方法生成路径约束判断其可达性,结合多热点搜索优化策略进一步消除不可达子路径,从而快速生成能够覆盖热点代码的测试用例。实验结果表明,与DFS(depth-firstsearch)和BFS(best-first search)方法相比,在达到相同热点代码覆盖率情形下,该方法能够有效减少测试路径并缩短搜索时间。     

数组越界的故障模型及其检测方法研究

数组越界是C程序中的常见故障，该类故障可能造成系统的崩溃。首先针对常见的数组越界故障进行了分析，提出了检测数组越界的判定准则，建立了故障模型。根据该故障模型，采用程序控制流图和路径条件，并结合静态分析思想，给出了可有效地检测出程序中存在的数组越界故障的方法。最后通过实例分析了该方法的应用过程。     

基于AOV网的抽象工作流模型

针对项目管理中的工作流控制需求,提出一个基于顶点活动(AOV)网的抽象工作流模型。给出该模型的形式化定义以及各结点的时序关系,阐述工作流的设计与执行规则,包括分支设计规则和回路设计规则,定义工作流图分支结构中汇聚结点的时序同步规则,并给出一个优化的回路检测方法。实例应用结果证明了该模型的有效性。     

一种覆盖测试中路径集的自动生成方法

覆盖测试是软件测试中的重要方法,路径覆盖测试中路径集的自动生成能提高测试效率。该文提出了一种描述程序分支情况的分支关系图,给出了基于分支关系图的路径集自动生成算法,实验证明了该方法的正确性,能有效地求出程序路径集。     

一种覆盖测试中路径集的自动生成方法

覆盖测试是软件测试中的重要方法,路径覆盖测试中路径集的自动生成能提高测试效率。该文提出了一种描述程序分支情况的分支关系图,给出了基于分支关系图的路径集自动生成算法,实验证明了该方法的正确性,能有效地求出程序路径集。     

基于用户导向的异构网络语义预测算法研究

随着异构网络的信息量与日俱增,如何准确地帮助用户获取所需要的信息已成为一个热门问题。相似性搜索在网络搜索中得到了广泛的应用。基于元路径的相似性搜索能更好地表达异构网络所包含的语义。但是现有的大多数该类方法存在路径选择数多导致计算量大的问题。根据用户导向去预测元路径以缓解上述问题成为一个重要的研究方向。这类方法需要用户在搜索的同时提供结果样例作为导向,据此预测与用户搜索相关的元路径。目前,相关研究主要是针对异构网络中的同类型结点。利用图的结构信息建立语义预测算法,计算各候选路径与用户搜索的匹配概率,然后选择概率最大的路径。实验表明,提出的算法能够实现对同类型和不同类型结点间语义的预测,具有较好的性能和有效性。并为如何在多语义环境下获得相似性结果提供了具体的实现方法。     

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

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

3维牙颌模型牙齿分割的路径规划方法

目的 从3维牙颌模型上分割出单颗牙齿是计算机辅助正畸系统的重要步骤。由于3维测量分辨率和网格重建精度的有限性,三角网格牙颌模型上牙龈和牙缝边界往往融合在一起,使得单颗牙齿的自动分割变得极为困难。传统方法容易导致分割线断裂、分支干扰等问题,且手工交互较多,为此提出一种新颖的基于路径规划技术的单颗牙齿自动分割方法。方法 为避免在探测边界时牙龈和牙缝相互干扰,采用牙龈路径和牙缝路径分开规划策略。首先基于离散曲率分析和一种双重路径规划法搜索牙龈分割路径,并基于搜索到的牙龈路径利用图像形态学和B样条拟合技术构建牙弓曲线;然后综合牙龈路径和牙弓曲线的形态特征探测牙龈路径上的牙缝凹点以划界每颗牙齿的牙龈边界轮廓,并通过匹配和搜索牙龈边界轮廓上颊舌侧凹点间的最优路径确定齿间牙缝边界路径;最后细化整个路径以获取每颗牙齿精确的封闭分割轮廓。结果 对不同畸形程度的患者牙颌模型进行分割实验,结果表明,本文方法对于严重畸形的牙齿能够产生正确的分割结果,而且简单快速,整个分割过程基本能够控制在20 s以内。和现有方法相比,本文方法具有较少的人工干预和参数调整,除了在个别牙齿边界较为模糊的位置需要手动调整外,大部分情况都是自动的。结论 提出的路径规划方法具有强大的抗干扰能力,能够有效克服牙缝牙沟等分支干扰以及分割线断裂等问题,最大程度地减少人工干预,适用于各类畸形牙患者模型的牙齿分割。     

基于文件格式信息的改进模糊测试方法

本文针对盲目变异的模糊测试策略带来的效率低下的问题,综合程序控制流图、输入种子样本特征、异常样本发现、模糊测试器路径反馈等信息,提出一种更为有效的种子输入变异策略.本文通过不断监控种子文件在目标程序中的执行路径,并引入污点分析的方法,以建立起新增执行路径的起始语句与种子文件中关键字节的一对多映射关系.最终本文将根据这种映射关系对种子文件中的能够增加路径覆盖的字节进行变异,以期得到更有效率的模糊测试结果.我们的实验表明,增加定向变异之后的模糊测试器在代码覆盖率,以及模糊测试的效率上都有较为显著的提升.     

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

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

相关路径静态分析中协同式逆向推理方法

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

编译器中激进蝴蝶优化方法的研究与实现

编译优化技术的目的是挖掘程序中的优化空间,提高程序编译或运行效率,无效代码删除优化是被广泛使用的编译优化技术之一,它旨在删除程序中不可达的代码,以提升程序的执行效率.许多应用程序的执行路径往往与运行时的输入参数值相关,并且在一些分支路径上与运行时参数值相结合,可能存在无效代码,通过现有的无效代码删除优化,很难做出优化处...     

一种应用于动态污点分析的路径自动生成方法

在对现有动态污点分析平台研究和分析的基础上,提出一种路径自动生成技术。借助二进制静态分析技术获取目标程序的指令序列,以基本块为粒度计算执行覆盖率,在目标程序动态执行中抓取其运行轨迹,由收集到的路径约束条件构造新的路径约束条件,经约束求解生成覆盖其它路径的新的测试用例。借助虚拟化技术实现动态污点分析各用例的并行执行,较大幅度提高污点分析的路径覆盖率和执行效率。     

基于时空A*算法的多AGV无冲突路径规划

物流中心作为快递转运的重要枢纽,其分拣效率在一定程度上影响着快递的配送时间.多台自动导引车(automatic guided vehicle,AGV)协同分拣能够大幅提高作业效率.本文研究了多AGV协同作业场景中的无冲突路径规划问题,在栅格地图建模环境的基础上,提出了基于冲突搜索的两层路径规划架构.冲突搜索与约束添加均...     

基于分支相关性分析的不可达路径检测方法

软件测试中,不可达路径的存在会导致测试资源浪费,有效地检测程序中的不可达路径有助于节约测试资源、提高测试效率.分支相关性的存在是不可达路径产生的主要起因.因此,确定分支的相关性在不可达路径的检测中占据十分重要的地位.提出了一种利用关联分析和数据流分析确定分支相关性的方法,进而实现不可达路径的自动检测.首先,结合静态分析和动态分析,构建反映程序中各分支判断语句静态依赖关系和动态执行信息的数据集;然后,利用关联分析和数据流分析技术确定分支的相关性;最后,根据分支相关性信息检测不可达路径.基于一组基准程序和开源程序,开展不可达路径检测实验.实验结果表明,该方法能够准确地检测出程序中的不可达路径,可以有效地提高软件测试的效率.     

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.