[PATCH] bpf: 32-bit RSH verification must truncate input before the ALU op

[PATCH] bpf: 32-bit RSH verification must truncate input before the ALU op

[Jann Horn]

When I wrote commit 468f6eafa6c4 ("bpf: fix 32-bit ALU op verification"), I
assumed that, in order to emulate 64-bit arithmetic with 32-bit logic, it
is sufficient to just truncate the output to 32 bits; and so I just moved
the register size coercion that used to be at the start of the function to
the end of the function.

That assumption is true for almost every op, but not for 32-bit right
shifts, because those can propagate information towards the least
significant bit. Fix it by always truncating inputs for 32-bit ops to 32
bits.

Also get rid of the coerce_reg_to_size() after the ALU op, since that has
no effect.

Fixes: 468f6eafa6c4 ("bpf: fix 32-bit ALU op verification")
Acked-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Jann Horn <jannh@google.com>
---
 kernel/bpf/verifier.c | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index bb07e74b34a2..465952a8e465 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2896,6 +2896,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 	u64 umin_val, umax_val;
 	u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32;
 
+	if (insn_bitness == 32) {
+		/* Relevant for 32-bit RSH: Information can propagate towards
+		 * LSB, so it isn't sufficient to only truncate the output to
+		 * 32 bits.
+		 */
+		coerce_reg_to_size(dst_reg, 4);
+		coerce_reg_to_size(&src_reg, 4);
+	}
+
 	smin_val = src_reg.smin_value;
 	smax_val = src_reg.smax_value;
 	umin_val = src_reg.umin_value;
@@ -3131,7 +3140,6 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 	if (BPF_CLASS(insn->code) != BPF_ALU64) {
 		/* 32-bit ALU ops are (32,32)->32 */
 		coerce_reg_to_size(dst_reg, 4);
-		coerce_reg_to_size(&src_reg, 4);
 	}
 
 	__reg_deduce_bounds(dst_reg);
-- 
2.19.0.605.g01d371f741-goog

Re: [PATCH] bpf: 32-bit RSH verification must truncate input before the ALU op

[Edward Cree]

On 05/10/18 17:17, Jann Horn wrote:
> When I wrote commit 468f6eafa6c4 ("bpf: fix 32-bit ALU op verification"), I
> assumed that, in order to emulate 64-bit arithmetic with 32-bit logic, it
> is sufficient to just truncate the output to 32 bits; and so I just moved
> the register size coercion that used to be at the start of the function to
> the end of the function.
>
> That assumption is true for almost every op, but not for 32-bit right
> shifts, because those can propagate information towards the least
> significant bit. Fix it by always truncating inputs for 32-bit ops to 32
> bits.
>
> Also get rid of the coerce_reg_to_size() after the ALU op, since that has
> no effect.
Might be worth saying something like "because src_reg is passed by value".
> Fixes: 468f6eafa6c4 ("bpf: fix 32-bit ALU op verification")
> Acked-by: Daniel Borkmann <daniel@iogearbox.net>
> Signed-off-by: Jann Horn <jannh@google.com>
> ---
Acked-by: Edward Cree <ecree@solarflare.com>
>  kernel/bpf/verifier.c | 10 +++++++++-
>  1 file changed, 9 insertions(+), 1 deletion(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index bb07e74b34a2..465952a8e465 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -2896,6 +2896,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>  	u64 umin_val, umax_val;
>  	u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32;
Incidentally, I don't see why this needs to be a u64 (rather than say a u8).

-Ed
>  
> +	if (insn_bitness == 32) {
> +		/* Relevant for 32-bit RSH: Information can propagate towards
> +		 * LSB, so it isn't sufficient to only truncate the output to
> +		 * 32 bits.
> +		 */
> +		coerce_reg_to_size(dst_reg, 4);
> +		coerce_reg_to_size(&src_reg, 4);
> +	}
> +
>  	smin_val = src_reg.smin_value;
>  	smax_val = src_reg.smax_value;
>  	umin_val = src_reg.umin_value;
> @@ -3131,7 +3140,6 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>  	if (BPF_CLASS(insn->code) != BPF_ALU64) {
>  		/* 32-bit ALU ops are (32,32)->32 */
>  		coerce_reg_to_size(dst_reg, 4);
> -		coerce_reg_to_size(&src_reg, 4);
>  	}
>  
>  	__reg_deduce_bounds(dst_reg);

Re: [PATCH] bpf: 32-bit RSH verification must truncate input before the ALU op

[Jann Horn]

On Fri, Oct 5, 2018 at 7:45 PM Edward Cree <ecree@solarflare.com> wrote:
> On 05/10/18 17:17, Jann Horn wrote:
> > When I wrote commit 468f6eafa6c4 ("bpf: fix 32-bit ALU op verification"), I
> > assumed that, in order to emulate 64-bit arithmetic with 32-bit logic, it
> > is sufficient to just truncate the output to 32 bits; and so I just moved
> > the register size coercion that used to be at the start of the function to
> > the end of the function.
> >
> > That assumption is true for almost every op, but not for 32-bit right
> > shifts, because those can propagate information towards the least
> > significant bit. Fix it by always truncating inputs for 32-bit ops to 32
> > bits.
> >
> > Also get rid of the coerce_reg_to_size() after the ALU op, since that has
> > no effect.
> Might be worth saying something like "because src_reg is passed by value".
> > Fixes: 468f6eafa6c4 ("bpf: fix 32-bit ALU op verification")
> > Acked-by: Daniel Borkmann <daniel@iogearbox.net>
> > Signed-off-by: Jann Horn <jannh@google.com>
> > ---
> Acked-by: Edward Cree <ecree@solarflare.com>
> >  kernel/bpf/verifier.c | 10 +++++++++-
> >  1 file changed, 9 insertions(+), 1 deletion(-)
> >
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index bb07e74b34a2..465952a8e465 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -2896,6 +2896,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
> >       u64 umin_val, umax_val;
> >       u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32;
> Incidentally, I don't see why this needs to be a u64 (rather than say a u8).

Yeah, the size of the integer doesn't really matter there... but it's
being compared against other u64 values further down, so I also don't
see a particular need to change it.

Re: [PATCH] bpf: 32-bit RSH verification must truncate input before the ALU op

[Daniel Borkmann]

On 10/05/2018 06:17 PM, Jann Horn wrote:
> When I wrote commit 468f6eafa6c4 ("bpf: fix 32-bit ALU op verification"), I
> assumed that, in order to emulate 64-bit arithmetic with 32-bit logic, it
> is sufficient to just truncate the output to 32 bits; and so I just moved
> the register size coercion that used to be at the start of the function to
> the end of the function.
> 
> That assumption is true for almost every op, but not for 32-bit right
> shifts, because those can propagate information towards the least
> significant bit. Fix it by always truncating inputs for 32-bit ops to 32
> bits.
> 
> Also get rid of the coerce_reg_to_size() after the ALU op, since that has
> no effect.
> 
> Fixes: 468f6eafa6c4 ("bpf: fix 32-bit ALU op verification")
> Acked-by: Daniel Borkmann <daniel@iogearbox.net>
> Signed-off-by: Jann Horn <jannh@google.com>

Applied to bpf, thanks Jann!