Aho-Corasick Algorithmus

Aus THM-Wiki
Wechseln zu: Navigation, Suche

Snort benutzt zum Identifizieren von Attacken einen Suchalgorithmus, den sog. Aho-Corasick Algorithmus. Dieser wird zum Beispiel auch beim Unix Kommando "fgrep" verwendet.

Überblick

Der Algorithmus beruht auf der Suche von Zeichenfolgen, es ist eine Art Wörterbuchvergleich. Um durch Snort eine Attacke zu identifizieren, werden eine endliche Anzahl bekannter Muster mit dem Eingabetext (Netzwerkdatenpaket) verglichen. Dabei baut der Algorithmus einen endlichen Zustandsautomaten auf und vergleicht diesen mit dem Eingabetext. Der Name Aho-Corasick rührt von der Benutzung eines speziellen Automaten, dem sogenannten Aho-Corasick-Automaten. Der Algorithmus ist ein Trie mit sogenannten "Fehler-Links". Diese geben bei einem Mismatch im Text an, wohin man im Trie (ist ein gerichteter Baum / Automat mit einer Wurzel / Anfangsknoten) springen muss. Geht vom aktuellen Knoten keine mit dem aktuellen Textsymbol x beschriftete Kante aus, so verfolgt man die Fehler-Links, bis man einen Knoten erreicht, von dem eine mit x beschriftete Kante ausgeht oder die Wurzel erreicht.

Trie

In der Informatik ist ein Trie (abgeleitet aus dem engl. reTrieval, auch Prefix Tree genannt) eine Datenstruktur, genauer eine spezialisierte Art eines Suchbaumes zur gleichzeitigen Speicherung von mehreren Zeichenketten. Tries werden unter anderem verwendet, um effizient gleichzeitig nach mehreren Zeichenketten suchen zu können. In einem Trie repräsentiert jede Kante des Baums einen zusätzlichen Buchstaben. Jeder Knoten entspricht der Zeichenkette, die aus der Verkettung aller Kantenbuchstaben entsteht. Der Wurzelknoten eines Trie entspricht einer leeren Zeichenkette (Quelle: www.wikipedia.de)

Weblinks

Wikipedia:
http://de.wikipedia.org/wiki/Aho-Corasick-Algorithmus



--Klose-MKL 21:10, 18. Jan. 2007 (CET)