[發(fā)明專利]含隨機數(shù)軟件測試數(shù)據(jù)生成問題的優(yōu)化模型及進化求解

有效

• 申請?zhí)枺?/td>: 201410139311.6
• 申請日: 2014-04-08
• 公開（公告）號: CN103902455A
• 公開（公告）日: 2014-07-02
• 發(fā)明（設(shè)計）人: 姚香娟;鞏敦衛(wèi);王文亮;李彬;張功杰;田甜
• 申請（專利權(quán)）人: 中國礦業(yè)大學
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.含隨機數(shù)軟件測試數(shù)據(jù)生成問題的優(yōu)化模型及進化求解，其特征在于如下步驟：?

步驟1.1：提出含隨機數(shù)軟件測試充分性準則，保障每個測試目標被測試數(shù)據(jù)集覆蓋的概率大于設(shè)定的閾值；?

步驟1.2：給出含隨機數(shù)軟件測試數(shù)據(jù)生成問題的隨機優(yōu)化模型，保障測試數(shù)據(jù)滿足給定的測試充分性準。?

步驟1.3：設(shè)計了一種個體適應(yīng)值的近似計算方法，用遺傳算法來對隨機性軟件測試數(shù)據(jù)生成問題進行進化求解。?

2.權(quán)利要求1中步驟1.1所述的含隨機數(shù)軟件測試充分性準則，其特征在于本發(fā)明對給定的測試目標（語句，分支，路徑等）集，在程序的輸入空間尋找測試數(shù)據(jù)集，使得以該測試數(shù)據(jù)集為輸入運行程序時，每個測試目標被執(zhí)行的概率達到給定的閾值。這樣，對于內(nèi)部含有隨機數(shù)軟件，避免了測試數(shù)據(jù)覆蓋目標語句受隨機數(shù)影響帶來的不確定性。?

例如，以下列程序片段為例：?

如果選取測試數(shù)據(jù)集{-18,-27,-10,-23,-2,-15,-9,15,3,5,19,19}，就可以保證每個目標被覆蓋的概率至少為0.9，而且對目標語句1和2，平均被覆蓋的次數(shù)為5×0.5=2.5；目標語句3平均被覆蓋的次數(shù)為7×0.3=2.1；目標語句4平均被覆蓋的次數(shù)為7×0.7=4.9。雖然得到的測試數(shù)據(jù)集不能保證每個測試目標一定會被覆蓋，但可以保證每個測試目標被覆蓋的概率大于設(shè)定的閾值。?

3.權(quán)利要求1中步驟1.2所述的含隨機數(shù)軟件測試數(shù)據(jù)生成問題的隨機優(yōu)化模型，其特征在于給出了目標函數(shù)和約束條件，從而保證可以保障滿足給定的測試充分性準則。?

設(shè)被測程序為G，程序G的的輸入變量分別為x₁,x₂,…,x_l，則程序G的輸入向量X=(x₁,x₂,…,x_l)，G包含m個測試目標λ₁,λ₂,…,λ_m，是一個包含n個測?試數(shù)據(jù)的集合。若以{X₁,X₂,…,X_n}為輸入數(shù)據(jù)運行程序，每個測試目標被覆蓋的概率至少為q，則稱該測試數(shù)據(jù)集的可信度為q。對給定的閾值1-α，{X₁,X₂,…,X_n}是滿足測試準則1的測試數(shù)據(jù)，當且僅當其可信度q≥1-α。另外，q的值越大，該測試數(shù)據(jù)集就越接近測試充分性準則1的要求。因此，測試數(shù)據(jù)集{X₁,X₂,…,X_n}的可信度是需要進行優(yōu)化的目標。?

設(shè)以X_i為輸入運行程序時，T_j被執(zhí)行的概率為那么運行測試數(shù)據(jù)集{X₁,X₂,…,X_n}的所有元素后，T_j至少被執(zhí)行一次的概率：測試數(shù)據(jù)集{X₁,X₂,…,X_n}的可信度為我們就把q的值作為決策變量S={X₁,X₂,…,X_n}的目標函數(shù)，記為f(X₁,X₂,…,X_n)，即?

對給定的測試目標T₁,T₂,…,T_m，滿足步驟1.1的準則的測試數(shù)據(jù)生成問題優(yōu)化模型如下：?

其中。

4.權(quán)利要求1中步驟1.3所述對隨機性軟件測試數(shù)據(jù)生成問題的進化求解方法，其特征在于以下步驟：?

步驟4.1：個體表示方法?

在遺傳算法中，所求問題的一個可能解稱為一個個體。在本發(fā)明中，優(yōu)化問題(3)的決策變量是一個包含n個測試數(shù)據(jù)的集合{X₁,X₂,…,X_n}，因此，使用進化方法對該問題進行求解時，{X₁,X₂,…,X_n}就是一個個體，其中每個X_i對應(yīng)被測程序的一個輸入。設(shè)X_i=(x_i1,x_i2,…,x_il)，那么個體{X₁,X₂,…,X_n}可以用一個n×s的矩陣來表示：?

其中，每個輸入變量x_ij采用實數(shù)或二進制編碼，根據(jù)輸入變量的類型決定。?

步驟4.2：個體適應(yīng)值?

個體{X₁,X₂,…,X_n}的目標函數(shù)如式(3)所示。但是，一般情況下要確定的值并不容易，因此，直接利用式(3)計算個體適應(yīng)值不太現(xiàn)實。下面給出個體適應(yīng)值的近似計算方法。?

我們由以下引理和定理：?

引理1其中0≤x_i≤1,i=1,…,n。?

定理1其中

令表示隨機從{X₁,X₂,…,X_N}中任取一個測試數(shù)據(jù)運行程序后能夠覆蓋測試目標T_j的概率，則

由定理1，個體{X₁,X₂,…,X_N}的可信度因此，可以用q'代替q作為對個體{X₁,X₂,…,X_N}的評價。但是，q'的真值依然不好得到。下面給出q'的估計值。?

設(shè)Y_j表示集合{X₁,X₂,…,X_N}中能夠覆蓋測試目標T_j的元素個數(shù)。令?

則Y_j=Z_1j+Z_2j+…+Z_Nj。故?

因此，是的無偏估計量，記為f_e(T_j)。我們可以用f_e(T_j)作為對p(T_j)的估計值。這樣，個體{X₁,X₂,…,X_N}的適應(yīng)值就轉(zhuǎn)化為?

步驟4.3：遺傳操作?

（1）交叉算子?

這里采用單點交叉的方式。設(shè)M₁和M₂是兩個個體，隨機選擇兩個隨機數(shù)H和L，其中1≤H≤n，1≤L≤l。令?

其中，M(i,j)表示矩陣M的第i行第j列元素。這樣，可以得到兩個新個體M'₁和M'₂。?

（2）變異算子?

這里采用兩種變異方式，一種是常規(guī)變異，一種是拉伸變異。?

常規(guī)變異：設(shè)M是一個個體，隨機選擇四個隨機數(shù)H₁、H₂、L₁和L₂，其中1≤H₁,H₂≤n，1≤L₁,L₂≤l。對滿足H₁≤i≤H₂且L₁≤j≤L₂的個體x_ij實施變異。具體的變異方式根據(jù)個體的編碼方式?jīng)Q定。?

拉伸變異：設(shè)M={X₁,X₂,…,X_n}是一個包含n個輸入的測試數(shù)據(jù)集，隨機生成k個新的輸入數(shù)據(jù)X_n+1,…,X_n+k，令M'={X₁,X₂,…,X_n,X_n+1,…,X_n+k}，則稱這種變異方法為拉伸變異，而M'是由M經(jīng)過拉伸變異得到的新個體，k稱為拉伸強度。?

需要指出的是，本算法中，每一代個體都要實施常規(guī)變異，而拉伸變異用于改變測試數(shù)據(jù)集的容量，只有在合適的時機才會實施該種變異。?

(3)選擇算子?

本算法中的個體是一個集合。為了減少計算量并加快算法收斂速度，我們采用貪心方式對個體進行選擇。設(shè)第i代種群為Pop_i，經(jīng)過交叉、變異后得到的新個體組成的集合為Pop'_i，令Total=Pop_i∪Pop'_i，再從Total中選擇最好的個體組成下一代種群Pop_i+1。?

步驟4.4：算法終止條件?

對給定的閾值1-α，由4.2節(jié)討論可知，要使個體{X₁,X₂,…,X_n}的可信度q≥1-α，只需令則得到?

(1-(1-p)ⁿ)≥1-α?

解得：?

也就是說，對給定的n，要使個體{X₁,X₂,…,X_n}的可信度達到給定的閾值1-α，只要保證?這里

基于以上討論，算法的終止條件為：達到給定的閾值，或者算法運行到最大代數(shù)。?