[Snort-devel] Thoughts on threads

Martin Roesch roesch at ...48...
Sat Apr 7 00:28:55 EDT 2001


Nash wrote:
> 
> On Sat, Apr 07, 2001 at 02:21:04AM +0700, Fyodor wrote:
> >
> > I see. IMHO the data which we expect to be used to generated would be the same
> > as the 'real-world' data since we will probably be running compiled for
> > profiling snort binary on the real network. (althrough during last my testings
> > it slowed down the process alot, so I donno if profiled snort could really keep
> > up on a busy segment).
> 
> That's basically the problem. You might consider running snort on the network in
> unprofiled mode for awhile and just having it log all the packets. When it fills
> up a few dozen gig you can then write a perl script to replay the packets to a
> profiling perl. Mmm ...  test harnesses. Much fun in the sun. ;-)

This wouldn't actually be a good test since I know where our main time
sinks are (packet acq and output) and half of that code wouldn't be
tested effectively in a readback test.

> But, you still face the possibility that the XX gigs of data you have stored on
> disk will be different enough that performance will be lost b/c of it being a
> special case.

Exactly, changing the primary data acquisition mechanism is a huge
change.

> > By the way you have any suggestions for more complex math except for manual
> > code analysis? :) Looks like you have got quite some experience with this :)
> 
> Not enough experience. My only suggestion would be to always keep in mind the
> worst case performance for the algorithms involved. Known the value of the O(f(n))
> performance for your algorithm (f(n)) is really important. Manual code analysis
> meaning line by line? Yeah, that's icky stuff.

Yup.  My way is to write it fast the first time and you won't have to
worry about profiling it later. :)

> E.g., your idea about building the rules into trees is a really good one. It
> can be shown that in the right kind of tree your performance will never be worse
> than O(n * log(2, n)). This is quite good for a match. Its far better to optimize
> this way first and then optimize for fewer instructions. Your biggest benefits are
> usually from using better algorithms. That being said, Marty has incredible instincts
> for what makes fast algorithms. Its tough to argue against the current decoder scheme
> since its essentially instantaneous. =)

Aw shucks. :)  Treeing out the stateless detection engine would be the
final stage of optimization that could be made on the existing system,
but that would save us some serious clock cycles because we'd be
dropping a lot of calls to detection functions that can be collapsed
into more singular tests.  For instance, the following:

alert tcp any any -> $HOME_NET 80 (flags: A+; content: "phf"; msg: "a";)
alert tcp any any -> $HOME_NET 80 (flags: A+; content: "perl.exe"; msg:
"b";)
alert tcp any any -> $HOME_NET 80 (flags: A+; content: "foo"; msg: "c";)
alert tcp any any -> $HOME_NET 79 (flags: A+; content: "root"; msg:
"d";)


is (notionally) put into the current detection engine structures like
this:

alert
  |
  |
  +-->tcp
       |
       |
       +-->RTN (CheckDstIP(HOME_NET, p), CheckDstPort(80, p))
       |    |
       |    |
       |    +-->CheckFlags(A+, p), CheckContent("phf", p)
       |    |
       |    +-->CheckFlags(A+, p), CheckContent("perl.exe", p)
       |    |
       |    +-->CheckFlags(A+, p), CheckContent("foo", p)
       |
       +-->RTN (CheckDstIP(HOME_NET, p), CheckDstPort(79, p))
            |
            |
            +-->CheckFlags(A+, p), CheckContent("root", p)

This could be better expressed as"

alert
  |
  |
  +->tcp
       |
       |
       +->CheckDstIP(HOME_NET, p) 
             |
             |
             +->CheckDstPort(80, p)
             |     |
             |     |
             |     +->CheckFlags(A+, p)
             |          |
             |          |
             |          +->CheckContent("phf", p)
             |          |
             |          +->CheckContent("perl.exe", p)
             |          |
             |          +->CheckContent("foo", p)
             |
             +->CheckDstPort(79, p)
                   |
                   |
                   +->CheckFlags(A+, p)
                        |
                        |
                        +->CheckContent("root", p)

In 2.0 when we implement the Aho-Corasick pattern matcher we'll be able
to search the entire pattern space of the final content check in one
pass.  Note that if we write the optimizer properly, it'll automatically
move any pattern matching we end up doing to the leaf nodes of the tree.

    -Marty




More information about the Snort-devel mailing list