敏感變量和感知機結(jié)合的測試預言生成方法?

馬春燕,李尚儒,王慧朝,張 磊,張 濤

(西北工業(yè)大學 軟件與微電子學院,陜西 西安 710072)

軟件測試是保證軟件系統(tǒng)質(zhì)量的主要活動.在軟件測試中,測試預言的作用至關(guān)重要,它是一種判斷程序在給定測試輸入下的執(zhí)行結(jié)果是否符合預期的方法.測試預言的質(zhì)量直接影響測試活動的有效性和軟件系統(tǒng)的質(zhì)量.目前,雖然研究人員已提出了各種自動化測試輸入生成技術(shù),成果頗豐,但是測試預言問題仍然被公認為是軟件測試中最難解決的問題之一[1].

測試預言問題的綜述文獻[1]將測試預言生成的研究分為基于軟件形式化規(guī)格說明或形式化模型(例如狀態(tài)機或時序邏輯規(guī)范等)的測試預言生成方法(317篇相關(guān)論文)、基于各種軟件制品(例如需求和設(shè)計文檔、軟件執(zhí)行的屬性信息、軟件其他版本等)的測試預言生成方法(245篇相關(guān)論文)、基于常識或隱含的知識生成測試預言(76篇相關(guān)論文)這3類.第1類需要軟件開發(fā)人員或測試人員給出軟件的形式化規(guī)格說明,人工參與的工作量較大,形式化規(guī)格說明缺乏以及程序行為描述不全面等,是該類方法面臨的極大挑戰(zhàn);第2類研究克服了第1類研究面臨的挑戰(zhàn),正在成為一個活躍的研究方向,主要研究包括基于規(guī)格說明或編程接口挖掘的方法、基于程序文檔的挖掘方法、蛻變測試、基于源碼的靜態(tài)和動態(tài)分析方法以及基于機器學習的方法等,該類測試預言的生成方法包括全自動的方法或人工輔助的半自動化方法,其中,半自動化方法較多;第3類應(yīng)用領(lǐng)域較窄,僅針對特種類型或特定的應(yīng)用范圍的軟件.

智能化技術(shù)在測試預言生成方面的應(yīng)用研究具有鮮明的學科交叉特點,目前研究成果相對較少,上述第 2類測試預言生成方法的研究中逐步開始出現(xiàn)智能化技術(shù)的應(yīng)用.本文的工作屬于無需測試人員干預的測試預言自動生成方法,借助揭示成功和失敗概率的敏感變量,采用監(jiān)督的機器學習算法——線性感知機作為測試預言自動生成的模型,收集部分測試用例的語句覆蓋、不同斷點處的內(nèi)存變量及其取值的集合等數(shù)據(jù)信息作為訓練集,觀察新測試用例執(zhí)行的相應(yīng)語句覆蓋和內(nèi)存變量集等信息,對該新測試用例在不同斷點處的執(zhí)行結(jié)果是成功還是失敗進行預測,自動生成測試預言.本文成果可以形成測試用例集合構(gòu)造的“滾雪球效應(yīng)”,不斷迭代自動生成新測試用例或回歸測試用例的測試預言.

本文第 1節(jié)首先給出相關(guān)定義和假設(shè),在此基礎(chǔ)上,給出求解斷點處敏感變量集的算法,并應(yīng)用線性感知機算法求解斷點處成功或故障概率的門限值,提出本文的測試預言生成算法.第2節(jié)對算法進行討論.第3節(jié)給出實驗對象和實驗方法.第4節(jié)通過案例對算法進行闡釋和驗證.第5節(jié)將已有研究工作進行總結(jié),并與本文工作進行對比分析.

1 測試預言自動生成方法

1.1 相關(guān)定義

本文測試預言生成方法用到的定義如下.

定義 1(測試用例ta和tb的相似度Sim(ta,tb)).設(shè)測試用例ta和tb執(zhí)行的語句集合分別為A(其元素個數(shù)記作|A|)和B(其元素個數(shù)記作|B|),|A∩B|表示A與B交集的元素個數(shù),則ta和tb的相似度定義為Sim(ta,tb)=2×|A∩B|/(|A|+|B|)∈[0,1].Sim(ta,tb)的值越大,ta和tb的相似度越高:如果A=B,則Sim(ta,tb)=1,ta和tb的相似度最高;如果A∩B=?,則Sim(ta,tb)=0,ta和tb的相似度最低.

