Hardware/Software Mechanisms for Protecting an IDS against Algorithmic Complexity Attacks

Govind Sreekar Shenoy, J. Tubella, A. Gonz'lez

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Intrusion Detection Systems (IDS) have emerged as one of the most promising ways to secure systems in the network. An IDS like the popular Snort[17] detects attacks on the network using a database of previous attacks. So in order to detect these attack strings in the packet, Snort uses the Aho-Corasick algorithm. This algorithm first constructs a Finite State Machine (FSM) from the attack strings, and subsequently traverses the FSM using bytes from the packet. We observe that there are input bytes that result in a traversal of a series of FSM states (also viewed as pointers). This chain of pointer traversal significantly degrades (22X) the processing time of an input byte. Such a wide variance in the processing time of an input byte can be exploited by an adversary to throttle the IDS. If the IDS is unable to keep pace with the network traffic, the IDS gets disabled. So in the process the network becomes vulnerable. Attacks done in this manner are referred to as algorithmic complexity attacks, and arise due to weaknesses in IDS processing. In this work, we explore defense mechanisms to the above outlined algorithmic complexity attack. Our proposed mechanisms provide over 3X improvement in the worst-case performance.
Original languageEnglish
Title of host publicationParallel and Distributed Processing Symposium Workshops PhD Forum (IPDPSW), 2012 IEEE 26th International
PublisherInstitute of Electrical and Electronics Engineers
Pages1190-1196
Number of pages7
ISBN (Print)978-1-4673-0974-5
DOIs
Publication statusPublished - 1 May 2012

Keywords / Materials (for Non-textual outputs)

  • computational complexity
  • computer network security
  • finite state machines
  • string matching
  • Aho-Corasick algorithm
  • FSM states
  • IDS processing
  • IDS protection
  • algorithmic complexity attacks
  • finite state machine
  • hardware mechanisms
  • intrusion defense mechanisms
  • intrusion detection systems
  • network traffic
  • processing time
  • software mechanisms
  • string detection
  • worst-case performance
  • Clocks
  • Complexity theory
  • Databases
  • Hardware
  • Optimization
  • Payloads
  • Software
  • Defense Mechanisms
  • Hardware Support
  • Intrusion Detection Systems

Fingerprint

Dive into the research topics of 'Hardware/Software Mechanisms for Protecting an IDS against Algorithmic Complexity Attacks'. Together they form a unique fingerprint.

Cite this