[PATCH] Inaccurate rejection conditions

[PATCH] Inaccurate rejection conditions

[Tao Lyu]

Signed-off-by: Tao Lyu <tao.lyu@epfl.ch>
---
 kernel/bpf/verifier.c | 1 +
 1 file changed, 1 insertion(+)

Hi,

I am sorry to bother you due to my confusion on constraints about stack writes.

1. When an instruction stores 64-bit values onto the stack with fixed offset and BPF_CAP only,
   the verifier marks the stack slot type as STACK_SPILL, no matter whether they are scalar or pointers.

2. Then, a store instruction with a **32-bit scalar value** on the same stack slot leads to a verification rejection.
   As it says, this might corrupt the stack pointer by asserting if the stack slot type is STACK_SPILL. 
   However, even if the stack slot type is STACK_SPILL, it might store a 64-bit scalar and not a stack pointer.
   IMHO, this "issue" might originate from the incomplete conditions in the check_stack_write_fixed_off() function below.
   It only checks if the stack slot is a spilled register but forgets to check if the spilled register type is a pointer.

 4479 static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
 ...
 4494     if (!env->allow_ptr_leaks &&
 4495         is_spilled_reg(&state->stack[spi]) &&
 4496         size != BPF_REG_SIZE) {
 4497         verbose(env, "attempt to corrupt spilled pointer on stack\n");
 4498         return -EACCES;
 4499     }
 ...
 4600 }

Below is an example bpf program, which stores a 64-bit and 32-bit immediate value on the same stack slot.
But the second one gets rejected due to the above.