定義2(內(nèi)存變量).內(nèi)存變量是一個二元式[var,val],其中,var表示變量名,val表示該變量的值.

定義3(兩個內(nèi)存變量相等).兩個內(nèi)存變量[vara,vala]和[varb,valb]相等當且僅當vara=varb和vala=valb.

定義4(兩個內(nèi)存變量集合M和N的交集).兩個內(nèi)存變量集合M和N的交集記作M∩N,定義為M與N中相等的內(nèi)存變量的集合.

定義5(兩個內(nèi)存變量集合M和N的差集).兩個內(nèi)存變量集合M和N的差集記作M-N,定義為與N中變量名相同而變量值不同的M中內(nèi)存變量的集合.

定義6(敏感變量的定義).一個敏感變量t是一個內(nèi)存變量二元式t=[sv,v],其中,sv表示敏感變量的名字,v表示敏感變量的值.

1.2 相關(guān)假設(shè):

根據(jù)程序測試和調(diào)試經(jīng)驗,本文的算法思想基于下述基本假設(shè).

· 假設(shè)1:變量集對成功和失敗具有一定的揭示能力.

對于高相似度的測試用例(見定義1)形成的一個集合St而言,在每個斷點處,St中測試用例執(zhí)行的變量集合的交集或差集對程序執(zhí)行的成功概率或失敗概率具有一定的揭示能力.

· 假設(shè)2:不同斷點處變量集合對成功或故障的揭示能力不同.

因為故障發(fā)生程序的某個位置且故障有傳播能力,斷點位置越靠后,其相應(yīng)變量集合對成功或故障的揭示能力逐步增強.

1.3 測試預言生成算法

已知一個程序、一個測試用例集合及各測試用例執(zhí)行成功或失敗的信息,本文通過在程序中設(shè)置批量斷點的方法收集所有測試用例在各斷點處的內(nèi)存數(shù)據(jù)以及代碼覆蓋信息作為訓練集;然后根據(jù)新測試用例的執(zhí)行,計算各斷點處的敏感變量集合,并應(yīng)用線性感知機算法計算該斷點處執(zhí)行失敗或成功概率的門限值;在此基礎(chǔ)上,本節(jié)給出了一種基于內(nèi)存分析的測試預言自動生成方法,即對新產(chǎn)生的測試用例執(zhí)行同一程序的運行結(jié)果是成功還是失敗進行預測,自動生成測試預言(見下文算法1).為了闡述本文提出的測試預言生成算法,表1給出了算法中涉及的符號名稱及其含義描述.

Table 1 Notations and their meanings in this section's algorithm表1 本節(jié)算法中涉及的符號名稱及其含義描述

1.3.1 算法1:測試預言生成算法

給定P,ST,SB和tnew的測試輸入t,首先計算ST中與tnew最相似的測試用例集合STtnew(見下述算法1偽代碼中的第1行～第20行).將獲得的STtnew分為最相似成功測試用例集SPTtnew和失敗測試用例集SFTtnew,調(diào)用后文算法2計算SB中每個斷點處的敏感變量集.

· 如果SPTtnew≠?,SFTtnew≠?,求得的敏感變量的含義為:從所有與tnew相似正確測試用例和失敗測試用例的執(zhí)行來看,可能錯誤的內(nèi)存變量有哪些,在這種情況下,敏感變量稱為“故障敏感變量”;

· 如果SPTtnew≠?,SFTtnew=?,求得的敏感變量的含義為:從所有與tnew相似的正確測試用例的執(zhí)行來看,可能正確的內(nèi)存變量有哪些,在這種情況下,敏感變量稱為“成功敏感變量”;

· 如果SPTtnew=?,SFTtnew≠?,求得的敏感變量的含義為:從所有與tnew相似的失敗測試用例的執(zhí)行來看,可能錯誤的內(nèi)存變量有哪些,在這種情況下,敏感變量稱為“故障敏感變量”.

然后調(diào)用后文算法3,計算bi處的門限值Thresholdbi,根據(jù)算法1的第21行～第79行陸續(xù)計算各斷點處程序執(zhí)行成功的概率PP1,PP2,PP3,…,PPm.

