一种基于梯度下降算法的蜕变关系生成方法

2020-11-26穆翔宇李苏吉

吉林大学学报（理学版） 2020年6期

穆翔宇, 范钰, 李苏吉,2, 张鹏, 刘磊

(1. 吉林大学计算机科学与技术学院, 长春 130012； 2. 吉林大学口腔医院, 长春 130021)

文献[1]提出的蜕变测试方法解决了传统测试中的Oracle问题. 蜕变测试的思想是根据待测程序中的某些性质, 寻找程序不同输入之间存在的关系以及这些输入对应输出之间存在的关系, 这种输入之间的关系和输出之间的关系称为蜕变关系. 蜕变测试利用蜕变关系在现有成功测试用例的基础上构造新的测试用例, 通过判断这些测试用例对应的输出之间是否满足相应的蜕变关系判定程序中是否存在错误. 目前, 蜕变测试的研究主要分为蜕变测试技术的应用和改进两类, 蜕变测试技术的改进又分为原始测试用例的生成和有效蜕变关系的获取两类.

在蜕变测试技术应用方面, Lindvall等[2]将蜕变测试和基于模型的测试相结合, 开发了自动化的NASA DAT系统测试框架; Sun等[3]设计了一种利于蜕变测试过程规范化的基于XML的语言表示, 并开发了一种支持Web服务应用程序的自动化测试工具MT4WS, 将其应用于Web服务测试中； Yan等[4]针对一个无测试预言的现实世界中科学计算程序提取该程序的蜕变关系, 并证明了蜕变测试探测错误的有效性; 文献[5]对比了错误捕获和蜕变测试在电子表格测试中的故障检测功能, 并发现两者存在互补关系, 因此提倡同时使用； Saha等[6]将蜕变测试运用到强化学习中, 为强化学习的监督分类器测试提供了一种新方法; Nakajima[7]将蜕变测试和机器学习相结合, 提出了一种适用于神经网络学习模型的新蜕变测试方法, 数据集多样性考虑了训练结果对数据集的依赖性, 并提供了一种生成后续测试输入的新方法. 对于测试用例生成, Barus等[8]比较了随机测试和自适应随机测试作为原始测试用例选择策略对蜕变测试有效性的影响, 实验结果表明, 自适应随机测试在提高蜕变测试的有效性方面优于随机测试; Batra等[9]提出了一种使选取原始测试用例对应路径最大差异化的遗传算法; Chen等[10]提出了一种将程序的输入域划分为等价类的思想, 减少了原始测试用例数目, 但错误探测率仍较高; Murphy等[11]为蜕变测试的自动化应用提出了启发式测试预言和Amsterdam框架; Bluemke等[12]开发了一种蜕变测试的工具, 使蜕变测试的研究更简便. 对于有效蜕变关系的获取, Just等[13]研究表明, 根据系统组件推出的蜕变关系在错误探测方面通常优于从整个系统得到的蜕变关系; Liu等[14]提出了一种通过组合现有的蜕变关系构建新蜕变关系的方法, 验证了组合蜕变关系具有更高的错误探测效率和成本效益; Segura等[15]为探测可变性分析工具中的错误, 提出了一种基于蜕变关系集合的迭代蜕变测试方法; Zhang等[16]为解决面向对象软件测试中方法序列的Oracle问题, 提出了一种基于代数规范的面向对象软件测试构建蜕变关系的方法, 显著降低了蜕变关系的冗余; Lü等[17]提出了一种基于蜕变关系和粒子群优化算法相结合的测试用例生成方法, 显著提高了时间消耗和实用性评估方面的效率.

