[PATCH v2 bpf-next 1/3] bpf: Fix propagation of bounds from 64-bit min/max into 32-bit and var_off.

From: Alexei Starovoitov <ast@kernel.org>

Before this fix:
166: (b5) if r2 <= 0x1 goto pc+22
from 166 to 189: R2=invP(id=1,umax_value=1,var_off=(0x0; 0xffffffff))

After this fix:
166: (b5) if r2 <= 0x1 goto pc+22
from 166 to 189: R2=invP(id=1,umax_value=1,var_off=(0x0; 0x1))

While processing BPF_JLE the reg_set_min_max() would set true_reg->umax_value = 1
and call __reg_combine_64_into_32(true_reg).

Without the fix it would not pass the condition:
if (__reg64_bound_u32(reg->umin_value) && __reg64_bound_u32(reg->umax_value))

since umin_value == 0 at this point.
Before commit 10bf4e83167c the umin was incorrectly ingored.
The commit 10bf4e83167c fixed the correctness issue, but pessimized
propagation of 64-bit min max into 32-bit min max and corresponding var_off.

Fixes: 10bf4e83167c ("bpf: Fix propagation of 32 bit unsigned bounds from 64 bit bounds")
Acked-by: Yonghong Song <redacted>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 kernel/bpf/verifier.c                               | 2 +-
 tools/testing/selftests/bpf/verifier/array_access.c | 2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 3c8aa7df1773..29671ed49ee8 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c

@@ -1425,7 +1425,7 @@ static bool __reg64_bound_s32(s64 a)
 
 static bool __reg64_bound_u32(u64 a)
 {
-	return a > U32_MIN && a < U32_MAX;
+	return a >= U32_MIN && a <= U32_MAX;
 }
 
 static void __reg_combine_64_into_32(struct bpf_reg_state *reg)

diff --git a/tools/testing/selftests/bpf/verifier/array_access.c b/tools/testing/selftests/bpf/verifier/array_access.c
index 1b1c798e9248..1b138cd2b187 100644
--- a/tools/testing/selftests/bpf/verifier/array_access.c
+++ b/tools/testing/selftests/bpf/verifier/array_access.c

@@ -186,7 +186,7 @@
 	},
 	.fixup_map_hash_48b = { 3 },
 	.errstr_unpriv = "R0 leaks addr",
-	.errstr = "R0 unbounded memory access",
+	.errstr = "invalid access to map value, value_size=48 off=44 size=8",
 	.result_unpriv = REJECT,
 	.result = REJECT,
 	.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,

-- 
2.30.2

From: Alexei Starovoitov <ast@kernel.org>

Similar to unsigned bounds propagation fix signed bounds.
The 'Fixes' tag is a hint. There is no security bug here.
The verifier was too conservative.

Fixes: 3f50f132d840 ("bpf: Verifier, do explicit ALU32 bounds tracking")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 kernel/bpf/verifier.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 29671ed49ee8..a4b48bd4e3ca 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c

@@ -1420,7 +1420,7 @@ static void __reg_combine_32_into_64(struct bpf_reg_state *reg)
 
 static bool __reg64_bound_s32(s64 a)
 {
-	return a > S32_MIN && a < S32_MAX;
+	return a >= S32_MIN && a <= S32_MAX;
 }
 
 static bool __reg64_bound_u32(u64 a)

-- 
2.30.2

From: Alexei Starovoitov <ast@kernel.org>

./test_progs-no_alu32 -vv -t twfw

Before the 64-bit_into_32-bit fix:
19: (25) if r1 > 0x3f goto pc+6
 R1_w=inv(id=0,umax_value=63,var_off=(0x0; 0xff),s32_max_value=255,u32_max_value=255)

and eventually:

invalid access to map value, value_size=8 off=7 size=8
R6 max value is outside of the allowed memory range
libbpf: failed to load object 'no_alu32/twfw.o'

After the fix:
19: (25) if r1 > 0x3f goto pc+6
 R1_w=inv(id=0,umax_value=63,var_off=(0x0; 0x3f))

verif_twfw:OK

Acked-by: Yonghong Song <redacted>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 .../bpf/prog_tests/bpf_verif_scale.c          |  5 ++
 tools/testing/selftests/bpf/progs/twfw.c      | 58 +++++++++++++++++++
 2 files changed, 63 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/twfw.c

diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
index 867349e4ed9e..27f5d8ea7964 100644
--- a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
+++ b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c

@@ -202,3 +202,8 @@ void test_verif_scale_seg6_loop()
 {
 	scale_test("test_seg6_loop.o", BPF_PROG_TYPE_LWT_SEG6LOCAL, false);
 }
+
+void test_verif_twfw()
+{
+	scale_test("twfw.o", BPF_PROG_TYPE_CGROUP_SKB, false);
+}

diff --git a/tools/testing/selftests/bpf/progs/twfw.c b/tools/testing/selftests/bpf/progs/twfw.c
new file mode 100644
index 000000000000..de1b18a62b46
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/twfw.c

