基于有限状态机的错误诊断算法

赵保华; 钱兰; 周颢; 郭雄辉

基于有限状态机的错误诊断算法

计量
- 文章访问数: 2165
- HTML全文浏览量: 102
- PDF下载量: 742
- 被引次数: 0
出版历程
- 收稿日期: 2005-03-18
- 修回日期: 2005-10-17
- 刊出日期: 2006-09-19

Fault Diagnosis Algorithm Based on Finite State Machine

摘要

摘要: 基于有限状态机的协议的一致性测试问题已经得到了广泛的研究。在检测到错误后，如何诊断错误是一个很重要的问题。该文在有限状态机模型和单个错误的假设下，提出了一种新的错误诊断算法，该算法利用已经确定正确的转换信息以及可疑转换的下一个输入/输出对的头状态集合等信息来高效地诊断单个错误。文中给出了与已有的错误诊断算法的比较结果，并且用一个具体的实例来详细描述本文提出的算法。
- 错误诊断;一致性测试;有限状态机
Abstract: A lot of research work has been done for conformance testing of protocols based on the FSM model. After a fault has been detected, it arises the problem that how to diagnose the fault. In this paper, it is assumed that IUT (Implementation Under Testing) exists only one single fault and a fault diagnosis algorithm is proposed. The diagnosis algorithm makes full use of transitions confirmed to be correct and head states set of the next observed input/output pair to the symptom transition and guarantees the diagnostic of any single fault in an FSM. In this paper, the comparison of time complexity with other existing fault diagnosis algorithms is given and an example to demonstrate the algorithm is presented.

HTML全文

参考文献(1)

Lee D, Yannakakis M. Principles and methods of testing finite state machinesA survey[J].Proc. Of the IEEE.1996, 84:1090-1126[2]龚正虎. 计算机网络协议工程. 长沙: 国防科技大学出版社,1993.[3]Ghedamsi A, Von Bochmann G. Test result analysis and diagnostics for finite state machines. Proceedings of the 12th International Conference on Distributed Computing Systems,Yokohama, Japan, 1992: 244－251.[4]Belhassine Cherif R, Ghedamsi A. Multiple fault diagnostics for communicating nondeterministic finite state machines. Proceedings of the Sixth IEEE Symposium on Computers and Communications, Hammamet, Tunisia, 2001: 661－666.[5]Belhassine Cherif R, Ghedamsi A. Diagnostic tests for communicating nondeterministic finite state machines. Proceedings of the Fifth IEEE Symposium on Computers and Communications, Antibes, France, 2000: 424－429.[6]Ghedamsi A, Bochmann G V, Dssouli R. Diagnosis of single transition faults in communicating finite state machines. Proceedings of the 13th International Conference on Distributed Computing Systems, Pittsburgh, Pennsylvania, USA, 1993: 157 －166.[7]Ghedamsi A, Bochmann G V, Dssouli R. Multiple faultdiagnosis for finite state machines. Proceedings of INFOCOM '93, San Francisco, California, USA, 1993, 2: 782－791.[8]Lee D, Sabnani K. Reverse-engineering of communication protocols. Proceedings of the International Conference on Network Protocols, San Francisco, California, USA, 1993: 208 －216.[9]Miller R E, Arisha K A. Fault identification in networks by passive testing. Proceedings of the 34th Annual Simulation Symposium, Seattle, WA, USA, 2001: 277－284.[10]Guo X H, Zhao B H, Qian L. Fault identification by passive testing[J].Telecommunications and Networking - ICT 2004, Fortaleza, Brazil.2004, 3124:826-834

施引文献

资源附件(0)

访问统计