嵌入式软件路径覆盖测试用例生成仿真

陈金萍,赵成喜

(大连海洋大学应用技术学院,辽宁 大连 116300)

1 引言

现阶段,嵌入式系统飞速发展,已涉及国防、医疗、商业等多个行业。例如常用的移动终端、机顶盒等均为嵌入式技术的产物。随着该系统的深入应用,软件规模与复杂程度也不断增加。软件设计过程中,难以做到十全十美,一方面,由于开发人员疏忽或技术问题,导致软件达不到理想要求;再加上嵌入式系统自身空间有限,还附加上高可靠性等要求,加大了软件缺陷检测的难度,使其成为系统中的定时炸弹,对系统安全带来严重威胁。例如,因软件故障造成火箭发射失败,欧洲不得不推迟航天计划;由于机票系统出现软件程序错误,美国造成百万美元经济损失。因此,对软件进行测试、及时修正缺陷,保证系统运行稳定十分必要。

惠子青[1]等人构建了动态加权神经网络模型测试软件。综合分析软件多样性特征,使用神经网络建立加权组合模型;根据故障发生过程进行软件缺陷预测。除此之外,还有学者通过建立高阶Markov模型生成软件测试用例。针对马尔科夫模型测试用例生成不稳定的缺陷,进行改进,利用快速轮盘赌的二分查找方法生成测试用例。

上述两种测试方案是在目标机上进行的,因软件运行过程中具有不可视性,测试人员不能实时掌握代码覆盖情况,随机性较强。此外,测试用例生成会占用系统CPU利用率,对系统运行造成负担。为此,本文提出嵌入式软件路径覆盖测试用例生成算法。路径覆盖表示设置多个测试用例,将程序中全部可行路径都覆盖。该方法是评估软件性能的重要手段,但是程序中若出现多个循环,路径数据会大幅度增加。因此,本文首先对软件中污点数据进行检测,避免覆盖不可行路径,再引入遗传算法使路径覆盖得到简化,经过遗传变异操作输出最终测试用例。

2 污点数据检测

分析待测试软件的过程中,要着重注意程序中的数据计算和传递,解决任意节点中可能存在的污点数据[2,3]。这些数据有可能是恶意添加或是随机生成的,如果不删除,会生成太多无用路径,影响测试效率。

1)软件数据分类

内部数据:是软件自身存在的,与软件结构有关,在软件测试过程中,通常不将这些数据当作恶意数据。即便这些数据存在一定缺陷,通过修复后,不会对测试造成影响。

外部数据:此种数据一般会改变软件执行路径,存在很强的不稳定性,对这些数据分析具有一定难度,污点数据通常会存在其中。

2)污点数据确定

污点数据具有威胁的原因是它能以信息流的方式进行传播,当软件定义某变量a为污点数据时,存在a中的信息,经过赋值等操作将数值传递给变量b,此种情况就是信息流传播[4],是导致程序崩溃的主要原因。污点数据传播示意图如图1所示。

图1 污点数据传播示意图

由于数据来源不同,污点数据被分为下述两种:

网络数据:因网络结构复杂,某些恶意攻击者通过发送不良数据对主机进行攻击[5],导致污点数据生成;

I/O数据:此种数据包含键盘数据输入以及文件读取生成的数据。

信息流传播过程中,具体传播方式可通过下述公式描述

(1)

公式中,b和c代表污点数据,经过传播a和d也变为污点数据。

3)流向分析

分析污点数据流向即可找出不可行的覆盖路径,进而加快模型求解速度。具体分析过程如下:

第一步:设置两个变量,包括污点数据和可信数据;

第二步:将污点数据通过文件取读方式传递给a,此时a变为污点数据;

步骤三:如果传递数据为可信,则返回值同样可信;

步骤四:若使用污点数据,则危险函数[6]被调用,此时污点数据会控制函数的具体执行情况。

通过以上分析,将可能存在污点数据的路径筛选出来,作为不可行路径,减少路径冗余。

3 基于路径覆盖的软件测试用例生成

要想高效生成测试用例,需要对目标路径分组,使所有个体均被有效使用。路径相似度的高低能够反映出测试数据的利用效率,所以结合路径相似度完成路径分组,将具有高度相似性的归为同一组。完成分组后,可将任意一组用例生成问题转换为初始问题的子问题,再通过遗传算法求解,获取子种群最优解。在进化期间,当已知某路径的测试数据,储存此信息与路径的同时删除被覆盖路径,这样会降低CPU利用率[7]。

