> >
> 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.
Strange way of reasoning... what if pattern1 is "(subpat1|subpat2)" ?
regexp is a regular language so it is equivalent to a DFA.
For every NDFA, there exist a DFA that recognize the same language.
So, it is possible.
The question is : will we have enough memory to store a DFA that recognize
a big regexp ? The answer is : let loose some speed and use NDFA.
> If your lib did that, it would work quite well for the layer-7 filter.
Anyone here interested by doing a regexp compiler ? I can help for details
or libqsearch internals, but I won't find enough time to do all that
quickly enough.
--
Philippe Biondi <biondi@ cartel-securite.fr> Cartel Sécurité
Security Consultant/R&D http://www.cartel-securite.fr
Phone: +33 1 44 06 97 94 Fax: +33 1 44 06 97 99
PGP KeyID:3D9A43E2 FingerPrint:C40A772533730E39330DC0985EE8FF5F3D9A43E2
|