一種基于梯度下降算法的蛻變關系生成方法

穆翔宇, 范 鈺, 李蘇吉,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函數的蛻變關系式成立.

圖4 tan損失函數波動Fig.4 Fluctuations of tan loss function

圖5 Adam算法對于tan函數的損失值Fig.5 Loss values of Adam algorithm for tan function

盡管Adam算法可求出tan函數的蛻變關系式, 但tan函數易導致損失函數高波動的特征, 使執行Adam算法失敗率也較高. 但相比隨機梯度下降法無法求解tan函數的蛻變關系式, Adam算法已有很大優勢.

綜上所述, 本文將科學計算程序的蛻變關系推導問題視為一個多項式系數搜索問題, 用經典的機器學習算法----梯度下降法解決該問題, 并使用Adam算法對梯隊下降法進行優化, 取得了較好的效果.