蜕变测试的本质是验证程序多组输入和输出之间是否满足蜕变关系, 因此蜕变关系是蜕变测试的核心, 决定了蜕变测试的能力和效果. 由上述分析可见, 目前关于蜕变关系的研究多数都集中于如何在已知的蜕变关系集合中选取、生成更有效的蜕变关系或蜕变关系组合方案, 但都有一个前提条件, 即需预先构造一个蜕变关系集合, 而目前该蜕变关系集合均依赖测试人员的领域知识构建, 从而限制了蜕变测试的进一步发展, 增加了蜕变测试的使用成本. 科学计算的蜕变关系存在多种形式, 但50%以上的蜕变关系可使用多项式的形式表示[18]. 因此本文研究蜕变关系的多项式形式, 先用基于机器学习基本原理的梯度下降法对多项式系数进行求解, 再通过所得多项式自动提取所测程序的蜕变关系.

1 蜕变测试基本原理

在软件测试中, Oracle表示当程序正确运行时输入的测试用例应该对应的输出结果. 通常情况下, 获取合适的Oracle将花费较大的代价, 且多数情形下, 由于待测程序复杂度等原因, 所以很难或完全不能得到每个测试用例对应的Oracle. 此时, 由于测试用例作为输入所得结果无法判断其是否正确, 因此无法测试程序是否存在问题.

蜕变测试基本原理是通过检测两个或两个以上输出结果之间是否满足程序中包含的某种关系(蜕变关系)检测程序中的错误. 蜕变测试不同于传统软件测试之处是传统软件测试将关注点聚焦于出现错误的测试用例中, 而蜕变测试则认为正确的测试用例也包含重要信息. 由于蜕变测试不依赖于测试用例产生输出的正确性, 所以对于多个测试用例, 在未知Oracle的情况下仍可进行程序测试. 蜕变测试一般由以下4步构成：

1) 根据合适的测试用例生成策略生成一个或多个测试用例；

2) 分析待测程序的性质, 生成蜕变关系；

3) 根据原始测试用例和蜕变关系生成衍生的蜕变测试用例集;

4) 依次检查每个原始测试用例和对应衍生测试用例的输出是否满足蜕变关系.

在蜕变测试中, 蜕变关系的生成是关键. 蜕变关系表示待测函数或软件的一些特殊性质, 这些性质对程序的不同输入产生影响, 从而检测出一部分错误. 例如, 对于最大值函数max{X}, 只要X中元素值不变, 则无论X值的顺序如何变化, 最大值函数max{X}的最终输出一定不变. 通过该性质可检测出函数的部分正确性. 又例如, 计算sin(x)的程序, 对于大部分x, sin(x)的具体数值无法确定, 但根据相关数学知识可知sin(x)与sin(x+2kπ)的值相同, sin(x)与-sin(-x)的值相同, 所以只要在相同的输入下“sin(x)-sin(x+2kπ)=0”与“sin(x)+sin(-x)=0”都成立, 即可证明程序部分正确. 当然, 对于蜕变关系, 不一定都与“=”相关. 例如, 对于f(x)=x程序, “若x1>x2, 则f(x1)>f(x2)成立”可作为程序的一条蜕变关系. 但蜕变关系的提取依赖于测试人员的人工推算, 从而要求测试人员对测试程序所在的领域必须深入了解, 且对于一些复杂的问题很难推算出合适的蜕变关系. 为解决该问题, Kanewala等[19]提出了在缺少Oracle的情形下用机器学习的方法发掘是否一些程序含有某些形式的蜕变关系. 本文将科学计算蜕变关系的提取和机器学习相结合, 通过大量的数据寻找两个或两个以上不同参数的函数之间存在的数值关系.

2 基于梯度下降法的蜕变关系获取

2.1 蜕变关系

蜕变关系表示软件输入变化对输出的影响, 即在一定取值范围内, 程序的输入变化和程序输出变化存在关系. 在进行蜕变测试时, 如果原始用例和衍生用例之间的关系不满足所选择的蜕变关系, 则表明这一对测试用例发现了程序中的错误. 蜕变关系可用下列公式表示：

R1(x1,x2)→R2(P[x1],P[x2]),

(1)

