程序不可達(dá)路徑的檢測方法

姚婷

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

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

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：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

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

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

1 已有的研究方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實驗結(jié)果分析

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

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

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

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

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

5 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

[4] 張艷梅，姜淑娟，王慶壇，等.不可達(dá)基路徑的靜態(tài)檢測方法[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] 趙云山.基于符號分析的靜態(tài)缺陷檢測技術(shù)研究[D].北京：北京郵電大學(xué)，2012.

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

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