[bpf] bpf: fix verification of indirect var-off stack access

Commit Message

Andrei Matei Dec. 4, 2023, 1:01 a.m. UTC

This patch fixes a bug around the verification of possibly-zero-sized
stack accesses. When the access was done through a var-offset stack
pointer, check_stack_access_within_bounds was incorrectly computing the
maximum-offset of a zero-sized read to be the same as the register's min
offset. Instead, we have to take in account the register's maximum
possible value.

The bug was allowing accesses to erroneously pass the
check_stack_access_within_bounds() checks, only to later crash in
check_stack_range_initialized() when all the possibly-affected stack
slots are iterated (this time with a correct max offset).
check_stack_range_initialized() is relying on
check_stack_access_within_bounds() for its accesses to the
stack-tracking vector to be within bounds; in the case of zero-sized
accesses, we were essentially only verifying that the lowest possible
slot was within bounds. We would crash when the max-offset of the stack
pointer was >= 0 (which shouldn't pass verification, and hopefully is
not something anyone's code attempts to do in practice).

Thanks Hao for reporting!

Reported-by: Hao Sun <[e-mail]>
Fixes: 01f810ace9ed3 ("bpf: Allow variable-offset stack access")
Closes: https://lore.kernel.org/bpf/CACkBjsZGEUaRCHsmaX=[e-mail]/
Signed-off-by: Andrei Matei <[e-mail]>
---
 kernel/bpf/verifier.c | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)

Comments

Andrei Matei Dec. 4, 2023, 1:09 a.m. UTC | #1

I'm fairly confused about the zero-access check done by check_mem_size_reg()
iff the access size register's lower bound is zero ([1]). Can someone kindly
explain what that's about; what does it add to the other
check_helper_mem_access() just below?
[1] https://github.com/torvalds/linux/blob/33cc938e65a98f1d29d0a18403dbbee050dcad9a/kernel/bpf/verifier.c#L7486-L7489

---
FWIW, I have a test reproducing the crash, below. Although we had a bug, it
seems to me too random of a test to add. But I can add it if reviewers think
so.


SEC("socket")
__description("xxx")
__success
__log_level(4)
__naked void xxx(void)
{
asm volatile ("                     \
r0 = 0;                             \
*(u64*)(r10 - 16) = r0; \
*(u64*)(r10 - 8) = r0; \
/* Get an unknown value */ \
r1 = *(u32*)(r1 + 0); \
r1 &= 64;         \
r1 += -16;         \
/* r1 is now anywhere in [-16,48)*/ \
r1 += r10;                          \
r2 = 0;                             \
r3 = 0;         \
call %[bpf_probe_read_kernel];      \
exit;         \
" :
: __imm(bpf_probe_read_kernel)
: __clobber_all);
}

On Sun, Dec 3, 2023 at 8:02 PM Andrei Matei <[e-mail]> wrote:
>
> This patch fixes a bug around the verification of possibly-zero-sized
> stack accesses. When the access was done through a var-offset stack
> pointer, check_stack_access_within_bounds was incorrectly computing the
> maximum-offset of a zero-sized read to be the same as the register's min
> offset. Instead, we have to take in account the register's maximum
> possible value.
>
> The bug was allowing accesses to erroneously pass the
> check_stack_access_within_bounds() checks, only to later crash in
> check_stack_range_initialized() when all the possibly-affected stack
> slots are iterated (this time with a correct max offset).
> check_stack_range_initialized() is relying on
> check_stack_access_within_bounds() for its accesses to the
> stack-tracking vector to be within bounds; in the case of zero-sized
> accesses, we were essentially only verifying that the lowest possible
> slot was within bounds. We would crash when the max-offset of the stack
> pointer was >= 0 (which shouldn't pass verification, and hopefully is
> not something anyone's code attempts to do in practice).
>
> Thanks Hao for reporting!
>
> Reported-by: Hao Sun <[e-mail]>
> Fixes: 01f810ace9ed3 ("bpf: Allow variable-offset stack access")
> Closes: https://lore.kernel.org/bpf/CACkBjsZGEUaRCHsmaX=[e-mail]/
> Signed-off-by: Andrei Matei <[e-mail]>
> ---
>  kernel/bpf/verifier.c | 5 +----
>  1 file changed, 1 insertion(+), 4 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index af2819d5c8ee..a428735d232e 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -6816,10 +6816,7 @@ static int check_stack_access_within_bounds(
>                         return -EACCES;
>                 }
>                 min_off = reg->smin_value + off;
> -               if (access_size > 0)
> -                       max_off = reg->smax_value + off + access_size - 1;
> -               else
> -                       max_off = min_off;
> +               max_off = reg->smax_value + off + access_size - 1;
>         }
>
>         err = check_stack_slot_within_bounds(min_off, state, type);
> --
> 2.40.1
>

