一種基於擴展有限狀態機可行路徑分析的測試用例自動生成方法
2023-10-09 15:46:44
專利名稱：一種基於擴展有限狀態機可行路徑分析的測試用例自動生成方法
技術領域：
本發明屬於軟體測試技術領域，尤其是模型測試技術領域，用於擴展有限狀態機 (Extended Finite State Machine)中路徑可行性分析，一種基於擴展有限狀態機的自動化測試用例生成方法。
背景技術：
軟體測試是軟體發展過程的重要階段，據估計測試花費佔整個軟體開發過程的花費的30%-50%。目前測試的方式主要以人工測試為主，人工測試準確性較差，需要花費大量時間和費用。而測試自動化方法可以減少測試過程的代價，提高軟體測試的質量。自動化生成測試用例的一種典型方法是創建軟體的測試模型，並且在模型的基礎上自動化生成測試用例。近年來，隨著面向對象技術的成熟和廣泛應用，基於模型軟體測試方法得到了快速的發展，成為研究的熱點之一，引起了學術界和工業界的廣泛關注。模型驅動的測試方法是在軟體開發過程中通過建立各個級別的模型，在此基礎上進行測試用例的生成、測試用例的執行和測試用例的評估，以檢測軟體中存在的錯誤，驗證實際系統是否符合實際需求， 擴展有限狀態機(Extended Finite State Machine)是其中應用最廣泛的模型之一。擴展有限狀態機(Extended Finite State Machine)是由有限狀態機(Finite State Machine) 擴充而來，有限狀態機模型只能表達實際應用的控制流部分而擴展有限狀態機則既可以表達控制流也可以表達數據流部分，描述複雜的應用系統更加適合。目前已有許多基於有限狀態機模型的測試序列生成方法，通用的方法是利用圖論的方法遍歷有限狀態機，生成測試序列以達到規定的覆蓋。然而利用擴展有限狀態機生成測試用例仍然是一個開放研究課題，擴展有限狀態機中不可行路徑的存在使得傳統的基於有限狀態機的方法不能應用於擴展有限狀態機模型，擴展有限狀態機模型中路徑是否可行是個不可判定問題，目前還沒有相關的有效方法能夠全面檢測擴展有限狀態機模型中存在的不可行路徑。此外對應路徑的測試數據生成和測試預言(oracle)自動化問題也是擴展有限狀態機模型測試的難題，測試預言是用來判定一個被測系統是否正確的一種機制。基於可行路徑分析的測試用例自動生成技術旨在解決上述問題。該測試用例自動化生成方法通過路徑可行性分析儘可能的避開不可行路徑、自動化的生成測試用例，並且達到規定的測試充分準則。該方法結合了靜態分析和動態分析技術來找到一個較小的可行路徑集合達到指定的路徑覆蓋準則，此外還開發了可執行模型，通過運行時信息反饋和分散搜索(Scatter Search)技術來直接指導測試數據的生成。可執行模型帶來的另一個好處是可以用來自動化的創建測試預言。
發明內容
本發明要解決的問題是通過路徑可行性分析識別部分不可行路徑，並儘可能的避開其餘的具有較高不可行概率的路徑，自動化生成路徑對應的測試數據和的創建測試預
4言，大大提高測試用例生成的效率。本發明的技術方案為一種自動化測試用例生成方法，基於擴展有限狀態機可行路徑分析，通過路徑可行性分析儘可能的避開不可行路徑，自動化生成測試用例和創建測試預言，結合靜態分析和動態分析技術獲取可行路徑集合達到指定的路徑覆蓋準則，包括以下步驟1)根據擴展有限狀態機模型生成測試路徑候選集，利用遍歷、循環路徑分析和插入方法，生成從擴展有限狀態機模型的起始狀態結點到其他結點的所有路徑作為候選路徑，並約束規定路徑中只插入有限次循環路徑或自循環路徑；2)路徑可行性評估策略，利用靜態分析技術對候選路徑集中的路徑進行分析，首先識別出其中不可行路徑，將這部分不可行路徑從路徑候選集中移除，然後對其餘路徑的可行性提出評估公式，對其進行不可行概率評估並計算出評估值，對候選路徑集中的路徑按不可行概率從小到大進行排序；3)開發可執行模型，利用圖論遍歷方法和表達式語義解析工具使得擴展有限狀態機模型可執行化，可執行模型定義了模型的動態行為並通過使用語義執行使得靜態模型具有類似程序的動態執行能力；4)自動生成測試數據和測試預言，由步驟幻的可執行模型的動態執行過程獲得相應的運行時反饋信息，利用所述反饋信息結合分散搜索技術Matter karch來指導測試數據生成並自動創建測試預言，生成的測試用例觸發對應的路徑；測試用例的生成過程為首先從步驟1)和步驟2、生成的測試路徑候選集中按不可行概率順序選取一條候選路徑，檢查該路徑中的邊是否被指定的測試充分性準則覆蓋， 若是則跳過該路徑選取候選集中的下一條路徑進行生成，以避開不可行路徑，提高測試用例生成的效率，同時動態識別不可行路徑；否則利用步驟幻開發的可執行模型和步驟4)獲取的運行時反饋信息，結合分散搜索方法Matter karch，對選擇的路徑進行語義執行，並利用反饋信息搜索狀態空間中的解，若在規定迭代次數範圍內找到解集則將結果加入測試用例結果集，否則認為該路徑不可執行。步驟1)具體為首先利用圖論的遞歸遍歷算法找出從擴展有限狀態模型源結點到其他所有結點間的所有簡單狀態路徑，所述簡單狀態路徑由狀態序列構成，且路徑中不含循環；並識別出擴展有限狀態機模型中所有的狀態循環路徑，所述狀態循環路徑由狀態序列構成，源結點和終止結點相同，包括自循環路徑；檢查簡單狀態路徑，檢查其實是否有能和狀態循環路徑匹配的結點，若是，則將狀態循環路徑插入簡單路徑，生成狀態路徑候選集；再利用全組合方法將狀態路徑轉換為遷移路徑集合，並將生成的遷移路徑集合作為最終的測試路徑候選集。步驟2)中所述可行性評估公式為
權利要求
1.一種自動化測試用例生成方法，其特徵是基於擴展有限狀態機可行路徑分析，通過路徑可行性分析儘可能的避開不可行路徑，自動化生成測試用例和創建測試預言，結合靜態分析和動態分析技術獲取可行路徑集合達到指定的路徑覆蓋準則，包括以下步驟1)根據擴展有限狀態機模型生成測試路徑候選集，利用遍歷、循環路徑分析和插入方法，生成從擴展有限狀態機模型的起始狀態結點到其他結點的所有路徑作為候選路徑，並約束規定路徑中只插入有限次循環路徑或自循環路徑；2)路徑可行性評估策略，利用靜態分析技術對候選路徑集中的路徑進行分析，首先識別出其中不可行路徑，將這部分不可行路徑從路徑候選集中移除，然後對其餘路徑的可行性提出評估公式，對其進行不可行概率評估並計算出評估值，對候選路徑集中的路徑按不可行概率從小到大進行排序；3)開發可執行模型，利用圖論遍歷方法和表達式語義解析工具使得擴展有限狀態機模型可執行化，可執行模型定義了模型的動態行為並通過使用語義執行使得靜態模型具有類似程序的動態執行能力；4)自動生成測試數據和測試預言，由步驟幻的可執行模型的動態執行過程獲得相應的運行時反饋信息，利用所述反饋信息結合分散搜索技術Matter Search來指導測試數據生成並自動創建測試預言，生成的測試用例觸發對應的路徑；測試用例的生成過程為首先從步驟1)和步驟幻生成的測試路徑候選集中按不可行概率順序選取一條候選路徑，檢查該路徑中的邊是否被指定的測試充分性準則覆蓋，若是則跳過該路徑選取候選集中的下一條路徑進行生成，以避開不可行路徑，提高測試用例生成的效率，同時動態識別不可行路徑；否則利用步驟幻開發的可執行模型和步驟4)獲取的運行時反饋信息，結合分散搜索方法Matter Search,對選擇的路徑進行語義執行，並利用反饋信息搜索狀態空間中的解，若在規定迭代次數範圍內找到解集則將結果加入測試用例結果集，否則認為該路徑不可執行。
2.根據權利要求1所述的一種自動化測試用例生成方法，其特徵是步驟1)具體為 首先利用圖論的遞歸遍歷算法找出從擴展有限狀態模型源結點到其他所有結點間的所有簡單狀態路徑，所述簡單狀態路徑由狀態序列構成，且路徑中不含循環；並識別出擴展有限狀態機模型中所有的狀態循環路徑，所述狀態循環路徑由狀態序列構成，源結點和終止結點相同，包括自循環路徑；檢查簡單狀態路徑，檢查其實是否有能和狀態循環路徑匹配的結點，若是，則將狀態循環路徑插入簡單路徑，生成狀態路徑候選集；再利用全組合方法將狀態路徑轉換為遷移路徑集合，並將生成的遷移路徑集合作為最終的測試路徑候選集。
3.根據權利要求1所述的一種自動化測試用例生成方法，其特徵是步驟幻中所述可行性評估公式為
4.根據權利要求1所述的一種自動化測試用例生成方法，其特徵是步驟4)通過由步驟 3)中可執行模型的動態執行過程來獲得相應的運行時反饋信息，獲取的反饋信息如下
全文摘要
一種自動化測試用例生成方法，基於擴展有限狀態機可行路徑分析，由於不可行路徑的存在使得擴展有限狀態機模型中生成測試用例仍然是一個難題，本發明通過路徑可行性分析儘可能的避開不可行路徑、自動化的生成測試用例和創建測試預言。特徵是結合了靜態分析和動態分析技術來找到一個較小的可行路徑集合達到指定的路徑覆蓋準則，此外還給出了路徑可行性評估策略，開發了可執行模型，通過運行時信息反饋和分散搜索ScatterSearch技術來自動生成測試數據和創建測試預言。靜態和動態兩種可行性分析技術的結合大大提高了測試用生成的效率，實際應用中可以減少測試過程的代價，提高軟體測試的質量。
文檔編號G06F11/36GK102368226SQ20111030694
公開日2012年3月7日 申請日期2011年10月10日 優先權日2011年10月10日
發明者張潔, 徐寶文, 楊瑞, 陳振宇 申請人:南京大學