Algorithmic Complexity Attack on Packet Classifiers

OData support
Kőrösi Attila
Department of Telecommunications and Media Informatics

This document is a paper, what searches the dangers and opportunities of the algorithmic complexity based attacks against the routing and packet sorting algorithms used in packet classifiers, especially the Open vSwitch. In theese systems, the searching algorithm compares the header of the packet with all of the rules, than it chooses the highest priority match, and does, what it says. It might be given as an action to search for further matches, and than do what is given as theese matches actions as well. But before this, it searches in a cache, used to speed up the search, between the previous matches, here only the first match counts. The time needed to this search is linear with the number of the cache entries, so if we send a lot of such packets, that all of them generate a new cache entry, than we can significantly slow down the service.

The rules are masked bit-rows, so only some of the headers bits have to match with the rule. The original rules may overlap, in theese cases the predefined priorities will decide, that which action should be executed. But in the cache, the same action have to belong to all packets matching the same entry, and because of this at most cases, more rule have to be given to cover the original one. This combinatory problem, saying what is the minimal number of the rules which is enough to cover the original rule, is NP-complete, and in some cases it is exponential with the number of the rules.

I dealt with the bounds for a special case, and I made four algorhitms to find the packets, that can generate as much cache entry as possible. Theese algorithms are good in different cases, and based on different criterias, but either of them is good generally. The presentation of theese algorithms will be followed with a few simple test case with the help of mininet test environment. Theese tests will show, how big speed decrease can be reached with a good planned attack, even at a simple rule set.


Please sign in to download the files of this thesis.