Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.3/217474

Title

An enhanced flow analysis technique for detecting unreachability faults in concurrent systems

Author(s)

Chen, Tsong Yueh;  Hu, Peifeng;  Li, Hao;  Tse, T. H.

Abstract

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

Source

Information Sciences, Vol. 194 (Jul 2012), pp. 254-269

Publication year

2012

FOR Code(s)

01 Mathematical Sciences;  08 Information and Computing Sciences;  09 Engineering

Keyword(s)

Concurrency;  Distributed systems;  Reachability analysis;  Static analysis

Publisher

Elsevier

ISSN

0020-0255

Publisher URL

http://dx.doi.org/10.1016/j.ins.2011.11.034

Copyright

Copyright © 2011 Elsevier Inc. The accepted manuscript will reproduced 24 months after publication (July 2014) 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).

Peer reviewed