3.1 分组策略

假设Pi与Pj代表两个目标路径,其中i,j=1,2,…,n,且Pi的节点表示为ni1,ni2,…,nirj,Pj的节点则是nj1,nj2,…,njrj。将nj1当作起点进行对比,直至找出首个Pi与Pj不一致的节点njk,此时Pi与Pj存在的相同节点数量是same(Pi,Pj)=k-1。反之,若Pi与Pj全部节点均相同,则同类节点数量描述为same(Pi,Pj)=ri=rj。Pi与Pj存在的相似度s(Pi,Pj)表达式为

(2)

由此可知,s(Pi,Pj)∈[0,1],该值越大,同类节点数量越多。假设阈值设置为s0∈(0,1),从众多目标路径中选取一条路径Pi,获取该路径与其它路径之间的相似度,如果高于或等于s0,则将符合该要求的路径放在一组,记作{g1};再从路径集合中去除{g1},针对剩余路径,通过上述方式获得{g2}。反复以上操作,直至全部路径均被划分在某组中。

3.2 路径覆盖测试用例生成数据模型构建

因{gi}中随机两个路径的相似度不能低于s0,因此,ϖ需符合s(Pi1,P(ϖ))≥s0,则第i个优化子问题表示为

(3)

因此可以得出,在第i个优化问题中包括的目标函数数量少于整体优化问题,计算起来更为方便。此外,由于相同子问题的目标路径相似度较高,所以可通过一个子种群完成优化,缩小可行域,使搜索范围变小,提高测试效率。

根据上述分析结果,可将路径覆盖测试用例生成问题变换为多个具有较少目标的子问题,构建的数据模型如下

(4)

此模型一共包括I个子问题,任意一个子问题均包括多个优化问题。利用该模型即可将全部路径覆盖问题,变换成I个子问题进行求解,这样可以降低求解难度。

3.3 基于遗传算法的模型求解

对于上述路径覆盖测试用例生成模型,本文利用遗传算法对变换成I个的子问题求解。具体过程如下。

1)确定编码方式

通过遗传算法对模型求解时,需对个体进行编码[8],此处个体指程序输入。若程序输入是整数,则利用二进制编码,若为实数,则使用实数编码方式。

2)适应值构建

已知ϖij的适应值,则子问题中包括ni个目标函数,能够得出ni个目标函数在个体ϖij处的函数值fi1(ϖij),fi2(ϖij),…,fini(ϖij)。

若ϖij可对{gi}中某条路径覆盖,则ϖij即为需要的测试用例。即只要存在某个k,确保fik(ϖij)=0,则

min{fi1(ϖij),fi2(ϖij),…,fini(ϖij)}=fik(ϖij)=0

(5)

可通过min{fi1(ϖij),fi2(ϖij),…,fini(ϖij)}判定ϖij是否符合{gi}的覆盖需求。

另外,针对第i个问题还存在一个约束条件是s(Pi1,P(ϖij))≥s0,通过惩罚函数[9]对该约束条件进行处理。针对个体ϖij,若符合此条件,说明ϖij为可行解,反之不可行,必须对其惩罚。s(Pi1,P(ϖij))与s0之间的差距越大,表明越不能满足约束条件,应加大惩罚力度。因此,建立惩罚函数α(s0-s(Pi1,P(ϖij))),α表示某正数,本文取值为0.2。

经过上述分析,个体ϖij具有的适应值公式如下

fiti(ϖij)=min{fi1(ϖij),fi2(ϖij),…,fini(ϖij)}

+αmax{max(s0-s(Pi1,P(ϖij)),0)}

(6)

利用上述公式完成对ϖij的评价,得出的fiti(ϖij)值越小,表明ϖij覆盖某路径的可能性越高,将其代入到下一代种群内继续操作。

3)终止条件确定

针对任意一个优化问题,终止条件均包括两种:第一种是此问题含有的目标函数数量等于零,此时优化完成,获取覆盖组中全部路径的测试用例;第二种则是算法进化到设置的代数,这时即使没有完成任务,也会停止操作。

路径覆盖测试用例生成的整个过程为:

步骤一:设计参数与个体编码,确定交叉与变异概率;

