[PATCH bpf] bpf: Fix possible out of bound write in narrow load handling

[PATCH bpf] bpf: Fix possible out of bound write in narrow load handling

[Andrey Ignatov]

Fix a verifier bug found by smatch static checker in [0].

When narrow load is handled, one or two new instructions are added to
insn_buf array, but before it was only checked that

	cnt >= ARRAY_SIZE(insn_buf)

And it's safe to add a new instruction to insn_buf[cnt++] only once. The
second try will lead to out of bound write. And this is what can happen
if `shift` is set.

Fix it by making sure that if the BPF_RSH instruction has to be added in
addition to BPF_AND then there is enough space for two more instructions
in insn_buf.

The full report [0] is below:

kernel/bpf/verifier.c:12304 convert_ctx_accesses() warn: offset 'cnt' incremented past end of array
kernel/bpf/verifier.c:12311 convert_ctx_accesses() warn: offset 'cnt' incremented past end of array

kernel/bpf/verifier.c
    12282
    12283 			insn->off = off & ~(size_default - 1);
    12284 			insn->code = BPF_LDX | BPF_MEM | size_code;
    12285 		}
    12286
    12287 		target_size = 0;
    12288 		cnt = convert_ctx_access(type, insn, insn_buf, env->prog,
    12289 					 &target_size);
    12290 		if (cnt == 0 || cnt >= ARRAY_SIZE(insn_buf) ||
                                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^
Bounds check.

    12291 		    (ctx_field_size && !target_size)) {
    12292 			verbose(env, "bpf verifier is misconfigured\n");
    12293 			return -EINVAL;
    12294 		}
    12295
    12296 		if (is_narrower_load && size < target_size) {
    12297 			u8 shift = bpf_ctx_narrow_access_offset(
    12298 				off, size, size_default) * 8;
    12299 			if (ctx_field_size <= 4) {
    12300 				if (shift)
    12301 					insn_buf[cnt++] = BPF_ALU32_IMM(BPF_RSH,
                                                         ^^^^^
increment beyond end of array

    12302 									insn->dst_reg,
    12303 									shift);
--> 12304 				insn_buf[cnt++] = BPF_ALU32_IMM(BPF_AND, insn->dst_reg,
                                                 ^^^^^
out of bounds write

    12305 								(1 << size * 8) - 1);
    12306 			} else {
    12307 				if (shift)
    12308 					insn_buf[cnt++] = BPF_ALU64_IMM(BPF_RSH,
    12309 									insn->dst_reg,
    12310 									shift);
    12311 				insn_buf[cnt++] = BPF_ALU64_IMM(BPF_AND, insn->dst_reg,
                                        ^^^^^^^^^^^^^^^
Same.

    12312 								(1ULL << size * 8) - 1);
    12313 			}
    12314 		}
    12315
    12316 		new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
    12317 		if (!new_prog)
    12318 			return -ENOMEM;
    12319
    12320 		delta += cnt - 1;
    12321
    12322 		/* keep walking new program and skip insns we just inserted */
    12323 		env->prog = new_prog;
    12324 		insn      = new_prog->insnsi + i + delta;
    12325 	}
    12326
    12327 	return 0;
    12328 }

[0] https://lore.kernel.org/bpf/20210817050843.GA21456@kili/

Fixes: 46f53a65d2de ("bpf: Allow narrow loads with offset > 0")
Reported-by: Dan Carpenter <dan.carpenter@oracle.com>
Signed-off-by: Andrey Ignatov <rdna@fb.com>
---
 kernel/bpf/verifier.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 381d3d6f24bc..b991fb0a5da4 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -12004,6 +12004,10 @@ static int convert_ctx_accesses(struct bpf_verifier_env *env)
 		if (is_narrower_load && size < target_size) {
 			u8 shift = bpf_ctx_narrow_access_offset(
 				off, size, size_default) * 8;
+			if (shift && cnt + 1 >= ARRAY_SIZE(insn_buf)) {
+				verbose(env, "bpf verifier narrow ctx load misconfigured\n");
+				return -EINVAL;
+			}
 			if (ctx_field_size <= 4) {
 				if (shift)
 					insn_buf[cnt++] = BPF_ALU32_IMM(BPF_RSH,
-- 
2.30.2

Re: [PATCH bpf] bpf: Fix possible out of bound write in narrow load handling

[Daniel Borkmann]

On 8/19/21 12:11 AM, Andrey Ignatov wrote:
> Fix a verifier bug found by smatch static checker in [0].
> 
> When narrow load is handled, one or two new instructions are added to
> insn_buf array, but before it was only checked that
> 
> 	cnt >= ARRAY_SIZE(insn_buf)
> 
> And it's safe to add a new instruction to insn_buf[cnt++] only once. The
> second try will lead to out of bound write. And this is what can happen
> if `shift` is set.

Afaik, the insn_buf[] should always be large enough, could you add something to
the commit message of this fix whether this created an actual issue in practice
where we do oob overrun insn_buf[] (or whether it's 'only' the static checker
report ... from above paragraph I read you saw the former in practice)?

Thanks,
Daniel

Re: [PATCH bpf] bpf: Fix possible out of bound write in narrow load handling

[Andrey Ignatov]

Daniel Borkmann <daniel@iogearbox.net> [Wed, 2021-08-18 15:48 -0700]:
> On 8/19/21 12:11 AM, Andrey Ignatov wrote:
> > Fix a verifier bug found by smatch static checker in [0].
> > 
> > When narrow load is handled, one or two new instructions are added to
> > insn_buf array, but before it was only checked that
> > 
> > 	cnt >= ARRAY_SIZE(insn_buf)
> > 
> > And it's safe to add a new instruction to insn_buf[cnt++] only once. The
> > second try will lead to out of bound write. And this is what can happen
> > if `shift` is set.
> 
> Afaik, the insn_buf[] should always be large enough, could you add something to
> the commit message of this fix whether this created an actual issue in practice
> where we do oob overrun insn_buf[] (or whether it's 'only' the static checker
> report ... from above paragraph I read you saw the former in practice)?

It's 'only' the static checker report. I've never seen this problem in
practice.

I also have an impression that convert_ctx_accesses should not in
general (or should never?) return too many insn to hit insn_buf[] limit,
but it may not be trivial to check all scenarios so I can't say for
sure. That's why it makes sense to me to address the report.

Sure, I can add this info to the commit message in v2.

-- 
Andrey Ignatov