最后,對于序列PP1,PP2,PP3,…,PPm,用等差序列作為對預測結(jié)果影響所占的權(quán)重,分別記為a1,a2,a3,…,am,則等差數(shù)列的公差為d=(am-a1)/(m-1),可以求得該等差數(shù)列首項a1=1/m-(am-a1)/2=3/4m,其余各項為ai=a1+(i-1)d,測試用例執(zhí)行程序P成功的概率為PP=PP1*a1+PP2*a2+…+PPm*am.

算法1的偽代碼如下所示(第1行～第86行).

算法1.GeneratingTestOracles.

1.3.2 算法2:敏感變量集求解算法

給定輸入P,SPTtnew,SFTtnew以及SB中第i個斷點bi,設(shè)兩個臨時變量ST1和ST2.

· 如果SPTtnew≠?,SFTtnew≠?,則令ST1=SPTtnew,ST2=SFTtnew;

· 如果SPTtnew≠?,SFTtnew=?,則令ST1=SPTtnew,ST2=SPTtnew;

· 如果SPTtnew=?,SFTtnew≠?,則令ST1=SFTtnew,ST2=SFTtnew.

令x=|ST1|,y=|ST2|,首先計算得到個內(nèi)存變量集合{dj1,dj2,dj3,…,djy},將其存入哈希表Dpj,其中,djk(1≤k≤y)作為哈希表的key(記作djk.key),該內(nèi)存變量出現(xiàn)的次數(shù)作為哈希表的value(記作djk.value)

然后,可計算得到的x個哈希表Dp1,Dp2,Dp3,…,Dpx,計算哈希表Hbi=Dp1∪Dp2∪…∪DpX,其中,∪表示的含義為:各個Dpj(1≤j≤|SFTtnew|)中,key不同則合并;key相同,則value相加.

最后對Hbi中各value值從大到小排序,key值為前20%的變量(取key值較大的變量作為敏感變量)加入SBbi,算法結(jié)束,返回SBbi.

算法2的偽代碼如下所示(第1行～第29行).

算法2.CalculateSensitiveVariabls.

1.3.3 算法3:應(yīng)用線性感知機算法求解每個斷點處門限值

給定輸入P,SPTtnew,SFTtnew,bi以及SBbi,首先初始化候選門限值二維數(shù)組temp[][]為 0,兩維數(shù)組長度都為SPTtnew∪SFTtnew中測試用例個數(shù).對于SPTtnew∪SFTtnew中每個測試用例tk(1≤k≤|SPTtnew∪SFTtnew|),將其作為一個新測試用例,分別計算temp的第k行元素,根據(jù)“測試預言生成算法”,對于SPTtnew∪SFTtnew中每個測試用例tk(1≤k≤|SPTtnew∪SFTtnew|),將其作為一個新測試用例tnew;計算每個候選門限值的預測成功率,將temp中預測準確率最大的候選門限值存入Thresholdbi,算法結(jié)束,返回Thresholdbi.

算法3的偽代碼如下所示(第1行～第34行).

算法3.Threshold.

2 實驗對象及實驗方法

本文采用SIR(software-artifact infrastructure repository)知識庫[2]提供的5個C程序?qū)嶒瀸ο蠛蛷拈_源網(wǎng)站travis-ci上下載的兩個C程序?qū)嶒瀸ο骵xpresstionParser和sort(網(wǎng)址:https://travis-ci.org/swenson/),通過實際案例程序闡釋本文給出的測試預言自動生成方法的有效性.表2給出了實例驗證過程中所使用的每個案例名、功能、故障版本數(shù)、測試用例數(shù)以及正確版本的源碼行數(shù)等信息.

Table 2 Experimental objects表2 實驗對象

為了將提出的測試預言生成算法進行實踐,本文開發(fā)了圖1所示的實驗輔助工具,工具的開發(fā)環(huán)境是Ubuntu Linux 10.04.為了方便與SQLite數(shù)據(jù)庫以及GDB調(diào)試集成,本文應(yīng)用Python語言和shell script實現(xiàn)工具的開發(fā),輔助工具源碼TestOracleGen.rar在https://github.com/machunyan/LCEC網(wǎng)站上可以公開下載.工具的主要模塊功能闡述如下.

1)程序代碼分析模塊.該模塊負責分析源文件,根據(jù)斷點的設(shè)置原則進行斷點標注(本文實驗過程中設(shè)置的斷點設(shè)置原則為:以return和exit作為結(jié)束的行,本實驗輔助工具允許用戶批量自定義斷點位置),為程序執(zhí)行以及執(zhí)行過程中調(diào)用GDB命令獲取內(nèi)存數(shù)據(jù)做準備.

