Snort mailing list archives
Re: Optimized implementation of AC and AC_Q pattern matching algorithms
From: abed mohammad kamaluddin <abedamu () gmail com>
Date: Sun, 27 Jan 2013 00:27:08 +0530
Hi Pablo, That looks neater :) I will try your modifications on our system on Monday when I return to work. I used zero-alert traffic to measure perf which gave me 11% up on 2.9.0.4. PS: I have noticed a more than 15% overall performance drop on 2.9.4 as compare to 2.9.3.1 when compiled with exactly same options. I haven't analyzed it so far, however this particular optimization has the same relative improvement on all versions (2.9.0.4, 2.9.3.1 and 2.9.4) . Thanks, Abed Message: 2
Date: Sat, 26 Jan 2013 16:50:37 +0100 From: Pablo Cantos <pablocantos () gmail com> Subject: Re: [Snort-devel] Optimized implementation of AC and AC_Q pattern matching algorithms To: snort-devel () lists sourceforge net Message-ID: <CADQcQ1OzJDso9FEQhG77dGtSTEiX= J80bxRDMv9t8Yz7WhH0-g () mail gmail com> Content-Type: text/plain; charset="iso-8859-1" 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. -------------- next part -------------- An HTML attachment was scrubbed... ------------------------------ Message: 3 Date: Sat, 26 Jan 2013 11:26:55 -0500 From: Joel Esler <jesler () sourcefire com> Subject: Re: [Snort-devel] Optimized implementation of AC and AC_Q pattern matching algorithms To: Pablo Cantos <pablocantos () gmail com> Cc: "snort-devel () lists sourceforge net" <snort-devel () lists sourceforge net> Message-ID: <2B25430D-9736-49BB-9A81-EC9AF163C28F () sourcefire com> Content-Type: text/plain; charset="utf-8" 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 pcapfiles, 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 eachpcap file by the MPSE and AC, separately.I have been working for several months with Snort to get improvements inother 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 thenew 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. Inany 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!-------------- next part -------------- An HTML attachment was scrubbed... ------------------------------ ------------------------------------------------------------------------------ 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 End of Snort-devel Digest, Vol 78, Issue 10 *******************************************
------------------------------------------------------------------------------ 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!
Current thread:
- Re: Optimized implementation of AC and AC_Q pattern matching algorithms Pablo Cantos (Jan 26)
- Re: Optimized implementation of AC and AC_Q pattern matching algorithms Joel Esler (Jan 26)
- <Possible follow-ups>
- Re: Optimized implementation of AC and AC_Q pattern matching algorithms abed mohammad kamaluddin (Jan 26)
- Re: Optimized implementation of AC and AC_Q pattern matching algorithms abed mohammad kamaluddin (Jan 28)
- Re: Optimized implementation of AC and AC_Q pattern matching algorithms Pablo Cantos (Jan 28)
- SNORT compilation in ECLIPSE patricio (Jan 28)
- Re: Optimized implementation of AC and AC_Q pattern matching algorithms abed mohammad kamaluddin (Jan 28)