Paper 2011/639

Towards a Probabilistic Complexity-theoretic Modeling of Biological Cyanide Poisoning as Service Attack in Self-organizing Networks

Jiejun Kong, Dapeng Wu, Xiaoyan Hong, and Mario Gerla

Abstract

We draw an analogy of \emph{biological cyanide poisoning} to security attacks in self-organizing mobile ad hoc networks. When a circulatory system is treated as an enclosed network space, a hemoglobin is treated as a mobile node, and a hemoglobin binding with cyanide ion is treated as a compromised node (which cannot bind with oxygen to furnish its oxygen-transport function), we show how cyanide poisoning can reduce the probability of oxygen/message delivery to a rigorously defined ``negligible'' quantity. Like formal cryptography, security problem in our network-centric model is defined on the complexity-theoretic concept of ``negligible'', which is asymptotically sub-polynomial with respect to a pre-defined system parameter $x$. Intuitively, the parameter $x$ is the key length $n$ in formal cryptography, but is changed to the network scale, or the number of network nodes $N$, in our model. We use the $\RP$ ($n$-runs) complexity class with a virtual oracle to formally model the cyanide poisoning phenomenon and similar network threats. This new analytic approach leads to a new view of biological threats from the perspective of network security and complexity theoretic study.