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

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

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

0 引 言

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

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

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

1 基本概念

1.1 蛻變關系

定義1 蛻變關系[5]：假設程序P用來計算函數(shù)f，x1,x2,…,xn(n>1)是f的變元組，且f(x1),f(x2),…,f(xn)是它們所對應的函數(shù)結果。若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的正確性。

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

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

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

2 似然蛻變關系識別方法

2.1 基本框架

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

該方法框架如下：

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

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

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

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

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

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

2.2 識別過程

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

2.2.1 輸入模式

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

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

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

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

表1 數(shù)據(jù)變異型輸入模式

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

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

2.2.2 生成測試數(shù)據(jù)

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

2.2.3 輸出模式

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

表2 比較型和函數(shù)型輸出模式

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

2.2.4 篩選似然蛻變關系

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

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

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

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

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

2.3 算法描述

根據(jù)前面的步驟，算法如下。

算法1：似然蛻變關系發(fā)現(xiàn)算法

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

輸出DR,LMR

其中

P為待測程序；

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

n為隨機產(chǎn)生的測試數(shù)據(jù)序對的個數(shù)；

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

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

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

算法開始 **/

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

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

for(j=0;j

r=Dr[j];

for(i=0;i

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

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

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

end if

end for

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

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;

自動挖掘函數(shù)類型的輸出模式集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; //統(tǒng)計同時滿足輸入模式和輸出模式的用例數(shù)

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++; //成功的測試數(shù)據(jù)

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

end if

end if

end for

end for

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

end for

3 數(shù)值例子

3.1 龍格庫塔計算程序

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

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

(4)

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

(5)

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

(6)

3.2 實現(xiàn)過程

3.2.1 提取輸入模式

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

(1)數(shù)值解的性質

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

(2)輸入數(shù)據(jù)的數(shù)值特性

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

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

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

(3)數(shù)據(jù)變異關系

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

r-3.2：對原始用例取倍數(shù)，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 生成測試數(shù)據(jù)

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

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

表3 兩倍輸入模式生成的測試數(shù)據(jù)

3.2.3 挖掘輸出模式

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

表4 模型匯總和參數(shù)估計

圖4 曲線擬合效果

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

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

3.2.4 驗證似然蛻變關系

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

表5 輸入、輸出模式匯總

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

3.3 實驗結果分析

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

表6 似然蛻變關系的篩選

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

y=e3*e-3x(7)

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

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

4 結束語

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