一種基於遺傳算法的mc/dc測試數據自動生成方法

2023-09-20 23:51:55 2

專利名稱：一種基於遺傳算法的mc/dc測試數據自動生成方法
技術領域：
本發明屬於軟體測試技術領域，具體涉及一種基於遺傳算法的MC/DC測試數據自動生成方法，特別涉及工程測試中滿足MC/DC覆蓋(修正條件判定覆蓋)的測試數據自動生成方法。
背景技術：
測試數據自動生成技術是指通過特定的算法依據軟體的規約或者程序結構自動構造測試輸入數據，其目的在於減輕測試人員所必須付出的大量勞動，降低手工測試的高額成本，同時提高測試過程的可信賴程度。遺傳算法是一種模擬生物進化過程和機制求解極值問題的自適應人工智慧技術，在解決大空間、非線性等高複雜度問題時具有獨特的優勢。動態執行程序生成測試數據的思想最初由Miller和Spooner提出，後來的學者做了大量的進一步研究。1992年，Xanthakis首先將遺傳算法應用於測試用例生成，它採用編碼技術將D映射到基因空間G，並通過選擇、交叉、變異等遺傳操作和優勝劣汰的自然選擇確定搜索方向。交叉和變異操作為種群引入新的信息，從而更有利於找到全局最優解，避免了以往算法往往容易陷入局部極值的問題，能夠生成滿足所有分支判定準則的測試數據。 在國內，1996到1998年，莢偉、高仲儀等發表多篇論文，討論將遺傳算法應用於基於路徑覆蓋的Ada軟體結構測試數據的自動生成，並得出遺傳算法比爬山法和隨機法生成測試數據的效率高的結論。2001年，汪浩等給出了遺傳算法的形式化的表示和一個基於此算法的測試數據生成系統原型。2003年，景志遠從數學的角度分析了將MGA和遺傳K均值等改進的算法應用於測試用例的自動生成。2006年，程燁在學位論文將遺傳算法用於路徑覆蓋測試數據自動生成，並開發了相應的工具模型。2008年，呂珊珊在她的學位論文中使用神經網絡和遺傳算法生成基於輸入域的測試數據。總的來說，現在國內外的研究學者多採用遺傳算法或者遺傳算法的改進算法作為核心算法來生成測試數據。但上述均是選擇邏輯結構相對簡單的語句覆蓋或分支覆蓋生成測試用例，使其在實際的工程領域無法得到廣泛的應用。

