姚婷

摘要：對(duì)于復(fù)雜的大型軟件，程序中不可達(dá)路徑存在會(huì)浪費(fèi)軟件測(cè)試的資源也影響了測(cè)試的準(zhǔn)確性。通過(guò)對(duì)程序基本路徑集中不可達(dá)路徑存在的問(wèn)題進(jìn)行了研究，提出基于條件語(yǔ)句之間具有的相關(guān)性檢測(cè)不可達(dá)路徑的方法，通過(guò)考察這些條件語(yǔ)句之間的相關(guān)性，可以檢測(cè)不可達(dá)路徑，生成程序的可達(dá)路徑集。

關(guān)鍵詞：軟件測(cè)試；不可達(dá)路徑；條件相關(guān)性

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）29-0084-04

Abstract： To complex large-scale software， the inaccessible path in the program will waste resources for software testing and also affect the accuracy of the test. Through the research on the problem of the unreachable path in the basic path of the program， this paper proposes a method based on the correlation between the conditional statements to detect the unreachable path. By examining the correlation between these conditional statements， the unreachable path can be detected. Generate a set of program reachable paths.

Keywords： software testing； unreachable path； conditional correlation

在軟件測(cè)試中，路徑覆蓋是一種最常用的測(cè)試充分性準(zhǔn)則，該準(zhǔn)則要求采用合適的方法生成測(cè)試用例，以覆蓋給定的目標(biāo)路徑。[1]對(duì)于給定的目標(biāo)路徑，如果任何輸入都不能覆蓋該路徑，該路徑就稱為不可達(dá)的。研究不可達(dá)路徑的檢測(cè)試用例的方法非常重要，若無(wú)法明確某且標(biāo)路徑是不可達(dá)的，測(cè)試者將花費(fèi)很多計(jì)算資源用于尋找覆蓋該路徑的測(cè)試用例，從而浪費(fèi)寶貴的計(jì)算資源[2]；相反，如果已經(jīng)知道其目標(biāo)路徑是不可達(dá)的，測(cè)試者就根本不需要尋找覆蓋該路徑的測(cè)試用例，從而能夠?qū)⒂邢薜挠?jì)算資源用于尋找覆蓋可執(zhí)行目標(biāo)路徑的測(cè)試用例。

鑒于不可達(dá)路徑產(chǎn)生的主要原因是該路徑包含的條件語(yǔ)句之間的相關(guān)性，所以，通過(guò)考察這些條件語(yǔ)句之間的相關(guān)性，可以檢測(cè)出不可達(dá)路徑。在此提出基于條件語(yǔ)句相關(guān)性的不可達(dá)路徑自動(dòng)檢測(cè)理論與方法，生成程序的可達(dá)路徑集。

1 已有的研究方法

已有的檢測(cè)不可達(dá)路徑的方法有動(dòng)態(tài)法和靜態(tài)法。動(dòng)態(tài)法難以直接判定某目標(biāo)路徑是不可達(dá)的，通常根據(jù)試圖覆蓋某目標(biāo)路徑，所需要的測(cè)試用例迭代次數(shù)，或者測(cè)試用例迭代一定次數(shù)時(shí)已經(jīng)覆蓋的路徑深度等，判定某目標(biāo)路徑是不可達(dá)的。[3]容易看出，覆蓋某目標(biāo)路徑需要的測(cè)試用例迭代次數(shù)，除了與該路徑的覆蓋難度相關(guān)之外，還與測(cè)試用例的初始位置、采用的迭代方法等密切相關(guān)。[4]因此，即使?jié)M足設(shè)定的迭代終止條件，判定某目標(biāo)路徑是不可達(dá)的也往往是不準(zhǔn)確的。

靜態(tài)法檢測(cè)不可達(dá)路徑有符號(hào)估值法和分支相關(guān)性檢測(cè)法。符號(hào)估值法使用符號(hào)代替程序的輸入變量，得到覆蓋目標(biāo)路徑應(yīng)該滿足的條件。缺點(diǎn)是缺乏有針對(duì)性的路徑覆蓋條件信息，難以確定哪個(gè)符號(hào)對(duì)路徑覆蓋起關(guān)鍵作用。[5]通常得到上述條件需要付出非常大的代價(jià)，實(shí)用性不高。

