Search Swinburne Research Bank
Home List of Titles An enhanced flow analysis technique for detecting unreachability faults in concurrent systems
Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.3/217474
|Download PDF (Accepted manuscript) (Adobe Acrobat PDF, 812 KB)|
- An enhanced flow analysis technique for detecting unreachability faults in concurrent systems
- Chen, Tsong Yueh; Hu, Peifeng; Li, Hao; Tse, T. H.
- We present a flow analysis technique for detecting unreachable states and actions in concurrent systems. It is an enhancement of the approach by Cheung and Kramer. Each process of a concurrent system is modeled as a finite state machine, whose states represent process execution states and whose transitions are labeled by actions. We construct dependency sets incrementally and eliminate spurious paths by checking the execution sequences of actions. We prove mathematically that our algorithm can detect more unreachability faults than the well-known Reif/Smolka and Cheung/Kramer algorithms. The algorithm is easy to manage and its complexity is still polynomial to the system size. Case studies on two commonly used communication protocols show that the technique is effective.
- Publication type
- Journal article
- Research centre
- Swinburne University of Technology
- Information Sciences, Vol. 194 (Jul 2012), pp. 254-269
- Publication year
- FOR Code(s)
- 01 Mathematical Sciences; 08 Information and Computing Sciences; 09 Engineering
- Concurrency; Distributed systems; Reachability analysis; Static analysis
- Publisher URL
- Copyright © 2011 Elsevier Inc. The accepted manuscript is reproduced in accordance with the copyright policy of the publisher.
- Additional information
- The authors acknowledge support from the Australian Research Council and a grant of the Research Grants Council of Hong Kong (Project No. 717308).
- Full text
- Peer reviewed