2)程序執(zhí)行分析模塊.該模塊運行每一個測試用例,在程序運行過程中獲取斷點處程序執(zhí)行的內(nèi)存變量集,并通過gcov軟件獲取每個測試用例運行時的程序覆蓋信息.

3)數(shù)據(jù)存儲模塊.該模塊將程序代碼分析模塊和程序執(zhí)行分析模塊得到的斷點信息和測試用例的執(zhí)行覆蓋信息存入數(shù)據(jù)庫.在分析所有測試用例執(zhí)行覆蓋的基礎(chǔ)上,對不同覆蓋進行分類,計算測試用例之間執(zhí)行覆蓋的聯(lián)系.

4)預言模塊.該模塊根據(jù)上述 3個模塊收集的故障程序的斷點信息、測試用例運行故障程序時所有斷點的內(nèi)存變量信息以及執(zhí)行語句覆蓋信息,執(zhí)行第 1.3節(jié)中的測試預言生成算法,對測試用例運行同一故障程序的運行結(jié)果是成功還是失敗進行預測.

Fig.1 Assistant tool framework for experiments圖1 實驗工具總體架構(gòu)

采用該實驗輔助工具的具體實驗步驟如下.

1)將工具復制到需要進行測試預言生成的測試程序所在的文件夾中.

2)在測試程序的文件夾中建立output文件夾,用于存放程序的執(zhí)行覆蓋文件cov_result和mod_classify_result.

3)將已知執(zhí)行結(jié)果的所有測試用例存放在文件trainset中.

4)運行數(shù)據(jù)收集程序 train.sh,輸入?yún)?shù)為已知結(jié)果的測試用例存放的文件名、測試程序?qū)ο竺y試故障程序版本號.數(shù)據(jù)收集程序執(zhí)行完成后,將收集的所有數(shù)據(jù)信息存放于數(shù)據(jù)庫中.

5)運行預測程序predict.sh,計算新測試用例的測試預言.

3 實驗結(jié)果及分析

3.1 實驗對象的實驗結(jié)果及分析

Tcas、print_tokens、schedule2、replace、tot_info、expressionParser和 sort共129個故障版本.為每一個故障版本設(shè)計100個新的測試用例(其中,成功和失敗的比率與訓練集一致),計算這100個測試用例預言正確的個數(shù).圖2～圖8分別展示了每類程序所有故障版本的預言正確數(shù)目的折線圖.圖中橫軸表示每類程序的版本號,豎軸表示100個新測試用例使用本文的測試預言自動生成方法預測正確的個數(shù).

Fig.2 Test oracle prediction results of 41 tcas versions圖2 Tcas的41個版本的測試預言預測結(jié)果

Fig.3 Test oracle prediction results of 7 print_tokens versions圖3 Print_tokens的7個版本的測試預言預測結(jié)果

Fig.4 Test oracle prediction results of 10 schedule2 version圖4 Schedule2的10個版本的測試預言預測結(jié)果

Fig.5 Test oracle prediction results of 32 replace versions圖5 Replace的32個版本的測試預言預測結(jié)果

Fig.6 Test oracle prediction results of 23 tot_info versions圖6 Tot_info的23個版本的測試預言預測結(jié)果

Fig.7 Test oracle prediction results of 8 expressionParser versions圖7 ExpressionParser 8個版本的測試預言預測結(jié)果

Fig.8 Test oracle prediction results of 8 sort versions圖8 Sort 8個版本的測試預言預測結(jié)果

程序tcas共有41個故障版本,每個版本運行100個新的測試用例,預測情況如圖2所示.預測效果最差的是V39,91個測試用例預測正確.V3、V7等8個故障版本的100個測試用例全部預測正確.41個tcas版本預言生成的正確率平均為96.3%.

程序print_tokens共有7個故障版本,每個版本運行100個新的測試用例,預測情況如圖3所示.預測效果最差的是版本V4,92個測試用例預測正確.預測正確個數(shù)最多的是版本V2,預測正確95個.7個版本平均預言正確率為93.7%.

程序 schedule2共有 10個故障版本,每個版本運行 100個新的測試用例,預測情況如圖4所示.故障程序schedule2的預測效果比較平均,有8個版本預測正確95個.10個版本平均預言正確率為95.1%.