2 基于條件語(yǔ)句相關(guān)性的不可達(dá)路徑檢測(cè)

研究表明，在復(fù)雜軟件中，有13%-50%的條件語(yǔ)句之間具有某種相關(guān)性，[6]而不可達(dá)路徑產(chǎn)生的主要根源在于該路徑包含的條件語(yǔ)句之間具有相關(guān)性，因此，通過(guò)考察這些條件語(yǔ)句之間的相關(guān)性，有可能檢測(cè)不可達(dá)路徑。鑒于此，本文通過(guò)考察某目標(biāo)路徑包含的條件語(yǔ)句之間的相關(guān)性，提出不可達(dá)路徑的自動(dòng)檢測(cè)理論與方法，思想是：將不同條件語(yǔ)句謂詞表達(dá)式的取值看成隨機(jī)事件，定義相應(yīng)的隨機(jī)變量，并根據(jù)這些隨機(jī)變量取值的概率提出條件語(yǔ)句不同類型相關(guān)性的判定定理。上述隨機(jī)變量取值的概率難以精確得到，且對(duì)判定條件語(yǔ)句之間具有的相關(guān)性非常重要，因此，可采用數(shù)理統(tǒng)計(jì)中的極大似然估計(jì)方法對(duì)其進(jìn)行估計(jì)；基于條件語(yǔ)句之間具有的相關(guān)性，自動(dòng)檢測(cè)不可達(dá)路徑。在大量程序測(cè)試的實(shí)驗(yàn)結(jié)果表明，本文提出的方法能夠簡(jiǎn)便且準(zhǔn)確地檢測(cè)程序的全部或絕大部分不可達(dá)路徑，為程序可達(dá)路徑集生成奠定了堅(jiān)實(shí)的基礎(chǔ)。

可以看出，條件語(yǔ)句相關(guān)性的判定，隨機(jī)變量取值概率的估計(jì)及不可達(dá)路徑的自動(dòng)檢測(cè)是本文的關(guān)鍵技術(shù)所在。下面將分別詳細(xì)闡述這些關(guān)鍵技術(shù)。

2.1 條件語(yǔ)句相關(guān)性

首先定義條件語(yǔ)句之間的相關(guān)性，然后提出條件語(yǔ)句相關(guān)性的判定定理，并給出該定理的證明過(guò)程。

2.1.1 條件語(yǔ)句相關(guān)性的定義

記被測(cè)程序?yàn)镚，其輸入變量為x1，x2，…，xk，由此構(gòu)成的輸入向量為X=（x1，x2，…，xk）。如果xi的取值域?yàn)镈i（i=1，2，…，k），則G的取值域?yàn)镈=D1XD2X…XDk。

定義2.1如果存在X∈D，使得當(dāng)輸入為X時(shí)，程序G執(zhí)行的路徑為P，則稱路徑P為可執(zhí)行的；否則，如果對(duì)于任意X∈D，當(dāng)輸入為X時(shí)，G都不能執(zhí)行P，則稱P為不可達(dá)的。

考慮路徑P的兩個(gè)條件語(yǔ)句si和sj，如果sj的謂詞表達(dá)式的取值能夠由si謂詞表達(dá)式的取值確定，則稱si和sj是相關(guān)的，或者說(shuō)，條件語(yǔ)句si和sj之間具有相關(guān)性。容易知道，對(duì)于具有相關(guān)性的條件語(yǔ)句對(duì)，至少存在一條不可達(dá)路徑[7]。因此，通過(guò)條件語(yǔ)句之間具有的相關(guān)性能夠檢測(cè)程序包含的不可達(dá)路徑。

大部分條件語(yǔ)句之間的相關(guān)性難以被及時(shí)發(fā)現(xiàn)，特別是多個(gè)條件語(yǔ)句之間存在相關(guān)性時(shí)。研究發(fā)現(xiàn)，僅有12%的條件語(yǔ)句之間具有的相關(guān)性能夠在編譯階段被發(fā)現(xiàn)。[8]因此，如何準(zhǔn)確且高效地判定條件語(yǔ)句之間的相關(guān)性是一個(gè)非常值得研究的問(wèn)題。

