一種面向路徑的測試數據自動生成方法

2023-10-18 10:58:29

專利名稱：一種面向路徑的測試數據自動生成方法
技術領域：
本發明涉及計算機軟體測試中為指定的程序路逕自動生成測試數據的方法，尤其是指定的程序路徑中包括函數調用或者可執行程序調用時的測試數據自動生成方法。
背景技術：
計算機及軟體在國民經濟和社會生活等方面的應用越來越廣泛和深入。人們在開發軟體的過程中難免會引入錯誤。軟體測試是揭示軟體錯誤的重要手段。在軟體測試中，面向路徑的測試數據生成問題可以描述為給定一個程序P和P中一條路徑W，設P的輸入空間為D，求x∈D，使得P以x為輸入運行，所經過的路徑為W。軟體測試中的控制流測試中諸如語句覆蓋、分支覆蓋、條件覆蓋、判定一條件覆蓋、路徑覆蓋等問題，數據流測試中的定義覆蓋、引用覆蓋等問題，組裝測試中的凋用對覆蓋、數據流測試等問題，以及面向斷言的測試和回歸測試中的一些問題都可以歸結為該問題。目前，測試人員一般採用手工方法尋找x。自動求解面向路徑的測試數據將有效地提高軟體測試的效率和質量。
解決面向路徑的測試數據生成的關鍵在於約束系統的建立和求解。建立約束系統的困難是分析、化簡路徑W上的各種語句成分和各種數據類型，建立儘可能簡潔的約束系統；求解約束系統的主要困難是處理可能存在的非線性約束。Matiyasevi 和E.J.Weyuker等人的研究表明不存在通用的有效的算法，對於任意的P和W，能生成使W被經過的程序輸入。但是實際應用的需要迫使人們進行研究，並提出各種方法求解該問題。
對於某種面向路徑的測試數據生成方法，當W上存在函數調用或者可執行程序調用，但是沒有提供被調用的函數或程序的原始碼，只是給出該函數編譯後的目標代碼或程序編譯後的可執行代碼，且後面的謂詞函數對這些目標代碼或可執行代碼存在數據依賴關係，此時，若該方法仍能生成測試數據，則稱該方法能夠用於黑盒測試，否則稱該方法不能用於黑盒測試。
目前，國內外面向路徑的測試數據生成方法可分為四類隨機法、試探法、靜態法和動態法。隨機法實質上是困難的。試探法主要包括遺傳算法和模擬退火法兩種。遺傳算法本身很複雜，其理論研究目前相當有限，結果也不太深入，作為遺傳算法的理論基石之一的隱性並行性的證明還存在嚴重缺陷。模擬退火法的收斂速度很緩慢。靜態法包括符號執行法和區間算術法，它們都需要對W上的語句進行轉換，故不能用於黑盒測試。符號執行方法通常要進行複雜的代數運算，且難於處理依賴於輸入變量的循環條件、數組元素下標和函數調用。區間算術法需要對變量的取值區間進行對分窮舉，當變量的取值區間為無窮區間時，該方法也是困難的。動態法可分為直線式程序法和Bogdan Korel、M.Gallagher等人、Neelam Gupta等人分別提出的方法等幾種。直線式程序法要求用戶先提供所有整數類型的變量值，並且在數值優化過程有可能陷於局部極值。Bogdan Korel和M.Gallagher等人分別提出的方法一次只考慮一個分支謂詞和一個輸入變量，且使用回溯技術，迭代次數多，資源消耗大；且Bogdan Korel提出的方法為了減小搜索的盲目性，需要採用動態數據流分析技術確定影響分支謂詞的變量，不能用於黑盒測試。
Neelam Gupta等人於1998年在ACM SIGSOFT第六屆軟體工程基礎國際研討會的論文集(Proceedings of The ACM SIGSOFT Sixth InternationalSymposium on the Foundations of Software Engineering)上發表的論文「Automated test data generation using an iterative relaxationmethod」中提出一種動態方法，從程序輸入空間D中任選一組程序輸入考察W上各分支謂詞，通過靜態、動態數據流分析確定各謂詞函數對於輸入變量的依賴關係，構造謂詞片和動態切片，建立這些謂詞函數關於當前輸入的線性算術表示，然後建立輸入變量的增量的線性約束系統，進而建立輸入變量的增量的線性方程系統，採用高斯消去法求解後得到各輸入變量的增量，從而獲得一組新的程序輸入。
該方法在構造線性約束系統的過程中必須分析W上各語句之間的靜態、動態數據依賴關係，故構造線性約束系統的效率較低，求解問題的能力較弱，不能用於黑盒測試當W上有循環語句時，必須指明該循環的循環體執行的次數，並將循環在W上展開；當W上存在函數調用時，需要採用類似宏替換的方法用實參替換被調用的函數體中的形參，將被調用的函數體在調用處展開。該方法不允許W上有goto語句；且該方法採用高斯消去法求解所建立的線性方程系統存在以下缺點若自由變量取值不適當，可能導致線性方程系統不相容。
Neelam Gupta等人於1999年在IEEE第十四屆自動化軟體工程國際會議的論文集(Proceedings of The 14th IEEE International Conference onAutomated Software Engineering)上發表的論文「UNA based iterativetest data generation and its evaluation」中提出基於最小二乘解的約束求解方法，克服了基於高斯消去法的約束求解方法的缺點，但仍存在以下缺點(1)存在這樣的線性混合整數規劃問題，至少有一組解，但是基於最小二乘解的約束求解方法找不到；(2)對於所有規模的問題，基於最小二乘解的約束求解方法尋找實數值解的迭代算法在最壞情況下不收斂。
Jon Edvardsson等人於2001年在第八屆歐洲軟體工程會議與ACMSIGSOFT第九屆軟體工程基礎國際研討會的聯合會議的論文集(Proceedings of The Joint 8th European Software EngineeringConference and 9th ACM SIGSOFT Symposium on the Foundations ofSoftware Engineering)上發表的論文「Analysis of the constraint solverin UNA based test data generation」中提出的基於線性規劃、線性整數規劃、線性混合整數規劃的約束求解方法可以克服基於最小二乘解的約束求解方法的缺點。但是基於線性規劃、線性整數規劃、線性混合整數規劃的約束求解方法仍存在以下缺點存在可行的W，並且W上某些謂詞函數中含有輸入變量的非線性函數，由於採用線性算術表示對謂詞函數進行線性化，根據某些初始程序輸入建立的線性約束系統轉化為一個矛盾的線性方程系統，如果採用基於線性規劃、線性整數規劃、線性混合整數規劃的約束求解方法，則無法生成相應的測試數據。此外，人們在建立約束系統後，還研究了一些其它的約束求解方法，效果均不理想。

