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 language | English |
---|---|
Title of host publication | Parallel and Distributed Processing Symposium Workshops PhD Forum (IPDPSW), 2012 IEEE 26th International |
Publisher | Institute of Electrical and Electronics Engineers |
Pages | 1190-1196 |
Number of pages | 7 |
ISBN (Print) | 978-1-4673-0974-5 |
DOIs | |
Publication status | Published - 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