基于適應(yīng)度函數(shù)的聯(lián)鎖軟件測(cè)試用例生成仿真

劉 明，王新強(qiáng)

(天津中德應(yīng)用技術(shù)大學(xué)軟件與通信學(xué)院，天津 300350)

1 引言

聯(lián)鎖軟件的可靠性影響著系統(tǒng)的安全，其錯(cuò)誤輸出可能會(huì)導(dǎo)致重大事故。但開發(fā)過程中，軟件缺陷是難以避免的，通常由軟件說明不夠詳細(xì)造成的錯(cuò)誤、開發(fā)人員考慮不周引發(fā)的失誤兩種。軟件測(cè)試是確保其安全的關(guān)鍵方法，但傳統(tǒng)人工測(cè)試會(huì)過度依賴測(cè)試員經(jīng)驗(yàn)，測(cè)試質(zhì)量不能得到保障。因此，研究一種可靠的軟件測(cè)試用例生成方法對(duì)確保聯(lián)鎖系統(tǒng)安全具有現(xiàn)實(shí)意義。

不同學(xué)者從以下角度探究如何生成測(cè)試用例：王微微[1]等人基于遺傳算法，將種群并行化計(jì)算應(yīng)用到用例生成中，設(shè)計(jì)線程池與邏輯結(jié)構(gòu)，實(shí)現(xiàn)種群個(gè)體在軟件上的覆蓋計(jì)算，高效生成測(cè)試用例。徐鵬[2]等人利用神經(jīng)網(wǎng)絡(luò)算法，通過樣本訓(xùn)練網(wǎng)絡(luò)結(jié)構(gòu)特征，結(jié)合隨機(jī)變異算法構(gòu)建自動(dòng)生成模型，有效改善測(cè)試模型結(jié)構(gòu)復(fù)雜等缺陷。但是在聯(lián)鎖系統(tǒng)中，軟件功能類型眾多，測(cè)試內(nèi)容復(fù)雜，且部分軟件功能根本無需測(cè)試，如果測(cè)試全部功能，不僅增加執(zhí)行成本，還會(huì)浪費(fèi)時(shí)間，占用較多的系統(tǒng)內(nèi)存。因此，為了更好地反映系統(tǒng)實(shí)際使用情況，本文利用日志挖掘算法獲取用戶端的日志信息[3]，分析用戶實(shí)際操作需求，針對(duì)這些需求通過遺傳算法生成測(cè)試用例[4]。這樣不但減少測(cè)試開銷，還能提高測(cè)試效率。遺傳算法可準(zhǔn)確模仿生物進(jìn)化過程，可以很好地處理非線性問題[5]，在每一次進(jìn)化過程中都能及時(shí)調(diào)整變異率，優(yōu)化搜索方向，在測(cè)試用例生成過程中有較強(qiáng)的適用性。

2 聯(lián)鎖系統(tǒng)軟件結(jié)構(gòu)分析

軟件是聯(lián)鎖系統(tǒng)的“大腦”，可接收各方面的反饋信息，結(jié)合信息內(nèi)容傳輸指令，進(jìn)而控制聯(lián)鎖系統(tǒng)。聯(lián)鎖軟件具體結(jié)構(gòu)如圖1所示。

圖1 軟件結(jié)構(gòu)組成示意圖

由聯(lián)鎖軟件具體結(jié)構(gòu)可知，其主要執(zhí)行的功能有：

1)信息顯示：利用大屏幕顯示器顯示所有操作信息、設(shè)備運(yùn)行信息、系統(tǒng)工作情況以及故障預(yù)警信息。

2)聯(lián)鎖控制：列車線路安排、完成閉鎖與解鎖道岔、自動(dòng)關(guān)閉和開啟信號(hào)燈。

3)保存用戶操作記錄：聯(lián)鎖軟件具備強(qiáng)大的儲(chǔ)存功能，且可隨時(shí)提供用戶歷史操作記錄[7]。

3 基于日志挖掘的聯(lián)鎖軟件測(cè)試用例生成

3.1 日志挖掘過程

通過分析聯(lián)鎖軟件組成結(jié)構(gòu)可知，其能保存用戶操作數(shù)據(jù)，生成對(duì)應(yīng)日志信息。本文正是通過日志挖掘來生成測(cè)試用例的，經(jīng)過采集、預(yù)處理和模式識(shí)別等過程[8]，挖掘用戶行為模式與聯(lián)鎖系統(tǒng)功能的使用情況，掌握用戶操作行為，根據(jù)挖掘結(jié)果確定測(cè)試項(xiàng)目，提高軟件用戶友好度，生成更加有針對(duì)性的測(cè)試用例，大大減少測(cè)試開銷。日志挖掘過程主要包括以下幾個(gè)步驟：

