On-the-fly model checking with partial-order state space reducti

Details On-the-fly model checking with partial-order state space reducti On-the-fly model checking with partial-order state space reducti

1996-06-21

1997-03-25

Teska, Kevin J.

Boots, shoes, and leggings

364491, G06F 1750

Patent

active

056151373

ABSTRACT:
An on-the-fly verification system which employs statically-available information to reduce the size of the state space required to verify liveness and safety properties of a target system consisting of asynchronous communicating processes. The verification system generates a verifier from a description of the target system and a specification of the property to be verified. The verifier models the target system as a set of finite state machines, constructs a state space containing a graph of nodes representing states of the target system and transitions between the states, and uses the state space to verify the property. The size of the state space is reduced by using information from the description and the specification to divide transitions from a node into per-process bundles and to determine which bundles of transitions must be included in the state space and which may be left out of the state space. The state space reduction technique never increases the size of the state space and often reduces it by orders of magnitude.

REFERENCES:
"The Existence of Refinement Mappings", by M. Abadi et al., IEEE Logic in Computer Science, 3rd Annual Symposium, 1988, pp. 165-175.
"Protocol Design: Redefining the State of the Art", by G. Holzmann, IEEE Software, vol. 9, Issue 1, Jan. 1992, pp. 17-22.
"A Partial Order Approach to Branch Time Logic Model Checking", by Gerth et al., IEEE, Israel Symposium on the Theory of Computing and Systems, 1994, pp. 130-139.
R. Gopal, "Dynamic Program Slicing Based on Dependence Relations", Proceedings of the Conference on Software Maintenance 1991, Oct. 17, 1991, pp. 191-200.
"Petri Net Approach to Correctness Checking on Changing Software", Research Disclosure, No. 348, Apr. 1993, Havant GB, p. 225.
P. Godefroid, "Using Partial Orders to Improve Automatic Verification Methods", DIMACS Serial in Discrete Mathematics and Theoretical Computer Science, vol. 3, 1991.
S. Katz, D. Peled, "Verification of Distributed Programs Using Representative Interleaving Sequences", Distributed Computing, vol. 6, pp. 107-120 (1992).
P. Godefroid, P. Wolper, "Using Partial Orders for the Efficient Verification of Deadlock Freedom and Safety Properties", Formula Methods in Systems Design, Kluwer Academic Publishers, vol. 2, No. 2, pp. 149-164, Apr. 1993.
A. Valmari, "A Stubborn Attack on State Explosion", Formal Methods in System Design, vol. 1, No. 4, pp. 297-322, 1990.
A. Valmari, "On-The-Fly Verification with Stubborn Sets", 5th Int'l Conf. on Computer Aided Verification, Greece, 1993, Lecture Notes in Comp. Science, Springer-Verlag, 397-408.

Affiliated with

Also associated with

Rating

On-the-fly model checking with partial-order state space reducti does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with On-the-fly model checking with partial-order state space reducti, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On-the-fly model checking with partial-order state space reducti will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2209409