netdev
[Top] [All Lists]

Re: [Fwd: [ANNOUNCE] Layer-7 Filter for Linux QoS]

To: Ethan Sommer <sommere@xxxxxxxxxxx>
Subject: Re: [Fwd: [ANNOUNCE] Layer-7 Filter for Linux QoS]
From: Philippe Biondi <biondi@xxxxxxxxxxxxxxxxxx>
Date: Thu, 22 May 2003 10:26:30 +0200 (CEST)
Cc: Jamal Hadi <hadi@xxxxxxxxxxxxxxxx>, Martin Josefsson <gandalf@xxxxxxxxxxxxxx>, "David S. Miller" <davem@xxxxxxxxxx>, <linux-net@xxxxxxxxxxxxxxx>, <netdev@xxxxxxxxxxx>
In-reply-to: <3ECC0B14.7020105@xxxxxxxxxxx>
Sender: netdev-bounce@xxxxxxxxxxx
> >
> 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



<Prev in Thread] Current Thread [Next in Thread>