其中：P[x]表示输入x在执行完程序P后的输出;R1表示输入x1与x2之间存在的关系;R2表示输出P[x1]与P[x2]之间存在的关系. 即当输入x1与x2满足关系表达式R1时, 若输出P[x1]与P[x2]满足关系表达式R2, 则该程序在此蜕变关系下成立, 否则程序错误. 在蜕变测试中, 如何找到合适的R1与R2是测试的关键.

2.2 蜕变关系算法实现

在蜕变关系生成过程中, 如何确定两个或多个相关联的输入对相应输出的影响是确定蜕变关系的关键. 本文采用对于确定关系的两个或多个输入, 通过大量数据多次迭代的方式确定不同输入对输出的影响, 即使用机器学习方法进行蜕变关系的获取. 梯度下降算法作为机器学习中的基本算法之一, 具有大样本下标准差低、学习效率不会下降等优点. 梯度表示函数中上升最快的方向, 即f(x,y,z)=(∂f/∂x,∂f/dy,∂f/∂z). 梯度下降算法的基本思想是按照函数梯度下降的方向求解函数的极小值, 本文使用梯度下降算法作为基本算法获取科学计算程序中存在的蜕变关系.

科学计算程序中50%以上的蜕变关系可用多项式形式表示, 为简便, 本文中对输入x1与x2之间存在的关系r1和输出P[x1]与P[x2]之间存在的关系r2都作为线性方程的情形. 当r1为线性方程时,x和r1(x)之间的关系可表示为r1(x)=ax+b, 其中a,b均为系数. 当r2为线性方程时,P(x)和P(r1(x))之间的关系可表示为θ1P(x)+θ2P(r1(x))+θ3=0, 其中θ1,θ2,θ3均为系数. 因此, 蜕变关系可表示为

θ1P(x)+θ2P(ax+b)+θ3=0.

(2)

由于在系数θ1,θ2,θ3都确定的情形下, 自变量x在任何取值下蜕变关系(2)都成立, 所以蜕变关系的损失函数可表示为

L(θ)=|θ1P(x)+θ2P(r1(x))+θ3|.

(3)

多项式蜕变关系作为最小化损失函数, 可通过梯度下降法迭代, 使多项式蜕变关系最小化并得到模型参数值. 下面给出梯度下降法原理, 设目标函数为L(θ),L(θ)关于参数θ1的梯度是损失函数上升最快的方向. 对于最小化优化问题, 只需将参数沿梯度相反方向前进一个步长, 即可实现目标函数的下降(步长又称为学习率). 则参数更新公式如下：

θ=θ-αθL(θ),

(4)

算法1蜕变关系梯度下降算法.

步骤1) 初始化θ(参数向量) ,α(步长),r1(x)=ax+b,θ1P(x)+θ2P(r1(x))+θ3=0(蜕变关系);

步骤2)L(θ)=|θ1P(x)+θ2P(r1(x))+θ3|(损失函数),hθ(x)=θ1P(x)+θ2P(r1(x))+θ3;

步骤3) whileL(θ)收敛 do

步骤5) end while

步骤6) 返回θt.

算法1中, 梯度下降算法根据函数下降最快的方向进行损失函数的最小值求解, 通过多次迭代最终实现假设函数hθ(x)和样本点的拟合. 在梯度下降算法中, 由于损失函数的复杂性, 使得到的极值点不一定是损失函数的最小值点, 可能是函数局部的极值点, 但由于科学计算中多数程序的蜕变关系可用多项式形式表示, 因此本文采用梯度下降法得到的一定是损失函数的最小值. 由于选取参数θ的初始值不同, 因此得到的极小值也可能不同. 对于下降步长α也需选取合适的值, 若步长α偏小, 则函数下降得较慢, 需消耗大量的资源; 若步长α选取较大, 则可能会出现无法收敛的情形.

3 算法优化

