Conference Paper 

Title 

Modeling Adhoc Rushing Attack in a Negligibilitybased Security Framework


Abstract 

In this paper, we propose a formal notion of network security for
ad hoc networks. We adopt a probabilistic security framework, that
is, security is defined by a polynomially bounded adversary model,
the cost of attack and the cost of defense. In a complex and probabilistic
system, we speak of the “infeasibility” of breaking the security
system rather than the “impossibility” of breaking the same
system. Security is defined on the concept of “negligible”, which
is asymptotically subpolynomial with respect to a predefined system
parameter x. Intuitively, the parameter x in cryptography is the
key length n. We apply the same bounds in ad hoc network security
research, but in regard to scalability from now on. We propose
an RP (nruns) complexity class with a global virtual god oracle
(GVG) to model a general class of network protocols. In GVGRP (nruns) class, the network scale (i.e., number of network members)
N replaces the role of key length n in cryptography. From
our formal rigorous treatment, we show that “rushing attack” is a
severe attack that can reduce the success probability of common ad
hoc routing schemes to negligible.
Fortunately, countermeasures can be devised to answer this challenge.
(1) Common network protocols are not designed to ensure
that probability of security failure is negligible. In such designs, the
system’s security is not related to scalability. There is no asymptotic
security guarantee in the network design; (2)We seek to devise
security schemes to ensure that the probability of security failure is
negligible in regard to network scale. In Theorem 2, we present
an asymptotic invariant for scalable networks: “a polynomialtime
network algorithm that ensures negligible probability of security
failure at each step would stay in the state of ensuring negligible
probability of security failure globally”. This invariant demonstrates
the existence of asymptotic security guarantee in ad hoc networks.
It leads to the design of communitybased secure routing to
defend against rushing attacks. Nevertheless, it is unknown to us
whether the ideal invariant can be practically implemented.


Download 
Paper: PDF file of paper


Information & Date 

ACM Wireless Security (WiSe), in conjunction with MobiCom 2006, Los Angeles, California, USA, September. 2006


Authors 

Jiejun Kong
Xiaoyan Hong
Mario Gerla

