Redundant/unnecessary BPF instructions generated for some capture filters

[cjmaynard]

trafficstars

Running dumpcap 3.4.5 on Windows 10 with Npcap version 1.31, based on libpcap version 1.10.1-PRE-GIT.

I recently discovered a few capture filters that cause some redundant and/or unnecessary BPF instructions to be generated. For example:

1. Capture TCP/IPv6 traffic over port 100: Capture Filter ip6[6]=6 and tcp port 100 generates redundant instructions 003 and 004:

    (000) ldh      [12]
    (001) jeq      #0x86dd          jt 2    jf 10
    (002) ldb      [20]
    (003) jeq      #0x6             jt 4    jf 10
    (004) jeq      #0x6             jt 5    jf 10
    (005) ldh      [54]
    (006) jeq      #0x64            jt 9    jf 7
    (007) ldh      [56]
    (008) jeq      #0x64            jt 9    jf 10
    (009) ret      #262144
    (010) ret      #0

2. Reversing the order doesn't help, but adding a redundant clause isn't ignored as one might expect: Capture filter tcp port 100 and ip6[6]=6 and tcp port 100 generates redundant instructions 008-013:

    (000) ldh      [12]
    (001) jeq      #0x86dd          jt 2    jf 15
    (002) ldb      [20]
    (003) jeq      #0x6             jt 4    jf 15
    (004) ldh      [54]
    (005) jeq      #0x64            jt 8    jf 6
    (006) ldh      [56]
    (007) jeq      #0x64            jt 8    jf 15
    (008) ldb      [20]
    (009) jeq      #0x6             jt 10   jf 15
    (010) ldh      [54]
    (011) jeq      #0x64            jt 14   jf 12
    (012) ldh      [56]
    (013) jeq      #0x64            jt 14   jf 15
    (014) ret      #262144
    (015) ret      #0

3. Capture traffic from source port 100 over IP: Capture filter ip and src port 100 generates BPF code that prioritizes SCTP (132) traffic, but why is SCTP (132) prioritized over TCP (6) or UDP (17)? Surely it's not as widely used in most applications, right?

    (000) ldh      [12]
    (001) jeq      #0x800           jt 2    jf 12
    (002) ldb      [23]
    (003) jeq      #0x84            jt 6    jf 4
    (004) jeq      #0x6             jt 6    jf 5
    (005) jeq      #0x11            jt 6    jf 12
    (006) ldh      [20]
    (007) jset     #0x1fff          jt 12   jf 8
    (008) ldxb     4*([14]&0xf)
    (009) ldh      [x + 14]
    (010) jeq      #0x64            jt 11   jf 12
    (011) ret      #262144
    (012) ret      #0

4. Capture traffic on TCP port 100 where either the SYN, FIN or RST flags are set: Capture filter port 100 and tcp[tcpflags] & (tcp-syn|tcp-fin|tcp-rst) != 0 generates BPF code that includes a useless check for IPv6 at instruction 001. If IPv6 isn't supported, then there's no need for 001 as 002 will take care of it. On the other hand ... why isn't IPv6 supported here? There was no ip specifier in the capture filter, after all. Also, why check protocol SCTP (132) here at instruction 004 when clearly this capture filter pertains to TCP only?

    (000) ldh      [12]
    (001) jeq      #0x86dd          jt 16   jf 2
    (002) jeq      #0x800           jt 3    jf 16
    (003) ldb      [23]
    (004) jeq      #0x84            jt 16   jf 5
    (005) jeq      #0x6             jt 6    jf 16
    (006) ldh      [20]
    (007) jset     #0x1fff          jt 16   jf 8
    (008) ldxb     4*([14]&0xf)
    (009) ldh      [x + 14]
    (010) jeq      #0x64            jt 13   jf 11
    (011) ldh      [x + 16]
    (012) jeq      #0x64            jt 13   jf 16
    (013) ldb      [x + 27]
    (014) jset     #0x7             jt 15   jf 16
    (015) ret      #262144
    (016) ret      #0

Ref: https://twitter.com/geraldcombs/status/1397694137533534208?s=20

[cjmaynard]

Another one:

5. Ports already included within a port range should be optimized away. For example instructions 013, 014 and 015 are completely unnecessary, given the following capture filter:

    tcpdump -i eth0 -d "ip and (tcp portrange 16-48 or tcp port 32)"
    (000) ldh      [12]
    (001) jeq      #0x800           jt 2    jf 17
    (002) ldb      [23]
    (003) jeq      #0x6             jt 4    jf 17
    (004) ldh      [20]
    (005) jset     #0x1fff          jt 17   jf 6
    (006) ldxb     4*([14]&0xf)
    (007) ldh      [x + 14]
    (008) jge      #0x10            jt 9    jf 10
    (009) jgt      #0x30            jt 10   jf 16
    (010) ldh      [x + 16]
    (011) jge      #0x10            jt 12   jf 13
    (012) jgt      #0x30            jt 13   jf 16
    (013) jeq      #0x20            jt 16   jf 14
    (014) ldh      [x + 14]
    (015) jeq      #0x20            jt 16   jf 17
    (016) ret      #262144
    (017) ret      #0

[splitice]

FYI @cjmaynard I optimized an a case that affected me in #1025 not a case described by you, but if you are making a comprehensive list...

[splitice]

Case 1 & 2 are becasue ip6 itself adds a comparison of version, [6]=6 adds another. I'm not aware of any optimization built into libpcap for the elimination of duplicate comparisons. This could however be resolved at instruction generation, it doesnt need optimizer update.

[cjmaynard]

Case 1 & 2 are becasue ip6 itself adds a comparison of version, [6]=6 adds another. I'm not aware of any optimization built into libpcap for the elimination of duplicate comparisons. This could however be resolved at instruction generation, it doesnt need optimizer update.

Sorry, I must be missing something. In case 1, the following 2 instructions are the same and thus only 1 of them is required:

(003) jeq #0x6 jt 4 jf 10
(004) jeq #0x6 jt 5 jf 10

In case 2, the following sets of instructions are identical in functionality and thus the 2nd set is redundant:

Set 1:

(002) ldb [20]
(003) jeq #0x6 jt 4 jf 15
(004) ldh [54]
(005) jeq #0x64 jt 8 jf 6
(006) ldh [56]
(007) jeq #0x64 jt 8 jf 15

Set 2:

(008) ldb [20]
(009) jeq #0x6 jt 10 jf 15
(010) ldh [54]
(011) jeq #0x64 jt 14 jf 12
(012) ldh [56]
(013) jeq #0x64 jt 14 jf 15