算法学习率(即步长α)的取值大小对梯度下降算法的效率影响较大. 如果学习率过高则会增加损失函数的波动性, 而学习率过低则会降低算法效率, 增加收敛所需时间. 随机梯度下降算法使用固定的学习率进行参数更新, 已成为限制算法性能的一个重要因素. 此外, 随机梯度下降算法的固定步长使算法在每次迭代后对参数的更新都有可能会引起损失函数数值的剧烈变化, 很难获取理想的目标参数. 例如, 对于函数tanx, 由于该函数拥有无穷大和无穷小, 且参数的更新和损失函数的变化互相影响, 故函数tanx的损失函数值将剧烈波动, 很难选择合适的参数.

理论上, 如果数据集不密集, 则使用自适应学习速率的优化方法(如Adagrad, RMSprop, Adam)可提高随机梯度下降算法效率. 本文使用Adam算法解决该问题, 该算法通过计算一阶矩估计和二阶矩估计设计独立的自适应学习率, 算法描述如下.

算法2随机Adam算法.

步骤1) 初始化α(步长),β1,β2(超参数),θ0(参数向量),m0=0,v0=0,t=0(时间步);

步骤2) whileθt不收敛 do

步骤3)t=t+1;

步骤4)gt=θft(θt-1);

步骤5)mt=β1×vt-1+(1-β1)×gt;

步骤10) end while

步骤11) 返回θt.

算法2计算了梯度的指数移动均值, 而超参数β1和β2控制移动均值的衰减率. 在给定学习率、超参数和损失函数及初始化各参数后, 算法2对时间步+1, 并计算该时间步下的梯度, 更新偏差的一阶估计和原始二阶估计, 然后再计算偏差修正的一阶矩估计和偏差修正的二阶矩估计, 最后根据计算值更新参数θ直至收敛.

由于Adam算法在进行迭代时通过计算一阶矩估计和二阶矩估计动态的调节学习率, 所以可较好地解决由随机梯度下降算法学习率固定导致的一系列问题.

4 实验

4.1 有效性分析实验

本文实验以sin函数作为研究对象, 随机梯度下降算法中所有参数每次更新都使用相同的学习率. 由于sin函数的损失函数梯度较大, 若采用较大的学习率则会出现收敛缓慢甚至无法收敛的情形, 因此本文将学习率取较小值0.000 1. 此外, 由于式(2)在梯度下降求解中可能会出现θ1,θ2,θ3均为0的情形(特别地, 经过实验证明若不采取措施参数将会直接下降到0), 因此可将参数θ1去除, 去除参数θ1能完全杜绝参数归零的情形, 所以可将式(2)表示为

(5)

令m=θ2/θ1,n=θ3/θ1, 则损失函数可表示为

L(m,n)=|P(x)+mP(ax+b)+n|.

(6)

该方法不仅能解决参数归零问题, 且不会对蜕变关系的推断有影响. 此外, 多数线性多项式的系数主要集中在1和2上, 并且若初始值和真实值较接近时可减少迭代次数, 故本文实验中将m,a,n的初始化值局限在[-2,2]内,b值局限在[-10,10]内.

图1 一次随机梯度下降算法的损失函数Fig.1 Loss function of a stochastic gradient descent algorithm

将式(6)作为损失函数, 通过Pytorch框架可实现随机梯度下降算法. 实验成功的标准：在进行足够多次迭代后, 若损失函数能降为零, 且参数值也稳定在某值, 验证参数值(代入式(3))符合所测科学计算函数的规律, 则可判断成功推出了蜕变关系. 对于每个科学计算函数, 重复执行程序若干次, 并用Tensorboard记录数据, 观察实验结果. 本文选取一个具有代表性的典型特征结果为例, 图1为进行某次实验损失函数每次迭代的数值结果. 由图1可见, 损失函数在5万次迭代内呈现了高波动性, 这是因为随机梯度下降每个样本更新一次梯度, 损失函数值都会进行频繁地更新. 损失函数在前期迭代时波动幅度较大并非完全无益, 其可能有益于挖掘新的及更优的局部最小值. 后期波动相对前期逐渐减小, 但也在波动中收敛, 多次迭代后损失函数在波动中降为零. 根据实验得到此次运行梯度下降算法的参数值为：m=1,a=1,b=π,n=0, 代入到多项式蜕变关系式为sin(x)+sin(x+π)=0. 通过查阅三角函数的相关定理可知, 该多项式蜕变关系成立. 本文进行了大量重复性实验, 按同样流程进行数据记录和验证, 结果表明, 随机梯度下降算法可对有多项式蜕变关系的科学计算函数进行蜕变关系推导.

