Wow, sounds like you're the guy to talk to on this stuff (for the record, I was counting you as one of the people who understood the state transition tables).  What do you mean by rule groups?  I'd love to know how you broke the emerging-all.rules into 50mb.  Running with ac-std takes over 2gb normally, and I think ac takes well over 4gb, but I've never used it.  Is a longer match always better?  Is there a threshold at which a pattern (say 100 or so bytes long) is too unwieldy and thus creates a "sweet spot?"<br>
<br>The frequency of matching was kind of what I was getting at the other day on the ET list regarding the use of the Snort HTTP preproc versus the straight pattern matcher because I was trying to figure out if the HTTP preproc (itself having already searched for terms like "POST" and "GET") would allow us to significantly reduce the load over sigs which use things like content:"GET"; distance:5;<br>
<br>So, in a brand-new design for a pattern matcher, how can we take advantage of the fact that we know certain strings will be searched on and hit much more frequently than others?  Would separating that into a separate thread provide any advantage?  Perhaps it could become like a mini-barnyard kind of situation in which it spits out much, much more traffic than alerting but still only a fraction of the overall throughput. As in, an HTTP preprocessor that dumps HTTP field streams without doing further app level pattern matching.  That trims the workload down substantially for another process, operating barnyard style, to come through and do higher-level matching and logic.  I think writing to disk barnyard-style would be fairly out of the question performance-wise, but maybe not writing to a socket where an entirely different process can read from.  Snort doesn't allow the preproc to cross CPU's, so the resources are all coming from the same pool.  If your HTTP preproc had a dedicated CPU, then the cache hits would be extremely high since it would only search for a few patterns.  If you did it right, I bet you could get almost ASIC or FPGA-level performance for URI content searches on a dedicated CPU. <br>
<br><div class="gmail_quote">On Thu, Feb 12, 2009 at 2:26 AM, Victor Julien <span dir="ltr"><<a href="mailto:lists@inliniac.net">lists@inliniac.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
-----BEGIN PGP SIGNED MESSAGE-----<br>
Hash: SHA1<br>
<br>
Martin Holste wrote:<br>
> I've done a little bit of work with rule profiling enough to realize<br>
> that I need help from someone who understands Aho-Corasick better so<br>
> that I can more accurately figure out what the load would be on the<br>
> detection engine.  (I posted something to this effect on the Emerging<br>
> Threats list last week.)  One real performance factor, as far as I can<br>
> tell, would be to see if the content matching already appears in another<br>
> rule.  If that's true, then the effective load of adding that rule could<br>
> be negligible, since the detection engine's effective load doesn't<br>
> actually increase.  So, a tool which takes the entire ruleset into<br>
> account would be very helpful.  I know that Sourcefire kind of already<br>
> does this in Snort in a few places, but I think the number of people who<br>
> understand the information from the state transition table reports could<br>
> be counted on one hand (judging from the lack of comments on the ET<br>
> list).  That information needs to be wrapped into a larger profiler.<br>
<br>
I'll add in some more variables that matter a lot:<br>
<br>
Number of patterns. All pattern matcher algorithms slow down if the<br>
number of patterns increases. This is because the match verification<br>
process gets more expensive as hash tables will fill up (using a 8bit<br>
alphabet in a 2gram algorithm results in a hash of max 65536). Usually<br>
switching from 2gram to 3 (or more) gram versions of algorithms helps,<br>
however at a cost of using more memory & higher computation overhead.<br>
That influences performance quite a bit, probably because of more memory<br>
meaning more CPU cache misses. Usually the average pattern length goes<br>
down too.<br>
<br>
The minimum largest pattern size. Most pattern matcher algorithms<br>
perform best with longer patterns since the matcher can step through the<br>
searched data in bigger steps. So if all your sigs have at least a<br>
pattern length of 8 and you add in one of length 3 your performance hit<br>
is going to be bigger than when there are already sigs with smaller<br>
patterns.<br>
<br>
Similar rules are grouped together so safe memory on (among others)<br>
pattern matcher contexts. A bad rule will only influence the groups it's<br>
in. But an even worse rule can end up in a lot of contexts. (using the<br>
emerging-all.rules file I can easily have the engine use a few gigabytes<br>
of ram, but using the grouping I have slimmed it down to about 50mb.<br>
Guess which performs better? The smaller one :))<br>
<br>
CPU cache size & memory bus speeds seems to make a big difference too.<br>
In my code I've implemented the (simple) BNDM algorithm, both in a<br>
2-gram and 3-gram version. On a Core2duo T5500 (2mb cache) a 2-gram<br>
sBNDM performed best, on Core2duo E6600 (4mb cache) a 3-gram BNDM. On my<br>
gateway box, P3 500mhz 512mb cache, again the 2-gram sBNDM, but with<br>
different hash table sizes and stuff...<br>
<br>
One thing that also influences performance is the likelihood of a match<br>
because after the pattern matcher suspects a match, it has to be<br>
verified by the detection engine.  For example I think HTTP keywords,<br>
HTML stuff, SMTP commands, etc, etc, all have a bigger likelihood of<br>
matching and thus are more expensive... maybe a blacklist could help<br>
there. Any pattern on that list would be classified as more expensive...<br>
<br>
Regards,<br>
Victor<br>
<br>
- --<br>
- ---------------------------------------------<br>
Victor Julien<br>
<a href="http://www.inliniac.net/" target="_blank">http://www.inliniac.net/</a><br>
PGP: <a href="http://www.inliniac.net/victorjulien.asc" target="_blank">http://www.inliniac.net/victorjulien.asc</a><br>
- ---------------------------------------------<br>
<br>
-----BEGIN PGP SIGNATURE-----<br>
Version: GnuPG v1.4.9 (GNU/Linux)<br>
Comment: Using GnuPG with Mozilla - <a href="http://enigmail.mozdev.org" target="_blank">http://enigmail.mozdev.org</a><br>
<br>
iEYEARECAAYFAkmT3SAACgkQiSMBBAuniMeyRgCfe0nDEaM+qzCpWQ1V2aCfotzp<br>
hOUAn14sw9BI3LZGCRYLKh9dFB6oiubV<br>
=kZSl<br>
-----END PGP SIGNATURE-----<br>
</blockquote></div><br>