进化测试在嵌入式汇编的嵌套分支结构中的应用

发布时间：2020-05-01 01:05

【摘要】：进化测试是近年来刚刚兴起的测试数据自动生成技术,已在很多实际工程中得到了成功应用。其主要思想是利用进化算法将测试数据的生成问题转化成为进化搜索问题,从而实现测试的自动化。进化测试利用进化算法的全局搜索能力,在具有导向性的适值函数的引导下,能够快速高效的自动生成测试数据。其中适值函数在这当中充当着重要的角色,一个设计良好的适值函数能够为进化搜索提供更好更准确的导向,从而提高进化搜索的效率。在实现进化测试对基于嵌入式汇编程序的应用过程中,首先要面临的问题就是代码的植入问题,由于汇编语言具有多种寻址方式,它的植入方法不像高级语言的植入那么简单,对此本文提出了一种基于汇编的代码植入方案并将其应用到具体实现中。同时在基于汇编语言的嵌入式程序中,分支结构是程序中最主要的控制结构,而其中嵌套的分支结构最为复杂,因此本文将主要针对基于嵌入式汇编中的嵌套分支结构的适值函数的计算进行讨论和实现。在具体的应用过程中将分别从基于传统的适值计算方法、基于分支距离的适值计算方法以及基于分支乐观度的适值计算方法这三种方法来进行实现。通过具体应用发现对于这三种方法,传统的方法在测试输入无法满足各层分支条件的情况下,无法对内层的数据进行有效评价；基于分支距离的适值计算方法则完全忽略了分支之间的控制依赖关系而同样在有些情况下无法正确评价测试数据；而基于分支乐观度的适值计算方法则解决了前面二者所出现的问题,使得适值计算对进化搜索具有更好的导向性。通过实验检验表明,在基于汇编的嵌套分支结构的适值函数计算中基于分支乐观度的适值计算方法确实能够更有效的引导进化搜索,提高搜索效率。
【图文】：

框架结构,测试工具,框架结构

相关的自动化测试工具，本课题组之前也在基于信号处理程序中实现了进化测试的工具，尽管他们之间所面对领域和方向不同，但是这些工具框架还是大体类似的。如图1.1所示为进化测试工具的基本框架。在图中的静态分析模块，首先通过现有的静态分析工具将源代码进行分析得到被测程序的抽象语法树，然后根据需要对该抽象语法树进行遍历(针对不同的程序结构或者测试口标会需要多次遍历)，从遍历过程中获得的静态信息:函数的参数信息(包括参数类型等)，函数/分支依赖信息等将用来生成测试数据，以及完成对测试数据的评价工作，即计算出该测试数据的适值。而适值函数计算所需的程序运行轨迹，以及变量的取值等信息则是通过静态分析之后对程序加以植入所采集的。在动态搜索模块

代码,静态,语法树

静态植入指的是不执行程序，静态扫描代码找出植入点，同时利用静态分析技术得到植入代码，然后将植入代码插入到对应的植入点，完成代码植入，该过程如图2.1所示。在源代码级别，静态植入一般在程序的抽象语法树(AST)上进行，该方法首先需要得到程序的抽象语法树，然后遍历语法树，找出植入点，同时在语法树上分析得到植入代码，然后直接在语法树上以子树的方式插入植入代码的语法树片段，最后将语法树还原成源代码。静态植入在程序实际运行前完成，因此不会产生额外的运行时开销(不包括植入代码运行所需的开销)，同时由于只需要静态扫描程序代码即能实现植入，因此实现起来也是简单易行。
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2009
【分类号】：TP368.1

【参考文献】