@@ -0,0 +1,58 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2021 Facebook */
+#include <linux/types.h>
+#include <bpf/bpf_helpers.h>
+#include <linux/bpf.h>
+#include <stdint.h>
+
+#define TWFW_MAX_TIERS (64)
+/*
+ * load is successful
+ * #define TWFW_MAX_TIERS (64u)$
+ */
+
+struct twfw_tier_value {
+	unsigned long mask[1];
+};
+
+struct rule {
+	uint8_t seqnum;
+};
+
+struct rules_map {
+	__uint(type, BPF_MAP_TYPE_ARRAY);
+	__type(key, __u32);
+	__type(value, struct rule);
+	__uint(max_entries, 1);
+};
+
+struct tiers_map {
+	__uint(type, BPF_MAP_TYPE_ARRAY);
+	__type(key, __u32);
+	__type(value, struct twfw_tier_value);
+	__uint(max_entries, 1);
+};
+
+struct rules_map rules SEC(".maps");
+struct tiers_map tiers SEC(".maps");
+
+SEC("cgroup_skb/ingress")
+int twfw_verifier(struct __sk_buff* skb)
+{
+	const uint32_t key = 0;
+	const struct twfw_tier_value* tier = bpf_map_lookup_elem(&tiers, &key);
+	if (!tier)
+		return 1;
+
+	struct rule* rule = bpf_map_lookup_elem(&rules, &key);
+	if (!rule)
+		return 1;
+
+	if (rule && rule->seqnum < TWFW_MAX_TIERS) {
+		/* rule->seqnum / 64 should always be 0 */
+		unsigned long mask = tier->mask[rule->seqnum / 64];
+		if (mask)
+			return 0;
+	}
+	return 1;
+}

-- 
2.30.2

On 11/1/21 3:21 PM, Alexei Starovoitov wrote:

From: Alexei Starovoitov <ast@kernel.org>

Similar to unsigned bounds propagation fix signed bounds.
The 'Fixes' tag is a hint. There is no security bug here.
The verifier was too conservative.

Fixes: 3f50f132d840 ("bpf: Verifier, do explicit ALU32 bounds tracking")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>

The change looks good. Should a new test_verifier test be added
to exercise the new change?

On Mon, Nov 1, 2021 at 4:03 PM Yonghong Song [off-list ref] wrote:

On 11/1/21 3:21 PM, Alexei Starovoitov wrote:

quoted

From: Alexei Starovoitov <ast@kernel.org>

Similar to unsigned bounds propagation fix signed bounds.
The 'Fixes' tag is a hint. There is no security bug here.
The verifier was too conservative.

Fixes: 3f50f132d840 ("bpf: Verifier, do explicit ALU32 bounds tracking")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>

The change looks good. Should a new test_verifier test be added
to exercise the new change?

I think manually string comparing output the way VERBOSE_ACCEPT is doing
is an overkill here.
The real test case in .c will take some time to craft.

On 11/1/21 4:06 PM, Alexei Starovoitov wrote:

On Mon, Nov 1, 2021 at 4:03 PM Yonghong Song [off-list ref] wrote:

quoted

On 11/1/21 3:21 PM, Alexei Starovoitov wrote:

quoted

From: Alexei Starovoitov <ast@kernel.org>

Similar to unsigned bounds propagation fix signed bounds.
The 'Fixes' tag is a hint. There is no security bug here.
The verifier was too conservative.

Fixes: 3f50f132d840 ("bpf: Verifier, do explicit ALU32 bounds tracking")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>

The change looks good. Should a new test_verifier test be added
to exercise the new change?

I think manually string comparing output the way VERBOSE_ACCEPT is doing
is an overkill here.
The real test case in .c will take some time to craft.

Okay. Sounds good to me.

Acked-by: Yonghong Song <redacted>

Hello:

This series was applied to bpf/bpf-next.git (master)
by Andrii Nakryiko [off-list ref]:

On Mon,  1 Nov 2021 15:21:51 -0700 you wrote:

From: Alexei Starovoitov <ast@kernel.org>

Before this fix:
166: (b5) if r2 <= 0x1 goto pc+22
from 166 to 189: R2=invP(id=1,umax_value=1,var_off=(0x0; 0xffffffff))

After this fix:
166: (b5) if r2 <= 0x1 goto pc+22
from 166 to 189: R2=invP(id=1,umax_value=1,var_off=(0x0; 0x1))

[...]

Here is the summary with links:
  - [v2,bpf-next,1/3] bpf: Fix propagation of bounds from 64-bit min/max into 32-bit and var_off.
    https://git.kernel.org/bpf/bpf-next/c/b9979db83401
  - [v2,bpf-next,2/3] bpf: Fix propagation of signed bounds from 64-bit min/max into 32-bit.
    https://git.kernel.org/bpf/bpf-next/c/388e2c0b9783
  - [v2,bpf-next,3/3] selftests/bpf: Add a testcase for 64-bit bounds propagation issue.
    https://git.kernel.org/bpf/bpf-next/c/0869e5078afb

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html