Search

Showing total 1,089 results
Start Over Publication Year Range Last 50 years Journal science of computer programming Publisher elsevier b.v.
1,089 results

47. Narrowing and heuristic search for symbolic reachability analysis of concurrent object-oriented systems.

Author

Kang, Byeongjee and Bae, Kyungmin

Subjects
*HEURISTIC, *DISTRIBUTED algorithms, *MULTICASTING (Computer networks)
Abstract

A concurrent system specified as a rewrite theory can be analyzed symbolically using narrowing-based reachability analysis. Narrowing-based approaches have been applied to formally analyze cryptographic protocols and parameterized protocols. However, existing narrowing-based analysis methods, 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 and implicit constraints imposed on object-oriented systems. This paper proposes a heuristic search approach for narrowing-based reachability analysis to guide the search for counterexamples with a small number of objects. As a result, our method can effectively find a counterexample if an error state is reachable. In addition, this paper also shows how to encode implicit object-oriented constraints using order-sorted signatures and equational constraints. We demonstrate the effectiveness of our technique using a nontrivial distributed consensus algorithm. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF