一种嵌入式二进制软件测试用例优先排序方法

摘要

本发明涉及一种嵌入式二进制软件测试用例优先排序方法，传统的测试用例排序技术按照一定的排序策略对测试用例进行执行优先权的排序，检测效率较低。本发明所提出的基于函数依赖的测试用例排序技术将测试用例之间的依赖性作为重要因素进行考虑，首先根据二进制程序分析出函数之间的调用关系，然后根据该关系生成相应的邻接矩阵，依据动态规划思想进一步生成可达矩阵。最后由可达矩阵对测试用例进行排序。本发明解决了传统测试用例排序技术对于测试用例依赖方面缺乏考虑的局限性，生成更符合程序实际运行情况的测试用例排序。

说明书

技术领域

本发明属于软件测试技术领域，涉及一种嵌入式二进制软件测试用例优先排序方法。

背景技术

 软件测试对于软件开发而言有着极其重要的作用，但与此同时软件测试也是软件开发中一个高成本的过程。测试人员利用测试用例对软件进行性能测试，但穷举测试对于有限的开发周期而言是不切实际的方法。测试人员通过软件测试工具可以为一个软件生成大量的测试用例，对于软件测试而言最大的障碍在于如何从庞大的测试用例集中筛选出符合该软件的测试用例子集使得该子集能够降低软件测试的开销，并能提供良好的测试覆盖率。

国内外的研究学者针对测试用例的选择和使用问题做了大量的研究工作，测试用例约简技术（ Test case reduction）和测试用例排序技术（ Test case prioritization）就是其中相对成熟的技术，这两种技术通过较小的代价解决了测试用例的筛选问题。

但这两种技术均存在一定的局限性，主要体现在：TCR技术对于约简后的测试用例集，可能将一些原本能够检测软件漏洞的测试用例当做冗余测试用例进行删除。由此得到的越简集在错误检测能力上要有所下降，失去了检测出潜在漏洞的可能。传统TCP技术注重于按照某一种排序策略对测试用例进行排序，而忽略了测试用例之间存在的约束关系，使得最终的排序结果不符合实际的函数调用，虽然在一定程度提高检错的效率但仍然有提升的空间。

发明内容

本发明针对现有技术的不足，提供了一种嵌入式二进制软件测试用例优先排序方法。

本发明方法具体包括以下步骤：

步骤1）分析嵌入式二进制软件函数调用关系，定位函数表，获得函数描述信息，并对特殊函数调用情况进行处理，最终得到全部函数调用关系。

步骤2）分析函数调用关系，构建函数调用关系邻接矩阵，并通过矩阵运算生成可达矩阵，得到函数间的依赖关系。

步骤3）根据函数间依赖关系，利用可达矩阵，对函数测试的先后顺序进行排序，并依该顺序对测试用例进行排序。

本发明的有益效果：

1.该技术考虑到软件系统中各个模块之间的关系，测试用例所涉及到的模块越多就越容易发现软件系统中所存在的错误，因此基于函数依赖的测试用例排序能够更高效地发现软件系统中存在的错误。

2.该技术通过优先排序，优先执行权限高的测试用例，因此在测试时间有限的情况下，仍然能对重要的测试用例优先执行，从而削减软件测试成本。

附图说明

图1为分析二进制文件函数调用的具体流程。

图2为生成可达矩阵的具体流程。

具体实施方式

本发明是对测试用例集的一种优化处理方法，旨在通过该技术使得处理后的测试用例在对软件进行检测时，能够起到高效检错，削减测试成本的作用。

本发明包括如下步骤：

步骤1）分析嵌入式二进制软件函数调用关系，定位函数表，获得函数描述信息，并对特殊函数调用情况进行处理，最终得到全部函数调用关系。

步骤2）分析函数调用关系，构建函数调用关系邻接矩阵，并通过矩阵运算生成可达矩阵，得到函数间的依赖关系。

步骤3）根据函数间依赖关系，利用可达矩阵，对函数测试的先后顺序进行排序，并依该顺序对测试用例进行排序。

其中步骤1）具体包括如下步骤：

 1）对二进制文件进行结构分析,定位符号表，并从中提取函数的信息，建立函数信息表。

2）定位到主函数入口地址，从主函数入口地址开始遍历程序中的每条指令,并按照顺序从每个函数入口地址处的指令开始进行深度优先搜索,搜集函数的调用信息。

 3）对特殊函数调用情况进行处理,特殊函数包括系统函数和跳转指令；对于编译后以“_”开头的系统函数，则直接过滤掉；对于跳转指令，如果跳转目地地址是函数的地址，按照普通函数调用指令处理，否则视为语句跳转指令。

其中步骤2）具体包括如下步骤：

1）利用二进制程序分析后的结果，分析函数之间的是否存在调用关系，并依此调用关系构建出N×N的邻接矩阵。

2）利用该邻接矩阵，依次遍历矩阵中的每一个元素，根据其下标i和j判断对应的函数是否存在调用关系。

3）若存在调用关系则遍历下一个元素；若不存在调用关系则考虑通过未被包含进路径的其他结点来判断是否存在通路。

4）循环遍历所有的元素，最终得到对应的可达矩阵。

其中步骤3）包括如下步骤：

1）根据最终生成的邻接矩阵，计算每一行中包含1的个数，并按递减的顺序进行排序，此时可以得到函数调用的复杂关系。

2）查看需要进行程序检测的测试用例，分析每一个测试用例经过的函数。

3）根据第1步的排序结果对测试用例进行排序，给包含最多调用关系的测试用例赋予最高的优先执行权，以此类推最终得到测试用例排序结果。

以下结合附图对本发明作进一步说明。

二进制文件的本身是按照一定的格式来存储的，具体如在Linux平台下以elf文件格式进行存储，elf文件格式如表1所示，包括文件头、程序头表、段头表、符号表、字符串表、重定位表、动态链接表等，从文件的不同段中我们可以获取一些与函数调用有关的信息。

 表1                                               

分析二进制文件中的函数调用关系主要思想如下：遍历程序中的每个函数，从每个函数起始地址处的指令开始进行深度优先扫描。处理函数的每一条指令，当指令为调用子程序的指令时，计算出具体的跳转目标地址，将跳转地址与函数信息表中的函数的起始地址进行匹配，获取被调用函数的信息，并将其函数标识编号id入队，深度优先遍历完该函数后，将队中元素出队，对其进行递归遍历。在将函数标识id入队时，并不需检查是否重复入队。主要流程如图1所示。

根据分析后所得的函数调用关系生成对应的邻接矩阵，然后利用动态规划的思想生成可达矩阵。具体步骤如下：依次遍历邻接矩阵中的每一个元素，根据对应元素是否为1进行不同的处理。若为1则表示该元素对应的函数之间存在调用关系，遍历下一个元素即可；若为0则表示该元素对应的函数之间不存在调用关系，此时考虑通过其他的结点的情况下是否存在调用关系，若存在调用关系则也将该元素置为1否则就置为0，循环迭代直到所有元素均被遍历。此时所得的矩阵就是最终的可达矩阵。主要流程如图2所示。

根据可达矩阵每一行中元素1的个数对所有的函数进行递减排序，函数中包含的1越多则表示该函数与其他函数之间的依赖性越高，因此可以根据测试用例是否包含该函数进行执行优先权的排序，最终就可以得到测试用例的优先排序结果。

本发明将全部测试用例当成一个整体，更全面的考虑到了函数之间的调用关系，因此排序后的测试用例在检错时更符合程序的实际运行情况，从而提高测试用例的检错效率。