Hao Sun Dec. 4, 2023, 10:28 a.m. UTC | #2

On Mon, Dec 4, 2023 at 2:02 AM Andrei Matei <[e-mail]> wrote:
> 
> This patch fixes a bug around the verification of possibly-zero-sized
> stack accesses. When the access was done through a var-offset stack
> pointer, check_stack_access_within_bounds was incorrectly computing the
> maximum-offset of a zero-sized read to be the same as the register's min
> offset. Instead, we have to take in account the register's maximum
> possible value.
> 
> The bug was allowing accesses to erroneously pass the
> check_stack_access_within_bounds() checks, only to later crash in
> check_stack_range_initialized() when all the possibly-affected stack
> slots are iterated (this time with a correct max offset).
> check_stack_range_initialized() is relying on
> check_stack_access_within_bounds() for its accesses to the
> stack-tracking vector to be within bounds; in the case of zero-sized
> accesses, we were essentially only verifying that the lowest possible
> slot was within bounds. We would crash when the max-offset of the stack
> pointer was >= 0 (which shouldn't pass verification, and hopefully is
> not something anyone's code attempts to do in practice).
> 
> Thanks Hao for reporting!
> 
> Reported-by: Hao Sun <[e-mail]>
> Fixes: 01f810ace9ed3 ("bpf: Allow variable-offset stack access")
> Closes: https://lore.kernel.org/bpf/CACkBjsZGEUaRCHsmaX=[e-mail]/
> Signed-off-by: Andrei Matei <[e-mail]>
> ---
> kernel/bpf/verifier.c | 5 +----
> 1 file changed, 1 insertion(+), 4 deletions(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index af2819d5c8ee..a428735d232e 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -6816,10 +6816,7 @@ static int check_stack_access_within_bounds(
>                        return -EACCES;
>                }
>                min_off = reg->smin_value + off;
> -               if (access_size > 0)
> -                       max_off = reg->smax_value + off + access_size - 1;
> -               else
> -                       max_off = min_off;
> +               max_off = reg->smax_value + off + access_size - 1;
>        }
> 
>        err = check_stack_slot_within_bounds(min_off, state, type);
> —

(Resend, forgot cc list)

Andrei, thanks for the quick fix! But with this fix, I suspect the
max_off would be incorrect when access_size is zero. We probably
should do something like this:

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 2a9d521b64f4..70d5201f7d08 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -6556,10 +6556,9 @@ static int check_stack_access_within_bounds(
 			return -EACCES;
 		}
 		min_off = reg->smin_value + off;
+		max_off = reg->smax_value + off;
 		if (access_size > 0)
-			max_off = reg->smax_value + off + access_size - 1;
-		else
-			max_off = min_off;
+			max_off += access_size - 1;
 	}
 
 	err = check_stack_slot_within_bounds(env, min_off, state, type);

Andrei Matei Dec. 4, 2023, 3:41 p.m. UTC | #3

[...]

>
> Andrei, thanks for the quick fix! But with this fix, I suspect the
> max_off would be incorrect when access_size is zero. We probably
> should do something like this:
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 2a9d521b64f4..70d5201f7d08 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -6556,10 +6556,9 @@ static int check_stack_access_within_bounds(
>                         return -EACCES;
>                 }
>                 min_off = reg->smin_value + off;
> +               max_off = reg->smax_value + off;
>                 if (access_size > 0)
> -                       max_off = reg->smax_value + off + access_size - 1;
> -               else
> -                       max_off = min_off;
> +                       max_off += access_size - 1;
>         }
>
>         err = check_stack_slot_within_bounds(env, min_off, state, type);
>

Indeed, thanks. Resent.

I would love to add a few words about what the intention and exact
semantics of checking a zero-sized access are, if anyone can explain
it. I'm wondering if it'd be better to massage the code such that the
smallest access to verify has size 1.

Patch

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index af2819d5c8ee..a428735d232e 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -6816,10 +6816,7 @@  static int check_stack_access_within_bounds(
 			return -EACCES;
 		}
 		min_off = reg->smin_value + off;
-		if (access_size > 0)
-			max_off = reg->smax_value + off + access_size - 1;
-		else
-			max_off = min_off;
+		max_off = reg->smax_value + off + access_size - 1;
 	}
 
 	err = check_stack_slot_within_bounds(min_off, state, type);