Graph Grammar Modeling and Verification of Ad Hoc Routing Protocols: (Extended Version)
2007 (English)Report (Other scientific)
We present a technique for modeling and automatic veriﬁcation of network protocols, based on graph transformation. It is suitable for protocols with a potentially unbounded number of nodes, in which the structure and topology of the network is a central aspect, such as routing protocols for ad hoc networks. Safety properties are speciﬁed as a set of undesirable global conﬁgurations. We verify that there is no undesirable conﬁguration which is reachable from an initial conﬁguration, by means of symbolic backward reachability analysis.
In general, the reachability problem is undecidable. We implement the technique in a graph grammar analysis tool, and automatically verify several interesting nontrivial examples. Notably, we prove loop freedom for the DYMO ad hoc routing protocol. DYMO is currently on the IETF standards track, to potentially become an Internet standard.
Place, publisher, year, edition, pages
2007. , 22 p.
, IT Technical Reports, ISSN 1404-3203 ; 2007-035
IdentifiersURN: urn:nbn:se:uu:diva-15913OAI: oai:DiVA.org:uu-15913DiVA: diva2:43684