1)日志采集

在聯(lián)鎖系統(tǒng)的磁盤中，隨機(jī)采集初始日志數(shù)據(jù)，此步驟是日志挖掘的必然前提。

2)數(shù)據(jù)清洗

初始日志數(shù)據(jù)無法直接進(jìn)行挖掘，其中包括大量冗余信息，為提高日志質(zhì)量，本文利用支持向量機(jī)算法辨別日志，刪除冗余數(shù)據(jù)。具體做法為：假設(shè)存在某日志樣本訓(xùn)練集合{(x1，y1)，(x2，y2)，…，(xn，yn)}，其中xi表示輸入向量，yi代表類別標(biāo)志，如果前t-1個(gè)樣本屬于正例集合P，其它樣本組成沒有標(biāo)注的數(shù)據(jù)集合U。結(jié)合支持向量機(jī)相關(guān)原理[9]，將數(shù)據(jù)分類過程表示為

(1)

該分類過程的約束條件如下

(2)

式中，w屬于一個(gè)參量，該值越大說明分類界限越明顯，ξi代表松弛變量，b?R表示偏置，C為懲罰系數(shù)，C值越大，邊界越小。經(jīng)過上述處理后初始日志數(shù)據(jù)被分為有用和冗余兩類，刪除冗余數(shù)據(jù)，將剩余數(shù)據(jù)作為日志挖掘目標(biāo)，提高日志挖掘質(zhì)量。

3)頻繁模式挖掘

經(jīng)過數(shù)據(jù)處理后，利用頻繁模式發(fā)掘算法完成日志挖掘。該步驟的目的是構(gòu)建頻繁路徑和測(cè)試用例之間的相對(duì)關(guān)系[10]，同時(shí)賦予測(cè)試用例相關(guān)支持度。日志挖掘過程描述如下：

假設(shè)I={I1，I2，…，In}表示一系列日志項(xiàng)集，事務(wù)集合為T={t1，t2，…，tn}，其中ti∈I(1≤i≤n)，n表示某事務(wù)集內(nèi)含有項(xiàng)的個(gè)數(shù)。針對(duì)隨機(jī)事物T，都有T∈I。TDS={T1，T2，…，Tn}代表事務(wù)數(shù)據(jù)流，且T1與Tn分別描述最早和最近產(chǎn)生的事務(wù)。

在T中，隨機(jī)選取某數(shù)據(jù)項(xiàng)ti，令其出現(xiàn)概率為pi，表現(xiàn)為二元組形式為〈ti，pi(T)〉，如果pi=0，說明T中沒有數(shù)據(jù)項(xiàng)ti。

如果H={〈hi，pi(T)〉|1≤i≤k|}表示由k個(gè)數(shù)據(jù)項(xiàng)構(gòu)成的集合，則認(rèn)為H是k-項(xiàng)集。如果H?Ti，則項(xiàng)集H在Ti上的理想支持度如下[11]

(3)

分析不確定樣本流特征，設(shè)定滑動(dòng)窗口[12]為τ=(τ1，τ2，…，τn)，如果僅挖掘最近窗口內(nèi)的頻繁項(xiàng)集，則窗口中最新與最舊事務(wù)分別表示為Tv、Tu，且滿足u

(4)

已知最小理想支持度閾值κ，?H?I，如果Sup(H，τ)<δ，則項(xiàng)集H即為窗口中的頻繁項(xiàng)集。

經(jīng)過上述頻繁模式挖掘，獲取聯(lián)鎖系統(tǒng)用戶的操作行為，根據(jù)挖掘結(jié)果可確定需要測(cè)試的項(xiàng)目。

3.2 測(cè)試項(xiàng)與測(cè)試準(zhǔn)則確定

測(cè)試用例的主要作用就是完成聯(lián)鎖系統(tǒng)中各項(xiàng)操作項(xiàng)目的性能測(cè)試以及結(jié)果分析。通過日志挖掘，現(xiàn)階段測(cè)試項(xiàng)目主要包括的內(nèi)容如表1所示。

表1 測(cè)試項(xiàng)目表

如表1所示，測(cè)試項(xiàng)目共包括11項(xiàng)內(nèi)容，這些項(xiàng)目都對(duì)聯(lián)鎖系統(tǒng)的安全性起決定性作用。因此，為提高測(cè)試用例的覆蓋率，需要制定覆蓋準(zhǔn)則[13]，保證測(cè)試的充分性。