步骤二:将目标路径划分为不同小组,对某组{gi}生成个体种群M(Pi),并将其当作输入矢量;

步骤三:适应值获取,计算所有个体的适应值,该值越小,与最优解越接近,被选入下一轮的几率越高;

步骤四:设置终止条件,如果终止转到步骤六;

步骤五:如果不符合终止要求,在相同种群内进行遗传操作,主要包含交叉、变异等[10],并转回步骤三;

步骤六:输出最终结果,即为测试用例生成结果。

4 仿真数据分析与研究

本次仿真选取了较为典型的电话程序、三角形分类程序以及某银行业务程序,三种系统软件作为测试目标。将从用例生成数量、充分性判定、用例生成时间以及CPU利用率多个方面对所提算法性能进行仿真分析。

实验一:电话机系统

1)用例生成数量分析

以电话机待机状态作为初始测试状态,经过各类操作直到挂机为止,停止测试。在此期间本文方法、动态加权神经网络、高阶马尔科夫模型三种算法生成的测试用例数量如图2所示。

图2 不同方法测试用例生成数量

由图2可知,动态加权神经网络与高阶马尔科夫模型算法生成的用例数量多、波动较大,表明生成过程随机,可控性较差,会生成太多无用用例。所提方法生成数量相对较少,整个测试过程表现得较为稳定,可避免用例冗余。这是因为该方法在用例生成前对程序中的污点数据进行分析,删除不可覆盖的路径,提高测试效率。

2)充分性分析

在软件测试中,停止时间尤为重要,也就是对测试充分性的判定。为衡量测试是否充分,需找出一个平衡点来阻止测试过程。Discriminant值一般指2个事件似然率期望值,通过计算该值即可获取事件之间的相似度,表示为D′(U′,T′),U′与T′分别代表软件使用模型与测试模型。该值与零越接近,代表两模型越逼近,如果该值低于设定阈值时,则认为测试充分,可停止,其计算公式如下

(7)

式中,x1,x2,…,xn代表测试序列。三种算法的Discriminant值计算结果如图3所示。

图3 不同算法Discriminant比较

分析图3得出,在多次实验中本文方法的Discriminant值较为平稳,且始终接近或等于0。表明测试停止时间刚好,充分性较强,能够更好地应用在软件测试中,避免早熟现象。

实验二:三角形分类程序

对于分类程序不同的数据区间,将获取所有可行路径当作结束条件。实验过程中,实时记录每次寻找路径的进化代数,求取平均值。三种方法仿真结果如表1所示。

表1 不同方法平均迭代次数表

由表1得出,随着输入信息区间的扩大,对于三种行分类问题,三种算法找出目标路径的平均进化代数也随着增加。这是由于数据量较大,搜索难度加大导致的。但本文方法的平均进化代数小,说明该方法总是能以较快速度完成三角形分类测试。数据量越大这种优势越明显。证明了基于遗传算法路径覆盖的软件测试用例生成效率高,可快速实现目标测试。

3)银行业务程序

由于银行业务系统在线人数较多,共包含20个分行,每个分行下还有多个网点,业务量大,基本上每天都会产生业务处理峰值。因此必须对该系统的软件功能进行测试,确保每笔业务都能顺利操作。针对该系统而言,软件的CPU利用率最为关键,实验利用上述三种方法对其CPU利用率进行测试,测试结果如图4所示。

图4 不同方法测试CPU利用情况

通过分析图4可知,利用三种方法对银行业务软件的CPU利用率进行测试,由于测试环境相同,软件自身CPU利用率保持不变。本文方法测试出的CPU利用率最低,这是因为该方法在测试过程中占用系统内存较少,而其它两种方法内存占用率很高。当银行业务出现峰值时,会影响系统正常运行,因此其它两种方法不适合在业务办理高峰时段进行测试,容易造成系统崩溃。

5 结论

软件测试在系统开发过程中发挥着重要作用,通过测试可及时发现软件错误,提高可信度。基于此,本文提出一种嵌入式软件路径覆盖测试用例生成算法。通过对污点数据的检测,排除不可行路径,再利用遗传算法建立路径覆盖的数学模型,经过模型求解,输出测试用例。实验证明,该方法提高测试效率,不占用系统内存,具有较强的可控性。但本文利用遗传算法求解效果还有待提高,遗传策略与参数设置问题还需进一步优化。