Snort mailing list archives
Re: Optimized implementation of AC and AC_Q pattern matching algorithms
From: Pablo Cantos <pablocantos () gmail com>
Date: Mon, 28 Jan 2013 21:40:31 +0100
Hi Abed, 2013/1/28 abed mohammad kamaluddin <abedamu () gmail com>
Hi Pablo, I tried you modification on OCTEON today and was disappointed that there was a drop in performance on it, however on Intel there is significant improvement in perf. In comparison to unmodified snort using Network traffic and ac-q: cross-compiling (Octeon) gcc (Intel) Using your modification - 15% down 21% up Using mine - 11% up 12% up I supposed it. I mean, when I have been working on getting a better
performance for the MPSE a Intel machine was used and I found that in many cases a better performance was obtained using gcc, but a worse performance was obtained with icc. This time, probably we won't be able to perform these tests on the Intel machine until next week.
On Intel, we can remove sindex altogether: state = ps[2 + xlatcase[T[0]]] Yes, I removed it too and I got very similar results, maybe because the
compiler (gcc) removed it by itself.
Maybe it could be because I am cross compiling ; there were lot of wasted cycles in my case. Unless I introduce an intermediate state, I am not getting any improvement. I had earlier analyzed this routine in detail and each cycle reduced in this macro gave significant perf improvements. Could you please mention the following: - Which compiler have you used (gcc/icc version). - If you can provide the pcap file you are using for the tests it would help. I have used gcc 4.6.1-9ubuntu3.
One of them (1gb) was downloaded from here: https://www.itoc.usma.edu/research/dataset/ but I don't remember which it is exactly. I will send you tomorrow a private link to download them. Anyway, if someone else wants to download the pcap files just send me an email and I'll provide him/her the link. I will try your modifications on a bigger Intel machine sometime this
week and report the findings. I'll be waiting for your news
Thanks, Abed M K
On Sun, Jan 27, 2013 at 12:27 AM, abed mohammad kamaluddin <abedamu () gmail com> wrote:Hi Pablo, That looks neater :) I will try your modifications on our system onMondaywhen I return to work. I used zero-alert traffic to measure perf whichgaveme 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: 2Date: 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 4GBRAM.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 differentpcapfiles, one of them (612MB-sized) throws around 900k alerts and theother one(1GB-sized) throws just 55 alerts. I have used an AMD Turion IIdual-coremobile 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 macrosand Ididn't find them completely efficients but I didn't go further. Now,afterseeing 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 skillscurrentwith 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)