1)語句覆蓋

該標(biāo)準(zhǔn)代表生成的用例集合，可以被測(cè)試樣本中全部可操作的語句均執(zhí)行一次，其覆蓋程度可通過覆蓋率描述

(5)

式中，Sexe代表被覆蓋的語句集合，Si為全部無法執(zhí)行的語句集合，Stot描述被測(cè)目標(biāo)中全部語句集合。

2)分支覆蓋

此準(zhǔn)則是在滿足語句覆蓋基礎(chǔ)上制定的，將被判定為真或假的分支再繼續(xù)執(zhí)行一遍，避免出現(xiàn)漏檢現(xiàn)象，覆蓋率表達(dá)式如下

(6)

式中，Dexe代表被操作覆蓋到的分支集合，Dtot為全部分支總和，Di是沒有經(jīng)過判定的集合。

3.3 測(cè)試用例生成

基于上述測(cè)試準(zhǔn)則，根據(jù)日志挖掘獲取的測(cè)試項(xiàng)目，利用遺傳算法遍歷所有樣本集合，生成測(cè)試用例。主要過程如下。

1)編碼方式

通過遺傳算法解決實(shí)際問題時(shí)，需構(gòu)建編碼策略，其影響著交叉算子結(jié)構(gòu)，決定著遺傳操作性能。本文使用二進(jìn)制編碼方式，將0和1當(dāng)作構(gòu)成基因的單元，生成二進(jìn)制位串描述基因型。

假設(shè)某參數(shù)β滿足的取值條件為{β|βmin≤β≤βmax}，此時(shí)存在2L種編碼策略，L代表位串長(zhǎng)度，則不同編碼方式存在如下映射關(guān)系

(7)

式中，λ表示編碼精度。與編碼策略對(duì)應(yīng)的解法方式為

(8)

2)適應(yīng)度函數(shù)選取

適應(yīng)度函數(shù)[14]選取是否科學(xué)影響著搜索性能，遺傳算法利用優(yōu)勝劣汰的個(gè)體篩選思想，必須對(duì)所有個(gè)體作適應(yīng)性評(píng)價(jià)。本文通過目標(biāo)函數(shù)轉(zhuǎn)化方式得到適應(yīng)度函數(shù)。

目標(biāo)函數(shù)的極大值優(yōu)化問題表示為

(9)

式中，Cmin屬于一個(gè)系數(shù)，通常為g(x′)進(jìn)化時(shí)出現(xiàn)的極小值。

目標(biāo)函數(shù)的極小值優(yōu)化問題描述為

(10)

式中，Cmax同樣是一個(gè)系數(shù)，表示g(x′)進(jìn)化時(shí)出現(xiàn)的最大值。

上述適應(yīng)度函數(shù)綜合了多方面考慮，能夠提高搜索效率和全面性。

3)遺傳算子選取

將所有個(gè)體的適應(yīng)度值當(dāng)作一個(gè)圓形輪盤，利用隨機(jī)輪盤賭方式選取扇形區(qū)域個(gè)體[15]。如果種群規(guī)模是Q，其中個(gè)體o的適應(yīng)度值表示為fo，則該個(gè)體被選中繼續(xù)參與遺傳過程的概率ρo為

(11)

綜合上述所有步驟，建立如圖2所示的測(cè)試用例生成模型。

圖2 測(cè)試用例生成模型圖

由圖2可知，算法搜索過程即為測(cè)試用例生成過程，在每次進(jìn)化中，不斷調(diào)整交叉與變異率，優(yōu)化搜索方向。

4 仿真數(shù)據(jù)分析與研究

為分析該方法的優(yōu)勢(shì)和不足，搭建仿真平臺(tái)。通過在控制器上安裝仿真軟件，與聯(lián)鎖軟件共同組成實(shí)驗(yàn)平臺(tái)的下位機(jī)，同時(shí)在操作層增加測(cè)試設(shè)備，形成上位機(jī)。在仿真系統(tǒng)中，上位機(jī)的任務(wù)是控制系統(tǒng)流程，下位機(jī)則需實(shí)現(xiàn)現(xiàn)場(chǎng)信號(hào)的仿真。仿真系統(tǒng)結(jié)構(gòu)如圖3所示。

圖3 仿真系統(tǒng)結(jié)構(gòu)示意圖