發明內容
本發明所要解決的技術問題就是針對現有的面向路徑W測試數據自動生成方法的不足，提出一種新的測試數據自動生成方法，無須分析W上各語句之間的數據依賴關係，通過計算W上各謂詞函數的線性算術表示，為輸入變量建立線性約束系統，採用線性規劃、線性整數規劃、線性混合整數規劃和最小二乘解法相結合的約束求解方法，經過若干次迭代尋找所需的測試數據，該方法既能用於白盒測試，又能用於黑盒測試。
本發明的技術方案是本發明由輸入接口、詞法分析器、語法分析器、約束構造器、約束求解器、路徑滿足檢查器、輸出接口模塊實現測試數據自動生成。本發明總體邏輯結構是用戶指定程序路徑W，詞法分析器對W進行詞法分析後，語法分析器根據詞法分析的結果對W進行語法分析，將W轉換為約束構造程序和路徑滿足檢查程序，約束構造程序經編譯產生約束構造器，路徑滿足檢查程序經編譯產生路徑滿足檢查器；約束構造器根據當前程序輸入和各輸入變量的增量執行W上的語句，不分析W上的語句之間的數據依賴關係，構造W上各謂詞函數的線性算術表示，然後建立輸入變量的線性約束系統；約束求解器採用線性規劃、線性整數規劃、線性混合整數規劃和最小二乘解法相結合的方法求解線性約束系統若W上的謂詞函數均為輸入變量的線性函數，則採用基於線性規劃、線性整數規劃、線性混合整數規劃方法求解，若W上的謂詞函數中含有輸入變量的非線性函數，則採用線性規劃、線性整數規劃、線性混合整數規劃和最小二乘解法相結合的方法求解；求解後獲得新的程序輸入即測試數據；最後由路徑滿足檢查器進行檢查，若該程序輸入能使W被經過則結束，若該程序輸入不能使W被經過則根據W上所有謂詞函數是否為輸入變量的線性函數以及迭代次數上限決定是否繼續迭代求解；求解結果由輸出接口輸出。本發明定義了以下四個名詞定義1.分支謂詞程序路徑W上具有明確取值要求的判斷語句中的條件表達式稱為分支謂詞。不失一般性，設分支謂詞為Exp1？Exp2的形式，其中Exp1？Exp2是關係表達式，Exp1和Exp2是算術表達式，？∈{＞，≥，＝，＜，≤}。
循環語句可以轉換為等價的用判斷語句和轉移語句表達的形式。當人們關心W上的循環體的內部執行情況時，可以將循環展開。當人們不關心循環體的內部執行情況時，可以直接將該循環作為一個黑盒放在W上，不必將其展開。
當人們不關心W上判斷語句是執行「真」分支還是「假」分支時，可以直接將該判斷語句作為一個黑盒放在W上。定義2.謂詞結點稱分支謂詞所在的判斷語句為謂詞結點。定義3.謂詞函數謂詞結點的分支謂詞Exp1？Exp2可被轉換成等價的分支謂詞形式F？0，其中F為算術表達式Exp1-Exp2，稱F為該謂詞結點的謂詞函數。定義4.線性算術表示設ni為W上的謂詞結點，並且X＝x1，…，xt和Y＝y1，…，yt)為程序輸入和輸入變量的增量，其中t為W上輸入變量的個數，yj≠0，j＝1，...，t，若ni的謂詞函數為F，則稱L(i，X，Y，W)＝di1v1+…+ditvt+ci為W上ni處F關於X和Y的線性算術表示，其中dij＝(Pnewij-Poldi)/yj，ci＝Poldi-di1×x1-…-dit×xt，Poldi和Pnewij分別為按照程序輸入X和X+0，…，0，yj，0，…，0依次執行W上的ni之前的除謂詞結點之外的語句，計算F所得之值。
本發明允許程序中變量的數據類型為整數類型，實數類型，基本數據類型為整數類型或實數類型的數組、結構等複合類型，以及指向上述各種類型的指針類型。
如果程序中包含了布爾類型的變量，就將其轉化為實數類型，用大於或等於零的數表示「真」值，用負數表示「假」值。如果一條路徑上的某分支謂詞中的條件表達式由兩個或兩個以上的布爾類型的變量的合取組成(如A∧B)，那麼就將這個分支謂詞視同在經過該路徑時必須同時滿足的多個分支謂詞A≥0、B≥0。如果一條路徑上的某分支謂詞中的條件表達式由兩個或兩個以上的布爾變量的析取組成(如A∨B)，那麼在該路徑上一次只取一個分支謂詞A≥0或B≥0與其它分支謂詞一起考慮。如果用其中的一個沒找到解，就試另一個。
若分支謂詞為Exp1≠Exp2，則將其轉化為等價的形式(Exp1＞Exp2)∨(Exp1＜Exp2)，然後按與布爾類型的變量的析取類似的方法進行處理即可。
字符類型的變量的取值實質上是取值範圍受限的整數值。對於字符類型的變量，用ASCII字符集將字符類型的值映射為整數類型，並引入附加的約束以限制它的整數解落在有效的取值範圍內，然後用ASCII字符集將整數解映射回相應的字符類型的值。按類似的方法可以處理枚舉類型的變量。
W中允許包括函數調用或者可執行程序調用，本發明將被調用的函數或可執行程序視為黑盒，直接將調用語句放在W上。若黑盒中包含輸入語句，用戶還需提供黑盒的接口規範規定的黑盒中的輸入變量的個數及各輸入變量的數據類型。
本發明具體實現步驟是1.用戶從輸入接口指定程序路徑W、各輸入變量的初值和增量以及其它參數值，如W上的所有謂詞函數是否均為輸入變量的線性函數、當W上的某謂詞函數為輸入變量的非線性函數時迭代求解的次數上限、以及當W上存在黑盒且黑盒中包含輸入語句時，根據黑盒的接口規範所規定的黑盒中的輸入變量的個數及各輸入變量的數據類型等。
2.詞法分析器對W進行詞法分析後，語法分析器根據詞法分析的結果對W進行語法分析，將W轉換為約束構造程序和路徑滿足檢查程序，約束構造程序經編譯產生約束構造器，路徑滿足檢查程序經編譯產生路徑滿足檢查器。
3.約束構造器根據當前程序輸入和各輸入變量的增量執行W上的語句，構造W上各謂詞函數的線性算術表示，方法是用戶輸入程序路徑W、輸入變量的初值X＝x1，…，xt和輸入變量的增量Y＝y1，…，yt。對於W上的m個謂詞結點n1…，nm，依次令ni的謂詞函數的線性算術表示為L(i，X，Y，W)＝di1v1+…+ditvt+ci，按照X依次執行W上的ni之前的除謂詞結點之外的語句，計算ni的謂詞函數值Poldi，並且令ci＝Poldi，其中i＝1，...，m。然後計算各線性算術表示的係數值和常數項，計算方法是對於W上的t個輸入變量v1，…，vt的初值x1，…，xt，依次將第j個輸入變量vj的值xj與其增量yj相加，其餘輸入變量的值保持不變，將新的輸入記作Z，然後按照Z依次執行W上的ni之前的除謂詞結點之外的語句，計算ni的謂詞函數值Pnewij，並且令dij＝(Pnewij-Poldi)/yj，ci＝ci-dij×xj，其中i＝1，...，m，j＝1，...，t。然後建立輸入變量的線性約束系統如果謂詞結點nj的分支謂詞F？0的值應該為「真」，那麼由nj的謂詞函數的線性算術表示L(i，X，Y，W)建立的線性約束為L(i，X，Y，W)？0，其中的關係操作符與F？0中的相同；如果謂詞結點ni的分支謂詞F？0的值應該為「假」，那麼由ni的謂詞函數的線性算術表示L(i，X，Y，W)建立的線性約束為L(i，X，Y，W)？？0，其中的關係操作符「？？」與F？0中的「？」相反，即當「？」為「＞」時，「？？」為「≤」；當「？」為「≥」時，「？？」為「＜」；當「？」為「＜」時，「？？」為「≥」；當「？」為「≥」時，「？？」為「＜」；當「？」為「＝」時，「？？」為「≠」，即(L(i，X，Y，W)＞0)∨(L(i，X，Y，W)＜0)。
4.約束求解器採用線性規劃、線性整數規劃、線性混合整數規劃和最小二乘解法相結合的方法求解該線性約束系統若用戶指定W上的謂詞函數均為輸入變量的線性函數，則採用線性規劃、線性整數規劃、線性混合整數規劃方法求解；若用戶指定W上的謂詞函數中含有輸入變量的非線性函數，則先採用線性規劃、線性整數規劃、線性混合整數規劃方法求解，若無法找到解，則將該線性約束系統轉換為線性方程系統，求它的最小二乘解。
4.1若用戶指定W上的謂詞函數均為輸入變量的線性函數，並且線性規劃、線性整數規劃、線性混合整數規劃方法找到解，則由路徑滿足檢查器進行檢查，若該解能使W被經過則從輸出接口輸出解，然後結束；若該解不能使W被經過則從輸出接口給出求解精度可能不夠的警告，然後結束。
4.2若用戶指定W上的謂詞函數均為輸入變量的線性函數，所有輸入變量均無整數限制，並且線性規劃方法找不到解，則從輸出接口給出W不可行的結論，然後結束。
4.3若用戶指定W上的謂詞函數均為輸入變量的線性函數，某輸入變量有整數限制，並且線性整數規劃、線性混合整數規劃方法找不到解，則從輸出接口給出W可能不可行的結論，然後結束。
4.4若用戶指定W上的某謂詞函數為輸入變量的非線性函數，則先採用線性規劃、線性整數規劃、線性混合整數規劃方法求解，若找到解，則由路徑滿足檢查器進行檢查，若該解能使W被經過則從輸出接口輸出解，然後結束；若該解不能使W被經過，並且當前迭代次數已經達到用戶指定的迭代次數上限，則從輸出接口給出W可能不可行的結論，然後結束；若該解不能使W被經過，並且當前迭代次數尚未達到用戶指定的迭代次數上限，則當前迭代次數加一，將該解作為新的當前程序輸入，轉第3步進行下次迭代。
4.5若用戶指定W上的謂詞函數中含有輸入變量的非線性函數，則先採用線性規劃、線性整數規劃、線性混合整數規劃方法求解，若找不到解，則將該線性約束系統轉換為線性方程系統，求它的最小二乘解。由路徑滿足檢查器進行檢查，若該最小二乘解能使W被經過則從輸出接口輸出該最小二乘解，然後結束；若該最小二乘解不能使W被經過，並且當前迭代次數已經達到用戶指定的迭代次數上限，則從輸出接口給出W可能不可行的結論，然後結束；若該最小二乘解不能使W被經過，並且當前迭代次數尚未達到用戶指定的迭代次數上限，則當前迭代次數加一，將最小二乘解作為新的當前程序輸入，轉第3步進行下次迭代。
採用本發明進行軟體測試數據自動生成可以達到如下有益效果1.無須分析程序路徑W上各語句之間的數據依賴關係，構造線性約束系統的效率高，分析表明，Neelam Gupta等人提出的方法構造線性約束系統的時間複雜性為O(k2·n+k·n·lmax·t)，空間複雜性為O(k2·n)，本發明構造線性約束系統的時間複雜性和空間複雜性分別為O(k·t)和O(m·t)，其中k，n，lmax，t，m分別表示W上的語句個數、被定值變量個數(即輸入變量個數與被賦值變量個數之和)、各謂詞結點的謂詞片中語句個數的最大值、輸入變量個數和謂詞結點個數，並且m≤k，t≤n。
2.無須分析程序路徑W上各語句之間的數據依賴關係，生成測試數據的能力強，不僅能夠用於白盒測試，而且能夠用於黑盒測試。當W上有循環語句而且人們不關心循環體的內部執行情況時，本發明能夠直接將該循環作為一個黑盒放在W上，不必將其展開。當人們不關心W上判斷語句是執行「真」分支還是「假」分支時，本發明同樣可以直接將該判斷語句作為一個黑盒放在W上。當W上存在函數調用或可執行程序調用時，本發明可以將被調用的函數體或可執行程序視為黑盒，不必在調用處展開，從而進一步提高了效率。本發明能夠直接處理goto語句。
3.約束求解器採用線性規劃、線性整數規劃、線性混合整數規劃和最小二乘解法相結合的方法求解線性約束系統，結合了線性規劃、線性整數規劃、線性混合整數規劃和最小二乘解法的優點，通用性好，對於謂詞函數均為輸入變量的線性函數或者謂詞函數中含有輸入變量的非線性函數的一些程序路徑能夠有效地找到解。
4.當程序路徑W上各謂詞函數均為輸入變量的線性函數且所有輸入變量均無整數限制時，迭代一次後，本發明或者能找到所需的測試數據，或者保證該程序路徑不可行。
5.可移植性好，不受程序設計語言和作業系統的限制，易於移植到各種程序設計語言和作業系統。
6.適用範圍廣，能夠用於單元測試、集成(組裝)測試等階段以及面向斷言的測試數據自動生成和回歸測試數據的自動生成。


