ALCOMFT-TR-01-101

Sotiris Nikoletseas, Grigorios Prasinos, Paul Spirakis and Christos Zaroliagis
Attack Propagation in Networks
Patras. Work packages 2 and 5. May 2001.

Abstract: A new model for intrusion and its propagation through various attack schemes in networks is considered. The model is characterized by the number of network nodes n, and two parameters f and g. Parameter f represents the probability of failure of an attack to a node and is a gross measure of the level of security of the attacked system and perhaps of the intruder's skills; g represents a limit on the number of attacks that the intrusion software can ever try, when it issues them from a particular (broken) network node, due to the danger to be discovered. The success of the attack scheme is characterized by two factors: the number of nodes captured (the spread factor) and the number of virtual links that a defense mechanism has to trace from any node where the attack is active to the origin of the intrusion (the traceability factor). The goal of an intruder is to maximize both factors. In our model, we present four different ways (attack schemes) by which an intruder can organize his attacks. Using analytic and experimental methods, we first show that for any 0<f<1, there exists a constant g for which any of our attack schemes can achieve a Theta(n) spread and traceability factor with high probability, given sufficient propagation time. We also show for three of our attack schemes that the spread and the traceability factors are, with high probability, linearly related during the whole duration of the attack propagation. This implies that it will not be easy for a detection mechanism to trace the origin of the intrusion, since it will have to trace a number of links proportional to the nodes captured.

Postscript file: ALCOMFT-TR-01-101.ps.gz (125 kb).