Wireshark-dev: [Wireshark-dev] one possible way to speed up filtering
From: yami <[email protected]>
Date: Tue, 17 Mar 2009 22:14:56 +0800
Hi dev,

I have implemented a prototype to speed up interactive filtering. The key idea is to reuse previous display information. (Is there anyone interested in this idea?)

For example, a user filters 'udp' first, then he tries to filter 'dns'. Since we know that only packets passed 'udp' filter string have the possibility to pass 'dns', there is no need to dissect packets not passed the 'udp' filter.

This could be a big gain, if the capture is large, but UDP packets occupy only a small portion of it.

In my current implementation, if in the second filtering, the user inputs 'udp && dns', Wireshark will find that 'udp' has already been filtered, so if a packet did not passed 'udp', Wireshark will not dissect it again.


The above is only the simplest case. In general this is a Boolean Satisfiability [1] problem. Assume a new display filter, say D, contains previous applied filters S1, ..., Sn. We know that S1...Sn are subtrees of D's syntax tree.

And for packet P, if it passed Si then assigned Bi to 1, otherwise 0, so we get B1,...,Bn; then we can generate a boolean _expression_, say EXP, for D with its subtrees S1,...,S2 replaced by B1,...,Bn.

If EXP could never be true, then P will not pass D (we know this without dissecting/filtering).
If !(EXP) could never be true, then P will pass D.
If the above two are satisfied, we should dissect/filter P.

[1] http://en.wikipedia.org/wiki/Boolean_satisfiability_problem