首先，選取一個(gè)大規(guī)模聯(lián)鎖軟件，分別向兩個(gè)軟件中植入錯(cuò)誤程序，不同測(cè)試時(shí)間植入的錯(cuò)誤數(shù)量不同(10秒10個(gè)、20秒15個(gè)，30秒20個(gè)，40秒25個(gè)，50秒30個(gè))。利用本文方法、遺傳算法與神經(jīng)網(wǎng)絡(luò)算法生成測(cè)試用例，分析不同類型聯(lián)鎖軟件下有效檢測(cè)出錯(cuò)誤程序的次數(shù)。仿真結(jié)果如圖4所示。

圖4 不同算法檢測(cè)結(jié)果圖

分析圖4可知，針對(duì)同一個(gè)聯(lián)鎖軟件，利用不同算法生成的測(cè)試用例對(duì)其錯(cuò)誤程序檢測(cè)，當(dāng)錯(cuò)誤注入數(shù)量較少時(shí)，三種方法都能全面檢測(cè)出錯(cuò)誤程序。隨著仿真時(shí)間的增加，錯(cuò)誤數(shù)量越來越多，只有本文方法始終保持較高的檢出率，其它兩種方法均存在漏檢現(xiàn)象。這是因?yàn)楸疚姆椒ㄟm應(yīng)度函數(shù)設(shè)置合理，提高算法搜索能力，能夠更加全面地測(cè)試出軟件中的錯(cuò)誤。

當(dāng)算法對(duì)于軟件注入的錯(cuò)誤檢出率相同時(shí)，將檢測(cè)出的錯(cuò)誤重復(fù)次數(shù)百分比(APDTFD)作為評(píng)價(jià)指標(biāo)，累計(jì)發(fā)現(xiàn)重復(fù)錯(cuò)誤次數(shù)越多，表明算法性能越好。該指標(biāo)計(jì)算公式如下：

(12)

式中，N表示測(cè)試用例總數(shù)，Nk代表用例k檢測(cè)出的新錯(cuò)誤程序數(shù)量，Dk指用例k重復(fù)發(fā)現(xiàn)錯(cuò)誤的次數(shù)，F(xiàn)描述用例檢測(cè)出全部錯(cuò)誤的次數(shù)，既包含新錯(cuò)誤，也含有重復(fù)錯(cuò)誤。

在實(shí)驗(yàn)條件相同的情況下，上述三種算法的APDTED指標(biāo)的仿真結(jié)果如圖5所示。

圖5 不同算法APDTED指標(biāo)性能對(duì)比圖

如圖5所示，隨著仿真時(shí)間的增加，注入的錯(cuò)誤數(shù)量也隨著增加，不同方法的APDTED指標(biāo)均呈現(xiàn)上升趨勢(shì)。但所提方法的指標(biāo)值最高，說明生成的測(cè)試用例有很好地重復(fù)發(fā)現(xiàn)錯(cuò)誤的性能，這會(huì)大大降低誤檢率，因?yàn)楫?dāng)更多的測(cè)試用例都檢測(cè)出某程序存在錯(cuò)誤時(shí)，表明該程序一定為錯(cuò)誤程序。因此，所提方法的檢測(cè)結(jié)果更具科學(xué)性。

最后，利用上述三種生成的測(cè)試用例測(cè)試相同聯(lián)鎖軟件，對(duì)于軟件中的不同測(cè)試項(xiàng)，不同方法的測(cè)試時(shí)間如表2所示。

表2 不同測(cè)試用例測(cè)試時(shí)間對(duì)比表

表2顯示，對(duì)于全部測(cè)試項(xiàng)目而言，利用本文方法測(cè)試聯(lián)鎖軟件性能時(shí)，可減少測(cè)試時(shí)間，能在更短時(shí)間內(nèi)獲取測(cè)試結(jié)果。這是因?yàn)楸疚睦昧巳罩就诰蛩惴?，了解用戶需求，更加快速地生成測(cè)試用例，使檢測(cè)更具有針對(duì)性，減少不必要的測(cè)試過程，降低時(shí)間開銷。

5 結(jié)論

為滿足聯(lián)鎖軟件安全性能極高的要求，本文將日志挖掘與遺傳算法相結(jié)合，生成軟件測(cè)試用例。通過日志挖掘分析用戶需求，減少非必要的測(cè)試項(xiàng)目生成，利用遺傳算法，設(shè)置目標(biāo)函數(shù)，經(jīng)過全局搜索，生成測(cè)試用例。仿真結(jié)果表明，所提方法不但漏檢率低，還能減少時(shí)間開銷。但本文只研究了如何生成測(cè)試序列，并沒有生成測(cè)試腳本。因此，將測(cè)試用例變換為可執(zhí)行腳本是下一步研究的主要方向。