程序replace共有32個故障版本,每個版本運行100個新的測試用例,預測情況如圖5所示.預測效果最差的是版本V16,93個測試用例預測正確.預測正確個數(shù)最多的是版本V9,預測正確98個.32個版本平均預言正確率為96.1%.

程序tot_info共有23個故障版本,每個版本運行100個新的測試用例,預測情況如圖6所示.預測效果最差的是版本V21,91個測試用例預測正確.預測正確個數(shù)最多的有版本V8,V11和V15,預測正確98個.23個版本平均預言正確率為96.2%.

程序expressionParser,sort各有8個故障版本,每個版本運行100個新的測試用例,預測情況如圖7、圖8所示.8個版本平均預言正確率分別為97.5%和98.6%.

綜上,對129個故障版本,每個版本預言100個測試用例,平均預言正確率為96.2%,說明了本文給出的測試預言自動生成方法預測的有效性.

3.2 實驗結(jié)果與其他相似方法的比較

從采用機器學習、現(xiàn)有測試用例的輸入及執(zhí)行結(jié)果協(xié)助自動生成新測試預言和完全自動化的角度來看,與本文相似的工作有文獻[3-5]等.與他們相比,本文工作的優(yōu)勢如下.

1)本文訓練集數(shù)據(jù)量要求寬松,文獻[5]要求失敗的輸入和成功的輸入各占一半,而且數(shù)據(jù)量偏大,在實際應(yīng)用中不可行.

2)本文測試預言的生成應(yīng)用范圍更廣.針對某個新的測試輸入,上述 3個文獻生成的測試預言準確率完全依賴于訓練集中的測試輸入特征,在具體應(yīng)用中具有一定的局限性和針對性;而本文的方法則是收集訓練集中測試輸入執(zhí)行的語句覆蓋、不同斷點處的內(nèi)存變量及其取值的集合等大量數(shù)據(jù)信息,更能真實反映被測試程序的行為,對于哪些輸入數(shù)據(jù)個數(shù)少、輸入取值有限或程序執(zhí)行是否成功與輸入的對應(yīng)關(guān)系不明顯等的應(yīng)用程序而言,本文的方法皆可應(yīng)用.

3)本文的實證研究更深入和合理.上述文獻的實證研究均通過個別案例程序并注入若干故障來檢測方法的有效性.從故障版本的數(shù)量(共 129版本)、故障類型的數(shù)量(比較和邏輯等各類運算符錯誤、常量賦值錯誤、變量定義錯誤、語句丟失、多余語句、變量賦值錯誤)和產(chǎn)生的測試預言數(shù)量角度,本文的實驗更加深入和合理.

4)測試預言的準確率方面本文有一定優(yōu)勢.從文獻[5]的實驗結(jié)果來看,對于案例Tcas而言,Sir知識庫中有效測試用例共 1 500個,其中成功測試用例約占 85%;該文獻在現(xiàn)有測試用例的基礎(chǔ)上又構(gòu)造了1 500個測試用例作為訓練集,其預測準確率為98.72%;但在1 500個測試數(shù)據(jù)集(還要求成功輸入與失敗輸入數(shù)量相當)的情況下,其預測準確率約為82%(文中未指明是否針對Sir知識庫中41個版本都進行了實驗,也未指明測試預言產(chǎn)生的數(shù)量).而本文針對Tcas的41個版本,每個版本均生成了100個測試輸入的測試預言,平均預測準確率為96.3%,其中,Tcas的第3、7、15、17～20和28這8個版本的預測準確率為 100%.文獻[5]中的其他實驗對象,預測準確率最低為 84.66%.本文在其他實驗對象中,在最少訓練集合1 052個的情況下,預測準確率最低平均為95.1%.

4 方法討論

4.1 方法的實用性

本文提出的測試預言自動生成方法獨立于源代碼,不需要向源代碼中插入任何斷言;獨立于編程語言,對任何一種編程語言都適用,沒有構(gòu)造形式模型的限制,具有很強的靈活性,適用范圍廣.本文的測試預言預測方法也適用于其他編程語言,例如Java和C++語言的程序,但是本文搭建的實驗環(huán)境僅支持C語言程序.

在軟件調(diào)試過程中,程序員需要通過在程序關(guān)鍵語句處加斷點,通過分析和比較部分斷點處的變量取值以及語句執(zhí)行序列等上下文來診斷故障,這是故障診斷的核心行為.所以本文假設(shè)符合實際情況,這一點在文獻[6]的研究成果中也得到印證.