為便于闡述，首先給出兩個(gè)條件語(yǔ)句之間相關(guān)性的定義，然后將其推廣到三個(gè)及以上條件語(yǔ)句的情況。

定義2.2 對(duì)于兩個(gè)條件語(yǔ)句si和sj，如果si的謂詞表達(dá)式取真時(shí)，sj的謂詞表達(dá)式也取真，則稱條件語(yǔ)句對(duì)（si，sj）具有真-真相關(guān)性。類似的，可以給出（si，sj）具有真-假相關(guān)性、假-真相關(guān)性及假假相關(guān)性的定義。

將上述概念進(jìn)一步推廣，能夠給出三個(gè)及以上條件語(yǔ)句之間的相關(guān)性定義。

有了上述定理，當(dāng)需要檢測(cè)某程序的不可達(dá)路徑時(shí)，僅需要考查某路徑包含的條件語(yǔ)句之間具有的相關(guān)性類型。鑒于程序的絕大部分不可達(dá)路徑都是由語(yǔ)句之間存在相關(guān)性造成的，本文方法能夠檢測(cè)程序的全部或絕大部分不可達(dá)路徑。

2） 循環(huán)體中條件語(yǔ)句不可達(dá)路徑的檢測(cè)

在實(shí)際的程序中，很多條件語(yǔ)句是包含在循環(huán)體內(nèi)的，這使得某條件語(yǔ)句可能會(huì)執(zhí)行多次。[9]對(duì)于該類程序，在設(shè)定目標(biāo)路徑時(shí)，往往僅考慮循環(huán)體執(zhí)行有限次的情況。此時(shí)，作如下規(guī)定：如果循環(huán)次數(shù)很少，則將每次循環(huán)都作為程序的一部分。如果循環(huán)次數(shù)很多，可以只考慮循環(huán)體執(zhí)行次數(shù)較少時(shí)相應(yīng)條件語(yǔ)句和其他條件語(yǔ)句之間的相關(guān)性，具體次數(shù)由目標(biāo)語(yǔ)句的選取情況而定[10]。

3） 不可達(dá)路徑自動(dòng)檢測(cè)步驟

利用條件語(yǔ)句之間具有的相關(guān)性自自動(dòng)檢測(cè)不可達(dá)路徑的步驟如下：

步驟1 根據(jù)目標(biāo)路徑包含的語(yǔ)句確定需要考查的兩（或多）個(gè)條件語(yǔ)句。

步驟2 采用2.2節(jié)的方法，定義相應(yīng)的隨機(jī)變量及條件語(yǔ)句謂詞表達(dá)式取值的概率。

步驟3 采用2.2節(jié)的方法，估計(jì)條件語(yǔ)句謂詞表達(dá)式取值的概率。

步驟4 根據(jù)條件語(yǔ)句謂詞表達(dá)式取值的概率，采用2.2節(jié)的方法，考查條件語(yǔ)句之間是否具有相關(guān)性。若是，確定相關(guān)性類型；否則，轉(zhuǎn)步驟6。

步驟5 根據(jù)條件語(yǔ)句之間具有的相關(guān)性類型，采用2.1節(jié)的方法，確定不可達(dá)路徑。

3 程序可達(dá)路徑生成

對(duì)使用本文方法檢測(cè)出的不可達(dá)路徑，不能簡(jiǎn)單地剔除，需要對(duì)不可達(dá)路徑進(jìn)行的分析。若該分支結(jié)點(diǎn)出現(xiàn)在復(fù)用路徑中，通過(guò)改變復(fù)用路徑，使不可達(dá)路徑變?yōu)榭蛇_(dá)，若未出現(xiàn)在復(fù)用路徑中，則說(shuō)明該路徑為恒不可達(dá)路徑，需要把恒不可達(dá)路徑從基本路徑集中剔除，并加以說(shuō)明。

4 實(shí)驗(yàn)結(jié)果分析

為評(píng)價(jià)本文所提方法的性能，選擇工業(yè)程序進(jìn)行一系列實(shí)驗(yàn)檢測(cè)工業(yè)程序不可達(dá)路徑的性能。選擇4個(gè)程序作為被測(cè)程序，對(duì)于每個(gè)被測(cè)程序，選擇部分子函數(shù)進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)程序中，存在大量的條件語(yǔ)句，且很多條件語(yǔ)句之間具有相關(guān)性。表1給出這些被測(cè)程序的基本信息。

