Out-of-bounds memory access in user-space BPF VM due to unsigned int overflow

[wingo]

To reproduce:

$ sudo /usr/sbin/tcpdump -i eth0 'ip[0xffffffee:4] == 0'

The BPF:

(000) ldh      [12]
(001) jeq      #0x800           jt 2    jf 5
(002) ld       [-4]
(003) jeq      #0x0             jt 4    jf 5
(004) ret      #262144
(005) ret      #0

Note that the resulting offset is 2**32 - 4.

Expected results: nothing prints, as the offset is not within the range of the packet

Actual results: depends on what's mapped at offset 2**32-4 from your packet start. On my system I don't get a crash but I do get passing packets. The reason is that the length check is performed against OFFSET + sizeof(int32), which overflows to 0.

Note that this vulnerability does not appear to affect the Linux kernel, as its range validation is different. The precise example above doesn't run on the kernel, because loading large constant offsets has special meaning to the kernel, and the constant is invalid, forcing the user-space VM to run. You can make the kernel try a similar codepath by making the offset a computed value. I wasn't able to cause a crash or unexpected passes, but I can't rule out the possibility of a vulnerability there.

[guyharris]

Note that OFFSET + sizeof(int32) overflows to 0 on an ILP32 platform but not an LP64 platform, and probably not even on an LLP64 platform (cf. WinPcap) as long as sizeof is 64-bit. In particular, with

tcpdump -O 'link[0xFFFFFFFC:4] != 0xf00ba4f'

I didn't see any packets on 64-bit OpenBSD but did see them on 32-bit OpenBSD. (This was capturing on a network device, so that's the kernel BPF. That's not our bug, but it's the same issue, so we want to report that issue to various uses of the in-kernel BPF engine as well, if they're not already checking whether the starting offset of the halfword or word being fetched is within the packet data.)

[guyharris]

For kernel BPFs, the -O is necessary because, without -O, it compiles to

(000) ld       [-4]
(001) jeq      #0xf00ba4f       jt 2    jf 3
(002) ret      #0
(003) ret      #65535

(yes, bpf_dump() needs to be fixed to print the offsets as signed; there's a bit of signed vs. unsigned cleanup to do on some kernel BPF interpreters as well), and the kernel's bpf_validate() rejects the first instruction, as the offset is bigger than the "maximum packet size" in the kernel's BPF interpreter, whereas, without -O, it compiles to

(000) ld       #0xfffffffc
(001) st       M[0]
(002) ldx      M[0]
(003) ld       [x + 0]
(004) st       M[1]
(005) ld       #0xf00ba4f
(006) st       M[2]
(007) ldx      M[2]
(008) ld       M[1]
(009) sub      x
(010) jeq      #0x0             jt 11   jf 12
(011) ret      #0
(012) ret      #65535

which contains nothing that bpf_validate() would reject, so the run-time range check for indexed loads needs to be fixed there.

The userland bpf_validate() doesn't do the check for a "maximum packet size". The "maximum packet size" for userland BPF is 2^32-1; that means that for "absolute" loads, userland bpf_validate() should check against 2^32-(size of the datum being loaded), which will cause the optimized program to be rejected.

However, we also need to make sure the indexed loads are checked correctly at run time in userland and all the kernel BPF interpreters. (The kernel's bpf_validate() also rejects offsets > the "maximum packet size" for those, which I guess is OK although it prevents loading stuff that precedes the current value of the X register, and also doesn't, as noted, obviate the need for run-time checks.)

[guyharris]

I've checked change 26a30758eb9c64bdb26e72b611418085e3a31e13 into the trunk; it makes the interpreter more like the FreeBSD interpreter, which does more bounds checking and catches this issue. Unless somebody finds a problem with it, I'll backport it to the 1.6 branch.

[fxlb]

After the change commited by Guy, any reason to keep this issue open?