[PATCH net 0/2] bpf/verifier: fix bounds calculation on BPF_RSH

[PATCH net 0/2] bpf/verifier: fix bounds calculation on BPF_RSH

[Edward Cree]

Fix a bug in adjust_scalar_min_max_vals().  Since the bug has no effect (a
 later call to __reg_deduce_bounds() happens to mask it), it can't be
 tested for directly without adding extra debug prints; but add a test case
 to at least cover the relevant behaviour.

Edward Cree (2):
  bpf/verifier: fix bounds calculation on BPF_RSH
  selftests/bpf: Add a test for shifts of values that might be negative

 kernel/bpf/verifier.c                    | 30 ++++++++++++------------
 tools/testing/selftests/bpf/test_align.c | 39 ++++++++++++++++++++++++++++++++
 2 files changed, 55 insertions(+), 14 deletions(-)

[PATCH net 1/2] bpf/verifier: fix bounds calculation on BPF_RSH

[Edward Cree]

Incorrect signed bounds were being computed, although this had no effect
 since the propagation in __reg_deduce_bounds() happened to overwrite them.

Fixes: b03c9f9fdc37 ("bpf/verifier: track signed and unsigned min/max values")
Reported-by: Jann Horn <jannh@google.com>
Signed-off-by: Edward Cree <ecree@solarflare.com>
---
 kernel/bpf/verifier.c | 30 ++++++++++++++++--------------
 1 file changed, 16 insertions(+), 14 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index d4593571c404..5bed7f773c87 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2184,20 +2184,22 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 			mark_reg_unknown(env, regs, insn->dst_reg);
 			break;
 		}
-		/* BPF_RSH is an unsigned shift, so make the appropriate casts */
-		if (dst_reg->smin_value < 0) {
-			if (umin_val) {
-				/* Sign bit will be cleared */
-				dst_reg->smin_value = 0;
-			} else {
-				/* Lost sign bit information */
-				dst_reg->smin_value = S64_MIN;
-				dst_reg->smax_value = S64_MAX;
-			}
-		} else {
-			dst_reg->smin_value =
-				(u64)(dst_reg->smin_value) >> umax_val;
-		}
+		/* BPF_RSH is an unsigned shift.  If the value in dst_reg might
+		 * be negative, then either:
+		 * 1) src_reg might be zero, so the sign bit of the result is
+		 *    unknown, so we lose our signed bounds
+		 * 2) it's known negative, thus the unsigned bounds capture the
+		 *    signed bounds
+		 * 3) the signed bounds cross zero, so they tell us nothing
+		 *    about the result
+		 * If the value in dst_reg is known nonnegative, then again the
+		 * unsigned bounts capture the signed bounds.
+		 * Thus, in all cases it suffices to blow away our signed bounds
+		 * and rely on inferring new ones from the unsigned bounds and
+		 * var_off of the result.
+		 */
+		dst_reg->smin_value = S64_MIN;
+		dst_reg->smax_value = S64_MAX;
 		if (src_known)
 			dst_reg->var_off = tnum_rshift(dst_reg->var_off,
 						       umin_val);

[PATCH net 2/2] selftests/bpf: Add a test for shifts of values that might be negative

[Edward Cree]

Signed-off-by: Edward Cree <ecree@solarflare.com>
---
 tools/testing/selftests/bpf/test_align.c | 39 ++++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)

diff --git a/tools/testing/selftests/bpf/test_align.c b/tools/testing/selftests/bpf/test_align.c
index 8591c89c0828..24c6757b4c51 100644
--- a/tools/testing/selftests/bpf/test_align.c
+++ b/tools/testing/selftests/bpf/test_align.c
@@ -601,6 +601,45 @@ static struct bpf_align_test tests[] = {
 			{20, "R5=pkt(id=2,off=0,r=4,umin_value=2,umax_value=1082,var_off=(0x2; 0x7fc))"},
 		},
 	},