對(duì)于每個(gè)被測(cè)程序，考查不同條件語(yǔ)句之間具有的相關(guān)性，并基于此檢測(cè)不可

達(dá)路徑，結(jié)果如表2所示。BC（）指i個(gè)條件語(yǔ)句之間具有相關(guān)性的個(gè)數(shù)； IBDC（i） 表示通過(guò)考查i個(gè)條件語(yǔ)句之間具有相關(guān)性，檢測(cè)的不可達(dá)徑數(shù)（i= 2，3.4）；檢測(cè)率是檢測(cè)到的不可達(dá)徑數(shù)與不可達(dá)路徑總數(shù)的比。

由表2可知，在四個(gè)被測(cè)程序中，具有相關(guān)性的條件語(yǔ)句大量存在。

對(duì)于程序Spacs，存在2個(gè)條件語(yǔ)句之間具有相關(guān)性的有24 組，存在3個(gè)條件語(yǔ)句之間具有相關(guān)性的有22 組，存在4個(gè)條件語(yǔ)句之間具有相關(guān)性的有20 組；其他程序也是如此?；谏鲜鰲l件語(yǔ)句具有的相關(guān)性，對(duì)于程序run.spacs，remove，利用本文提出的方法檢測(cè)到所有不可達(dá)路徑；盡管程序print 未檢測(cè)到全部不可達(dá)路徑，但檢測(cè)率也高達(dá)99.19%。這充分說(shuō)明本文提出的方法檢測(cè)不可達(dá)路徑是很有效的。

5 結(jié)束語(yǔ)

本文闡述了基本路徑集的生成方法，方法具有通用性。重點(diǎn)介紹了基于條件語(yǔ)句相關(guān)性的不可達(dá)路徑檢測(cè)的方法，給出了條件語(yǔ)句之間相關(guān)性的定義，并建立了相關(guān)判定定理。給出基于極大似然估計(jì)方法估計(jì)條件語(yǔ)句謂詞表達(dá)式取值概率的方法，證明了基于條件語(yǔ)句之間具有的相關(guān)性，自動(dòng)檢測(cè)不可達(dá)路徑的方法的可行性。

參考文獻(xiàn)：

[1] 單錦輝，姜瑛，孫萍，軟件測(cè)試研究進(jìn)展[J].北京大學(xué)學(xué)報(bào)：自然科學(xué)版，2005， 41（1）： 134-145.

[2] 李東，宮云戰(zhàn)，軟件測(cè)試方法綜述[J].裝甲兵工程學(xué)院學(xué)報(bào)， 2003， 17（2）： 9-13.

[3] 陳蕊，張廣梅，李曉維.程序中不可達(dá)路徑的檢測(cè)方法[J].計(jì)算機(jī)工程，2006，32（16） ： 86-88.

[4] 張艷梅，姜淑娟，王慶壇，等.不可達(dá)基路徑的靜態(tài)檢測(cè)方法[J].計(jì)算機(jī)科學(xué)與探索， 2012，6（2） ： 144-155.

[5] Beizer B. Software Testing Techniques [M].India： Dreamtech Press， 2002.

[6] Maiocchi M.Software engineering[J].Future Generation Computer Systems，1991，7（1）：23-29.

[7] Coward P D.A review of software testing[J].Information and Software Technology， 1988， 30（3）： 189-198.

[8] Goldberg A， Wang T.C and Zimmerman D. Applications of feasible path analysis to program testing[J].Proceedings of the 1994 International Symposium on Software Testing and Analysis （ISSTA） ， 1994： 80-94.

[9] 趙云山.基于符號(hào)分析的靜態(tài)缺陷檢測(cè)技術(shù)研究[D].北京：北京郵電大學(xué)，2012.

[10] 韓寒，姜淑娟.路徑測(cè)試中基本路徑集自動(dòng)生成方法的研究[J].微電子學(xué)與計(jì)算機(jī)，2013，30 （1）：104-109.

[通聯(lián)編輯：梁書]