算法1生成的tnew測試預言的有效性與集合T和St密切相關(guān),如果集合T或St的元素個數(shù)非常少,則算法輸出結(jié)果的準確率就會降低.該算法建立在已經(jīng)存在的測試用例集合T之上,要求集合T存在一定數(shù)量.根據(jù)目前程序(C、C++、Java等語言程序)的特點,僅有分支或while循環(huán)的判斷條件可能導致測試用例執(zhí)行的路徑不同,所以在實際求解中,T中與tnew最相似的測試用例集St也會滿足算法求解的要求.

算法1的有效性并不依賴于T中測試用例的類型,并不要求T必須包含成功測試用例或必須包含失敗測試用例.T可以僅包含成功測試用例,也可以僅包含失敗測試用例,也可以既包含成功測試用例又包含失敗測試用例.所以本文訓練集數(shù)據(jù)量要求寬松,并不要求失敗的輸入和成功的輸入各占一半保持均衡.

本文測試預言生成算法在實際項目應(yīng)用中可以迭代“滾雪球”式生成新的高質(zhì)量測試用例.例如在項目真實的測試實踐中,如果已經(jīng)運行了 100個測試用例都執(zhí)行成功,那么對若干新的測試輸入,可以用測試預言生成算法預測他們的輸出成功還是失敗,提示用戶重點關(guān)注預測失敗的新測試輸入的執(zhí)行.

4.2 測試預言生成的準確率問題

本文生成的某個新測試用例tnew的測試預言準確率與下述幾個方面的要素密切相關(guān).

1)給定tnew,與tnew相似測試用例集合St相關(guān),St元素個數(shù)越多,訓練集質(zhì)量越高,預測結(jié)果趨于越精確.

2)與各斷點處敏感變量集的成功或失敗的揭示能力相關(guān),例如枚舉變量、布爾變量及取值為離散值的變量,測試執(zhí)行時,它們的取值較為集中而且重復率較高,所以這些變量一定被作為敏感變量求解出來,他們揭示程序成功或失敗的能力更強.

本文通過分析不同版本的故障發(fā)現(xiàn),如果被測試程序的故障語句是每個測試用例一定執(zhí)行的語句,與tnew相似測試用例個數(shù)較多,我們的方法生成測試預言的準確率為100%,例如Tcas的V3、V7等V8版本.如果被測試程序的故障語句是if或 while中的語句,其對于測試輸入集合而言,故障語句未必遇到每個測試用例都執(zhí)行,故障語句執(zhí)行次數(shù)越少,預測準確率就越低.主要原因是故障語句執(zhí)行次數(shù)少,導致與預測測試用例高度相似的測試用例過少,并且故障敏感變量的影響指標(揭示成功或失敗的能力)明顯下降,例如 print_tokens的故障版本v4、tcas的故障版本v33和replace的故障版本v16等,它們的故障語句都在多層嵌套的if判斷條件中,通過其他條件不變,增加相似測試用例的控制實驗,我們發(fā)現(xiàn),如果增加相似測試用例集合中的個數(shù),它們的預測結(jié)果會進一步提高.這也印證了與測試預言準確率相關(guān)的上述要素1)和要素2).

4.3 方法成本的評估

目前,本文方法未考慮多線程程序以及通過界面與用戶交互的圖形界面程序.測試套件下被測試程序各斷點處變量值集合相關(guān)信息收集的工作量較大,它是測試預言生成算法的主要開銷,也是本文的主要缺點和代價.

測試預言預測速度受斷點個數(shù)P、全部測試用例用例的個數(shù)T以及與待預測測試用例相似的測試用例個數(shù)N的影響.算法1計算相似測試用例集合的復雜度為O(T2),每增加一個斷,算法1就要在該斷點處執(zhí)行獲取內(nèi)存數(shù)據(jù)、計算敏感變量集和門限值等操作,因此算法1的效率與P呈線性關(guān)系.算法2比較相似測試用例集合中成功輸入(令程序執(zhí)行成功的輸入)與失敗輸入(令程序執(zhí)行失敗的輸入)的內(nèi)存變量與其取值,計算敏感變量集合,該計算過程的復雜度為O(N2).最后,算法 3在每個斷點處計算門限值,所以每次計算的復雜度是O(N2).由于算法1調(diào)用了算法2和算法3,綜上所述,算法1的算法復雜度較大,為O(T2+P×N2).

