龍格庫塔程序的似然蛻變關系識別方法

文雙紅，陽小華，閆仕宇+，劉 杰，李 萌，馮晉濤

(1.南華大學 計算機學院，湖南 衡陽 421001；2.南華大學 中核集團高可信計算重點學科實驗室，湖南 衡陽 421001；3.南華大學 湖南省智能裝備軟件評測工程研究中心，湖南 衡陽 421001；4.中國核動力研究設計院 核反應堆系統設計技術重點實驗室，四川 成都 610041)

0 引 言

蛻變測試技術是緩解“測試Oracle”問題的有效方法之一，其成本效益好[1,2]。蛻變關系是蛻變測試中至關重要的組成部分，因為蛻變關系既為生成衍生測試用例做了鋪墊[3]，又為判斷程序是否正確提供依據。陽等通過分析科學計算程序的研發過程，建立了物理、計算和代碼模型蛻變關系的層次分類模型[4]，再由代碼模型蛻變關系層的程序輸入、輸出運行軌跡的分析中，引出了似然蛻變關系的定義[5]，由似然蛻變關系結合領域知識可以進一步驗證得到蛻變關系。

近年來在似然蛻變關系識別上，已有專家學者開展各項研究。Su等[6]分析轉換方法的輸入值前后特性動態推導似然蛻變屬性，利用同一方法的不同版本檢測到的不同蛻變屬性來發現潛在缺陷；Troya等[7]創建蛻變關系模式集合來對元模型進行轉換，進而發現回歸測試、增量轉換和語言遷移模型轉換程序中的錯誤；Zhang等[8]利用粒子群算法搜索多項式形式的似然蛻變關系；Sun等[9]根據數據變異算子定義輸入模式，再由輸出映射規則推導產生數值計算程序的蛻變關系；UK等[10,11]將程序代碼片段轉換控制流圖和特征值，預設的蛻變關系作為標簽值，利用機器學習的方法預測蛻變關系；陽等[5]借鑒動態不變量的思想，提出一種發現似然蛻變關系的算法框架。李[13]利用問題域和函數擬合知識，提出一種數據驅動的啟發式似然蛻變關系識別方法。以上研究在特定應用領域取得一定成就，對于推動蛻變測試技術的發展具有重要意義，但缺乏系統性和適用性，有待繼續深入研究。

邱等[12]已將蛻變測試應用到常微分方程程序，但是沒有描述如何系統地產生蛻變關系。因此，本文針對常微分方程的龍格庫塔算法程序，提出了一種基于SPSS的似然蛻變關系識別方法。SPSS工具是一款成熟的統計應用軟件，在數據擬合、分析和挖掘等方面具有優勢。本文采取靜態分析的方式識別程序有意義的輸入模式，通過預設豐富的形式，利用SPSS工具動態挖掘滿足特定輸入模式的測試數據序對的輸出模式，似然蛻變關系為識別真正的蛻變關系提供啟發信息。

1 基本概念

1.1 蛻變關系

定義1 蛻變關系[5]：假設程序P用來計算函數f，x1,x2,…,xn(n>1)是f的變元組，且f(x1),f(x2),…,f(xn)是它們所對應的函數結果。若x1,x2,…,xn之間滿足關系r時，f(x1),f(x2),…,f(xn)滿足關系R，即

r(x1,x2,…,xn)→R(f(x1),f(x2),…,f(xn))

(1)

則稱(r,R)是P的蛻變關系，其中，r為蛻變關系的輸入關系，R為輸出關系。

顯然，如果P是正確的，那么它一定滿足下面的推導式

r(I1,I2,…,In)→R(P(I1),P(I2),…,P(In))

(2)

其中，I1,I2,…,In是程序P的對應于x1,x2,…,xn的輸入，P(I1),P(I2),…,P(In)是相應的輸出。因此，可以通過檢測式(2)成立與否來判定程序P的正確性。

