Using dominators to extract observable protocol contexts

While verifying complex protocols, it is often fruitful to consider all protocol contexts in which an interesting set of transitions may appear. The contexts are represented as yet another protocol called observable protocol that may be further analyzed. An efficient approach based on static analysi...

Full description

Saved in:
Bibliographic Details
Main Authors: Subramaniam, M., Shi, J.
Format: Conference Proceeding
Language:English
Subjects:
Coherence
Computer science
Context
Interleaved codes
Parallel processing
Protocols
Read-write memory
Space exploration
State-space methods
System testing
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:While verifying complex protocols, it is often fruitful to consider all protocol contexts in which an interesting set of transitions may appear. The contexts are represented as yet another protocol called observable protocol that may be further analyzed. An efficient approach based on static analysis to compute an over-approximated protocol that includes all the runs of an observable protocol is described. The approach uses dominator relations over state and message dependency graphs. An over-approximation of transitions that occur with an interesting transition in any run are produced, from which a transition relation of the over-approximated protocol is automatically generated. To facilitate systematic state space exploration of the over approximated protocol, it is shown how a series of under-approximations can be generated by identifying parallelism among the transitions using dominators. The effectiveness of the proposed approach is illustrated by model checking several examples including several coherence protocols.
ISSN:1551-0255
2160-7656
DOI:10.1109/SEFM.2005.53