+	{
+		.descr = "unknown shift negative",
+		/* This isn't really a test of the alignment code, rather of the
+		 * signed min/max value handling, but it makes use of the
+		 * register-state-extracting code in do_test_single(), which
+		 * test_verifier.c doesn't have.
+		 */
+		.insns = {
+			LOAD_UNKNOWN(BPF_REG_3),
+			BPF_ALU64_IMM(BPF_SUB, BPF_REG_3, 0xff),
+			BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
+			LOAD_UNKNOWN(BPF_REG_4),
+			BPF_ALU64_IMM(BPF_SUB, BPF_REG_4, 0xff),
+			BPF_MOV64_REG(BPF_REG_5, BPF_REG_4),
+			BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
+			BPF_ALU64_IMM(BPF_SUB, BPF_REG_5, 1),
+			BPF_ALU64_IMM(BPF_RSH, BPF_REG_5, 1),
+			BPF_MOV64_IMM(BPF_REG_0, 0),
+			BPF_EXIT_INSN(),
+		},
+		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
+		.matches = {
+			{7, "R0=pkt(id=0,off=8,r=8,imm=0)"},
+			{7, "R3=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
+			{8, "R3=inv(id=0,smin_value=-255,smax_value=0)"},
+			/* All the verifier knows is, it's even.  While we could
+			 * conclude something tighter (the sign bit does not
+			 * change), the verifier doesn't bother right now.
+			 */
+			{9, "R3=inv(id=0,smax_value=9223372036854775806,umax_value=18446744073709551614,var_off=(0x0; 0xfffffffffffffffe))"},
+			{16, "R3=pkt_end(id=0,off=0,imm=0)"},
+			{16, "R4=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
+			{17, "R4=inv(id=0,smin_value=-255,smax_value=0)"},
+			/* both 0 and 0x7f...fff are possible */
+			{19, "R4=inv(id=0,umax_value=9223372036854775807,var_off=(0x0; 0x7fffffffffffffff))"},
+			{20, "R5=inv(id=0,umin_value=18446744073709551360,var_off=(0xffffffffffffff00; 0xff))"},
+			{21, "R5=inv(id=0,umin_value=9223372036854775680,umax_value=9223372036854775807,var_off=(0x7fffffffffffff80; 0x7f))"},
+		},
+	},
 };
 
 static int probe_filter_length(const struct bpf_insn *fp)

Re: [PATCH net 1/2] bpf/verifier: fix bounds calculation on BPF_RSH

[Jann Horn]

On Tue, Dec 5, 2017 at 8:15 PM, Edward Cree <ecree@solarflare.com> wrote:
> Incorrect signed bounds were being computed, although this had no effect
>  since the propagation in __reg_deduce_bounds() happened to overwrite them.
>
> Fixes: b03c9f9fdc37 ("bpf/verifier: track signed and unsigned min/max values")
> Reported-by: Jann Horn <jannh@google.com>
> Signed-off-by: Edward Cree <ecree@solarflare.com>
> ---
>  kernel/bpf/verifier.c | 30 ++++++++++++++++--------------
>  1 file changed, 16 insertions(+), 14 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index d4593571c404..5bed7f773c87 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -2184,20 +2184,22 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>                         mark_reg_unknown(env, regs, insn->dst_reg);
>                         break;
>                 }
> -               /* BPF_RSH is an unsigned shift, so make the appropriate casts */
> -               if (dst_reg->smin_value < 0) {
> -                       if (umin_val) {
> -                               /* Sign bit will be cleared */
> -                               dst_reg->smin_value = 0;
> -                       } else {
> -                               /* Lost sign bit information */
> -                               dst_reg->smin_value = S64_MIN;
> -                               dst_reg->smax_value = S64_MAX;
> -                       }
> -               } else {
> -                       dst_reg->smin_value =
> -                               (u64)(dst_reg->smin_value) >> umax_val;
> -               }
> +               /* BPF_RSH is an unsigned shift.  If the value in dst_reg might
> +                * be negative, then either:
> +                * 1) src_reg might be zero, so the sign bit of the result is
> +                *    unknown, so we lose our signed bounds
> +                * 2) it's known negative, thus the unsigned bounds capture the
> +                *    signed bounds
> +                * 3) the signed bounds cross zero, so they tell us nothing
> +                *    about the result
> +                * If the value in dst_reg is known nonnegative, then again the
> +                * unsigned bounts capture the signed bounds.
> +                * Thus, in all cases it suffices to blow away our signed bounds
> +                * and rely on inferring new ones from the unsigned bounds and
> +                * var_off of the result.
> +                */
> +               dst_reg->smin_value = S64_MIN;
> +               dst_reg->smax_value = S64_MAX;
>                 if (src_known)
>                         dst_reg->var_off = tnum_rshift(dst_reg->var_off,
>                                                        umin_val);
>

Reviewed-by: Jann Horn <jannh@google.com>

Re: [PATCH net 2/2] selftests/bpf: Add a test for shifts of values that might be negative

[Alexei Starovoitov]

