Abstract: Existing protocol state machine inference approaches based on algorithm L* are inefficient owing to ignorance of protocol-specific knowledge.As the protocol messages are abstracted as the independent and insignificant symbols,and test samples are completely generated randomly in equivalence query,invalid queries and test samples are inevi-table.A protocol state machine active inference algorithm named L⁺N was proposed,which improves the algorithm L⁺M in three aspects.Firstly,L⁺N filters the invalid output query according to the constraint on strict order,which is extracted from conservation samples.Secondly,L⁺N constructs the extended prefix tree accepter(EPTA) corresponding to the sample set and answers the output query in advance.Thirdly,a new proposed strategy to find counterexamples more effectively is applied to judge the equivalence query based on positive sample mutation.Experimental results show that L⁺N improves the inference efficiency greatly and achieves the same accuracy as algorithm L⁺M.

Key words: Algorithm L*,Protocol state machine,Active inference,Domain-specific knowledge,Inference efficiency