StoneBlog.stonesoft.com

Talking about Fingerprint Patterns (signatures) in our IPS, there are some “rule of thumbs” to respect to avoid having the FP eating resources on the sensor.

Computational model used by StoneGate IPS Sensor to render fingerprints is DFA.

Understanding how the regular expressions in IPS fingerprints affect the DFA used in matching is a bit difficult and is usually based on vague guidelines like “don’t use .* in the middle of a regular expression”.
Rendering the resulting DFA might provide more insight into how things work, and also produces pretty pictures
Here’s a sample rendering of the group DFA “TNS TCP Client Stream”:

Green nodes are normal states, red nodes matching states. The lines represent possible state changes depending on input bytes.

Did you like it? Here’s some more:

Simple regular expression:

(?x) .*abcdefgh| .*12345678

Simple regexp with a .* in the middle (not recommended):

(?x)
.*abcdefgh.*ijklmop|
.*12345678

Regexp with two .* sequences

(?x)
.*abcdefgh.*ijklmop|
.*12345678.*90x11x12x13x14x15

Same with variables instead of .*’s:

(?x)
.*abcdefgh(?{a=1,ignore})|
.*12345678(?{b=1,ignore})|
.*ijklmnop(?{a==1})|
.*90x11x12x13x14x15(?{b==1})

The last two regular expressions do the same thing, but the with 33 nodes in the DFA using variables versus 89 nodes in the .* version.

The .* version also grows quite fast with additional regexp branches unlike the flat DFA with variables.

written by RoarinPenguin - 1,797 views \\ tags: DFA, fingerprint, IPS, regular expression