uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Automatized Verification of Ad Hoc Routing Protocols
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. (Mobility)
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. (Mobility)
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
2004 (English)In: Formal Techniques for Networked and Distributed Systems – FORTE 2004, Berlin: Springer-Verlag , 2004, 343-358 p.Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Berlin: Springer-Verlag , 2004. 343-358 p.
Series
Lecture Notes in Computer Science, 3235
National Category
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-97745DOI: 10.1007/978-3-540-30232-2_22ISBN: 3-540-23252-4 (print)OAI: oai:DiVA.org:uu-97745DiVA: diva2:172799
Available from: 2008-11-13 Created: 2008-11-13 Last updated: 2011-01-05Bibliographically approved
In thesis
1. Creating Correct Network Protocols
Open this publication in new window or tab >>Creating Correct Network Protocols
2008 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Network protocol construction is a complex and error prone task. The challenges originate both from the inherent complexity of developing correct program code and from the distributed nature of networked systems. Protocol errors can have devastating consequences. Even so, methods for ensuring protocol correctness are currently only used to a limited extent. A central reason for this is that they are often complex and expensive to employ. In this thesis, we develop methods to perform network protocol testing and verification, with the goal to make the techniques more accessible and readily adoptable.

We examine how to formulate correctness requirements for ad hoc routing protocols used to set up forwarding paths in wireless networks. Model checking is a way to verify such requirements automatically. We investigate scalability of finite-state model checking, in terms of network size and topological complexity, and devise a manual abstraction technique to improve scalability.

A methodology combining simulations, emulations, and real world experiments is developed for analyzing the performance of wireless protocol implementations. The technique is applied in a comparison of the ad hoc routing protocols AODV, DSR, and OLSR. Discrepancies between simulations and real world behavior are identified; these are due to absence of realistic radio propagation and mobility models in simulation. The issues are mainly related to how the protocols sense their network surroundings and we identify improvements to these capabilities.

Finally, we develop a methodology and a tool for automatic verification of safety properties of infinite-state network protocols, modeled as graph transformation systems extended with negative application conditions. The verification uses symbolic backward reachability analysis. By introducing abstractions in the form of summary nodes, the method is extended to protocols with recursive data structures. Our tool automatically verifies correct routing of the DYMO ad hoc routing protocol and several nontrivial heap manipulating programs.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2008. 118 p.
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 571
Keyword
network protocols, formal methods, verification, testing, routing protocols, wireless ad hoc networks, model checking, graph transformation, infinite-state systems
National Category
Computer Science
Identifiers
urn:nbn:se:uu:diva-9361 (URN)978-91-554-7333-4 (ISBN)
Public defence
2008-12-05, Häggsalen, Ångströmlaboratoriet, Lägerhyddsvägen 1, Uppsala, 14:15 (English)
Opponent
Supervisors
Available from: 2008-11-13 Created: 2008-11-13 Last updated: 2011-02-18Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Wibling, OskarParrow, JoachimPears, Arnold

Search in DiVA

By author/editor
Wibling, OskarParrow, JoachimPears, Arnold
By organisation
Computer SystemsComputing Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 612 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf