Re: 4-year old off-by-two bug in the BPF verifier's boundary checks?

On 2021-11-09 13:34, Daniel Borkmann wrote:

Hi Maxim,

On 11/2/21 4:12 PM, Maxim Mikityanskiy wrote:

quoted

Hi guys,

I think I found cases where the BPF verifier mistakenly rejects valid 
BPF programs when doing pkt_end boundary checks, and the selftests for 
these cases test wrong things as well.

Daniel's commit fb2a311a31d3 ("bpf: fix off by one for range markings 
with L{T, E} patterns") [1] attempts to fix an off-by-one bug in 
boundary checks, but I think it shifts the index by 1 in a wrong 
direction, so instead of fixing, the bug becomes off-by-two.

A following commit b37242c773b2 ("bpf: add test cases to bpf selftests 
to cover all access tests") [2] adds unit tests to check the new 
behavior, but the tests look also wrong to me.

Let me analyze these two tests:

{
         "XDP pkt read, pkt_data' > pkt_end, good access",
         .insns = {
         BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, offsetof(struct 
xdp_md, data)),
         BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1,
                     offsetof(struct xdp_md, data_end)),
         BPF_MOV64_REG(BPF_REG_1, BPF_REG_2),
         BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 8),
         BPF_JMP_REG(BPF_JGT, BPF_REG_1, BPF_REG_3, 1),
         BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -8),
         BPF_MOV64_IMM(BPF_REG_0, 0),
         BPF_EXIT_INSN(),
         },
         .result = ACCEPT,
         .prog_type = BPF_PROG_TYPE_XDP,
         .flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
},

{
         "XDP pkt read, pkt_data' >= pkt_end, bad access 1",
         .insns = {
         BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, offsetof(struct 
xdp_md, data)),
         BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1,
                     offsetof(struct xdp_md, data_end)),
         BPF_MOV64_REG(BPF_REG_1, BPF_REG_2),
         BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 8),
         BPF_JMP_REG(BPF_JGE, BPF_REG_1, BPF_REG_3, 1),
         BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -8),
         BPF_MOV64_IMM(BPF_REG_0, 0),
         BPF_EXIT_INSN(),
         },
         .errstr = "R1 offset is outside of the packet",
         .result = REJECT,
         .prog_type = BPF_PROG_TYPE_XDP,
         .flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
},

The first program looks good both to me and the verifier: if data + 8 

quoted

data_end, we bail out, otherwise, if data + 8 <= data_end, we read 8 

bytes: [data; data+7].

The second program doesn't pass the verifier, and the test expects it 
to be rejected, but the program itself still looks fine to me: if data 
+ 8 >= data_end, we bail out, otherwise, if data + 8 < data_end, we 
read 8 bytes: [data; data+7], and this is fine, because data + 7 is 
for sure < data_end. The verifier considers data + 7 to be out of 
bounds, although both data + 7 and data + 8 are still valid offsets, 
hence the off-by-two bug.

Are my considerations valid, or am I stupidly missing anything?

Sorry for my late reply, bit too swamped lately. So we have the two 
variants:

   r2 = data;
   r2 += 8;
   if (r2 > data_end) goto <handle exception>
     <access okay>

   r2 = data;
   r2 += 8;
   if (r2 >= data_end) goto <handle exception>
     <access okay>

Technically, the first option is the more correct way to check, meaning, 
we have 8 bytes of
access in the <access okay> branch. The second one is overly pessimistic 
in that if r2 equals
data_end we bail out even though we wouldn't have to. So in that case 
<access okay> branch
would have 9 bytes for access since r2 with offset 8 is already < data_end.

Anyway, please send a fix and updated test cases. Thanks Maxim!

Just pinging with my status: I'm still on it, I returned from vacation 
and back to work, but I'm currently struggling with running the BPF 
selftests.

I'm using tools/testing/selftests/bpf/vmtest.sh, I've hit a few issues 
trying to make it work, especially the glibc version issue (I have glibc 
2.33 on my host, but the VM image has 2.32 and can't run binaries 
compiled on the host), for which I applied this workaround to build the 
test progs statically:

https://www.spinics.net/lists/bpf/msg41647.html

However, the test suite just hangs after:

...
+ /etc/rcS.d/S50-startup
./test_progs
[    1.639277] bpf_testmod: loading out-of-tree module taints kernel.
#1 align:OK
#2 atomic_bounds:OK
[    1.824515] tsc: Refined TSC clocksource calibration: 2399.983 MHz
[    1.826421] clocksource: tsc: mask: 0xffffffffffffffff max_cycles: 
0x22982765f14, max_idle_ns: 440795222551 ns
[    1.829486] clocksource: Switched to clocksource tsc
#3 atomics:OK
#4 attach_probe:OK
#5 autoload:OK
#6 bind_perm:OK
#7 bloom_filter_map:OK
#8 bpf_cookie:OK

Any hint would be much appreciated. I'm trying to do my debugging too.

Thanks,
Max