0: R1=ctx() R10=fp0
; asm volatile ( @ repro.bpf.c:679
0: (7a) *(u64 *)(r10 -8) = 1          ; R10=fp0 fp-8_w=1
1: (62) *(u32 *)(r10 -8) = 1
attempt to corrupt spilled pointer on stack
processed 2 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0.

If my understanding is correct, then we can apply the attached patch.

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index de7813947981..65f7eb315e9c 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -4493,6 +4493,7 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
 	 */
 	if (!env->allow_ptr_leaks &&
 	    is_spilled_reg(&state->stack[spi]) &&
+	    state->stack[spi].spilled_ptr.type != SCALAR_VALUE &&
 	    size != BPF_REG_SIZE) {
 		verbose(env, "attempt to corrupt spilled pointer on stack\n");
 		return -EACCES;
-- 
2.25.1

Re: [PATCH] Inaccurate rejection conditions

[Andrii Nakryiko]

On Wed, Mar 20, 2024 at 5:28 AM Tao Lyu <tao.lyu@epfl.ch> wrote:
>
> Signed-off-by: Tao Lyu <tao.lyu@epfl.ch>
> ---
>  kernel/bpf/verifier.c | 1 +
>  1 file changed, 1 insertion(+)
>
> Hi,
>
> I am sorry to bother you due to my confusion on constraints about stack writes.
>
> 1. When an instruction stores 64-bit values onto the stack with fixed offset and BPF_CAP only,
>    the verifier marks the stack slot type as STACK_SPILL, no matter whether they are scalar or pointers.
>
> 2. Then, a store instruction with a **32-bit scalar value** on the same stack slot leads to a verification rejection.
>    As it says, this might corrupt the stack pointer by asserting if the stack slot type is STACK_SPILL.
>    However, even if the stack slot type is STACK_SPILL, it might store a 64-bit scalar and not a stack pointer.
>    IMHO, this "issue" might originate from the incomplete conditions in the check_stack_write_fixed_off() function below.
>    It only checks if the stack slot is a spilled register but forgets to check if the spilled register type is a pointer.
>
>  4479 static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
>  ...
>  4494     if (!env->allow_ptr_leaks &&
>  4495         is_spilled_reg(&state->stack[spi]) &&
>  4496         size != BPF_REG_SIZE) {
>  4497         verbose(env, "attempt to corrupt spilled pointer on stack\n");
>  4498         return -EACCES;
>  4499     }
>  ...
>  4600 }
>
> Below is an example bpf program, which stores a 64-bit and 32-bit immediate value on the same stack slot.
> But the second one gets rejected due to the above.
>
> 0: R1=ctx() R10=fp0
> ; asm volatile ( @ repro.bpf.c:679
> 0: (7a) *(u64 *)(r10 -8) = 1          ; R10=fp0 fp-8_w=1
> 1: (62) *(u32 *)(r10 -8) = 1
> attempt to corrupt spilled pointer on stack
> processed 2 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0.
>
> If my understanding is correct, then we can apply the attached patch.
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index de7813947981..65f7eb315e9c 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -4493,6 +4493,7 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
>          */
>         if (!env->allow_ptr_leaks &&
>             is_spilled_reg(&state->stack[spi]) &&
> +           state->stack[spi].spilled_ptr.type != SCALAR_VALUE &&

I think it's possible to easily convert PTR_TO_MEM kind of register to
SCALAR_VALUE through arithmetic operations, and so allowing to spill
SCALAR_VALUE to stack is basically just as dangerous as spilling
PTR_TO_MEM directly.

So it feels a bit dangerous to do this.

pw-bot: cr

>             size != BPF_REG_SIZE) {
>                 verbose(env, "attempt to corrupt spilled pointer on stack\n");
>                 return -EACCES;
> --
> 2.25.1
>

Re: [PATCH] Inaccurate rejection conditions

[Tao Lyu]

>>
>> Signed-off-by: Tao Lyu <tao.lyu@epfl.ch>
>> ---
>>  kernel/bpf/verifier.c | 1 +
>>  1 file changed, 1 insertion(+)
>>
>> Hi,
>>
>> I am sorry to bother you due to my confusion on constraints about stack writes.
>>
>> 1. When an instruction stores 64-bit values onto the stack with fixed offset and BPF_CAP only,
>>    the verifier marks the stack slot type as STACK_SPILL, no matter whether they are scalar or pointers.
>>
>> 2. Then, a store instruction with a **32-bit scalar value** on the same stack slot leads to a verification rejection.
>>    As it says, this might corrupt the stack pointer by asserting if the stack slot type is STACK_SPILL.
>>    However, even if the stack slot type is STACK_SPILL, it might store a 64-bit scalar and not a stack pointer.
>>    IMHO, this "issue" might originate from the incomplete conditions in the check_stack_write_fixed_off() function below.
>>    It only checks if the stack slot is a spilled register but forgets to check if the spilled register type is a pointer.
>>
>>  4479 static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
>>  ...
>>  4494     if (!env->allow_ptr_leaks &&
>>  4495         is_spilled_reg(&state->stack[spi]) &&
>>  4496         size != BPF_REG_SIZE) {
>>  4497         verbose(env, "attempt to corrupt spilled pointer on stack\n");
>>  4498         return -EACCES;
>>  4499     }
>>  ...
>>  4600 }
>>
>> Below is an example bpf program, which stores a 64-bit and 32-bit immediate value on the same stack slot.
>> But the second one gets rejected due to the above.
>>
>> 0: R1=ctx() R10=fp0
>> ; asm volatile ( @ repro.bpf.c:679
>> 0: (7a) *(u64 *)(r10 -8) = 1          ; R10=fp0 fp-8_w=1
>> 1: (62) *(u32 *)(r10 -8) = 1
>> attempt to corrupt spilled pointer on stack
>> processed 2 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0.
>>
>> If my understanding is correct, then we can apply the attached patch.
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index de7813947981..65f7eb315e9c 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -4493,6 +4493,7 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
>>          */
>>         if (!env->allow_ptr_leaks &&
>>             is_spilled_reg(&state->stack[spi]) &&
>> +           state->stack[spi].spilled_ptr.type != SCALAR_VALUE &&
>
> I think it's possible to easily convert PTR_TO_MEM kind of register to
> SCALAR_VALUE through arithmetic operations, and so allowing to spill
> SCALAR_VALUE to stack is basically just as dangerous as spilling
> PTR_TO_MEM directly.
>
> So it feels a bit dangerous to do this.

Hi Andrii, thanks for the reply.

I think you might misunderstand this issue.
Let me rephrase it below:

** The verifier should allow partially overwriting an 8-byte stack slot
that contains a spilled scalar instead of rejecting it,
as the example shows below.** 

0: R1=ctx() R10=fp0
; asm volatile ( @ repro.bpf.c:679
0: (7a) *(u64 *)(r10 -8) = 1          ; R10=fp0 fp-8_w=1
1: (62) *(u32 *)(r10 -8) = 1
attempt to corrupt spilled pointer on stack

In this case, it's about overwriting a spill of a 64-bit scalar 
with another scalar with a smaller size (e.g., 32-bit). 
Pointers are not related to this IIUC.

Thanks for your time again.

>
>>             size != BPF_REG_SIZE) {
>>                 verbose(env, "attempt to corrupt spilled pointer on stack\n");
>>                 return -EACCES;
>> --
>> 2.25.1
>>

Re: [PATCH] Inaccurate rejection conditions

[Andrii Nakryiko]

On Tue, Apr 2, 2024 at 12:05 PM Tao Lyu <tao.lyu@epfl.ch> wrote:
>
> >>
> >> Signed-off-by: Tao Lyu <tao.lyu@epfl.ch>
> >> ---
> >>  kernel/bpf/verifier.c | 1 +
> >>  1 file changed, 1 insertion(+)
> >>
> >> Hi,
> >>
> >> I am sorry to bother you due to my confusion on constraints about stack writes.
> >>
> >> 1. When an instruction stores 64-bit values onto the stack with fixed offset and BPF_CAP only,
> >>    the verifier marks the stack slot type as STACK_SPILL, no matter whether they are scalar or pointers.
> >>
> >> 2. Then, a store instruction with a **32-bit scalar value** on the same stack slot leads to a verification rejection.
> >>    As it says, this might corrupt the stack pointer by asserting if the stack slot type is STACK_SPILL.
> >>    However, even if the stack slot type is STACK_SPILL, it might store a 64-bit scalar and not a stack pointer.
> >>    IMHO, this "issue" might originate from the incomplete conditions in the check_stack_write_fixed_off() function below.
> >>    It only checks if the stack slot is a spilled register but forgets to check if the spilled register type is a pointer.
> >>
> >>  4479 static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
> >>  ...
> >>  4494     if (!env->allow_ptr_leaks &&
> >>  4495         is_spilled_reg(&state->stack[spi]) &&
> >>  4496         size != BPF_REG_SIZE) {
> >>  4497         verbose(env, "attempt to corrupt spilled pointer on stack\n");
> >>  4498         return -EACCES;
> >>  4499     }
> >>  ...
> >>  4600 }
> >>
> >> Below is an example bpf program, which stores a 64-bit and 32-bit immediate value on the same stack slot.
> >> But the second one gets rejected due to the above.
> >>
> >> 0: R1=ctx() R10=fp0
> >> ; asm volatile ( @ repro.bpf.c:679
> >> 0: (7a) *(u64 *)(r10 -8) = 1          ; R10=fp0 fp-8_w=1
> >> 1: (62) *(u32 *)(r10 -8) = 1
> >> attempt to corrupt spilled pointer on stack
> >> processed 2 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0.
> >>
> >> If my understanding is correct, then we can apply the attached patch.
> >>
> >> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> >> index de7813947981..65f7eb315e9c 100644
> >> --- a/kernel/bpf/verifier.c
> >> +++ b/kernel/bpf/verifier.c
> >> @@ -4493,6 +4493,7 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
> >>          */
> >>         if (!env->allow_ptr_leaks &&
> >>             is_spilled_reg(&state->stack[spi]) &&
> >> +           state->stack[spi].spilled_ptr.type != SCALAR_VALUE &&
> >
> > I think it's possible to easily convert PTR_TO_MEM kind of register to
> > SCALAR_VALUE through arithmetic operations, and so allowing to spill
> > SCALAR_VALUE to stack is basically just as dangerous as spilling
> > PTR_TO_MEM directly.
> >
> > So it feels a bit dangerous to do this.
>
> Hi Andrii, thanks for the reply.
>
> I think you might misunderstand this issue.
> Let me rephrase it below:
>
> ** The verifier should allow partially overwriting an 8-byte stack slot
> that contains a spilled scalar instead of rejecting it,
> as the example shows below.**
>
> 0: R1=ctx() R10=fp0
> ; asm volatile ( @ repro.bpf.c:679
> 0: (7a) *(u64 *)(r10 -8) = 1          ; R10=fp0 fp-8_w=1
> 1: (62) *(u32 *)(r10 -8) = 1
> attempt to corrupt spilled pointer on stack
>
> In this case, it's about overwriting a spill of a 64-bit scalar
> with another scalar with a smaller size (e.g., 32-bit).
> Pointers are not related to this IIUC.
>

Ah, you are right, I misunderstood the use case. From my perspective
what you propose makes sense. Please prepare an official patch with a
proper commit message and send it again to bpf@vger.kernel.org.

> Thanks for your time again.
>
> >
> >>             size != BPF_REG_SIZE) {
> >>                 verbose(env, "attempt to corrupt spilled pointer on stack\n");
> >>                 return -EACCES;
> >> --
> >> 2.25.1
> >>