address can be selected and not selected when optimization is off

[amorsen]

tcpdump version 4.9.3
libpcap version 1.9.1 (with TPACKET_V3)
OpenSSL 1.1.1g FIPS 21 Apr 2020

This is a very simplified example where I believe tcpdump filters incorrectly. I would attach a pcap file demonstrating the problem, but that is apparently not possible here.

To create the pcap file do:

Pick any address that answers ping requests, and just replace 192.168.1.1 in the following.

tcpdump -w bug-icmp.pcap host 192.168.1.1 and icmp
ping 192.168.1.1

With the resulting file do:

tcpdump -nr bug-icmp.pcap 'host 192.168.1.1 and not ((host 1.2.3.4 or host 5.6.7.8) and icmp) and not (host 5.6.7.8 or host 192.168.1.1)'
reading from file bug-icmp.pcap, link-type EN10MB (Ethernet)
10:37:23.323954 IP 192.168.1.1 > 192.168.1.51: ICMP echo reply, id 6, seq 1, length 64
10:37:24.340916 IP 192.168.1.1 > 192.168.1.51: ICMP echo reply, id 6, seq 2, length 64
10:37:25.364920 IP 192.168.1.1 > 192.168.1.51: ICMP echo reply, id 6, seq 3, length 64
10:37:26.366324 IP 192.168.1.1 > 192.168.1.51: ICMP echo reply, id 6, seq 4, length 64

I believe the output from this filter should be empty, since the packet cannot both be from host 192.168.1.1 and at the same time NOT from host 192.168.1.1.

If I change the first 5.6.7.8 to 6.7.8.9 I get:

tcpdump -nr bug-icmp.pcap 'host 192.168.1.1 and not ((host 1.2.3.4 or host 6.7.8.9) and icmp) and not (host 5.6.7.8 or host 192.168.1.1)'
reading from file bug-icmp.pcap, link-type EN10MB (Ethernet)

which is the output I expected.

It is not immediately obvious why changing an unrelated IP address affects filtering on 192.168.1.1.

[fxlb]

Thanks. Could you attach the poc pcap in a zip file?

[amorsen]

bug-icmp.pcap.gz

Gzipping worked.

I ended up making another pcap, so the timestamps and one of the IP addresses do not match the above. Instead it is:

$ tcpdump -nr bug-icmp.pcap 'host 192.168.1.1 and not ((host 1.2.3.4 or host 5.6.7.8) and icmp) and not (host 5.6.7.8 or host 192.168.1.1)'
reading from file bug-icmp.pcap, link-type EN10MB (Ethernet)
12:14:58.458291 IP 192.168.1.1 > 192.168.1.4: ICMP echo reply, id 9, seq 1, length 64
12:14:59.511701 IP 192.168.1.1 > 192.168.1.4: ICMP echo reply, id 9, seq 2, length 64
12:15:00.534325 IP 192.168.1.1 > 192.168.1.4: ICMP echo reply, id 9, seq 3, length 64
12:15:01.558331 IP 192.168.1.1 > 192.168.1.4: ICMP echo reply, id 9, seq 4, length 64

[fenner]

Neat optimizer bug. If you add "-O", your filter works as desired.

[guyharris]

The "expression rejects all packets" test is done only if the optimizer is on; detecting filters that never match involves analysis that's done in the optimizer.

However, even with the optimizer on, it didn't reduce the filter to "ret 0". The filter 'host 192.168.1.1 and not (host 5.6.7.8 or host 192.168.1.1)', with the "and not" clause in the middle removed, is recognized as matching nothing, but the middle clause somehow confuses the optimizer.

[amorsen]

Is the new title correct? The problem happens when the optimization is on, not when it is off. Perhaps I am misunderstanding the title.

Either way, I would really love a fix for this one. The simplified case above may be considered silly, but the problem itself manifests in real filters that I use for debugging. It is not a theoretical problem.

I suspected the problem for years actually, but it took quite a bit of digging to get a clear test case. At first I thought the bug was only in a specific vendor implementation, but then it turned up in bog standard tcpdump. The only reliable workaround is to avoid brackets.

[tenarchits]

This test case creates many blocks which are rearranged by or_pullup in opt_blks . I think running find_dom every time the pullup is successful fixes this issue as it allows the dominator sets to be recomputed based on the updated control flow graph.

[guyharris]

This test case creates many blocks which are rearranged by or_pullup in opt_blks . I think running find_dom every time the pullup is successful fixes this issue as it allows the dominator sets to be recomputed based on the updated control flow graph.

Merging #976 does appear to fix this, in that the filter no longer matches any packets.

It doesn't report "expression rejects all packets"; the BPF program produced is

(000) ldh      [12]
(001) jeq      #0x800           jt 2	jf 22
(002) ld       [26]
(003) jeq      #0xc0a80101      jt 4	jf 7
(004) ld       [30]
(005) jeq      #0x1020304       jt 12	jf 6
(006) jeq      #0x5060708       jt 12	jf 18
(007) ld       [30]
(008) jeq      #0xc0a80101      jt 9	jf 22
(009) ld       [26]
(010) jeq      #0x1020304       jt 12	jf 11
(011) jeq      #0x5060708       jt 12	jf 22
(012) ldb      [23]
(013) jeq      #0x1             jt 22	jf 14
(014) ld       [26]
(015) jeq      #0x5060708       jt 22	jf 16
(016) ld       [30]
(017) jeq      #0x5060708       jt 22	jf 18
(018) jeq      #0xc0a80101      jt 22	jf 19
(019) ld       [26]
(020) jeq      #0xc0a80101      jt 22	jf 21
(021) ret      #262144
(022) ret      #0