Optimizing BPF filters

[Daniel Miller <bonsaiviking () gmail com>]

I am about to commit 2 changes to the way we call pcap_compile in libnetutil:

diff --git a/libnetutil/netutil.cc b/libnetutil/netutil.cc
index b7727f7..5350660 100644
--- a/libnetutil/netutil.cc
+++ b/libnetutil/netutil.cc
@@ -4069,7 +4069,7 @@ void set_pcap_filter(const char *device, pcap_t
*pd, const char *bpf, ...) {
     netutil_fatal("%s called with too-large filter arg\n", __func__);
   va_end(ap);

-  if (pcap_compile(pd, &fcode, buf, 0, 0) < 0)
+  if (pcap_compile(pd, &fcode, buf, 1, PCAP_NETMASK_UNKNOWN) < 0)
     netutil_fatal("Error compiling our pcap filter: %s", pcap_geterr(pd));
   if (pcap_setfilter(pd, &fcode) < 0)
     netutil_fatal("Failed to set the pcap filter: %s\n", pcap_geterr(pd));

The first change is requesting optimization of our BPF via the third argument.

The libpcap BPF optimizer is very good at what it does. It adds extra
processing up front, but since we limit (in
scan_engine_raw.cc:begin_sniffer) the number of individual
addresses in a single filter to 20, it's not a noticeable slowdown. It
does, however, reduce the number of BPF bytecode instructions for the
big-scan case (where we don't filter on source) to 10 from 45. In the
best case, the unoptimized code requires 3 loads and 3 jumps before
returning (false), whereas the optimized requires only 1 load and 1
jump.

Unoptimized:
sudo tcpdump -dO -- 'dst host 1 and (icmp or icmp6 or tcp or udp or sctp)'
(000) ldh      [12]
(001) jeq      #0x800           jt 2    jf 4
(002) ld       [30]
(003) jeq      #0x1             jt 12   jf 4
(004) ldh      [12]
(005) jeq      #0x806           jt 6    jf 8
(006) ld       [38]
(007) jeq      #0x1             jt 12   jf 8
(008) ldh      [12]
(009) jeq      #0x8035          jt 10   jf 45
(010) ld       [38]
(011) jeq      #0x1             jt 12   jf 45
(012) ldh      [12]
(013) jeq      #0x800           jt 14   jf 16
(014) ldb      [23]
(015) jeq      #0x1             jt 44   jf 16
<snip>
(044) ret      #65535
(045) ret      #0

Optimized:
sudo tcpdump -d -- 'dst host 1 and (icmp or icmp6 or tcp or udp or sctp)'
(000) ldh      [12]
(001) jeq      #0x800           jt 2    jf 10
(002) ld       [30]
(003) jeq      #0x1             jt 4    jf 10
(004) ldb      [23]
(005) jeq      #0x1             jt 9    jf 6
(006) jeq      #0x6             jt 9    jf 7
(007) jeq      #0x11            jt 9    jf 8
(008) jeq      #0x84            jt 9    jf 10
(009) ret      #65535
(010) ret      #0

I'm guessing this won't matter in most cases, but it may be
incrementally better in the super-fast Internet-scale scans that are
getting lots of press these days, or in local-LAN scans on gigabit or
faster networks.

The second change is changing the netmask argument from 0 to
PCAP_NETMASK_UNKNOWN. This should not affect Nmap at all for now, but
may serve as a warning if anyone tries to introduce a BPF filter that
uses the "broadcast" test. In order for this test to have meaning, we
have to provide a real netmask for the address/interface we are
listening on. We used to have code that did detection of this value,
but it was stripped in r23778, so I suspect it was incompatible with
IPv6 scans. Anyway, PCAP_NETMASK_UNKNOWN is the documented value to
use in this case, so that's what I'm going with.

Dan
_______________________________________________
Sent through the dev mailing list
http://nmap.org/mailman/listinfo/dev
Archived at http://seclists.org/nmap-dev/