Back to Tuomas Aura's home page

Analyzing single-server network inhibition

Tuomas Aura
Helsinki University of Technology, Lab. for Theoretical Computer Science, FIN-02015 HUT, Finland

Matt Bishop, Dean Sniegowski
University of California, One Shields Avenue, Davis, CA 95616-8562, USA


Network inhibition is a denial-of-service attack where the adversary attempts to disconnect network elements by disabling a limited number of communication links or nodes. We analyze a common variation of network inhibition where the links have infinite capacity and the goal of the attacker is to deny connections from a single server to as many clients as possible. The problem is defined formally and shown to be NP complete. Nevertheless, we develop a practical technique for network-inhibition analysis based on logic programming with stable-model semantics. The analysis scales well up to moderate-size networks. The results are a step towards quantitative analysis of denial of service and they can be applied to the design of robust network topologies.

Full paper in Postscript

  author =	 {Tuomas Aura and Matt Bishop and Dean Sniegowski},
  title =	 {Analyzing single-server network inhibition},
  month =	 jun,
  year =	 2000,
  booktitle = 	 {Proc.\ 13th IEEE Computer Security Foundations Workshop},
  pages =        "108--117",
  address =      {Cambridge, UK},
  publisher =	 {IEEE Computer Society Press}