4.2 三种自适应学习速率的优化方法对比

理论上, RMSprop算法是Adagrad算法的一种优化, 而Adam算法是在RMSprop算法的基础上进行优化, 引入了动量和偏差修正. 在类似情形下, RMSprop算法与Adam算法的性能相差较小, 但Adam算法收益于偏差修正, 因此略优于RMSprop算法, 因为Adam算法在其接近收敛时梯度变得更稀疏[20]. 本文进行多次实验的结果表明, Adam算法在自动推导蜕变关系程序的效率最高, 性能最好.

图2 三种算法的损失值对比Fig.2 Comparison of loss values of three algorithms

图2为在完全相同的数据训练集下, 同一程序中创建三种优化器, 随机梯度下降算法(A)、 RMSprop算法(B)和Adam算法(C)的损失值对比结果. 由图2可见, 在相同数据及相同迭代次数的条件下, 随机梯度下降算法和RMSprop算法无法将损失值降低到零, 即推导蜕变关系失败. 而Adam算法却能在约5 000次迭代时即摆脱高波动的损失值, 将损失值逐渐减低到零, 求出蜕变关系. 表明Adam算法即使初始化参数时, 参数距离最优解较远, 但能克服随机梯度下降算法的缺陷, 用更精巧的算法将损失函数降低至零, 证明了在解决该问题中Adam算法比另外两种算法性能更优. 多次运行程序后结果表明, 在求解科学计算函数的多项式蜕变关系问题中, Adam算法的效果最好.

4.3 随机梯度下降法与Adam算法对比

由上述实验可知, 使用随机梯度下降算法的损失函数平均迭代次数约5万次呈现高波动性, 在10万次迭代后开始收敛. 为与随机梯度下降算法进行对比, 本文在实现过程中将Adam算法的初始学习率设为0.001, 与随机梯度下降算法相同使用式(3)作为损失函数, 用Pytorch框架构造Adam优化器进行实现. 多次实验结果表明, 在多数情形下初始值为α=0.001,β1=0.9,β2=0.999,ε=1×10-8时算法性能优异.

图3 Adam算法损失值示例Fig.3 Example of loss values of Adam algorithm

图3为Adam算法损失值示例. 由图3可见, Adam算法优化后程序推导出蜕变关系所需的迭代次数极大降低, 多次实验结果表明, 使用Adam算法损失值降为零的次数约为2 000(不排除存在少量迭代次数远大于2 000的情形), 相比于随机梯度下降法的迭代次数性能明显提升, 因此Adam算法比随机梯度下降法收敛的更快且更稳定.

Adam算法比随机梯度下降算法效率高的一个重要原因是其可以修正偏差. 对于tan函数, 如尝试用随机梯度下降算法推导其蜕变关系式, 梯度计算将十分困难, 因为tan函数具有无穷大和无穷小, 高梯度将会导致损失函数大幅度波动, 如图4所示. 而Adam算法可很好地解决该问题, 图5是用Adam算法计算tan函数蜕变关系式的一个示例, 损失函数在波动中降为零, 此时对于优化后的蜕变关系式(4), 对应的参数为m=1,a=-1,b=π,n=0，代入到多项式蜕变关系式为tan(x)+tan(-x+π)=0. 经过验证, 该组系数代入tan函数的蜕变关系式成立.