程序不可達路徑的檢測方法

姚婷

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

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

中圖分類號：TP311 文獻標識碼：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

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

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

1 已有的研究方法

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

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

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

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

可以看出，條件語句相關(guān)性的判定，隨機變量取值概率的估計及不可達路徑的自動檢測是本文的關(guān)鍵技術(shù)所在。下面將分別詳細闡述這些關(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，使得當輸入為X時，程序G執(zhí)行的路徑為P，則稱路徑P為可執(zhí)行的；否則，如果對于任意X∈D，當輸入為X時，G都不能執(zhí)行P，則稱P為不可達的。

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

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

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

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

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

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

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

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

3） 不可達路徑自動檢測步驟

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

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

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

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

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

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

3 程序可達路徑生成

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

4 實驗結(jié)果分析

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

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

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

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

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

5 結(jié)束語

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

參考文獻：

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

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

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

[4] 張艷梅，姜淑娟，王慶壇，等.不可達基路徑的靜態(tài)檢測方法[J].計算機科學與探索， 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].北京：北京郵電大學，2012.

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

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