10 years 10 years

As a part of the Snort lecture in intrusion detection systems we learned about a multi-term string search algorithm called Aho-Corasick named by it's two creators. It's actually quite old, published in 1975, but still considered the most fit algorithm for this purpose.

I tried implementing it in python in order to get a grasp of what it's going. It has a phase of building a finite state machine based on the keywords, and this process is being performed for all signatures off-line. It consists of a "go to" tree and "failure" + "output" look-up tables.

The search phase consists of walking the input string, typically network traffic or logs, character by character. The state is continuously changing depending on whether the current input symbol has a next state defined, or if none found moved to a state defined in the failure table. The output table is checked for every state visited and outputted from if not empty.

<implement deterministic conversion>

Just a simple reminder to myself, as this gave me a lot of headacke :)

def func(a, b):
print a
func("a" is False)
# output: False

The python code with examples:

# coding=utf8
import os
os.system('clear') # empty the console

class GoTo:
# store state as index, containing list of (char, next state) pairs
def __init__(self):
self.storage = [] # store "g[state, char] = next"
self.length = 0

def list(self, state):
next = []
for i in self.storage[state]:
next.append((i[0], i[1])) # (char, next)
return next
return ()

def goto_get(self, state, char):
# used by the goto construction phase
state = self.storage[state]
for pair in state:
if (pair[0] == char):
return pair[1] # next state
return False # no match found
return False # no state exists

def get(self, state, char):
next_state = self.goto_get(state, char)
if (state == 0 and next_state is False):
return 0 # override: because all failed 0 states should return to 0 state
return next_state

def set(self, state, char, next): # state will be saved as the list-index
self.storage[state].append((char, next)) # try appending
while state > self.length: # add skipped "empty" states
self.length += 1
self.storage.append([(char, next)]) # add new state
self.length += 1

def dump(self):
return self.storage

class OutPut:
def __init__(self):
self.storage = []
self.length = 0

def set(self, state, term): # term must be a list of one or many terms to be added
state = self.storage[state]
for t in term:
state.append(t) # try to append if exists
while state > self.length: # add skipped states
self.length += 1
self.storage.append(term) # add new state output
self.length += 1

def get(self, state):
return self.storage[state]
return []

def dump(self):
return self.storage

def construct_goto(patterns, g, o):
#construct the goto structure and first round of output function
newState = 0
for term in patterns:
m = len(term)
state = 0
j = 0
while g.goto_get(state, term[j]) is not False:
state = g.goto_get(state, term[j])
j += 1
if j >= m: # avoid accessing out of bound chars in string
for k in range(j, m):
newState += 1
g.set(state, term[k], newState)
state = newState
o.set(state, [term])
# skipping setting all g[0, alpha] = 0 because g.get() takes care of it
return newState

def construct_failure(patterns, f, g, o):
# where to go in the goto structure on failure and build the rest of the output function
queue = []
alphas = g.list(0)
for char, next in alphas:
f[next - 1] = 0
while (len(queue)) > 0:
r = queue.pop(0)
alphas = g.list(r)
for char, next in alphas:
state = f[r - 1]
while g.get(state, char) is False:
state = f[state - 1]
f[next - 1] = g.get(state, char)
string = o.get(f[next - 1])
o.set(next, string)

def build_ahocorasick(keywords, nocase):
keywords_upper = []
for word in keywords:
keywords = keywords_upper
g = GoTo()
o = OutPut()
num_states = construct_goto(keywords, g, o)
f = [0] * num_states
construct_failure(keywords, f, g, o)
return [g, o.dump(), f, keywords]

def run_ahocorasick(machine, input_string, nocase):
input_string = input_string.lower()
goto_matrix = machine[0]
output_matrix = machine[1]
failure_matrix = machine[2]
keywords = machine[3]
print("Looking for %s in '%s'\n") % (keywords, input_string)
print("State machine:\ngoto matrix: %s\nfailture matrix: %s\noutput matrix: %s") % (goto_matrix.dump(), failure_matrix, output_matrix)
print("\n\tLooking for matches:")
state = 0
for i in range(0, len(input_string)):
while goto_matrix.get(state, input_string[i]) is False:
state = failure_matrix[state]
state = goto_matrix.get(state, input_string[i])
if output_matrix[state] != []:
print("end pos %s - %s") % (i + 1, output_matrix[state])

nocase = True # False or True
machine = build_ahocorasick(("snort", "or", "snow"), nocase)
run_ahocorasick(machine, "snort on snow", nocase)

machine = build_ahocorasick(("a", "ab", "abb", "abba", "b", "bb", "bba", "ba"), nocase)
run_ahocorasick(machine, "abba", nocase)

machine = build_ahocorasick(("t o", "n s", "ab", "cd"), nocase)
run_ahocorasick(machine, "rt on sn abcd", nocase)