5 相關(guān)工作及結(jié)論

一些研究成果需要測試人員手動輸入規(guī)格說明或模型,或訓練神經(jīng)網(wǎng)絡(luò)的方法,輔助部分測試預言的自動生成.例如:(1) 在回歸測試中,一些研究基于規(guī)格說明和組件應(yīng)用編程接口規(guī)范,應(yīng)用人工神經(jīng)網(wǎng)絡(luò)自動生成測試預言[7-10],這些方法需要手工構(gòu)造規(guī)格說明;(2) 由測試者首先定義包含蛻變關(guān)系和數(shù)據(jù)挖掘算法的 JML規(guī)格說明,然后采用蛻變測試技術(shù)來產(chǎn)生測試預言[11],中文參考文獻[1],通過實驗研究蛻變測試技術(shù)產(chǎn)生測試預言的有效性;(3) ASTOOT通過檢查兩個不同的執(zhí)行場景來產(chǎn)生測試預言,但是需要測試人員提供被測試系統(tǒng)的代數(shù)規(guī)格說明[12];(4) Li等人提出了基于模型的測試預言生成策略,包括采用狀態(tài)不變量作為基于狀態(tài)圖測試預言生成的依據(jù)[13];(5) Guo等人首次提出一個通用的聲明框架,該框架基于測試人員撰寫的語義和控制流圖生成測試預言[14];(6) Wang等人[15]利用支持向量機 SVM作為監(jiān)督的機器學習算法,測試人員采用智能測試預言庫對被測試程序代碼進行注釋,根據(jù)函數(shù)調(diào)用收集測試跟蹤信息,對訓練集中每個測試軌跡提取特征作為SVM 算法的輸入,然后使用構(gòu)建的 SVM 模型作為測試預言,通過兩個案例程序的實驗結(jié)果闡釋了方法的有效性.

無需測試人員干預的測試預言自動生成方法.Arantes等人采用逆向工程,通過靜態(tài)和動態(tài)源代碼分析的方式構(gòu)造程序的一個結(jié)構(gòu)化模型,然后基于該模型自動生成測試預言[3],提出的方法檢測 4了個案例中的部分故障.Goffi等人借助現(xiàn)代軟件系統(tǒng),可以通過不同的執(zhí)行順序提供相同的功能的特征,通過檢查給定執(zhí)行序列與所有可用的冗余和假設(shè)等效的執(zhí)行序列之間的等價性,設(shè)計和開發(fā)了一種完全自動化產(chǎn)生測試預言的技術(shù),方法生成的測試預言發(fā)現(xiàn)了多達53%的錯誤,并對開發(fā)人員撰寫的16個案例中4個案例的測試預言,應(yīng)用該方法提升了其有效性[4].Shahamiri等人以被測試程序輸入空間的行為作為訓練集合,應(yīng)用神經(jīng)網(wǎng)絡(luò)生成新測試集輸入的測試預言;然后,該測試預言的預期結(jié)果與被測試程序真實的輸出進行比對[16,17];最后,他們通過兩個案例闡釋其研究成果的有效性.由于被測試單元沒有輸出或輸出形式的多樣性,該方法以被測試單元的輸出域作為準則產(chǎn)生測試預言有很大的局限性.Gholami等人[5]以測試輸入及其對應(yīng)的成功或失敗標記作為訓練集,應(yīng)用神經(jīng)網(wǎng)絡(luò)算法建立一個模型,為測試輸入產(chǎn)生測試預言.他們通過兩個案例研究闡釋了其方法的有效性,但是該方法需要的訓練集數(shù)量較大,而且要求失敗的輸入和成功的輸入各占一半,而現(xiàn)實中積累大量執(zhí)行失敗的輸入是不可能的.

本文工作屬于無需測試人員干預的測試預言自動生成方法.本文采用監(jiān)督的機器學習算法線性感知機作為測試預言自動生成的模型.首先,本文收集部分已知測試用例執(zhí)行的語句覆蓋和內(nèi)存值集合,給出了程序在給定斷點處的內(nèi)存中敏感變量集求解算法;然后,將已知測試用例集合作為訓練集,應(yīng)用線性感知機求解每個斷點處的門限值;最后,提出新測試用例的測試預言自動生成方法.

未來的工作將采用大型真實案例對本文提出的測試預言自動生成方法進行進一步分析與驗證;同時,進一步探索測試預測的準確率與故障類型的關(guān)系.