More 'or' cases broken with packet indexing

[kbara]

Reminiscent of https://github.com/Igalia/pflua/issues/132 , some non-icmp6 pflang expressions with 'or' are broken; our pure-lua and bpf-lua pipelines do not agree about whether the given expressions match the given packets. The packets are from wingolog.pcap, as usual.

(Begin list of examples which show the bug) arp[123] < 152 or portrange 35707-47484; packet number 3584 ip6[231] != 180 or len >= 2147483647 & 2147483648; packet number 8282 rarp[4619] > 239 or 0 >> 29 = 0; packet number 10844

They can be simplified a little, while still having the pipelines diverge: arp[1] < 1 or port 35710; 3584 arp[1] > 1 or tcp" 3584; 3584 This appears to be related to indexing on arp, as the second clause can change.

ip6[1] != 1 or len >= 1; 8282 This one appears to be related to indexing on ip6 when it's not the only clause, as ip6 or len >= 1 is ok, as is ip6[1] > 1.

rarp[1] > 1 or tcp; 10844 rarp[1] > 1 or 0 = 0; 10844 Same story, but with rarp.

(End list of examples which show the bug)

---

Several things that look like plausible tries at simplification work correctly, rather than showing the bug(s), including every attempt to remove 'or':

% ./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "arp[123]  < 152 or port 3" 3584               
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
% ./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "arp or portrange 35707-47484" 3584 
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
% ./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "arp[123]  < 152 or portrange 1-2" 3584        
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
% ./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "arp or port 35710" 3584 
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true

% ./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ip6 or len >= 1 & 1" 8282 
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ip6[1] > 1" 8282
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true

% ./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "0 = 0" 10844 
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
% ./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "rarp[1]  >= 0 " 10844
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false

[kbara]

In summary, packet indexing with or seems to commonly be broken, except for tcp and ip. Packet indexing as the only clause (ie, rarp[1] >= 0) has worked in every case I've manually tried while investigating this bug.

% for x in ip tcp udp icmp igmp igrp vrrp ip6 arp rarp; 
   do echo -n "$x "; ./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "${x}[1] >= 0 or tcp" 1;
done
ip OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
tcp OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
udp BUG: pure-lua false, bpf-lua true, libpcap true.
icmp BUG: pure-lua false, bpf-lua true, libpcap true.
igmp BUG: pure-lua false, bpf-lua true, libpcap true.
igrp BUG: pure-lua false, bpf-lua true, libpcap true.
vrrp BUG: pure-lua false, bpf-lua true, libpcap true.
ip6 BUG: pure-lua false, bpf-lua true, libpcap true.
arp BUG: pure-lua false, bpf-lua true, libpcap true.
rarp BUG: pure-lua false, bpf-lua true, libpcap true.

Some protocols fundamentally aren't impacted by this, because libpcap doesn't allow indexing into them, such as icmp6:

tcpdump -d "icmp6[1] > 1"
tcpdump: IPv6 upper-layer protocol is not supported by proto[x]

[kbara]

As expected, clause order matters:

% ./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "rarp[1] > 1 or tcp" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
% ./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "tcp or rarp[1] > 1" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true

[kbara]

Minor evidence against it being an optimizer bug, and perhaps in favor of it being an expand bug:

./pipe-unopt-opt-match ../tests/data/wingolog.pcap "rarp[1] > 1 or tcp" 1
OK: false with and without optimization

[dpino]

As it happened with icmp6, the code generated for "rarp[1] > 1 or tcp" and "tcp or rarp[1] > 1". I still need to look more into this but you can get it working removing the is ether and ipv4 protocol asserts.

local function assert_ether_protocol(proto)
  return assert_expr(has_ether_protocol_min_payload(proto))
end

function ipv4_payload_offset(proto)
  local ip_offset, asserts = expand_offset('ip', dlt)
  asserts = concat(asserts, assert_first_ipv4_fragment())
  local res = { '+',
                { '<<', { '&', { '[]', ip_offset, 1 }, 0xf }, 2 },
                ip_offset }
  return res, asserts
end

for x in ip tcp udp icmp igmp igrp pim sctp vrrp ip6 arp rarp; do 
    echo -n "$x "; ./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "${x}[1] >= 0 or tcp" 1; 
done

ip OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
tcp OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
udp OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
icmp OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
igmp OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
igrp OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
pim OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
sctp OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
vrrp OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
ip6 OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
arp OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
rarp OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true

[dpino]

Commenting the protocol assertion:

--[[
if proto then
    asserts = assert_expr(has_ipv4_protocol(proto))
end
--]]

works cause there's no longer a conflict between what the protocol number should be. For instance, upd[1] > 0 or tcp will check for each branch whether P[23] == 17 or P[23] == 6, respectively.

Commenting the protocol offset assertion, removes P[23] == 17, leaving only P[23] == 6, which is part of the expansion code, not an assertion.

My question is, shouldn't be this protocol verifications part of the expanded code for the offsets instead of assertions?

OTOH, tcp[1] > 0 or tcp works cause there's no conflict between the expanded code for tcp and the assertion in tcp[1] > 0.

return function(P,length)
   if length < 54 then return false end
   if cast("uint16_t*", P+12)[0] ~= 8 then return false end
   if P[23] ~= 6 then return false end
   if band(cast("uint16_t*", P+20)[0],65311) ~= 0 then return false end
   local var7 = lshift(band(P[14],15),2)
   return (var7 + 16) <= length
end

ip[1] > 0 of tcp works because ip[1] > 0 generates no assertions:

local cast = require("ffi").cast
return function(P,length)
   if length < 34 then return false end
   if cast("uint16_t*", P+12)[0] ~= 8 then return false end
   return P[15] > 0
end

[wingo]

ip[1] > 0 should certainly generate an assertion.

I am a bit lost :) What's the bug again?

[kbara]

The bug is that our bpf-lua and pure-lua pipelines give different results for the same filter on the same packet (bpf-lua agrees with libpcap, suggesting it's our pure-lua pipeline that is buggy). Using one of the minimal test cases from the first post:

% ./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "rarp[1] > 1 or tcp" 1
BUG: pure-lua false, bpf-lua true, libpcap true.

Edit: I edited the first post to explicitly state that the pipelines diverge in the first paragraph.

[kbara]

The bug shows up on most packets, and with optimization disabled.

% ./pipe-lua-libpcap-match -O0 ../tests/data/wingolog.pcap "arp[1] > 1 or tcp" 1
BUG: pure-lua false, bpf-lua true, libpcap true.

[kbara]

Another example:

% ./env tools/pipe-lua-libpcap-match tests/data/wingolog.pcap 'igrp[50:4]  < 92 or 0 & 632899130 = 0' 7901
BUG: pure-lua false, bpf-lua true, libpcap true.

This can be reduced:

% ./env tools/pipe-lua-libpcap-match tests/data/wingolog.pcap 'igrp[1] < 1 or 0 = 0' 7901 
BUG: pure-lua false, bpf-lua true, libpcap true.

[kbara]

And yet another example, with minimization:

% ./env tools/pipe-lua-libpcap-match tests/data/wingolog.pcap 'arp[53]  >= 62 or ip' 6919 
BUG: pure-lua false, bpf-lua true, libpcap true.
% ./env tools/pipe-lua-libpcap-match tests/data/wingolog.pcap 'arp[1] >= 1 or ip' 1
BUG: pure-lua false, bpf-lua true, libpcap true

[kbara]

Fixed via https://github.com/Igalia/pflua/issues/171 , including its regression tests.