Aho-Corasick-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Der Aho-Corasick-Algorithmus ist ein Algorithmus, der auf der Suche von Zeichenfolgen beruht und von Alfred V. Aho und Margaret J. Corasick 1975 entwickelt wurde.

Der Algorithmus ist eine Art Wörterbuch-Vergleich, der eine endliche Anzahl aus bekannten Mustern mit einem Eingabetext vergleicht. Einfach gesagt, baut der Algorithmus einen endlichen Zustandsautomaten auf und vergleicht diesen mit dem Eingabetext. Falls die Signatur bereits im Vorfeld bekannt ist (zum Beispiel bei einer Anti-Viren-Datenbank), dann kann der Aufbau auch vor dem Start des Programms off-line erfolgen und zur späteren Benutzung abgespeichert werden.

Der Aho-Corasick-Algorithmus ist die Basis des UNIX-Kommandos fgrep, des IDS Snort und der WAF ModSecurity[1].

Quellen[Bearbeiten]

  1. Breach Security Inc.: ModSecurity Reference Manual (PDF; 524 kB)