基於程序控制依賴引導的回歸測試案例生成方法
2023-10-18 11:33:24 2
基於程序控制依賴引導的回歸測試案例生成方法
【專利摘要】本發明提出一種基於程序控制依賴引導的回歸測試案例生成方法，可以自動生成對程序修改部分進行有效測試的測試案例。該方法以發生修改的程序代碼為測試目標，通過分析程序的控制流和信息流，建立程序控制依賴圖；計算各個分支語句到達測試目標代碼的概率（到達概率），引導符號執行生成可以保證目標代碼被執行的測試案例；計算所有分支語句的可能使得目標代碼執行結果無法傳播到輸出的概率（阻斷概率），引導符號執行生成可以保證目標代碼執行結果影響輸出的測試案例。相比現有回歸測試方法，本方法可以保證測試案例的有效性，同時顯著提高測試案例生成的效率。
【專利說明】基於程序控制依賴引導的回歸測試案例生成方法
【技術領域】
[0001]本發明涉及可信軟體及軟體測試領域，特別涉及回歸測試案例生成方法。
【背景技術】
[0002]軟體回歸測試是指軟體代碼修改後，重新進行測試以確認修改沒有引入新的錯誤或導致其他代碼產生錯誤。對軟體的有效修改需要滿足兩個條件:1)程序的修改符合預期行為，即能夠將待修改的部分修改正確；2)程序的修改不會影響其它非預期的行為發生變化，即修改部分不會影響其它不需要修改的程序行為。回歸測試是保證軟體修改符合預期的重要手段，如何高效地進行回歸測試也是軟體測試中的重要問題。現有思路主要分為以下兩種:1)連續測試，利用已有的測試案例對演化的程序進行重新測試，此方法存在的主要問題是效率低，其絕大部分測試案例對被修改程序來說都是無效的測試案例。2)針對程序修改部分增量生成新的測試案例，其難點是如何高效地自動生成符合期望的測試案例。
[0003]為解決連續測試效率低下的問題，研究人員提出了兩種改進方法，測試案例選擇和測試案例排序。這兩種方法都是通過分析測試案例和演化程序的關係來選擇出最合適的測試案例。雖然測試案例選擇和測試案例排序解決了連續測試的效率低下問題，但是沒有解決連續測試的有效性問題，因為已有的測試案例在創建時並不會考慮到將來程序的變化，所以有可能這些測試案例都不能覆蓋被修改的程序部分。
[0004]為解決測試案例集覆蓋率低下的問題，目前研究的熱點是將程序抽象為形式化模型，採用測試案例自動生成算法對形式化模型中的各種信息進行提取、生成一個完備的測試案例集。其中最常用的方法是符號執行，符號執行是20世紀70年代提出的一種程序驗證方法，是一種基於符號化的模型檢驗方法。廣泛用於符號調試，測試案例生成等。其核心思想是使用符號值代替具體的變量輸入，並使用符號表達式來表示程序中各變量的值。最終，程序的輸出值被轉化為一個以符號值作為輸入的函數。符號執行將程序抽象為符號執行樹，其中順序語句對應著樹的計算節點，分支語句對應著分支節點，而對於循環語句，將其按循環次數展開為語義上等價的分支語句。一般，一條循環語句對應一組分支節點。可以認為，在符號執行過程中，程序只有順序和分支兩種結構。
[0005]符號執行的過程本質上是路徑條件的構造過程。路徑條件指的是對於執行該路徑的測試案例，程序輸入值所需要滿足的數學約束條件。因而一個路徑條件唯一地對應一條執行路徑。一個路徑條件由一組子條件(sub-condition)組成，每一個被執行分支的條件作為一個子條件。在初始時路徑條件為true，在探索程序的過程中，每遇到一個分支語句，就更新路徑條件，將被執行分支的條件加入到路徑條件中，公式為PC=PCTnewsub-condition。由於每一個分支語句都對應著true和false兩個分支，而符號執行基於靜態分析，變量沒有具體的數值，因而無法確定執行哪一條分支。所以對兩條分支都進行探索(搜索順序可按需定義，深度優先，廣度優先等)，即分別以兩個分支的條件作為子條件來更新路徑條件。這樣就得到了兩個新的路徑條件，對應兩條不同的執行路徑。之後，繼續對這兩條路徑分別進行探索。符號執行實現了對程序的全路徑探索。當程序探索結束時就得到了被測程序所有執行路徑的路徑條件。最後，檢查所有得到的路徑條件，如果路徑條件是無法被滿足的，則說明該路徑是一條不可執行路徑，如果路徑條件可以被滿足，則說明該路徑是一條可執行路徑。將路徑條件輸入約束求解器即可解出對應的測試案例。
[0006]符號執行存在兩個阻礙，使得其難以大規模使用。I)符號執行是一種基於搜索的遍歷算法，需要對程序的所有分支進行遍歷，雖然可以通過一些附加的剪枝條件進行優化，但其算法的複雜度非常高，為O (2η)，其中η為被測程序中條件語句(包括分支，循環，邏輯運算)的數目；2)符號執行不能很好地解決測試案例集更新的問題，每次代碼進行修改後，只能重新遍歷一次符號執行樹來生成一個新的測試案例集。由前面的分析可知，重新生成一個測試案例集的時間開銷比較大，而且一個軟體可能會頻繁變更，如果每次變更之後都通過符號執行生成一個新的測試案例集，測試的效率就會受到影響。
【發明內容】
[0007]本發明的目的在於提供一種基於程序控制依賴引導的回歸測試案例生成方法，以提高測試效率。
[0008]為了實現上述目的，本發明採用如下技術方案:
[0009]基於程序控制依賴引導的回歸測試案例生成方法，包括如下步驟:
[0010]S101)、利用程序靜態分析方法，分析測試程序的控制流和信息流，建立測試程序的控制依賴圖；
[0011]S102)、針對輸入的測試程序的目標代碼，根據步驟S101)中建立的控制依賴圖中計算各個分支的到達概率；
[0012]S103)、採用基於分支到達概率引導的約束生成算法，迭代搜索和取反測試案例執行路徑上到達概率最大的分支條件，生成新的約束，利用符號執行方法進行求解，若可以生成一個執行目標代碼的測試案例，轉入步驟S104);若無法生成測試案例可以執行目標代碼，則表示測試目標代碼在程序中不會被執行，轉入步驟S107)；
[0013]S104)、針對測試程序的目標代碼，根據程序信息流，檢測各個分支語句是否阻斷目標代碼執行結果對程序輸出的影響，若改變則標記為阻斷分支；然後，計算各個分支的阻斷概率；
[0014]S105)、採用基於分支阻斷概率引導的約束生成算法，迭代搜索和取反測試案例執行路徑上阻斷概率最小的分支條件，生成新的約束，利用符號執行方法進行求解，若可以生成一個測試案例保證目標代碼執行結果影響輸出，轉入步驟S106);若無法生成測試案例，轉入步驟S103)；
[0015]S106)輸出有效測試案例，流程結束；所述有效測試案例是指該測試案例可以保證測試目標代碼被執行，且執行結果影響程序輸出結果；
[0016]S107)針對輸出測試程序和測試目標代碼，無法生成有效測試案例。
[0017]本發明進一步的改進在於:步驟S103)中所述分支到達概率為:對於某一個分支，從該分支到目標代碼，所需要經過的最少依賴分支數目的倒數。
[0018]本發明進一步的改進在於:步驟S103)中所述基於分支到達概率引導的約束生成算法具體包括:
[0019]S1031)、執行測試案例，第一次執行初始測試案例；從第二次開始執行上一周期步驟S10310)生成的測試案例；
[0020]S1032)、檢查目標代碼是否被執行；如果測試案例能執行到期望執行的目標代碼，則轉至步驟S10312);如果測試案例不能執行到目標代碼，則轉至步驟S1033)；
[0021]S1033)、檢查執行路徑上是否有可取反的分支，如果有，則轉至步驟S1034);如果沒有，則轉至步驟S1035)；
[0022]S1034)、取反所有可取反的分支來生成一系列待擴展路徑片段，並將待擴展路徑片段最後一個分支的分支到達概率值作為該路徑片段能覆蓋目標代碼的概率，存入第一未探測集合中；
[0023]S1035)、未探測集合是否為空，若為空，轉至步驟S10311)，若不為空，轉至步驟S10316)；
[0024]S1036)、從第一未探測集合中選擇一條概率最大的待擴展路徑片段，基於此路徑片段進行符號執行；
[0025]S1037)、符號執彳了該路徑片段，並記錄路徑約束Cnew ；
[0026]S1038)、利用約束求解器求解Cnew，若可解，則轉至步驟S10310);若不可解，則轉至步驟S1039)；
[0027]S1039)、廢棄該路徑片段，同時跳轉至步驟S1033)；
[0028]S10310)、生成新的測試案例Tnew，然後跳轉至步驟S1031)；
[0029]S10311)、無有效測試案例輸出；
[0030]S10312)、輸出該能執行到期望執行的目標代碼的有效測試案例。
[0031]本發明進一步的改進在於:步驟S104)中所述阻斷分支為目標代碼執行後，導致目標代碼執行結果無法傳遞到輸出語句的分支。
[0032]本發明進一步的改進在於:步驟S104)中所述分支阻斷概率為:對於在目標代碼之後執行的某一個分支，執行該分支後將會執行阻斷分支的概率；取值範圍為0%-100%。
[0033]本發明進一步的改進在於:分支阻斷概率的計算公式為:
[0034]BP=1- Nb/Np
[0035]其中分支阻斷概率的計算方法包括:首先將待測程序的所有分支分為Ep，Eb兩個集合,Ep為所有分支的集合,Eb為阻斷分支的集合；對於某一個分支，從兩個集合中選擇子集Ep』，Eb』，分別表示在該分支之後執行的所有分支和所有阻斷分支，然後基於Ep』，Eb』構建可能的執行路徑；Np為基於Ep』構建的路徑數，Nb為基於Eb』構建的路徑數；得到Nb，Np後代入公式即可得到某一分支的分支阻斷概率值BP。
[0036]本發明進一步的改進在於:步驟S105)中所述基於分支阻斷概率引導的約束生成算法包括:
[0037]S1051)、執行測試案例；第一次執行步驟S103)的步驟S10312)生成的有效測試案例，從第二次開始執行上一周期步驟S10510)生成的測試案例；
[0038]S1052)、檢查目標代碼執行結果是否傳遞到輸出語句:如果目標代碼執行結果傳遞到了輸出語句，則轉至步驟S10512);否則，則轉至步驟S1053)；
[0039]S1053)、檢查執行路徑上是否有可取反的分支，如果有，則轉至步驟S1054);如果沒有，則轉至步驟S1055)；
[0040]S1054)、取反所有可取反的分支來生成一系列待擴展路徑片段，並將待擴展路徑片段最後一個分支的分支阻斷概率值作為該路徑片段將執行阻斷分支的概率值，存入第二未探測集合中；
[0041]S1055)、第二未探測集合是否為空，若為空，轉至步驟S10511 ;若不為空，轉至步驟 S1056)；
[0042]S1056)、從第二未探測集合中選擇一條阻斷概率最小的待擴展路徑片段，基於此路徑片段進行符號執行；
[0043]S1057)、符號執行該路徑片段，並記錄路徑約束Cnew ；
[0044]S1058)、利用約束求解器求解Cnew，若可解，則轉至步驟S10510);若不可解，則轉至步驟S1059)；
[0045]S1059)、廢棄該路徑片段，跳轉至步驟S1053)；
[0046]S10510)、生成新的測試案例Tnew，然後跳轉至步驟S1051)；
[0047]S10511)、無有效測試案例輸出；
[0048]S10512)輸出該能執行到期望執行的目標代碼，且執行結果影響程序輸出結果的有效測試案例。
[0049]相對於現有技術，本發明具有以下有益效果:本發明提出一種基於程序控制依賴引導的回歸測試案例生成方法，該方法以發生修改的程序代碼為測試目標，通過分析程序的控制流和信息流，建立程序控制依賴圖；計算各個分支語句到達測試目標代碼的概率(到達概率)，引導符號執行生成可以保證目標代碼被執行的測試案例；計算所有分支語句的可能使得目標代碼執行結果無法傳播到輸出的概率(阻斷概率)，引導符號執行生成可以保證目標代碼執行結果影響輸出的測試案例；本發明方法可以自動生成對程序修改部分進行有效測試的測試案例；相比現有回歸測試方法，本方法可以保證測試案例的有效性，同時顯著提高測試案例生成的效率。
【專利附圖】
【附圖說明】
[0050]圖1為本發明方法的整體流程圖；
[0051]圖2為測試目標代碼到達的測試案例生成流程圖；
[0052]圖3為測試目標執行影響輸出的測試案例生成流程圖；
[0053]圖4為示例待測試程序圖；
[0054]圖5為示例程序的控制依賴圖。
【具體實施方式】
[0055]以下結合附圖和實例詳細說明本發明的實施方式。待測程序如圖4所示，對於執行路徑，我們以路徑上經過的分支語句來表示。假設某一執行路徑經過了 2F，3T這兩個分支語句，則其表示為[2F，3T]。
[0056]步驟SlOl:基於靜態分析方法分析測試程序的控制流和信息流，生成測試程序的控制依賴圖，控制依賴圖如圖5所示，目標代碼為第19行；
[0057]步驟S102:針對輸入的測試程序的目標代碼，在步驟SlOl中建立的控制依賴圖中
計算各個分支的到達概率；結果如下表所示。
[0058]
【權利要求】
1.基於程序控制依賴引導的回歸測試案例生成方法，其特徵在於，包括如下步驟: 5101)、利用程序靜態分析方法，分析測試程序的控制流和信息流，建立測試程序的控制依賴圖； 5102)、針對輸入的測試程序的目標代碼，根據步驟S101)中建立的控制依賴圖中計算各個分支的到達概率； 5103)、採用基於分支到達概率引導的約束生成算法，迭代搜索和取反測試案例執行路徑上到達概率最大的分支條件，生成新的約束，利用符號執行方法進行求解，若可以生成一個執行目標代碼的測試案例，轉入步驟S104);若無法生成測試案例可以執行目標代碼，則表示測試目標代碼在程序中不會被執行，轉入步驟S107)； 5104)、針對測試程序的目標代碼，根據程序信息流，檢測各個分支語句是否阻斷目標代碼執行結果對程序輸出的影響，若改變則標記為阻斷分支；然後，計算各個分支的阻斷概率； 5105)、採用基於分支阻斷概率引導的約束生成算法，迭代搜索和取反測試案例執行路徑上阻斷概率最小的分支條件，生成新的約束，利用符號執行方法進行求解，若可以生成一個測試案例保證目標代碼執行結果影響輸出，轉入步驟S106);若無法生成測試案例，轉入步驟S103)； 5106)輸出有效測試案例，流程結束；所述有效測試案例是指該測試案例可以保證測試目標代碼被執行，且執行結果影響程序輸出結果； 5107)針對輸出測試程序和測 試目標代碼，無法生成有效測試案例。
2.根據權利要求1所述方法，其特徵在於，步驟S103)中所述分支到達概率為:對於某一個分支，從該分支到目標代碼，所需要經過的最少依賴分支數目的倒數。
3.根據權利要求1所述方法，其特徵在於，步驟S103)中所述基於分支到達概率引導的約束生成算法具體包括: 51031)、執行測試案例，第一次執行初始測試案例；從第二次開始執行上一周期步驟S10310)生成的測試案例； 51032)、檢查目標代碼是否被執行；如果測試案例能執行到期望執行的目標代碼，則轉至步驟S10312);如果測試案例不能執行到目標代碼，則轉至步驟S1033)； 51033)、檢查執行路徑上是否有可取反的分支，如果有，則轉至步驟S1034);如果沒有，則轉至步驟S1035)； 51034)、取反所有可取反的分支來生成一系列待擴展路徑片段，並將待擴展路徑片段最後一個分支的分支到達概率值作為該路徑片段能覆蓋目標代碼的概率，存入第一未探測集合中； 51035)、未探測集合是否為空，若為空，轉至步驟S10311)，若不為空，轉至步驟S10316)； 51036)、從第一未探測集合中選擇一條概率最大的待擴展路徑片段，基於此路徑片段進行符號執行； 51037)、符號執行該路徑片段，並記錄路徑約束Cnew； 51038)、利用約束求解器求解Cnew，若可解，則轉至步驟S10310);若不可解，則轉至步驟 S1039)；S1039)、廢棄該路徑片段，同時跳轉至步驟S1033)； 510310)、生成新的測試案例Tnew，然後跳轉至步驟S1031)； 510311)、無有效測試案例輸出； 510312)、輸出該能執行到期望執行的目標代碼的有效測試案例。
4.根據權利要求1所述方法，其特徵在於，步驟S104)中所述阻斷分支為目標代碼執行後，導致目標代碼執行結果無法傳遞到輸出語句的分支。
5.根據權利要求1所述方法，其特徵在於，步驟S104)中所述分支阻斷概率為:對於在目標代碼之後執行的某一個分支，執行該分支後將會執行阻斷分支的概率；取值範圍為0%-100%。
6.根據權利要求1或5所述方法，其特徵在於，分支阻斷概率的計算公式為:
BP=1- Nb/Np 其中分支阻斷概率的計算方法包括:首先將待測程序的所有分支分為Ep，Eb兩個集合，Ep為所有分支的集合,Eb為阻斷分支的集合；對於某一個分支，從兩個集合中選擇子集Ep』，Eb』，分別表示在該分支之後執行的所有分支和所有阻斷分支，然後基於Ep』，Eb』構建可能的執行路徑；Np為基於Ep』構建的路徑數，Nb為基於Eb』構建的路徑數；得到Nb，Np後代入公式即可得到某一分支的分支阻斷概率值BP。
7.根據權利要求1所述方法，其特徵在於，步驟S105)中所述基於分支阻斷概率引導的約束生成算法包括: 51051)、執行測試案例；第一次執行步驟S103)的步驟S10312)生成的有效測試案例，從第二次開始執行上一周期步驟S10510)生成的測試案例； 51052)、檢查目標代碼執行結果是否傳遞到輸出語句:如果目標代碼執行結果傳遞到了輸出語句，則轉至步驟S10512);否則，則轉至步驟S1053)； 51053)、檢查執行路徑上是否有可取反的分支，如果有，則轉至步驟S1054);如果沒有，則轉至步驟S1055)； 51054)、取反所有可取反的分支來生成一系列待擴展路徑片段，並將待擴展路徑片段最後一個分支的分支阻斷概率值作為該路徑片段將執行阻斷分支的概率值，存入第二未探測集合中； 51055)、第二未探測集合是否為空，若為空，轉至步驟S10511;若不為空，轉至步驟S1056)； 51056)、從第二未探測集合中選擇一條阻斷概率最小的待擴展路徑片段，基於此路徑片段進行符號執行； 51057)、符號執行該路徑片段，並記錄路徑約束Cnew； 51058)、利用約束求解器求解Cnew，若可解，則轉至步驟S10510);若不可解，則轉至步驟 S1059)； 51059)、廢棄該路徑片段，跳轉至步驟S1053)； 510510)、生成新的測試案例Tnew，然後跳轉至步驟S1051)； 510511)、無有效測試案例輸出； 510512)輸出該能執行到期望執行的目標代碼，且執行結果影響程序輸出結果的有效測試案例。
【文檔編號】G06F11/36GK103455421SQ201310362303
【公開日】2013年12月18日 申請日期:2013年8月19日 優先權日:2013年8月19日
【發明者】鄭慶華, 劉烴, 王海軍, 俞樂晨, 黃小龍 申請人:西安交通大學