Modeling Vulnerabilities of Ad Hoc Routing Protocols

The purpose of this work is to automate the analysis of ad hoc routing protocols in the presence of attackers. To this end, a formal model fo protocol behavior is developed in which time is modeled by a set of constraints on the time of occurrence of events, enabling the representation of partially ordered timed events and asynchronous communication. Data variables are represented symbolically, capturing a range of distinct executions in each expression. Given a formal description of Ad Hoc On-Demand Distance Vector Routing Algorithm (AODV) and the desired safety property (route stability), an analysis by a naive semi-decision procedure discovers an instance of an attack that leads to a violation of the property.