例如，三角函數sin程序，Chen等[2]通過人工靜態分析sin函數的數學屬性推導了10條蛻變關系，如圖1所示。以Rsin1來介紹蛻變關系的組成和原理，假設有一輸入值為52°，生成一個新的輸入值為52°+180°=232°，然后執行程序，判斷sin(52°)=sin(232°)是否成立，不成立則說明程序存在錯誤。

圖1 三角函數sin的蛻變關系

1.2 似然蛻變關系

定義2 似然蛻變關系[5]：假設T={(xi,yi)|xi∈D,yi=P(xi),i=1,2,…,n} 是P的運行軌跡，記Tx={xi|(xi,yi)∈T}，若對于任意的xi1,xi2,…,xin∈T,n?N，都有

r′(xi1,xi2,…,xin)→R′(yi1,yi2,…,yin)

(3)

其中，yi1,yi2,…,yin是xi1,xi2,…,xin對應的輸出，稱(r’, R’)是P關于T的似然蛻變關系，簡稱似然蛻變關系，也可以看成是輸入模式和輸出模式的蘊含式。r′為似然蛻變關系中的輸入模式，R′為輸出模式。

顯然，如果P是正確的，那么P關于x的定義域D的蛻變關系一定是P關于T的似然蛻變關系，反之則不然。因此P的似然蛻變關系對識別P的蛻變關系起到促進作用。

Zhang等[8]預設輸入模式為一次多項式、輸出模式為一次和二次多項式，將輸入模式和輸出模式組合為一個多項式，利用粒子群搜索算法從成功的測試用例中求解多項式參數，最后通過篩選得到檢錯率高的似然蛻變關系，以三角函數sin程序為例，如圖2為Apache庫下sin程序的多項式似然蛻變關系。

圖2 sin程序的多項式似然蛻變關系

2 似然蛻變關系識別方法

2.1 基本框架

現有的自動化的似然蛻變關系識別方法主要通過預設輸入模式和輸出模式，從成功的測試用例中挖掘具體的輸入模式和輸出模式來獲取程序的似然蛻變關系。但存在預設的關系模式太少、盲目搜索特定方程參數解。因為蛻變關系與待測程序的領域知識密切相關，而輸入模式是蛻變關系的前提，有意義的輸入模式是衍生測試用例的來源，如果能首先通過靜態分析導出其有意義的輸入模式，然后生成測試數據，執行程序后的測試輸出中再來挖掘其輸出關系，則更具針對性，減少了盲目性。

該方法框架如下：

(1)根據輸入模式識別規則，靜態分析領域知識來識別一批有意義的輸入模式；

(2)根據每一條輸入模式來生成測試輸入數據；

(3)從執行程序的輸出結果中，利用SPSS工具挖掘各種類型的輸出模式；

(4)最后驗證所發現的輸入、輸出模式，進而得到程序的似然蛻變關系。

該方法的主要過程如圖3所示，詳細的描述見2.2節。

圖3 似然蛻變關系識別方法流程

2.2 識別過程

似然蛻變關系識別方法具體而言，分為4個步驟。

2.2.1 輸入模式

似然蛻變關系是由輸入模式和輸出模式組成的，因此識別過程可以從兩個方面考慮，輸入模式從特定程序算法層次的背景知識中識別，下面提出了4條規則來指導產生程序的輸入模式：

(1)分析算法數值解的性質。需要已知少量算法的原始數據，分析這些數據是否滿足數學性質，如單調性、奇偶性、周期性、對稱性。設算法求解函數f(x)，若數值解呈單調趨勢，分析xi

(2)分析程序預置參數的數值特性。適用于除了生成測試數據外，還與預置參數(如坐標、范圍、步長等)相關的程序。進一步分析參數代表的含義，通過改變參數獲取輸入模式，例如改變起止點、縮小范圍或改變步長，檢查相同時刻/位置下的輸出是否存在關系。

(3)基于數據變異設置輸入模式。數據變異是對原始輸入數據進行變異，蛻變關系中的輸入關系也是對原始輸入數據進行一種轉化，兩者都是針對原始輸入數據進行變換，因此可以通過數據變異的方式來指導產生輸入模式，本文選擇7種基本的數據變異算子(表1)，為了便于檢驗結果，輸入模式不必構造得太復雜。

表1 數據變異型輸入模式

(4)組合不同的輸入模式生成新的輸入模式。假設根據前3種輸入模式識別規則結合靜態分析方法，得到了3條輸入模式：xj=-xi、xj=2xi、xj=xi+1，一條輸入關系的xi用另一條輸入關系的xj代替，就可以組合形成新的輸入模式，如xj=-(xi+1)、xj=-2(xi+1)。

本文提出的4條輸入模式識別規則中，前3條規則需要結合一定的領域知識才能推導產生有意義的輸入模式，第4條規則需要以已有的輸入模式為基礎才能組合成新的有意義的輸入模式。上述規則互為補充，能夠滿足大多數程序推導輸入關系的要求。

2.2.2 生成測試數據

蛻變測試中常用的原始測試用例生成方法是隨機法和特殊值，其次采用已有的測試套件，少部分文獻中使用的是工具，如約束編程、基于搜索的測試、符號執行等[1]，隨機方法是一種經濟有效且直截了當的方法。在選取原始測試用例時，可根據具體情況采取相應的測試用例生成策略。例如，龍格庫塔法生成常微分方程程序的測試數據時，由于程序自動生成一批等差的數據，因此數據產生方式為等價類劃分法。

2.2.3 輸出模式

似然蛻變關系的識別在很大程度上受到測試數據的影響，分析2.2.2節產生的測試數據是否為成功的測試數據，由于輸入模式是緊密結合領域知識的，且是有意義的輸入關系，所以由此再來生成的測試數據，在測試輸出結果數據中挖掘輸出模式，顯然提高了數據挖掘的針對性，有助于輸出模式識別。在挖掘似然蛻變關系的輸出模式時，實際上是根據預設的輸出模式，利用擬合功能對輸出數據進行分析。本文預設比較型輸出模式和函數型輸出模式，比較型輸出模式包括6種形式，即小于、小于等于、等于、大于、大于等于和不等于；函數型輸出模式包括10種形式，即線性、二次、復合、增長、對數、立方、S、指數分布、逆模型、冪，具體的介紹見表2。

表2 比較型和函數型輸出模式

為了得到似然蛻變關系的輸出模式參數和曲線的擬合效果，由于SPSS工具里面預設了多種形式的輸出表達式，因此，該文利用SPSS數據分析工具進行模擬。

2.2.4 篩選似然蛻變關系

為了進一步驗證所識別的輸入模式、輸出模式是否能夠構成似然蛻變關系，需要對產生的輸入模式、輸出模式進行篩選，即再次生成一批測試數據，分析關系模式的有效性，值得注意的是應當盡可能地選擇與原來用于生成輸入模式、輸出模式時不同的測試數據。如果經研究發現，輸入模式、輸出模式滿足條件：

條件一：SPSS挖掘輸出模式時的可決系數R方>0.95；

條件二：驗證時的測試用例的通過率>90%。

則可視為一條似然蛻變關系；否則，則選擇下一對輸入模式、輸出模式，直到結束。

似然蛻變關系不僅可以用來產生新的測試用例，而且可以用作驗證程序運行結果的一種預判(預期輸出)。因此似然蛻變關系可以用來發現程序中的錯誤，即觀察測試用例中是否有違反似然蛻變關系的情況，如果有則認為程序中存在錯誤。

2.3 算法描述

根據前面的步驟，算法如下。

算法1：似然蛻變關系發現算法

/** 輸入 P,Dr,n,m

輸出DR,LMR

其中

P為待測程序；

Dr為靜態分析程序文檔導出的似然蛻變關系輸入模式；

n為隨機產生的測試數據序對的個數；

m為驗證推導的輸入模式、輸出模式時生成的測試用例序對的個數；

DR為利用SPSS工具挖掘的滿足可信度要求的輸出模式；

LMR為驗證輸入模式、輸出模式后，最終得到的似然蛻變關系。

算法開始 **/