發明內容
針對現有技術中存在的問題，本發明提出一種基於遺傳算法的MC/DC測試數據自動生成方法。針對遺傳算法中傳統適應度函數僅依靠控制流圖中節點間的控制依賴關係， 沒有考慮被測程序內部的數據依賴關係的缺陷，提出使用連結法思想收集直接或者通過數據依賴間接影響問題節點遍歷的控制節點，並將其與表徵控制依賴關係見長的傳統適應度函數相結合，構造一個新的適應度函數，以此來克服傳統的適應度函數因忽略程序內部的數據依賴關係而造成的引導信息缺乏、搜索退化的問題。在此基礎上設計實現了基於遺傳算法的滿足MC/DC準則的測試數據自動生成方法。MC/DC準則強調單個變量對於最後表達式真假的影響的能力，要求每一個條件都要獨立的影響判定表達式的結果，對邏輯關係複雜且安全性要求較高的軟體系統進行測試時具有很大的實用價值。
本發明提出一種基於遺傳算法的MC/DC測試數據自動生成方法，具體包括以下幾個步驟步驟一對被測程序進行靜態分析，產生控制流圖、數據流圖、抽象語法樹和抽象分析樹。步驟二 生成MC/DC測試用例預期結果集。步驟2. 1 從抽象分析樹中提出條件節點，這些條件節點構成了抽象分析樹的葉子，每一個葉子就是一個變量，用N表示提取的葉子變量的個數。步驟2. 2 構建真值表，對N個葉子變量，有2n種排列組合。步驟2.3 用數字0和1填充真值表。步驟2. 4 針對真值表中的每一行步驟2. 5. 1 將真值表當前行中的布爾值對應分配給抽象分析樹的每一個葉子變量；步驟2. 4. 2 自底向上評價各個條件節點的布爾值，直到抽象分析樹的頂端，最終所得的抽象分析樹的頂端的條件節點的布爾值就是這個判定語句的輸出結果值；步驟2. 4. 3 用輸出結果值填充真值表的輸出列。步驟2. 5 針對每一個葉子變量，尋找其測試用例，並添加到每個葉子變量的MC/ DC測試用例集中步驟2. 5. 1 為每一個葉子變量建立一對空的MC/DC測試用例集；步驟2. 5. 2 在真值表中，尋找其他葉子變量值固定，只有目標葉子變量改變的兩行；步驟2. 5. 3 比較步驟2. 5. 2中的兩行的輸出結果值，如果兩行的輸出結果值不同，則這兩行就是目標葉子變量的一對測試用例，將這兩行以成對的形式添加到步驟2. 5. 1 中建立的MC/DC測試用例集中。步驟2. 6 將每一個葉子變量的MC/DC測試用例集合併，得到測試用例集，並最小化測試用例集。步驟三對被測程序進行代碼插樁。首先遍歷抽象語法樹找到插樁的位置，判斷是否是插樁點，如果不是插樁點，返回繼續遍歷抽象語法樹尋找找到插樁位置；如果是插樁點，則植入檢查語句，然後直接在抽象語法樹上以子樹的形式植入代碼的語法樹片段，判斷插樁是否完成，如已完成，則被測程序編譯運行；如未完成，返回繼續遍歷抽象語法樹找到插樁的位置，直至完成插樁。步驟四構造適應度函數。步驟4. 1 建立控制依賴關係適應度函數步驟4. 1. 1 通過被測程序的控制流圖，獲得每一個判定的控制依賴關係集合；控制依賴用來描述一個目標節點y的執行關於其前面分支節點輸出的依賴性，當每一條從目標節點y到出口節點e的路徑都包含節點ζ時，稱節點ζ被目標節點y後置控制；任意節點 χ，兩個節點(y，χ)之間可以構成一個分支路徑，當每一條從目標節點y到出口節點e的通過(y，x)分支路徑都包括節點ζ時，稱節點ζ後置控制一個分支(y，x)；當節點ζ後置控制 y的一個分支，且節點ζ不後置控制節點y，稱節點ζ控制依賴於目標節點y，控制依賴關係是從結構關係角度衡量當前輸入測試數據距離抵達目標的逼近程度，通過控制流圖中目標與執行偏離條件節點間的關鍵節點計算得到。步驟4. 1. 2 建立控制依賴關係適應度函數控制依賴關係適應度函數包含了控制依賴關係集合中各分支節點的目標函數，建立控制依賴關係適應度函數為
ControlDqps^tta d e ρ ef n s e(1)其中，d印endentde。isi。n為目標的控制依賴關係集合中的控制節點數； executeddecisions表示以當前測試數據為輸入；ControlD印Fittestdata表示控制依賴關係適應度函數；如果控制依賴關係適應度函數值為0，則測試數據能夠到達目標判定；如果控制依賴關係適應度函數值大於0，則測試數據在某處偏離了目標節點，通過控制依賴關係適應度函數的值，得到偏離節點divergecLde ；步驟4. 2 建立數據依賴關係適應度函數定義pn為問題節點，S為用來儲存一個給定節點的依賴關係的集合，以pn和S作為獲取數據依賴關係適應度函數方法的輸入，DepSets用來儲存當前搜集到的存在依賴關係的節點集合，PV用來存儲問題節點使用的變量，S和DepSets被初始化為空集，獲取一個節點S的依賴關係適應度函數的方法為步驟4. 2. 1 獲取問題節點pn的控制依賴關係集合ControlD印(pn)賦給S,並將 pn使用的變量UsedVariables (pn)加到PV中；步驟4. 2. 2 對於PV中的每一個變量pv，獲取pv的最後定義集合IastDefs ；(a)對於IastDefs中每一個最後定義ld，獲取Id的控制依賴關係集合 ControlDep (Id)，並將其與S合併，得到擴展的S，然後將Id使用的變量UsedVariables (Id) 添加到一個新建的PVnew中；(b)對於ControlD印(Id)中的每一個控制節點cd，獲取它使用的變量 UsedVariables (Id)，並添加到步驟4. 2. 2 (a)建立的PVnew集合中；步驟4. 2. 3 對於PV中的每一個變量pv，迭代獲取PV依賴關係集S (Id)，首先獲得PV中的第一個變量，獲取其依賴關係集S (Id)，返回步驟4. 2. 2，然後獲取PV中的下一個變量，直至完成PV中所有的變量，結束迭代，並將S (Id)添加到DepSets中；步驟4. 2. 4 建立用於定義適應度函數的依賴關係集合定義D印Fit為適應度函數依賴關係集合，對於D印Sets中的每一個子集Si (a)添加 Si 到 D印Fit 中；(b)判斷D印Sets中每一個非Si的子集Sj，與Si是否存在theruelse的分支衝突， 如果不存在，則合併兩個子集Si、Sj，得到新的子集Siij，並將Siij添加到D印Fit中；如果存在then、else的分支衝突則不能合併，將Si、Sj都添加到D印Fit中；步驟4. 2. 5 建立數據依賴關係適應度函數建立數據依賴關係集合後，用計算控制依賴關係適應度函數的方法得到數據依賴關係適應度函數。步驟4. 3 建立分支適應度函數當測試數據抵達目標時，用分支距離來度量測試數據是否滿足期望測試用例，通過計算分支距離度量測試數據距離期望測試用例的逼近程度，如果測試數據到達目標判定，但是不滿足任一個MC/DC測試用例，那麼每一個測試數據的接近水平都為0，但分支距離不為0 ；如果測試抵達目標並實現一個測試用例，那麼它的分支距離和接近水平都為0 ； 計算出來的分支距離的大小用來評價哪一個測試數據更接近於滿足期望的分支測試用例。步驟五在MC/DC測試用例、適應度函數公式和執行插樁代碼的基礎上，隨機產生測試數據，並在這些測試數據上執行插樁後的被測程序，獲得適應度值，同時檢驗是否滿足預期執行的路徑；如果滿足，則進入步驟七；否則進入步驟六。計算接近水平適應度函數 ApproachLevelFitness,如果 ApproachLevelFitness 為0，則測試數據到達目標；然後在目標判定處，計算分支距離BranchFitness，如果 ApproachLevelFitness和BranchFitness都為0，則測試數據達到MC/DC測試目標，否貝>J，iiJi式β白勺;SlSiSMlM,^" ApproachLevelFitness+normalized(BranchFitness)， normalized(BranchFitness)表示對分支距離BranchFitness的標準化，具體的計算過程為步驟5. 1 按照步驟二的方法生成MC/DC測試用例預期結果集。步驟5. 2 按照步驟4. 1和步驟4. 2的方法獲得依賴關係集合，包括控制依賴集和數據依賴集。步驟5. 3 針對每一個目標判定，隨機生成測試數據Ta和測試數據Tb。步驟5. 4 按照步驟4. 1中的計算方法，根據依賴關係集合，分別計算測試數據Ta 和測試數據Tb的控制依賴適應度函數和數據依賴適應度函數。步驟5. 5 按照步驟4. 3中的計算方法，分別計算測試數據Ta和測試數據Tb的分支距離；步驟5. 6 進行分支距離的標準化BranchFitness (Ta)normalised,計算公式為
BvcifichFitness (T)BranchFitnessiTa )normaUsed = --—-γ——
Brancnh itness (Ia) + Brancnh itness (Ib)其中，BranchFitness (Ta)表示測試數據Ta的分支距離，BranchFitness (Tb)表示測試數據Tb的分支距離。步驟5. 7 總適應度函數值Fitness⑴為Fitness (T) = ApproachLevelFitness (T)+BranchFitness (T)normalized其中，ApproachLevelFitness (T)表示測試數據T的接近水平適應度函數； BranchFitness(T)normalized表示測試數據T的分支距離的標準化值。步驟5. 8 根據總適應度函數值比較這兩個測試數據哪個更接近於達到判定目標。步驟5. 9 若ApproachLevelFitness 和 BranchFitness 都為 0，則測試數據達到 MC/DC 測試目標，進入步驟七，否則，進入步驟六。步驟六根據得到的適應度值，使用遺傳算法的選擇、交叉、變異等遺傳操作，生成新的測試數據，並返回步驟五，計算新生成的測試數據的適應度值。步驟6. 1 選擇編碼策略，把參數集合X和域轉換為位串結構空間S。採用整型和實型混合的方式編碼染色體，問題的參數直接轉換為染色體上的基因，參數的個數轉換為染色體長度，各參數的取值區間映射為各基因的取值範圍，具體過程如下設求解問題包含η個輸入變量X1, X2,. . .，Χη，首先，用等價類劃分和邊界值分析方法處理參數的值域，其中Yi(l < i < η)表示參數Xi (1 ^n)可以取值的有限離散點的集合，IYiI表示集合的大小，建立問題解空間和染色體空間的映射關係，染色體表示為X = (X1, X2, . . . , Xn) -C= (C1, C2, ... , Cn) (2)其中，C為染色體空間解空間中的解，X為問題空間的解；步驟6.2 設計和選擇遺傳操作，包括種群大小，選擇、交叉、變異方法，以及確定交叉概率P。和變異概率Pm等遺傳參數。步驟6. 2. 1 執行排序選擇策略和精英保留策略執行排序選擇策略的具體過程為(a)根據適應值的大小，降序排列種群中的所有個體；(b)設計概率分配表，根據適應值大小，升序分配每個個體的概率值；(c)每個個體被遺傳到下一代的概率由步驟(b)中分配的概率值決定，再基於這些概率值，用輪盤賭選擇法選擇被淘汰和被複製的染色體；經過一輪排序選擇策略後，會得到一個新的種群，然後在這個新的種群基礎上再執行精英保留策略，具體過程為(a)根據適應度函數值的大小從經過排序選擇策略後得到的新種群即當前種群中獲取最佳個體和最差個體；(b)如果當前種群的最佳個體的適應度高於此前獲得的出現的最佳個體的適應度，則用當前群體的最佳個體替換此前出現的最佳個體；(c)保持迄今出現的最佳個體狀態不變，將其完整的遺傳到下一代種群中。步驟6. 2. 2 交叉操作和變異操作採用自適應的交叉概率ρ。和變異概率pm，根據群體平均適應值及當前群體最優個體適應值來自動調整交叉概率P。和變異概率Pm ;fmax表示某一代種群中最優個體的適應度， Favg表示該代群體的平均適應度，最優個體的適應度與該代群體的平均適應度的差值Δ = f__Favg，則當△越小，表示種群個體之間的適應度差別越小，說明種群此時達到局部最優的可能性較大，過早收斂的可能性也越大；當Δ越大，表示個體之間的適應度差別越大，交叉概率P。和變異概率Pm由Δ來決定，pc和pm的計算公式為pc = V Δ (3)pm = k2/ Δ (4)其中，Ic1和k2分別為交叉概率調整係數和變異概率調整係數。
步驟6. 3 隨機初始化生成種群P。步驟6. 4 計算種群P中個體位串解碼後的適應度值。步驟6. 5 按照遺傳策略，將步驟6. 2中設計的各遺傳操作作用於種群，經過選擇、 交叉和變異後，形成了新一代種群。步驟6. 6 帶著新產生的染色體即測試數據返回步驟五，計算其適應度值，判斷其性能是否滿足指標，或者是否已完成預定迭代次數，若不滿足並且沒有完成迭代次數，則進入步驟6. 1，遺傳算法從編碼操作開始，對新產生的種群重新進行選擇複製、交叉和變異，不斷迭代；若滿足指標或已完成迭代次數則直接進入步驟七。
步驟七運行結束，得到合適的測試數據。本發明具有的優點在於1、本發明提出一種基於遺傳算法的MC/DC測試數據自動生成方法，針對遺傳算法中傳統適應度函數僅依靠控制流圖中節點間的控制依賴關係，沒有考慮被測程序內部的數據依賴關係的缺陷，提出使用連結法思想收集直接或者通過數據依賴間接影響問題節點遍歷的控制節點，並將其與表徵控制依賴關係見長的傳統適應度函數相結合，構造一個新的適應度函數，以此來克服傳統的適應度函數因忽略程序內部的數據依賴關係而造成的引導信息缺乏、搜索退化的問題。2、本發明提出一種基於遺傳算法的MC/DC測試數據自動生成方法，實現了基於遺傳算法的滿足MC/DC準則的測試數據自動生成方法，對邏輯關係複雜且安全性要求較高的軟體系統進行測試時具有很大的實用價值。


