基于分层有限状态自动机的一致性测试生成

Automatic test generation based on hierarchical finite state machines

为了进行分层有限状态自动机(HFSM)的一致性测试生成,提出了基于HFSM的状态同步序列算法和状态验证序列算法,并在此基础上提出了基于HFSM的一致性测试生成方法。以组播监听者发现(MLD)协议为例说明了该方法的应用。该方法虽然比传统的转化为有限状态自动机(FSM)描述再进行一致性测试生成的方法在适用性上有所降低,但是仍然能够满足大多数通信系统测试的需求,并且由于该方法利用了HFSM的分层特性,因此该方法生成的测试序列长度较短,执行的效率也较高。

Conventional methods of te st ing hierarchical finite state machines (HFSMs) always first 'flatten' them to finite state machines (FSMs) and then evaluate them using FSM testing methods. The famous 'state-explosion' problem always arises in the process. Algorithms have been developed using hierarchical characteristics to solve the 'state-ex plosion' problem for state synchronization sequences and verification sequences . Though a bit less feasible than conventional methods, the algorithms can be ap plied to almost all HFSM models in practice and achieve shorter sequences in les s time. An efficient test generation method was then developed based on these al gorithms for conformance testing of the multicast listener discovery (MLD) proto col.