On Tue, Dec 05, 2017 at 07:15:57PM +0000, Edward Cree wrote:
> Signed-off-by: Edward Cree <ecree@solarflare.com>
> ---
>  tools/testing/selftests/bpf/test_align.c | 39 ++++++++++++++++++++++++++++++++
>  1 file changed, 39 insertions(+)
> 
> diff --git a/tools/testing/selftests/bpf/test_align.c b/tools/testing/selftests/bpf/test_align.c
> index 8591c89c0828..24c6757b4c51 100644
> --- a/tools/testing/selftests/bpf/test_align.c
> +++ b/tools/testing/selftests/bpf/test_align.c
> @@ -601,6 +601,45 @@ static struct bpf_align_test tests[] = {
>  			{20, "R5=pkt(id=2,off=0,r=4,umin_value=2,umax_value=1082,var_off=(0x2; 0x7fc))"},
>  		},
>  	},
> +	{
> +		.descr = "unknown shift negative",
> +		/* This isn't really a test of the alignment code, rather of the
> +		 * signed min/max value handling, but it makes use of the
> +		 * register-state-extracting code in do_test_single(), which
> +		 * test_verifier.c doesn't have.
> +		 */
> +		.insns = {
> +			LOAD_UNKNOWN(BPF_REG_3),
> +			BPF_ALU64_IMM(BPF_SUB, BPF_REG_3, 0xff),
> +			BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
> +			LOAD_UNKNOWN(BPF_REG_4),
> +			BPF_ALU64_IMM(BPF_SUB, BPF_REG_4, 0xff),
> +			BPF_MOV64_REG(BPF_REG_5, BPF_REG_4),
> +			BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
> +			BPF_ALU64_IMM(BPF_SUB, BPF_REG_5, 1),
> +			BPF_ALU64_IMM(BPF_RSH, BPF_REG_5, 1),
> +			BPF_MOV64_IMM(BPF_REG_0, 0),
> +			BPF_EXIT_INSN(),
> +		},
> +		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
> +		.matches = {
> +			{7, "R0=pkt(id=0,off=8,r=8,imm=0)"},
> +			{7, "R3=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
> +			{8, "R3=inv(id=0,smin_value=-255,smax_value=0)"},
> +			/* All the verifier knows is, it's even.  While we could
> +			 * conclude something tighter (the sign bit does not
> +			 * change), the verifier doesn't bother right now.
> +			 */
> +			{9, "R3=inv(id=0,smax_value=9223372036854775806,umax_value=18446744073709551614,var_off=(0x0; 0xfffffffffffffffe))"},
> +			{16, "R3=pkt_end(id=0,off=0,imm=0)"},
> +			{16, "R4=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
> +			{17, "R4=inv(id=0,smin_value=-255,smax_value=0)"},
> +			/* both 0 and 0x7f...fff are possible */
> +			{19, "R4=inv(id=0,umax_value=9223372036854775807,var_off=(0x0; 0x7fffffffffffffff))"},
> +			{20, "R5=inv(id=0,umin_value=18446744073709551360,var_off=(0xffffffffffffff00; 0xff))"},
> +			{21, "R5=inv(id=0,umin_value=9223372036854775680,umax_value=9223372036854775807,var_off=(0x7fffffffffffff80; 0x7f))"},

hmm. it doesn't quite look right here and in this form it
already conflicts with net-next.
I would prefer to take only patch 1 into bpf->net and once
bpf->net->linus->net-next merge happens to add the test there.

Re: [PATCH net 1/2] bpf/verifier: fix bounds calculation on BPF_RSH

[Alexei Starovoitov]

On Tue, Dec 05, 2017 at 07:15:18PM +0000, Edward Cree wrote:
> Incorrect signed bounds were being computed, although this had no effect
>  since the propagation in __reg_deduce_bounds() happened to overwrite them.
> 
> Fixes: b03c9f9fdc37 ("bpf/verifier: track signed and unsigned min/max values")
> Reported-by: Jann Horn <jannh@google.com>
> Signed-off-by: Edward Cree <ecree@solarflare.com>

Acked-by: Alexei Starovoitov <ast@kernel.org>

Re: [PATCH net 1/2] bpf/verifier: fix bounds calculation on BPF_RSH

[Alexei Starovoitov]

On Tue, Dec 05, 2017 at 11:44:14AM -0800, Alexei Starovoitov wrote:
> On Tue, Dec 05, 2017 at 07:15:18PM +0000, Edward Cree wrote:
> > Incorrect signed bounds were being computed, although this had no effect
> >  since the propagation in __reg_deduce_bounds() happened to overwrite them.
> > 
> > Fixes: b03c9f9fdc37 ("bpf/verifier: track signed and unsigned min/max values")
> > Reported-by: Jann Horn <jannh@google.com>
> > Signed-off-by: Edward Cree <ecree@solarflare.com>
> 
> Acked-by: Alexei Starovoitov <ast@kernel.org>

turned out this one is incomplete fix. The more complete set
from Jann and Ed will be coming.