[Spamtrap] spam@onhacks.org

I have created a spam@onhacks.org to gather interesting spam from the wild.
Come on, bot! grab this email address (spam@onhacks.org) and show me your spam!!

Filed under: Uncategorized

Still alive

I am still alive, actually.
Quite busy these day working with test specifications.

BTW, I got my visiting visa. Probably will go to see my team on early Feb.

Planning to make this page to be a blog showing pictures that I took.

Filed under: Uncategorized , Alive

onhacks.org – My new security playground

Me and log0 is now gathered to write on the same security blog: onhacks.org. I hope that this is a great place for us to go deeply into security techniques and news. Thank you for supporting this blog. This blog will become my personal diary, but you are always welcome to come by and drop a comment.

See you in onhacks.org

Filed under: Uncategorized

Go to Vancouver

I am going to leave Hong Kong at 1245, in Hong Kong time. I will start working in Vancouver later.

May write some blog entries during the flight, so you can come back 15 hours later.

Hope to see you there.

Filed under: personal

Aho-Corasick – Automaton

Last time, we talked about how to construct the trie of a set of patterns. But with only the trie, we cannot perform pattern matching. The edges in the trie is only the transitions when target character matches the label on an edge. What if there is a mismatch occur? How can we handle the case? Before discussing the detail on how it solves the problem, let’s define some functions that is important for the discussion.

1. The go function go(q, a) gives the state entered from current state q by matching target character a. In other words, if there is an edge from q to other state v which is labeled by a, then go(q, a) = v. Let’s assume root is state 0, then go(0, a) = 0 for all a that does not label an edge outgoing from the root. It means that the automaton stays at the initial state while scanning non-matching characters. Otherwise, go(q, a) is null, which does not exist an edge with label a.
2. The fail function fail(q) for q not equal to start state gives the state entered at a mismatch occurs, a mismatch means there is no outgoing edge with suitable label for the target character. fail(q) is a state labeled by the longest proper prefix. Considering example above, the final states with incoming edge labeled in ‘S’, their fail function should be pointing to the internal node with incoming edge labeled in ‘S’. The diagram below shows two fail transitions (dotted edges) of the example.
   

   Trie with two fail transitions

3. The out function out(q) gives the set of patterns recognized when entering state q. Before the construction of automaton, the final states are only those nodes that is the end of a pattern. When constructing the automaton, some of the internal states will become final state because the fail transitions are added to the original trie. As mentioned before, the algorithm first construct a trie then use this trie to further construct the automaton. Actually, the construction of trie is, in other words, the computation of go function. Which means, the edges in trie are main part of the go transitions. What is the missing part? What if the outgoing edges from root does not exist? Yes, there is a case need to handle which is a mismatch character occurs at the start state. By adding these edges to the root which point to itself can solve the problem.
   

   for (int i = 0; i < N; ++i) {
     if (root->go[i] == NULL) {
       root->go[i] = root;
     }
   }

According to the definition, the most part of go transitions is already finished in the construction of trie. Then what kind of go transitions is missed in the construction? Yes, when the mismatch occur at the start state (root node). Obviously, this kind of mismatch does not include in the definition of fail function, because you cannot fall back to some precedant nodes since you are at the start state. To handle this situation, add an edge to the root node which pointing to itself, with label not equal the first character of all patterns.

The completed AC automaton

The remaining part of the construction is to compute the fail functions and the out functions. There are some observations on fail function and out function. The algorithm should first compute fail function and out function on nodes closer to the root, which means that the algorithm computes these functions in breath-first order. Besides, consider node u and v where v = go(u, a), in other words u is the parent of v. The pattern from root to v, denoted as L(v) is equal to L(u)a. So, what should fail function f(v) be? It should be the deepest node labeled by a proper suffix of L(u), a deepest node is the node that most far away from the root. As a result, the algorithm will first check f(u), see if it has go(f(u), a) transition, if no, check if there is a transition g(f(f(u)), a), continue until the algorithm find a valid go(state, a) transition. Here is psuedo code of the algorithm which compute fail functions, together with out functions. Please be reminded that, there is a little change in the structure of nodes, because a node may be a terminal node of more than one pattern. Why? Leave this for you to think.

struct Node {
  Node *fail;
  Node *go[N];
  list<string> out;
  Node() {
    fail = NULL;
    for (int i = 0; i < N; ++i)
      go[i] = NULL;
  }

  ~Node() {
    for (int i = 0; i < N; ++i)
      if (go[i] != NULL && go[i] != this)
        delete go[i];
  }
};

queue<Node *> q;
for (int i = 0; i < N; ++i) {
  Node *s = root->go[i];
  if (s != NULL && s != root) {
    s->fail = root;
    q.push(s);
  }
}
while (! q.empty()) {
  Node *p = q.front(); q.pop();
  for (int i = 0; i < N; ++i) {
    Node *u = p->go[i];
    if (u != NULL) {
      q.push(u);
      Node *v = p->fail;
      while (v->go[i] == NULL) {
        v = v->fail;
      }
      u->fail = v->go[i];
      (u->out).splice((u->out).end(), u->fail->out);
    }
  }
}

After the above preprocessing to the patterns, it is trivial to perform the pattern matching.

Node *q = root;
for (int i = 0; i < strlen(S); ++i) {
  while (q->go[S[i]] == NULL) {
    q = q->fail;
  }
  q = q->go[S[i]];
  if (q->out.size() > 0) {
    report_match(i, q->out);
  }
}

Thank you for reading. Please feel free to leave any comments or suggestions. Any suggestion what I should do next? Or any interesting security stuff that I can research on?

Reference:

• Set Matching and Aho-Corasick Algorithm

Filed under: Uncategorized