Symbolic Reachability Analysis of Distributed Systems using Narrowing and Heuristic Search
- Title
- Symbolic Reachability Analysis of Distributed Systems using Narrowing and Heuristic Search
- Authors
- Kang, Byeongjee; BAE, KYUNGMIN
- Date Issued
- 2022-12-07
- Publisher
- Association for Computing Machinery, Inc
- Abstract
- A concurrent system specified as a rewrite theory can be symbolically analyzed using narrowing-based reachability analysis. Narrowing-based approaches have been applied to formally analyze cryptographic protocols and parameterized protocols. However, existing narrowing-based techniques, based on a breadth-first-search strategy, cannot deal with generic distributed systems with objects and messages due to the symbolic state-space explosion problem. This paper proposes a heuristic search approach for narrowing-based reachability analysis to guide the search for counterexamples involving a small number of objects. As a result, our method can effectively find a counterexample if an error state is reachable. We demonstrate the effectiveness of our technique using a nontrivial distributed consensus algorithm.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/115763
- Article Type
- Conference
- Citation
- 8th ACM SIGPLAN International Workshop on Formal Techniques for Safety-Critical Systems, FTSCS 2022, co-located with the ACM SIGPLAN Conference on, page. 34 - 44, 2022-12-07
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.