Packet indexing should cause conditions and assertions
wingo opened this issue · 8 comments
The expression "arp[0] >= 0 or not arp" should match all packets. Right now it fails for non-arp packets; see #166. The issue is that packet access (arp[0]) was causing an assertion that the packet is an arp packet. By assertion I mean that if the packet is not an arp packet, the whole filter fails, not just the clause. Instead, the expansion of arp[0] should simply cause the clause to fail if the packet isn't an arp packet.
However, one assertion does remain: if an out-of-bounds access is made to the packet, the filter immediately fails. See https://github.com/Igalia/pflua/blob/master/doc/pflang.md#packet-access. This is an artifact of the implementation of the BPF VMs -- out-of-bounds packet access causes immediate failure.
So arithmetic expressions should residualize both assertions which cause the filter to fail immediately and conditions which cause the clause to fail.
One open question is, what is the ordering between conditions and assertions? Some tests show that e.g. arp[5000] < 42 will test "arp" and fail the clause before accessing the payload and failing the filter. Would ether[100] < tcp[100] test the "ether and tcp" conditions before checking the offsets, or would the conditions and the assertions be interleaved in some way? (The ordering is indeed visible to the user.) What if we swap the LHS and the RHS, is the result the same? We need to do some science on the language to see what its semantics are in this regard.
See #166 for a symptom of this problem.
Thank you for the excellent analysis, @andywingo !
A little bit of raw science suggests that it takes fairly particular conditions to trigger #166.
The following analysis was performed on packet 1 of wingolog.pcap, a 66-byte ethernet-encapsulated TCP packet.
First, the bad news - note particularly that libpcap's behavior is quite odd:
ether[1] > tcp[1] is true
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[1] or tcp" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
out-of-bounds or a true condition is ... false, according to libpcap
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[100] or ether[1] > tcp[1]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
out-of-bounds or a true condition is ... true, according to libpcap
% ./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[100] or tcp" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
Argh.
There is weak evidence that this is related to the second clause using packet access:
% ./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[100] or ip" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
% ./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[100] or ip[1] >= 0" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
By the way, did I mention that libpcap is odd? The following out-of-bounds packet access clause matches!
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[1] or ether[1] > tcp[100]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
See "clause order seems irrelevant" for more similar examples of this particular gem.
Out-of-bounds access in a relevant protocol followed by a matching clause triggers bug 166 in the following examples:
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[1] or not ether[1] > tcp[1]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[100] or not ether[1] > tcp[100]" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[100] > tcp[1] or not ether[100] > tcp[1]" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[100] > tcp[100] or not ether[100] > tcp[100]" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[1] or tcp" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[100] or tcp" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[100] > tcp[1] or tcp" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[100] > tcp[100] or tcp" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
Surprisingly, clause order seems irrelevant; any combination of ether[ok or big] > tcp[ok or big] or ether[ok or big] > tcp [ok or big] do not show buggy behaviour (relative to libpcap...here be oddity dragons)
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[1]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[100]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[100] > tcp[1]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[100] > tcp[100]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[1] or ether[1] > tcp[1]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[1] or ether[1] > tcp[100]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[1] or ether[100] > tcp[1]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[1] or ether[100] > tcp[100]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[100] or ether[1] > tcp[1]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[100] or ether[1] > tcp[100]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[100] or ether[100] > tcp[1]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[100] or ether[100] > tcp[100]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[100] > tcp[1] or ether[1] > tcp[1]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[100] > tcp[1] or ether[1] > tcp[100]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[100] > tcp[1] or ether[100] > tcp[1]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[100] > tcp[1] or ether[100] > tcp[100]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[100] > tcp[100] or ether[1] > tcp[1]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[100] > tcp[100] or ether[1] > tcp[100]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[100] > tcp[100] or ether[100] > tcp[1]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[100] > tcp[100] or ether[100] > tcp[100]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
The following are here for the sake of completeness, as they are also tests I ran and provide evidence, but the results are unsurprising in light of the above - none diverge from libpcap
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[1] or tcp[1] < ether[1]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[100] or tcp[100] < ether[1]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[100] > tcp[1] or tcp[1] < ether[100]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[100] > tcp[100] or tcp[100] < ether[100]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > arp[1] or arp[1] < ether[1]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > arp[100] or arp[100] < ether[1]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[100] > arp[1] or arp[1] < ether[100]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[100] > arp[100] or arp[100] < ether[100]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[1] or arp" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[100] or arp" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[100] > tcp[1] or arp" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[100] > tcp[100] or arp" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "tcp or ether[1] > tcp[1]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "tcp or ether[1] > tcp[100]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "tcp or ether[100] > tcp[1]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "tcp or ether[100] > tcp[100]" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
All of the above were generated by minor variants of
#!/usr/bin/env python
import subprocess
def gen_and_run():
template = "./pipe-lua-libpcap-match ../tests/data/wingolog.pcap \"%s\" 1"
ethers = ["ether[1]", "ether[100]"]
tcps = ["tcp[1]", "tcp[100]"]
for e in ethers:
for t in tcps:
pflang = "tcp or %s > %s" % (e, t)
cmd = template % pflang
print(cmd)
subprocess.call(cmd, shell=True)
gen_and_run()
... aside from the ip cases.
Can we re-try with 2000 instead of 100 in all cases? As far as I understand it, the point is to determine the order between out-of-bounds access (assertions) and protocol checks (conditionals). Best to make sure that one of our offsets will definitely cause an OOB assertion, seems to me; and let's punt on the "or tcp" cases for now, just to narrow down the problem.
I was trying specifically on packet 1 (that's what the "1" at the end of all the command lines means, and why I explained the salient properties of packet 1), which is a 66-byte packet, so 100 is out of bounds. I absolutely agree that the point is to check out-of-bounds accesses here!
The 'or tcp' cases were a trivial check of whether the second clause was getting run (in the cases where the first clause should fail); they're not the main point. It takes an 'or' clause to easily observe the bug from the level of packet matching/not matching behaviour, so the 'or' clauses are mainly there to make the semantics of the first clause clearer.
I think our understanding of libpcap's semantics might need an upgrade, though. I remain utterly baffled by this segment of my previous post:
% ./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[100] or ip" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
% ./pipe-lua-libpcap-match ../tests/data/wingolog.pcap "ether[1] > tcp[100] or ip[1] >= 0" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
Extra fun: disabling libpcap's optimizer yields different results. At that point, libpcap decides not to bother to run the second clause after all.
% ./pipe-lua-libpcap-match -O0 ../tests/data/wingolog.pcap "ether[1] > tcp[100] or ip" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
% ./pipe-lua-libpcap-match -O0 ../tests/data/wingolog.pcap "ether[1] > tcp[100] or ip[1] >=0" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
Perhaps this is purely an issue of libpcap's optimizer. With optimizations disabled, this bug seems to disappear. Whether outofboundsclause or ip matches our sample packet or not sometimes depends on whether optimizations are enabled in libpcap.
./pipe-lua-libpcap-match ../tests/data/tcp-ack-66-bytes.pcap "ether[1] > tcp[100] or ip" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
./pipe-lua-libpcap-match -O0 ../tests/data/tcp-ack-66-bytes.pcap "ether[1] > tcp[100] or ip" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
Libpcap's behavior also depends on the details of the second clause. Here are more examples that make it unhappy.
% ./pipe-lua-libpcap-match ../tests/data/tcp-ack-66-bytes.pcap "ether[1] > tcp[100] or 1 == 1" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
% ./pipe-lua-libpcap-match ../tests/data/tcp-ack-66-bytes.pcap "ether[1] > tcp[100] or ip" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
% ./pipe-lua-libpcap-match ../tests/data/tcp-ack-66-bytes.pcap "ether[1] > tcp[100] or ip or tcp" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
% ./pipe-lua-libpcap-match ../tests/data/tcp-ack-66-bytes.pcap "ether[1] > tcp[100] or 3 >= 1" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
% ./pipe-lua-libpcap-match ../tests/data/tcp-ack-66-bytes.pcap "ether[1] > tcp[100] or not arp" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
And some examples that don't invoke inconsistent behavior in libpcap:
% ../../env pipe-lua-libpcap-match tcp-ack-66-bytes.pcap "ip[100] > ether[1] or tcp" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
% ../../env pipe-lua-libpcap-match tcp-ack-66-bytes.pcap "tcp[100] > ether[1] or ip[1] >= 0" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
Note the contrast between the second clause being tcp, or it being ip in this example; it's hard to argue that this difference in libpcap's behavior makes any sense:
selkie% ../../env pipe-lua-libpcap-match tcp-ack-66-bytes.pcap "ip[100] > ether[1] or tcp" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
selkie% ../../env pipe-lua-libpcap-match tcp-ack-66-bytes.pcap "ip[100] > ether[1] or ip" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
Changing the first clause to use tcp makes things marginally worse in this example - both second clauses show the bug.
% ../../env pipe-lua-libpcap-match tcp-ack-66-bytes.pcap "tcp[100] > ether[1] or ip" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
% ../../env pipe-lua-libpcap-match tcp-ack-66-bytes.pcap "tcp[100] > ether[1] or tcp" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
Raw data
With optimizations enabled:
./pipe-lua-libpcap-match ../tests/data/tcp-ack-66-bytes.pcap "ether[1] > tcp[1] or ip" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
./pipe-lua-libpcap-match ../tests/data/tcp-ack-66-bytes.pcap "ether[1] > tcp[1] or ip[1] >= 0" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
./pipe-lua-libpcap-match ../tests/data/tcp-ack-66-bytes.pcap "ether[1] > tcp[100] or ip" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
./pipe-lua-libpcap-match ../tests/data/tcp-ack-66-bytes.pcap "ether[1] > tcp[100] or ip[1] >= 0" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/tcp-ack-66-bytes.pcap "ether[100] > tcp[1] or ip" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
./pipe-lua-libpcap-match ../tests/data/tcp-ack-66-bytes.pcap "ether[100] > tcp[1] or ip[1] >= 0" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match ../tests/data/tcp-ack-66-bytes.pcap "ether[100] > tcp[100] or ip" 1
BUG: pure-lua false, bpf-lua true, libpcap true.
./pipe-lua-libpcap-match ../tests/data/tcp-ack-66-bytes.pcap "ether[100] > tcp[100] or ip[1] >= 0" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
With optimizations disabled:
./pipe-lua-libpcap-match -O0 ../tests/data/tcp-ack-66-bytes.pcap "ether[1] > tcp[1] or ip" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
./pipe-lua-libpcap-match -O0 ../tests/data/tcp-ack-66-bytes.pcap "ether[1] > tcp[1] or ip[1] >= 0" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all true
./pipe-lua-libpcap-match -O0 ../tests/data/tcp-ack-66-bytes.pcap "ether[1] > tcp[100] or ip" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match -O0 ../tests/data/tcp-ack-66-bytes.pcap "ether[1] > tcp[100] or ip[1] >= 0" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match -O0 ../tests/data/tcp-ack-66-bytes.pcap "ether[100] > tcp[1] or ip" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match -O0 ../tests/data/tcp-ack-66-bytes.pcap "ether[100] > tcp[1] or ip[1] >= 0" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match -O0 ../tests/data/tcp-ack-66-bytes.pcap "ether[100] > tcp[100] or ip" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
./pipe-lua-libpcap-match -O0 ../tests/data/tcp-ack-66-bytes.pcap "ether[100] > tcp[100] or ip[1] >= 0" 1
OK: pure-lua, bfp-lua, and libpcap pipelines matched: all false
Oops - it turns out that most of my analysis on this bug actually pertained to libpcap: see the-tcpdump-group/libpcap#430 / . "arp[0] >= 0 or not arp" and its implications are unrelated to that, and still need to be fixed. Sorry for the clutter.
Bear in mind how this interacts with 'not':
% ./env tools/pipe-lua-libpcap-match tests/data/wingolog.pcap 'not igrp[1] >= 0' 1
BUG: pure-lua false, bpf-lua true, libpcap true.
The sample packet is not an igrp packet.