圖1本發明提出的基於遺傳算法的MC/DC測試數據自動生成方法的流程圖
圖2本發明中抽象語法樹的生成過程流程圖3本發明中抽象分析樹的生成過程流程圖4本發明中MC/DC測試用例預期結果集生成流程圖5本發明中代碼插樁流程圖6本發明中建立控制依賴關係適應度函數所應用的某一程序片段；
圖7本發明中遺傳算法基本流程圖。
具體實施例方式下面將結合附圖對本發明進行詳細說明。本發明提出一種基於遺傳算法的MC/DC測試數據自動生成方法，該包括抽象語法樹的生成、抽象分析樹的生成、MC/DC測試用例預期結果集的生成、代碼插樁、適應度函數的構造、遺傳算法設計等關鍵內容，具體流程如圖1所示，具體包括以下幾個步驟步驟一對被測程序進行靜態分析，產生控制流圖、數據流圖、抽象語法樹和抽象分析樹等信息；被測程序是指將要執行測試的軟體代碼。藉助解析工具(如測試工具Testbed)對被測程序進行詞法分析、語法分析和語義分析，生成抽象語法樹。抽象語法樹是編譯程序在經過語法分析以後得到的源程序的另外一種表示。每一個語法規則對應一個相應的處理函數，並作為抽象語法樹的一個節點掛在抽象語法樹上，提供對外的接口，它能夠為下一步的代碼插樁工作做準備。抽象語法樹的生成過程如圖2所示，首先對被測程序代碼進行詞法分析和語法分析。詞法分析提供了抽象語法樹所需要的符號結點，如常量和名字；語法分析則提供了含有代表相應語法結構的中間結點的抽象語法樹；然後對被測程序代碼進行語義分析，對名字、 符號等進行的處理，將語法樹轉變為一種包括表示類型信息和符號表的標準形式，並將它們連接成樹形結構，最終得到抽象語法樹。在代碼解析過程中，藉助於工具Flex和Bison 完成被測程序代碼的抽象語法樹的建立過程。通過訪問已建立的抽象語法樹，收集判定語句子樹，同時，用大寫字母表示關係表達式，新生成的子樹被稱為抽象分析樹。每一個判定都有一個表示其邏輯結構的抽象分析樹。解析工具在生成抽象分析樹後自動生成控制流圖和數據流圖。被測程序片段為「if (χ > y&&x >z||x> y+z)」；圖2為被測程序片段生成的抽象語法樹；圖3表示從抽象語法樹中提取出來的抽象分析樹，其中，AND和OR為條件節點， A、B、C稱為抽象分析樹的葉子。步驟二 生成MC/DC測試用例預期結果集；抽象分析樹構成了生成MC/DC測試用例預期結果集的輸入。抽象分析樹中的每一個節點都會被分配一個布爾值和一個布爾變量評價，用布爾變量評價來識別是否已經計算過該節點的布爾值。以被測程序片段「if (χ > y&&x >z||x> y+z)」為範例，介紹MC/DC 測試用例預期結果集的生成過程，如圖4。具體步驟如下步驟2. 1 從抽象分析樹中提出條件節點，這些條件節點構成了抽象分析樹的葉子。每一個葉子就是一個變量，用N表示提取的葉子變量的個數；如圖5，程序片段if(x > y&&x > ζ I I χ > y+z)葉子變量為 3，即 N = 3。步驟2. 2 構建真值表，對N個葉子變量，有2n種排列組合；如圖5，被測程序片段 "if (x > y&&x > ζ |χ> y+z)，，的真值表有8種組合方式。步驟2. 3 用數字0和1填充真值表；步驟2. 4 針對真值表中的每一行步驟2. 4. 1 將真值表當前行中的布爾值對應分配給抽象分析樹的每一個葉子變量；如圖5中，真值表中第四行A = 0，B= UC= 1，將其分別分配給抽象分析樹的葉子變量。步驟2. 4. 2 自底向上評價各個條件節點的布爾值，直到抽象分析樹的頂端。最終所得的抽象分析樹的頂端的條件節點的布爾值就是這個判定語句的輸出結果值；如圖5， 真值表中第五行A = 0，B = 1、C = 1，則A&&B為真，A&&B | | C為真，因此，該行判定的最終輸出為真。(3)用輸出結果值填充真值表的輸出列。通過以上步驟，完成某一給定判定語句(被測程序)的真值表的建立。然後開始提取測試用例。考慮到MC/DC的特點，針對每一個葉子變量，需要尋找能體現葉子變量獨立影響判定結果的兩行。步驟2. 5 針對每一個葉子變量，尋找其測試用例，並添加到每個葉子變量的MC/ DC測試用例集中步驟2. 5. 1 為每一個葉子變量建立一對空的MC/DC測試用例集；步驟2. 5. 2 在真值表中，尋找其他葉子變量值固定，只有目標葉子變量改變的兩個行，如圖5，當目標葉子變量為A時，取葉子變量B和C變量值固定的兩行，可取第三行和第七行，其中葉子變量B和C固定，只有目標葉子變量A改變；步驟2. 5. 3 比較步驟2. 5. 2中的兩行的輸出結果值(由各自行的條件節點的輸出結果值組成)，如果兩行的輸出結果值不同，則這兩行就是目標葉子變量的一對測試用例，並且該測試用例是有效的，因為它們顯示了目標葉子變量的影響作用，將這兩行以成對的形式添加到步驟(1)中建立的MC/DC測試用例集中。如圖4，目標變量為A時，第三行為(010)，第七行為(110)，由真值表可知，第三行的輸出為0，第七行的輸出為1，比較這兩行的輸出值，不相同，則(010)和(110)就是變量A 的一對測試用例，並且該測試用例是有效的，已成對的形式，添加到葉子變量A的測試用例集中。其他葉子變量作為目標葉子變量，尋找其測試用例的方法與上述的葉子變量A作為目標葉子變量的尋找方法相同，並添加到每個葉子變量的MC/DC測試用例集中。步驟2.6 將每一個葉子變量的MC/DC測試用例集合併，得到測試用例集，並最小化測試用例集。該測試用例集就是使用遺傳算法搜索所要實現的目標用例集。如圖4，葉子變量A、B、C的測試用例集分別為(010，110)，(100，110)，(000，001， 010，011，100，101)，最小化該測試用例集，得到(010，100，110，101)，這組測試用例集滿足每一個葉子變量的MC/DC測試用例集覆蓋要求。步驟三對被測程序進行代碼插樁；程序插樁是測試數據自動生成過程的步驟之一。在測試過程中，測試結果數據的獲取和記錄都是通過程序插樁完成的。主要過程是在保持被測程序原有邏輯完整性的基礎上插入檢查語句，當被測程序運行時，通過檢查語句的執行採集程序的運行特徵數據。分析這些特徵數據，可以獲得程序的邏輯覆蓋等動態信息，並由此完成個體適應值的計算。其具體過程如圖5，抽象語法樹(AST)生成後，首先遍歷抽象語法樹(AST)找到插樁的位置，判斷是否是插樁點，如果不是插樁點，返回繼續遍歷抽象語法樹尋找找到插樁位置；如果是插樁點，則植入檢查語句(探針)，然後直接在抽象語法樹上以子樹的形式植入代碼的語法樹片段，判斷插樁是否完成，如已完成，則被測程序編譯運行；如未完成，返回繼續遍歷抽象語法樹(AST)找到插樁的位置，直至完成插樁。步驟四構造適應度函數；適應度函數是遺傳算法與實際問題的唯一接口，是種群中個體優劣的一種量化反映，它的構造直接影響問題求解的效率。傳統的適應度函數f(X)由兩個部分組成f(χ) = approachlevel+branchdistance第一部分approachlevel體現的是控制依賴關係，通常被稱為接近水平。第二部分branchdistance被稱為分支距離，它克服了只使用接近水平進行適應評價的局限性，分支距離衡量了在當前輸入測試數據的基礎上距離滿足目標或是滿足偏離分支的逼近程度。在MC/DC測試數據的生成這一實際問題上，本發明的目標是最終找到滿足指定目標的MC/DC的測試數據。本發明充分利用連結法在表徵測試數據依賴關係方面的優勢，使用連結法思想收集直接或者通過測試數據依賴間接影響問題條件節點遍歷的控制節點，並將其與表徵控制依賴關係見長的傳統適應度函數相結合，構造新的適應度函數，以此來克服傳統的適應度函數因忽略程序內部的數據依賴關係而造成的引導信息缺乏、搜索退化的問題。具體來說，構造適應度函數從建立控制依賴關係適應度函數、數據依賴關係適應度和分支適應度三點因素對適應度函數三個方面進行設計。步驟4. 1 建立控制依賴關係適應度函數步驟4. 1. 1 通過被測程序的控制流圖，獲得每一個判定的控制依賴關係集合；控制依賴用來描述一個目標節點y的執行關於其前面分支節點輸出的依賴性，當每一條從目標節點y到出口節點e的路徑都包含節點ζ時，稱節點ζ被目標節點y後置控制；設χ為一個任意節點，兩個節點(y，x)之間可以構成一個分支路徑，當每一條從目標節點y到出口節點e的通過分支(y，X)的路徑都包括節點Z時，稱節點Z後置控制一個分支(y，X)；當節點 Z後置控制y的一個分支，並且Z不後置控制y，則稱節點Z控制依賴於目標節點y。控制依賴關係是從結構關係角度衡量當前輸入測試數據距離抵達目標的逼近程度，它是通過控制流圖中目標與執行偏離條件節點間的關鍵節點計算得到。如某被測程序片段的控制流圖如圖6所示。從圖中可以看出，第16行的判定依賴於第12行的判定取真和第13行的判定取假，由此認為16行的目標判定依賴於經過12、 13行的控制流，這些節點被稱為臨界分支，因為他們決定控制流流向或者遠離目標。因此， 第16行判定的控制依賴關係集包含第12、13行的判定，也就是說，為達到目標節點，必須依次執行這些分支節點，並且這些節點的輸出必須是特定的。可以得到控制依賴關係集 ControlDep (16) = {12，-13}，正數表示需要執行真分支，負數表示需要執行假分支。步驟4. 1. 2 建立控制依賴關係適應度函數。建立起控制依賴關係集合後，搜索判斷哪一個測試用例執行了最多的控制節點數目，例如圖6中，一個在13行偏離的測試數據比一個在12行偏離的測試數據更接近於目標。這時就需要一個評價函數用來判斷哪一個測試數據能使執行流更接近於目標，這樣就建立控制依賴關係適應度函數。控制依賴關係適應度函數包含了控制依賴關係集合中各分支節點的目標函數。建立控制依賴關係適應度函數如下式所示。
ControlDqps^tta d e ρ ef n s e(1)其中，dependentdecision為目標的控制依賴關係集合中的控制節點數； executeddecisions表示以當前測試數據為輸入；ControlD印Fittestdata表示控制依賴關係適應度函數。如果控制依賴關係適應度函數值為0，則說明測試數據能夠到達目標判定；如果控制依賴關係適應度函數值大於0，就說明測試數據在某處偏離了目標節點，可以通過控制依賴關係適應度函數的值，精確地得到是在目標判定前的哪一個控制節點偏離出去的，稱該點為偏離節點divergecLp以圖6為例，某輸入數據使執行流在12行偏離，則有控制依賴關係適應度函數值為2-0 = 2 ；但如果在12行執行真分支，而在13行偏離，那麼控制依賴關係適應度函數值就為2-1 = 1。這樣，根據測試數據各自相對於目標判定的接近水平， 就能夠對其進行區分，並且將搜索引導向最為接近的測試數據。步驟4. 2 建立數據依賴關係適應度函數在計算依賴關係上，本發明的重點在於通過插入控制依賴關係和數據依賴關係來改進由接近水平適應度向搜索提供的引導。這種對接近水平的擴展，包含了數據依賴關係， 將搜索向更有希望的搜索區域的搜索引導。本發明旨在克服謂詞中使用flag變量或者代碼謂詞間有強烈的數據依賴關係時存在的引導缺乏和平面搜索的問題。獲取數據依賴關係適應度函數方法步驟如下定義pn為問題節點，S為用來儲存一個給定節點的依賴關係的集合，以pn和S作為獲取數據依賴關係適應度函數方法的輸入。DepSets用來儲存當前搜集到的存在依賴關係的節點集合，PV用來存儲問題節點使用的變量。S和DepSets被初始化為空集。獲取一個節點S的依賴關係適應度函數的方法如下
步驟4. 2. 1 獲取問題節點pn的控制依賴關係集合ControlD印(pn)賦給S，並將 pn使用的變量UsedVariables (pn)加到PV中；步驟4. 2. 2 對於PV中的每一個變量pv，獲取pv的最後定義集合IastDefs ；(a)對於IastDefs中每一個最後定義ld，獲取Id的控制依賴關係集合 ControlDep (Id)，並將其與S合併，得到擴展的S，然後將Id使用的變量UsedVariables (Id) 添加到一個新建的PVnew中；(b)對於ControlD印(Id)中的每一個控制節點cd，獲取它使用的變量 UsedVariables (Id)，並添加到步驟(a)中建立的PVnew集合中。步驟4. 2. 3 對於PV中的每一個變量pv，迭代獲取PV依賴關係集S (Id)。首先獲得PV中的第一個變量，獲取其依賴關係集S (Id)，返回步驟4. 2. 2，然後獲取PV中的下一個變量，直至完成PV中所有的變量，結束迭代，並將S(Id)添加到D印Sets中。步驟4. 2. 4 建立一個用於定義適應度函數的依賴關係集合定義D印Fit為適應度函數依賴關係集合，對於D印Sets中的每一個子集Si (a)添加 Si 到 D印Fit 中；(b)判斷D印Sets中每一個非Si的子集Sj，與Si是否存在then、else的分支衝突，如果不存在則合併兩個子集Si、Sj，得到新的子集Siij，並將Siij添加到D印Fit中；如果存在then、else的分支衝突則不能合併，將Si、Sj都添加到D印Fit中。步驟4. 2. 5 建立數據依賴關係適應度函數建立起數據依賴關係集合後，用計算控制依賴關係適應度函數的方法得到數據依賴關係適應度函數，其計算方法與計算控制依賴關係適應度函數的方法相同。步驟4.3 計算分支距離當測試數據抵達目標時，用分支距離來度量測試數據是否滿足測試用例，即通過計算分支距離度量測試數據距離期望測試用例的逼近程度。如果測試數據到達目標判定， 但是不滿足任一個MC/DC測試用例，那麼每一個測試數據的接近水平都為0，但分支距離不為O ；如果測試抵達目標並實現一個測試用例，那麼它的分支距離和接近水平都為O ；計算出來的分支距離的大小用來評價哪一個測試數據更接近於滿足期望的分支測試用例。一個判定的分支距離是基於這個判定的結構來計算的(1)若判定的結構中含有a = = b表達式，當a = = b為真時，分支距離的計算公式為abs(a-b)；當a== b為假時，分支距離的計算公式為a== b k:0 ；(2)若判定的結構中含有a Φ b表達式，當a興b為真時，分支距離的計算公式為 a ！ = b ？ k:0;當a乒b為假時，分支距離的計算公式為a ！ = b ？ abs(a-b) :0 ；(3)若判定的結構中含有a < b表達式，當a < b為真時，分支距離的計算公式為 a<b ？ 0:a-b+k;當a<b為假時，分支距離的計算公式為a<b ？ a-b+k:0 ；(4)若判定的結構中含有a < = b表達式，當a < = b為真時，分支距離的計算公式為a<=b 0:a-b ；當a<=b為假時，分支距離的計算公式為a b表達式，當a > b為真時，分支距離的計算公式為 a>b ？ 0:a-b;當a>b為假時，分支距離的計算公式為a>b a-b+k:0 ；(6)若判定的結構中含有a > = b表達式，當a > = b為真時，分支距離的計算公式為a>=b 0:a-b ；當a>=b為假時，分支距離的計算公式為a>=b ？ a-b+k:0 ；
(7)若判定的結構中含有a| |b表達式，當a| |b為真時，分支距離的計算公式為 min[fit(a),fit(b)]；當a | | b為假時，分支距離的計算公式為fit (a)+fit (b)；(8)若判定的結構中含有a&&b表達式，當a&&b為真時，分支距離的計算公式為 fit (a)+fit (b)；當a&&b為假時，分支距離的計算公式為max [fit (a)，fit (b)]；在嘗試達到測試用例時，需要比較接近於完成測試用例的測試數據的逼近程度， 而不是測試數據本身，所以分支距離經常是一個正值。在嘗試達到測試用例時，比較接近於完成測試用例的測試數據的逼近程度，而不是測試數據本身。因此，一個負的適應的函數值不會給搜索增加任何有價值的信息，所以返回一個函數值的絕對值。總的分支距離為判定中每一個條件的分支距離的累加。步驟五在有效的MC/DC測試用例、適應度函數公式和執行插樁代碼的基礎上，隨機產生測試數據，並在這些測試數據上執行插樁後的被測程序，獲得適應度值，同時檢驗是否滿足預期執行的目標路徑(即指測試數據是否到達目標)；如果是，則進入步驟七；否則進入步驟六；計算接近水平適應度函數 ApproachLevelFitness,如果 ApproachLevelFitness 為0，則測試數據到達目標；然後在目標判定處，計算分支距離BranchFitness。如果 ApproachLevelFitness和BranchFitness都為0，則測試數據達到MC/DC測試目標。否貝>J，iiJi式β白勺;SlSiSMlM,^" ApproachLevelFitness+normalized(BranchFitness)， normalized (BranchFitness)表示對分支距離BranchFitness的標準化,它的值在O至Ij 1之間。具體的計算過程包括以下幾個步驟步驟5. 1 按照步驟二的方法生成MC/DC測試用例預期結果集；步驟5. 2 按照步驟4. 1和步驟4. 2的方法獲得依賴關係集合，包括控制依賴集和數據依賴集；步驟5. 3 針對每一個目標判定，隨機生成2個測試數據Ta和Tb ；步驟5.4 按照步驟4. 1中的計算方法，根據依賴關係集合，分別計算2個測試數據的控制依賴適應度函數和數據依賴適應度函數；步驟5.5 按照步驟4.3中的計算方法，分別計算2個測試數據的分支距離；步驟5.6 進行分支距離的標準化BranchFitness (Ta)nmialised，計算公式為
權利要求
1. 一種基於遺傳算法的MC/DC測試數據自動生成方法，其特徵在於包括以下幾個步驟步驟一對被測程序進行靜態分析，產生控制流圖、數據流圖、抽象語法樹和抽象分析樹；步驟二 生成MC/DC測試用例預期結果集；步驟2. 1 從抽象分析樹中提出條件節點，這些條件節點構成了抽象分析樹的葉子，每一個葉子就是一個變量，用N表示提取的葉子變量的個數； 步驟2. ·2 構建真值表，對N個葉子變量，有2n種排列組合； 步驟2. 3 用數字0和1填充真值表； 步驟2. 4 針對真值表中的每一行步驟2. 4. 1 將真值表當前行中的布爾值對應分配給抽象分析樹的每一個葉子變量； 步驟2. 4. 2 自底向上評價各個條件節點的布爾值，直到抽象分析樹的頂端，最終所得的抽象分析樹的頂端的條件節點的布爾值就是這個判定語句的輸出結果值； 步驟2. 4. 3 用輸出結果值填充真值表的輸出列；步驟2. 5 針對每一個葉子變量，尋找其測試用例，並添加到每個葉子變量的MC/DC測試用例集中步驟2. 5. 1 為每一個葉子變量建立一對空的MC/DC測試用例集； 步驟2. 5. 2 在真值表中，尋找其他葉子變量值固定，只有目標葉子變量改變的兩行； 步驟2. 5. 3 比較步驟2. 5. 2中的兩行的輸出結果值，如果兩行的輸出結果值不同，則這兩行就是目標葉子變量的一對測試用例，將這兩行以成對的形式添加到步驟2. 5. 1中建立的MC/DC測試用例集中；步驟2. 6 將每一個葉子變量的MC/DC測試用例集合併，得到測試2.用例集，並最小化測試用例集；步驟三對被測程序進行代碼插樁；首先遍歷抽象語法樹找到插樁的位置，判斷是否是插樁點，如果不是插樁點，返回繼續遍歷抽象語法樹尋找找到插樁位置；如果是插樁點，則植入檢查語句，然後直接在抽象語法樹上以子樹的形式植入代碼的語法樹片段，判斷插樁是否完成，如已完成，則被測程序編譯運行；如未完成，返回繼續遍歷抽象語法樹找到插樁的位置，直至完成插樁； 步驟四構造適應度函數； 步驟4. 1 建立控制依賴關係適應度函數步驟4. 1. 1 通過被測程序的控制流圖，獲得每一個判定的控制依賴關係集合；控制依賴用來描述一個目標節點y的執行關於其前面分支節點輸出的依賴性，當每一條從目標節點y到出口節點e的路徑都包含節點ζ時，稱節點ζ被目標節點y後置控制；任意節點χ， 兩個節點(y，χ)之間可以構成一個分支路徑，當每一條從目標節點y到出口節點e的通過 (y，χ)分支路徑都包括節點ζ時，稱節點ζ後置控制一個分支(y，χ)；當節點ζ後置控制y 的一個分支，且節點ζ不後置控制節點1，稱節點ζ控制依賴於目標節點1，控制依賴關係是從結構關係角度衡量當前輸入測試數據距離抵達目標的逼近程度，通過控制流圖中目標與執行偏離條件節點間的關鍵節點計算得到；步驟4. 1. 2 建立控制依賴關係適應度函數控制依賴關係適應度函數包含了控制依賴關係集合中各分支節點的目標函數，建立控制依賴關係適應度函數為ControlD 兮 pj志 tta depe^ smns e(1)其中，cbpendent—為目標的控制依賴關係集合中的控制節點數；eXeCutedde。isi。ns 表示以當前測試數據為輸入；ControlD印Fittestdata表示控制依賴關係適應度函數；如果控制依賴關係適應度函數值為0，則測試數據能夠到達目標判定；如果控制依賴關係適應度函數值大於0，則測試數據在某處偏離了目標節點，通過控制依賴關係適應度函數的值，得到偏離節點ClivergecLde ；步驟4. 2 建立數據依賴關係適應度函數定義Pn為問題節點，S為用來儲存一個給定節點的依賴關係的集合，以pn和S作為獲取數據依賴關係適應度函數方法的輸入，DepSets用來儲存當前搜集到的存在依賴關係的節點集合，PV用來存儲問題節點使用的變量，S和DepSets被初始化為空集，獲取一個節點 S的依賴關係適應度函數的方法為步驟4. 2. 1 獲取問題節點pn的控制依賴關係集合ControlDep (pn)賦給S,並將pn使用的變量UsedVariables (pn)加到PV中；步驟4. 2. 2 對於PV中的每一個變量pv，獲取pv的最後定義集合IastDefe ；(a)對於IastDefs中每一個最後定義ld，獲取Id的控制依賴關係集合 ControlDep (Id)，並將其與S合併，得到擴展的S，然後將Id使用的變量UsedVariables (Id) 添加到一個新建的PVnew中；(b)對於Contr0IDep(Id)中的每一個控制節點cd，獲取它使用的變量 UsedVariables (Id)，並添加到步驟4. 2. 2 (a)建立的PVnew集合中；步驟4. 2. 3 對於PV中的每一個變量pv，迭代獲取PV依賴關係集S (Id)，首先獲得PV 中的第一個變量，獲取其依賴關係集S (Id)，返回步驟4. 2. 2，然後獲取PV中的下一個變量， 直至完成PV中所有的變量，結束迭代，並將S (Id)添加到D印Sets中； 步驟4. 2. 4 建立用於定義適應度函數的依賴關係集合 定義D印Fit為適應度函數依賴關係集合，對於D印Sets中的每一個子集Si (a)添加Si到D印Fit中；(b)判斷D印Sets中每一個非Si的子集~，與Si是否存在then、else的分支衝突，如果不存在，則合併兩個子集Si、Sj，得到新的子集Siij，並將Siij添加到D印Fit中；如果存在 then、else的分支衝突則不能合併，將Si、Sj都添加到D印Fit中；步驟4. 2. 5 建立數據依賴關係適應度函數建立數據依賴關係集合後，用計算控制依賴關係適應度函數的方法得到數據依賴關係適應度函數；步驟4. 3 建立分支適應度函數當測試數據抵達目標時，用分支距離來度量測試數據是否滿足期望測試用例，通過計算分支距離度量測試數據距離期望測試用例的逼近程度，如果測試數據到達目標判定，但是不滿足任一個MC/DC測試用例，那麼每一個測試數據的接近水平都為0，但分支距離不為 O ；如果測試抵達目標並實現一個測試用例，那麼它的分支距離和接近水平都為O ；計算出來的分支距離的大小用來評價哪一個測試數據更接近於滿足期望的分支測試用例；步驟五在MC/DC測試用例、適應度函數公式和執行插樁代碼的基礎上，隨機產生測試數據，並在這些測試數據上執行插樁後的被測程序，獲得適應度值，同時檢驗是否滿足預期執行的路徑；如果滿足，則進入步驟七；否則進入步驟六；計算接近水平適應度函數 ApproachLevelFitness,如果 ApproachLevelFitness 為0，則測試數據到達目標；然後在目標判定處，計算分支距離BranchFitness，如果 ApproachLevelFitness和BranchFitness都為0，則測試數據達到MC/DC測試目標，否貝>J，iiJi式β白勺;SlSiSMlM,^" ApproachLevelFitness+normalized(BranchFitness)， normalized(BranchFitness)表示對分支距離BranchFitness的標準化，具體的計算過程為步驟5. 1 按照步驟二的方法生成MC/DC測試用例預期結果集； 步驟5. 2 按照步驟4. 1和步驟4. 2的方法獲得依賴關係集合，包括控制依賴集和數據依賴集；步驟5. 3 針對每一個目標判定，隨機生成測試數據Ta和測試數據Tb ； 步驟5. 4 按照步驟4. 1中的計算方法，根據依賴關係集合，分別計算測試數據Ta和測試數據Tb的控制依賴適應度函數和數據依賴適應度函數；步驟5. 5 按照步驟4. 3中的計算方法，分別計算測試數據Ta和測試數據Tb的分支距罔；步驟5. 6 進行分支距離的標準化BranchFitness (Ta)normalised,計算公式為
全文摘要
本發明公開了一種基於遺傳算法的MC/DC測試數據自動生成方法，包括對被測程序進行靜態分析，產生控制流圖、數據流圖、抽象語法樹和抽象分析樹；生成MC/DC測試用例預期結果集；對被測程序進行代碼插樁；構造適應度函數；隨機產生測試數據，檢驗是否滿足預期執行的路徑；使用遺傳算法的選擇、交叉、變異等遺傳操作，得到合適的測試數據。本發明在適應度函數的構造上，結合連結法思想，以傳統適應度函數為基礎，提出以獲取直接或者通過數據依賴間接影響問題節點遍歷的控制節點的方法來優化接近水平適應評價。本發明對邏輯關係複雜的系統進行測試時具有很大的實用價值。
文檔編號G06F11/36GK102323906SQ20111026519
公開日2012年1月18日 申請日期2011年9月8日 優先權日2011年9月8日
發明者劉廠, 李剛, 趙玉新, 高峰 申請人:哈爾濱工程大學