圖1是本發明總體邏輯結構圖。
圖2是本發明的總流程圖。
圖3是本發明構造線性算術表示的示意圖。
圖4是本發明求解線性約束系統的示意圖。
具體實施例方式圖1是本發明總體邏輯結構圖。本發明由輸入接口、詞法分析器、語法分析器、約束構造器、約束求解器、路徑滿足檢查器、輸出接口模塊實現測試數據自動生成。其總體邏輯結構是用戶指定程序路徑W，詞法分析器對W進行詞法分析後，語法分析器根據詞法分析的結果對W進行語法分析，將W轉換為約束構造程序和路徑滿足檢查程序，約束構造程序經編譯產生約束構造器，路徑滿足檢查程序經編譯產生路徑滿足檢查器；約束構造器根據當前程序輸入和各輸入變量的增量執行W上的語句，不分析W上的語句之間的數據依賴關係，計算W上各謂詞函數的線性算術表示，然後建立輸入變量的線性約束系統；約束求解器採用線性規劃、線性整數規劃、線性混合整數規劃和最小二乘解法相結合的方法求解線性約束系統；求解後獲得新的程序輸入即測試數據；最後由路徑滿足檢查器進行檢查，若該程序輸入能使W被經過則結束，若該程序輸入不能使W被經過則根據W上所有謂詞函數是否為輸入變量的線性函數以及迭代次數上限決定是否繼續迭代求解；求解結果由輸出接口輸出。
圖2是本發明的總流程圖，圖4描述了本發明求解線性約束系統的方法。本發明實現步驟是1.用戶從輸入接口指定程序路徑W、各輸入變量的初值和增量以及其它參數值，如W上的所有謂詞函數是否均為輸入變量的線性函數、當W上的某謂詞函數為輸入變量的非線性函數時迭代求解的次數上限、以及當W上存在黑盒且黑盒中包含輸入語句時，根據黑盒的接口規範所規定的黑盒中的輸入變量的個數及各輸入變量的數據類型等。
2.詞法分析器對W進行詞法分析後，語法分析器根據詞法分析的結果對W進行語法分析，將W轉換為約束構造程序和路徑滿足檢查程序，約束構造程序經編譯產生約束構造器，路徑滿足檢查程序經編譯產生路徑滿足檢查器。
3.約束構造器根據當前程序輸入和各輸入變量的增量執行W上的語句，計算W上各謂詞函數的線性算術表示，建立輸入變量的線性約束系統。
4.約束求解器採用線性規劃、線性整數規劃、線性混合整數規劃和最小二乘解法相結合的方法求解該線性約束系統，如圖4若用戶指定W上的謂詞函數均為輸入變量的線性函數，則採用線性規劃、線性整數規劃、線性混合整數規劃方法求解；若用戶指定W上的謂詞函數中含有輸入變量的非線性函數，則先採用線性規劃、線性整數規劃、線性混合整數規劃方法求解，若無法找到解，則將該線性約束系統轉換為線性方程系統，求它的最小二乘解。
4.1若用戶指定W上的謂詞函數均為輸入變量的線性函數，並且線性規劃、線性整數規劃、線性混合整數規劃方法找到解，則由路徑滿足檢查器進行檢查，若該解能使W被經過則從輸出接口輸出解，然後結束；若該解不能使W被經過則從輸出接口給出求解精度可能不夠的警告，然後結束。
4.2若用戶指定W上的謂詞函數均為輸入變量的線性函數，所有輸入變量均無整數限制，並且線性規劃方法找不到解，則從輸出接口給出W不可行的結論，然後結束。
4.3若用戶指定W上的謂詞函數均為輸入變量的線性函數，某輸入變量有整數限制，並且線性整數規劃、線性混合整數規劃方法找不到解，則從輸出接口給出W可能不可行的結論，然後結束。
4.4若用戶指定W上的某謂詞函數為輸入變量的非線性函數，則先採用線性規劃、線性整數規劃、線性混合整數規劃方法求解，若找到解，則由路徑滿足檢查器進行檢查，若該解能使W被經過則從輸出接口輸出解，然後結束；若該解不能使W被經過，並且當前迭代次數已經達到用戶指定的迭代次數上限，則從輸出接口給出W可能不可行的結論，然後結束；若該解不能使W被經過，並且當前迭代次數尚未達到用戶指定的迭代次數上限，則當前迭代次數加一，將該解作為新的當前程序輸入，轉第3步進行下次迭代。
4.5若用戶指定W上的謂詞函數中含有輸入變量的非線性函數，則先採用線性規劃、線性整數規劃、線性混合整數規劃方法求解，若找不到解，則將該線性約束系統轉換為線性方程系統，求它的最小二乘解。由路徑滿足檢查器進行檢查，若該最小二乘解能使W被經過則從輸出接口輸出該最小二乘解，然後結束；若該最小二乘解不能使W被經過，並且當前迭代次數已經達到用戶指定的迭代次數上限，則從輸出接口給出W可能不可行的結論，然後結束；若該最小二乘解不能使W被經過，並且當前迭代次數尚未達到用戶指定的迭代次數上限，則當前迭代次數加一，將最小二乘解作為新的當前程序輸入，轉第3步進行下次迭代。
圖3描述了本發明構造線性算術表示的方法。用戶輸入程序路徑W、輸入變量的初值X＝x1，…，xt和輸入變量的增量Y＝y1，…，yt。對於W上的m個謂詞結點n1，…，nm，依次令ni的謂詞函數的線性算術表示為L(i，X，Y，W)＝di1v1+…+ditvt+ci，按照X依次執行W上的ni之前的除謂詞結點之外的語句，計算ni的謂詞函數值Poldi，並且令ci＝Poldi，其中i＝1，...，m。然後計算各線性算術表示的係數值和常數項，計算方法是對於W上的t個輸入變量v1，…，vt的初值x1，…，xt，依次將第j個輸入變量vj的值xj與其增量yj相加，其餘輸入變量的值保持不變，將新的輸入記作Z，然後按照Z依次執行W上的ni之前的除謂詞結點之外的語句，計算ni的謂詞函數值Pnewij，並且令dij＝(Pnewij-Poldi)/yj，ci＝ci-dij×xj，其中i＝1，...，m，j＝1，...，t。
根據軟體工程的思想，本發明採用面向對象的方法，使用UML進行設計，在Windows98作業系統下用C++語言和Java語言對本發明進行了實現，開發出為C語言和Java語言程序路逕自動生成測試數據的原型工具(Path-wise Test Data Generator，簡稱PTDG)。
在以下函數中，對於一個具有十個元素的數組X，其中各元素的值是任意輸入的，要求採用冒泡排序方法對X中各元素進行排序，使得各元素按不減序排列，即X
＜＝X[1]＜＝X[2]＜＝X[3]＜＝X[4]＜＝X[5]＜＝X[6]＜＝X[7]＜＝X[8]＜＝X[9]。但是在該函數中存在一個錯誤，即外層循環的結束條件「i＜＝7」應為「i＜＝8」。
void Bubble_Sort(int X[])　　{　　int temp，i，j；!-- SIPO DP --dp/　　scanf(″％d％d％d％d％d％d％d％d％d％d″，　　amp;X
， amp;X[1]， amp;X[2]， amp;X[3]， amp;X[4]，　　amp;X[5]， amp;X[6]， amp;X[7]， amp;X[8]， amp;X[9])；　　for(i＝0；i＜＝7；i++)　　for(j＝0；j＜＝8；j++)　　if(X[j]＞X[j+1]){　　temp＝X [j]；　　X[j]＝X[j+1]；　　X[j+1]＝temp；}　　}當在以下程序路徑W1＝n1，n2，n3中調用該函數，n1int X[10]；n2Bubble_Sort(X)；n3@X
＞X[1]@PTDG從初始輸入X
＝X[1]＝X[2]＝X[3]＝X[4]＝X[5]＝X[6]＝X[7]＝X[8]＝X[9]＝1出發，假設各輸入變量的增量為1，1，1，1，1，1，1，1，1，-1，經過兩次迭代能夠找到使W1被經過的程序輸入X
＝X[1]＝X[2]＝X[3]＝X[4]＝X[5]＝X[6]＝X[7]＝X[8]＝0，X[9]＝-1。
上述結果表明，存在程序輸入X
＝X[1]＝X[2]＝X[3]＝X[4]＝X[5]＝X[6]＝X[7]＝X[8]＝0，X[9]＝-1，當按照這組輸入執行W1時，W1是可行的，即調用函數Bubble_Sort後，會出現「X
＞X[1]」的結果，故違反了設計要求，從而發現函數中存在錯誤。上述結果也表明PTDG可以直接處理函數調用。進一步的實驗表明當Bubble_Sort的函數體儀為目標代碼而無原始碼時，PTDG仍然能夠找到相同的解，而Neelam Gupta等人提出的方法則無法構造線性算術表示。因此本發明能夠用於黑盒測試。
在以下程序中，謂詞函數中含有輸入變量的非線性函數「x*x」。
n1float x；n2scanf(″％f″，x)；n3if(x＜-1)n4if(x*x＞0)
n5printf(″Ok！″)；n6else printf(″No.″)；n7else printf(″No.″)；對於其中的路徑W2＝n1，n2，n3，n4，n5，從初始輸入x＝1出發，假設輸入變量x的增量為1，PTDG所得到的如下線性約束系統n3x+1＜0n43x-2＞0是矛盾的，儀採用基於線性規劃、線性整數規劃、線性混合整數規劃的約束求解方法無法進行求解，PTDG採用線性規劃、線性整數規劃、線性混合整數規劃和最小二乘解法相結合的約束求解方法卻能夠經過六次迭代找到使W2被經過的程序輸入-1.388210。由此可見本發明強大的尋找測試數據的能力。
發明人還用其它一些實際的程序路徑對PTDG進行實驗。實驗結果表明PTDG能夠處理的程序中的語句包括順序、條件、循環、轉移等語句，其中順序語句包括說明語句、賦值語句、輸入語句、輸出語句等；能夠為整數類型、浮點類型、雙精度浮點類型的輸入變量生成測試數據；可以直接處理數組、結構、指針和函數調用。並且可以擴充為支持布爾類型、字符類型、枚舉類型。另外的實驗表明PTDG能夠用於面向斷言的測試以及回歸測試等場合的測試數據自動生成。
人們通常分單元測試、組裝測試、確認測試等階段對大型軟體進行測試。本發明可以直接應用在單元測試的控制流測試中諸如語句覆蓋、分支覆蓋、條件覆蓋、判定-條件覆蓋、路徑覆蓋等，數據流測試中的定義覆蓋、引用覆蓋等方面。由於本發明能夠用於黑盒測試，故本發明支持更高層次的軟體測試，譬如組裝測試中的調用對覆蓋、數據流測試。本發明也可以用於面向斷言的測試以及回歸測試等方面。
權利要求
1.一種面向路徑的測試數據自動生成方法，由輸入接口、詞法分析器、語法分析器、約束構造器、約束求解器、路徑滿足檢查器、輸出接口模塊實現測試數據自動生成，其特徵在於其實現步驟是[1]用戶從輸入接口指定程序路徑W、各輸入變量的初值和增量以及其它參數值，如W上的所有謂詞函數是否均為輸入變量的線性函數、當W上的某謂詞函數為輸入變量的非線性函數時迭代求解的次數上限、以及當W上存在黑盒且黑盒中包含輸入語句時，根據黑盒的接口規範所規定的黑盒中的輸入變量的個數及各輸入變量的數據類型等；[2]詞法分析器對W進行詞法分析後，語法分析器根據詞法分析的結果對W進行語法分析，將W轉換為約束構造程序和路徑滿足檢查程序，約束構造程序經編譯產生約束構造器，路徑滿足檢查程序經編譯產生路徑滿足檢查器；[3]約束構造器根據當前程序輸入和各輸入變量的增量執行W上的語句，不分析W上的語句之間的數據依賴關係，構造W上各謂詞函數的線性算術表示，然後建立輸入變量的線性約束系統；[4]約束求解器採用線性規劃、線性整數規劃、線性混合整數規劃和最小二乘解法相結合的方法求解該線性約束系統若用戶指定W上的謂詞函數均為輸入變量的線性函數，則採用線性規劃、線性整數規劃、線性混合整數規劃方法求解；若用戶指定W上的謂詞函數中含有輸入變量的非線性函數，則先採用線性規劃、線性整數規劃、線性混合整數規劃方法求解，若無法找到解，則將該線性約束系統轉換為線性方程系統，求它的最小二乘解；求解後獲得新的程序輸入即測試數據；最後由路徑滿足檢查器進行檢查，若該程序輸入能使W被經過則結束，若該程序輸入不能使W被經過則根據W上所有謂詞函數是否為輸入變量的線性函數以及迭代次數上限決定是否繼續迭代求解；求解結果由輸出接口輸出。
2.權利要求1所述的一種面向路徑的測試數據自動生成方法，其特徵在於所述約束構造器構造W上各謂詞函數的線性算術表示的方法是用戶輸入程序路徑W、輸入變量的初值X＝x1，…，xt和輸入變量的增量Y＝y1，…，yt；對於W上的m個謂詞結點n1，.…，nm，依次令ni的謂詞函數的線性算術表示為L(i，X，Y，W)＝di1v1+…+ditvt+ci，按照X依次執行W上的ni之前的除謂詞結點之外的語句，計算ni的謂詞函數值Poldi，並且令ci=Poldi，其中i=1，...，m；然後計算各線性算術表示的係數值和常數項，計算方法是對於W上的t個輸入變量v1，…，vt的初值x1，…，xt，依次將第j個輸入變量vj的值xj與其增量yj相加，其餘輸入變量的值保持不變，將新的輸入記作Z，然後按照Z依次執行W上的ni之前的除渭詞結點之外的語句，計算ni的謂詞函數值Pnewij，並且令dij＝(Pnewij-Poldi)/yi，ci＝ci-dij×xj，其中i=1，...，m，j＝1，...，t；然後建立輸入變量的線性約束系統如果渭詞結點ni的分支調詞F？0的值應該為「真」，那麼由ni的謂詞函數的線性算術表示L(i，X，Y，W，)建立的線性約束為L(i，X，Y，W)？0，其中的關係操作符與F？0中的相同；如果謂詞結點ni的分支謂詞F？0的值應該為「假」，那麼由ni的謂詞函數的線性算術表示L(i，X，Y，W)建立的線性約束為L(i，X，Y，W)？？0，其中的關係操作符「？？」與F？0中的「？」相反，即當「？」為「＞」時，「？？」為「≤」；當「？」為「≥」時，「？？」為「＜」；當「？」為「＜」時，「？？」為「≥」；當「？」為「≥」時，「？？」為「＜」；當「？」為「＝」時，「？？」為「≠」，即(L(i，X，Y，W)＞0)∨(L(i，X，Y，W)＜0)。
3．如權利要求1所述的一種面向路徑的測試數據自動生成方法，其特徵在於所述線性規劃、線性整數規劃、線性混合整數規劃和最小二乘解法相結合的方法求解線性約束系統的過程是3.1若用戶指定W上的謂詞函數均為輸入變量的線性函數，並且線性規劃、線性整數規劃、線性混合整數規劃方法找到解，則由路徑滿足檢查器進行檢查，若該解能使W被經過則從輸出接口輸出解，然後結束；若該解不能使W被經過則從輸出接口給出求解精度可能不夠的警告，然後結束；3.2若用戶指定W上的謂詞函數均為輸入變量的線性函數，所有輸入變量均無整數限制，並且線性規劃方法找不到解，則從輸出接口給出W不可行的結論，然後結束；3.3若用戶指定W上的謂詞函數均為輸入變量的線性函數，某輸入變量有整數限制，並且線性整數規劃、線性混合整數規劃方法找不到解，則從輸出接口給出W可能不可行的結論，然後結束；3.4若用戶指定W上的某謂詞函數為輸入變量的非線性函數，則先採用線性規劃、線性整數規劃、線性混合整數規劃方法求解，若找到解，則由路徑滿足檢查器進行檢查，若該解能使W被經過則從輸出接口輸出解，然後結束；若該解不能使W被經過，並且當前迭代次數已經達到用戶指定的迭代次數上限，則從輸出接口給出W可能不可行的結論，然後結束；若該解不能使W被經過，並且當前迭代次數尚未達到用戶指定的迭代次數上限，則當前迭代次數加一，將該解作為新的當前程序輸入，轉第[3]步進行下次迭代；3.5若用戶指定W上的調詞函數中含有輸入變量的非線性函數，則先採用線性規劃、線性整數規劃、線性混合整數規劃方法求解，若找不到解，則將該線性約束系統轉換為線性方程系統，求它的最小二乘解；山路徑滿足檢查器進行檢查，若該最小二乘解能使W被經過則從輸出接口輸出該最小二乘解，然後結束；若該最小二乘解不能使W被經過，並且當前迭代次數已經達到用戶指定的迭代次數上限，則從輸出接口給出W可能不可行的結論，然後結束；若該最小二乘解不能使W被經過，並且當前迭代次數尚未達到用戶指定的迭代次數上限，則當前迭代次數加一，將最小二乘解作為新的當前程序輸入，轉第[3]步進行下次迭代。
全文摘要
本發明公開了一種面向路徑的測試數據自動生成方法，目的是提出一種無數據依賴關係分析的能夠用於白盒、黑盒的測試數據自動生成的方法。本發明約束構造器根據當前程序輸入和各輸入變量的增量執行路徑W上的語句，不分析W上的語句之間的數據依賴關係，構造W上各謂詞函數的線性算術表示，然後建立輸入變量的線性約束系統；約束求解器採用線性規劃、線性整數規劃、線性混合整數規劃和最小二乘解法相結合的方法求解線性約束系統，經過若干次迭代尋找所需的測試數據。本發明構造線性約束系統的效率高，生成測試數據的能力強，既能用於白盒測試，又能用於黑盒測試；通用性和可移植性好，適用範圍廣。
文檔編號G06F11/36GK1402133SQ0213961
公開日2003年3月12日 申請日期2002年9月13日 優先權日2002年9月13日
發明者單錦輝, 王戟, 齊治昌 申請人:中國人民解放軍國防科學技術大學