在錯誤函式下產生測試EFSM transitions的測試順序

Abstract

縱觀以前協定測試的方法，我們發現測試順序已很成功地發展在以有限狀 態機(FSM)描述的協定上，藉著這些測試順序驗證待測產品 (IUT)的正確 性．然而，FSM 並不能完整的描述真實的協定．因此，利用延伸的有限狀 態機(EFSM)描述協定以尋找協定的測試順序是重要的且是不容易的．為了 解決這樣的問題，很多方法也曾被提出．不幸的，這些方法在運用上受到 很大的局限且有很高的複雜度．本論文提出一演算法可以有效率的產生較 短長度的測試順序以測試 EFSM的每一條transition．對特定的一 transition而言，所有含錯誤transition的EFSM便稱為mutant．首先，根 據一組衍生規則，對每一transition建構一Purge Tree(PT)．PT會持續生 長直到所有的 mutants都被清除才停止．對所考慮中的transiotion可以 在其建立成的PT直接找到最短長度的測試順序．本論文也證明只要是合法 的協定本演算法一定可以找到最短的測試順序以清除所有的mutants. Test sequences have been successfully used for testing the correctness of an Implementation Under Test(IUT) based on an Finite State Machine (FSM). However, FSMs have been shown to be unable to specify realistic protocols. Therefore, the test sequences generation for protocols specified by Extended FSM (EFSM) becomes essential and untrivial. To approach this problem, variousmethods have been proposed. These methods, unfortunately, are shown to be ad-hoc and of high complexity. This thesis proposes an algorithm which effectively generates a minimum-length test sequence for testing each transition of the EFSM. For a transition under consideration, all possible EFSMs with faulty transitions are called mutants. The method first constructs a Purge Tree (PT) for each transition according a set of derivation rules. The construction of the PT terminates when all the mutants have been purged. A minimum-length test sequence for the transition under considration can then be directly derived based on the PT. The thesis also proves that test sequences always exist using the proposed algorithm for any legitimate protocols.