Re: Optimized implementation of AC and AC_Q pattern matching algorithms

[Joel Esler <jesler () sourcefire com>]

Pablo,

Great stuff. We need to make sure we are testing and modifying against 2.9.4 though. 

--
Joel Esler
Sent from my iPhone 

On Jan 26, 2013, at 10:50 AM, Pablo Cantos <pablocantos () gmail com> wrote:

> Hi Abed,
>
> First of all, thanks for your contribution.
>
> I have checked your proposal in snort 2.9.1 by using two different pcap files, one of them (612MB-sized) throws 
> around 900k alerts and the other one (1GB-sized) throws just 55 alerts. I have used an AMD Turion II dual-core mobile 
> M520 at 2.3GHz, 512KB cache L2 by each core and 4GB RAM.
>
> These are the performance jumps that I have obtained:
>
> 612MB file -> 4.24% for MPSE, 5.93% for ac-q
> 1GB file -> 7.93% for MPSE, 8.03% for ac-q
>
> These results were obtained by measuring the times taken to analyze each pcap file by the MPSE and AC, separately.
>
> I have been working for several months with Snort to get improvements in other areas of the MPSE, I have also studied 
> the AC_SEARCH macros and I didn't find them completely efficients but I didn't go further. Now, after seeing your 
> proposal and checking the AC_SEARCH_Q again I thought that taking small changes it could work even better.
>
> You have suggested to pre-fetch the new state before was used it:
>
> #define AC_SEARCH_Q \
> +   acstate_t new_state; \
>     for (; T < Tend; T++) \
>     { \
>         ps = NextState[state]; \
>         sindex = xlatcase[T[0]]; \
> +       new_state = ps[2 + sindex];  \
>         if (ps[1]) \
>         { \
>             if (MatchList[state]) \
>             { \
>                 if (_add_queue(&acsm->q,MatchList[state])) \
>                 { \
>                     if (_process_queue(&acsm->q, Match,data)) \
>                     { \
>                         *current_state = state; \
>                         return 1; \
>                     } \
>                 } \
>             } \
>         } \
> -       state = ps[2 + sindex]; \
> +       state = new_state; \
>     }
> #endif
>
> But I think the routine could be more efficient too if we just fetch the new state in the end, and we move down one 
> line:
>
> #define AC_SEARCH_Q \
>     for (; T < Tend; T++) \
>     { \
>         ps = NextState[state]; \
> -       sindex = xlatcase[T[0]]; \
>         if (ps[1]) \
>         { \
>             if (MatchList[state]) \
>             { \
>                 if (_add_queue(&acsm->q,MatchList[state])) \
>                 { \
>                     if (_process_queue(&acsm->q, Match,data)) \
>                     { \
>                         *current_state = state; \
>                         return 1; \
>                     } \
>                 } \
>             } \
>         } \
> +       sindex = xlatcase[T[0]]; \
>         state = ps[2 + sindex]; \
>     }
> #endif
>
> In this way, I think the number of instructions could be reduced too.
>
> And these are the results that I have obtained:
>
> 612MB file -> 15.66% for MPSE, 22.13% for ac-q
> 1GB file -> 34.49% for MPSE, 35.13% for ac-q
>
> I will try to repeat these tests using other more powerful computers. In any case, we will give more information on 
> Monday.
> ------------------------------------------------------------------------------
> Master Visual Studio, SharePoint, SQL, ASP.NET, C# 2012, HTML5, CSS,
> MVC, Windows 8 Apps, JavaScript and much more. Keep your skills current
> with LearnDevNow - 3,200 step-by-step video tutorials by Microsoft
> MVPs and experts. ON SALE this month only -- learn more at:
> http://p.sf.net/sfu/learnnow-d2d
> _______________________________________________
> Snort-devel mailing list
> Snort-devel () lists sourceforge net
> https://lists.sourceforge.net/lists/listinfo/snort-devel
> Archive:
> http://sourceforge.net/mailarchive/forum.php?forum_name=snort-devel
>
> Please visit http://blog.snort.org for the latest news about Snort!
------------------------------------------------------------------------------
Master Visual Studio, SharePoint, SQL, ASP.NET, C# 2012, HTML5, CSS,
MVC, Windows 8 Apps, JavaScript and much more. Keep your skills current
with LearnDevNow - 3,200 step-by-step video tutorials by Microsoft
MVPs and experts. ON SALE this month only -- learn more at:
http://p.sf.net/sfu/learnnow-d2d

_______________________________________________
Snort-devel mailing list
Snort-devel () lists sourceforge net
https://lists.sourceforge.net/lists/listinfo/snort-devel
Archive:
http://sourceforge.net/mailarchive/forum.php?forum_name=snort-devel

Please visit http://blog.snort.org for the latest news about Snort!