//(1)對照輸入關系，生成測試數據

dr_len=Dr.len(); //獲取輸入模式的個數

for(j=0;j

r=Dr[j];

for(i=0;i

ti=(xi, P(xi)); //隨機生成程序輸入，運行程序得到輸出

t′i=(r(xi), P(r(xi))); //依據輸入模式，生成后續測試數據

if(ti,t′i的輸出結果正確)i++;

end if

end for

//(2)利用計數器和SPSS分別挖掘比較類型和函數類型的輸出模式

if(P(xi)

//< ≥ ≠

If(P(xi)>P(r(xi)))gc++;ltc++; uc++;

//> ≤ ≠

if(P(xi)==P(r(xi)))ec++;//=

判斷每個計算器/n是否>0.95，是則加入輸出模式集Rs;

P(xi), P(r(xi))導入SPSS;

自動挖掘函數類型的輸出模式集Rs;

//SPSS工具有“擬合”功能，取擬合效果R方>0.95加入Rs

DR[j]=Rs; //把Rs添加到DR中

end for

//(3)推導似然蛻變關系

for(j=0;j

r’ =Dr[j];

dR_len=DR[j].len();//取輸出模式

count=0; //統計同時滿足輸入模式和輸出模式的用例數

for(k=0;k

R’=DR[j][k];

for(i=0;i

ti=(xi,P(xi));

t’i=(r(xi),P(r(xi)));

if(ti,t’i的輸出結果正確)i++; //成功的測試數據

if(R’(P(xi),P(r(xi)))count++; //計數

end if

end if

end for

end for

判斷count/n是否>90%，是則將(r’,R’)添加到似然蛻變關系集LMR;

end for

3 數值例子

3.1 龍格庫塔計算程序

為了展示所提出的方法的有效性，以一個常微分方程計算程序為例進行闡述。

一階常微分方程(只求一次導)的標準形式如下

(4)

使用經典四階龍格庫塔法(Runge-Kuta)解上述表示的常微分方程，則對于該問題的求解過程如下所示

(5)

將式(4)實例化為一個常微分方程

(6)

3.2 實現過程

3.2.1 提取輸入模式

選定四階龍格庫塔法求解常微分方程計算程序后，首先輸入模式的識別，以下即為對應2.2.1節中提到由靜態分析導出的4類輸入模式。

(1)數值解的性質

r-1.1：分析其算法的數值解的數學性質，其數值解具有單調性，取輸入模式xi

(2)輸入數據的數值特性

r-2.1：龍格庫塔法算法的調用方式為RK4(起始坐標, 起始點的結果, 終止坐標, 數據個數, 常微分方程)，改變起始坐標點，其它參數保持不變。

r-2.2：設置不同的步長，除了數據個數外，其它參數保持不變。

r-2.3：交換運算，交換起始坐標和終止坐標，將第一次運行得到的終止坐標的輸出結果作為預置參數。

(3)數據變異關系

r-3.1：對原始用例取負數，x’=-x。

r-3.2：對原始用例取倍數，x’=2x。

r-3.3：對原始用例自增1，x’=x+1。

(4)組合輸入模式

r-4.1：組合r-3和r-4.1，得到x’=-2x。

r-4.2：組合r-4.1和r-4.2，得到x’=2*(x+1)。

3.2.2 生成測試數據

常微分方程程序的調用格式是RK4(x0,y0,x,n,pfunc)，由于程序本身的性質，將x0到x等份切割為n+1個數據，得到的測試數據格式為(xi,yi)，將xi看作有意義的輸入數據，yi看作輸出數據，因此本文采用的數據生成方式為等分等價類。針對每一條輸入模式生成100組測試數據，以r-3.2輸入模式為例進行說明，本文產生所有數據見GitHub：https://github.com/CsAndIt/LMR2020。

r-3.2輸入模式為2倍倍數關系，首先生成原始測試數據，調用RK4(1,1,2,100,pfunc)生成從1到2總共100個數據，然后由輸入模式獲取輸入對應為2倍的數據，即生成2到4的數據，調用RK4(1,1,4,300,pfunc)生成，選取后續測試數據中對應原始測試數據為2倍的數據，表3展示了部分數據。

表3 兩倍輸入模式生成的測試數據

3.2.3 挖掘輸出模式

生成數據后，針對 數據組，挖掘蘊含的輸出模式，根據預設的6種比較模式和11種函數模式，比較模式輸出關系用不同的計數表示。以第6條輸入模式為例，滿足條件的比較類型的輸出模式有：<、≤和≠；得到的函數模型匯總情況見表4，曲線擬合圖像如圖4所示。

表4 模型匯總和參數估計

圖4 曲線擬合效果

取R方大于等于0.95的擬合曲線為輸出模式，得到二次、三次和冪形式的函數關系，根據表2的函數關系式填入參數后，由于三次和冪關系與二次關系重合了，只取其中一個即可，得到了輸出模式y’=0.05y2。

用同樣的方法，分別執行其它輸出數據對，每條輸入模式與對應數據挖掘得到的輸出模式見表5。

3.2.4 驗證似然蛻變關系

由表5得到了33組輸入模式、輸出模式，輸出模式為比較類型的模式對無需再驗證，這是因為在大概率上與推導的模式對是一致的。下面將針對M7、M8、M12、M14、M18、M22、M26、M30這8條模式對生成測試數據，每組關系模式生成80對數據，來驗證輸入模式、輸出模式的正確性，由于程序在計算時出現了截斷誤差，綜合考慮后，采取通過率在90%及以上的作為一條成功推導的似然蛻變關系，測試數據通過率如圖5所示，實驗結果分析發現，本文的方法可以有效地發現常微分方程程序的似然蛻變關系。

表5 輸入、輸出模式匯總

圖5 輸入、輸出模式驗證的通過率

3.3 實驗結果分析

在3.2節中介紹了似然蛻變關系的識別方法，但是還需對結果進行驗證，本文采取的方式是與函數解析式及程序性質進行對比，篩選出符合程序屬性和要求的似然蛻變關系，解釋說明見表6。

表6 似然蛻變關系的篩選

常微分方程式(6)的解析式為

y=e3*e-3x(7)

由于M7和M12分別與M4和M9重復，因此剔除，剩下的31種模式對都可看作程序的似然蛻變關系。比較類型的似然蛻變關系有25條，占比80.65%；函數類型的似然蛻變關系，由于在導出輸入模式時沒有窮盡所有的可能性，根據每種規則分別只實例化一條輸入模式，故而生成得少。根據實驗結果得知，實驗較好地識別出了龍格庫塔計算程序的似然蛻變關系。

通過與Zhang等[8]提出的一種自動發現和清理數值蛻變關系的識別方法相比，由于本文結合領域知識推導有意義的輸入模式，避免了輸入形式預設的盲目性，而且輸出模式也囊括了更多的關系類型，包括比較關系及多種函數關系。進一步可知，依據有意義的輸入模式來生成測試的輸入數據，相應得到的輸出數據，在一定程度上提高了數據挖掘的針對性，也將為后續的輸出關系的挖掘降低冗余做準備。

4 結束語

本文從程序算法層面數學性質方面分析中，得到了識別輸入模式的4條規則，可以支持對輸入模式的識別和測試數據的生成；利用SPSS工具對依據輸入模式產生的程序運行結果進行挖掘，得到了近似真正的輸出模式；通過對龍格庫塔算法程序的研究分析發現，本文提出的似然蛻變關系識別方法在實際應用中是可行的、有效的。由于輸入模式是針對常微分數值程序而言的，下一步工作就如何建立更加有效的輸入模式識別規則以及推廣該方法的實際應用進行研究。