Attack propagation in networks

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, 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 in truder'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 O < f < 1, there exists a constant g for which any of our attack schemes can achieve a &THgr; (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.

REFERENCES

• 1: Dorothy E. Denning, Information warfare and security, Addison-Wesley Longman Ltd., Essex, UK, 1998
• 2: W. Feller, "An Introduction to Probability Theory and its Applications", Vol. I, John Wiley, New York, 1968.
• 3: John Douglas Howard, An analysis of security incidents on the Internet 1989-1995, Carnegie Mellon University, Pittsburgh, PA, 1998
• 4: J. Kephart and S. White, "Directed-Graph Epidemiological Models of Computer Viruses", IBM Research Report; also, in Proc. IEEE Symp. on Security and Privacy, 1991.
• 5: S. Nikoletseas and P. Spirakis. "Efficient Communication Establishment in Adverse Communication Environments". In Proc. ICALP Satellite Workshop on Approximation and Randomized Algorithms in Communication Networks, 2000.
• 6: Rafail Ostrovsky , Moti Yung, How to withstand mobile virus attacks (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.51-59, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112605]
• 7: Tsutomu Shimomura , John Markoff, Takedown: The Pursuit and Capture of Kevin Mitnick, America's Most Wanted Computer Outlaws - by the Man Who Did It, Hyperion Press, 1995
• 8: D. Safford, D. Shales, and D. Hess, "The TAMU Security Package: An Ongoing Response to Internet Intruders in an Academic Environment", in Proc. UNIX Security Symposium IV, 1993.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS

General Terms:
Algorithms, Measurement, Performance, Security, Standardization, Theory, Verification