On Wed, 21 May 2003, Ethan Sommer wrote:I take it back, it is regular (kinda) but you can't to it with a deterministic finite atomaton. If there is a cycle in pattern1, off of which pattern2 has a branch, then you would need to count how many times you have gone around the cycle to know where to jump to in pattern2 if it fails to match pattern1 (which you can't do, pumping lemma and all that.) If you use a non-determistic FA, you should be able to just go through each pattern until both crash or one matches and declare that the winner.
Philippe Biondi wrote:
We actually planned on doing that initially. You should note that if youregexp support was planned but not done yet. (if someone know where I can download more free time !).
The implementation should not be that hard, once you have the compiler to transform the string describing the regexp to an automaton.
Note that to respect the framework, you have to deal with multiple patterns (should not be that hard). If you have pat1 and pat2, searching for (pat1|pat2) is not sufficient because for each match, you have to point which pattern matched.
want to generate one automaton for multiple patterns, that is not a
regular language (and thus can not be represented by a FA or DFA.) You
will have to try matching against the first pattern, then the next and
so on.
If P and Q are regexps, P|Q is a regexp, so you do can.
So detection is clearly not a problem. But to fit in the libqsearch model,
you have to know which of the parterns matched. This is theorically
possible, but need a bit of work in comparison with using an
off-the-shelf regexp compiler on (Pat1|Pat2|..|Patn).
If your lib did that, it would work quite well for the layer-7 filter.
Ethan
- : send the line "unsubscribe linux-net" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
