[PATCH bpf-next v3 1/2] bpf: fix nullness propagation for reg to reg comparisons

[PATCH bpf-next v3 1/2] bpf: fix nullness propagation for reg to reg comparisons

[Hao Sun]

After befae75856ab, the verifier would propagate null information after
JEQ/JNE, e.g., if two pointers, one is maybe_null and the other is not,
the former would be marked as non-null in eq path. However, as comment
"PTR_TO_BTF_ID points to a kernel struct that does not need to be null
checked by the BPF program ... The verifier must keep this in mind and
can make no assumptions about null or non-null when doing branch ...".
If one pointer is maybe_null and the other is PTR_TO_BTF, the former is
incorrectly marked non-null. The following BPF prog can trigger a
null-ptr-deref, also see this report for more details[1]:

	0: (18) r1 = map_fd	        ; R1_w=map_ptr(ks=4, vs=4)
	2: (79) r6 = *(u64 *)(r1 +8)    ; R6_w=bpf_map->inner_map_data
					; R6 is PTR_TO_BTF_ID
					; equals to null at runtime
	3: (bf) r2 = r10
	4: (07) r2 += -4
	5: (62) *(u32 *)(r2 +0) = 0
	6: (85) call bpf_map_lookup_elem#1    ; R0_w=map_value_or_null
	7: (1d) if r6 == r0 goto pc+1
	8: (95) exit
	; from 7 to 9: R0=map_value R6=ptr_bpf_map
	9: (61) r0 = *(u32 *)(r0 +0)          ; null-ptr-deref
	10: (95) exit

So, make the verifier propagate nullness information for reg to reg
comparisons only if neither reg is PTR_TO_BTF_ID.

[1] https://lore.kernel.org/bpf/CACkBjsaFJwjC5oiw-1KXvcazywodwXo4zGYsRHwbr2gSG9WcSw@mail.gmail.com/T/#u

Fixes: befae75856ab4 ("bpf: propagate nullness information for reg to reg comparisons")
Signed-off-by: Hao Sun <sunhao.th@gmail.com>
Acked-by: Yonghong Song <yhs@fb.com>
---
v1 -> v2 add explanation comments above changes
v2 -> v3 rewrite selftests that run under test_progs to use CO-RE
---
 kernel/bpf/verifier.c | 9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index faa358b3d5d7..966d98bfdb60 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -11823,10 +11823,17 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
 	 *      register B - not null
 	 * for JNE A, B, ... - A is not null in the false branch;
 	 * for JEQ A, B, ... - A is not null in the true branch.
+	 *
+	 * Since PTR_TO_BTF_ID points to a kernel struct that does
+	 * not need to be null checked by the BPF program, i.e.,
+	 * could be null even without PTR_MAYBE_NULL marking, so
+	 * only propagate nullness when neither reg is that type.
 	 */
 	if (!is_jmp32 && BPF_SRC(insn->code) == BPF_X &&
 	    __is_pointer_value(false, src_reg) && __is_pointer_value(false, dst_reg) &&
-	    type_may_be_null(src_reg->type) != type_may_be_null(dst_reg->type)) {
+	    type_may_be_null(src_reg->type) != type_may_be_null(dst_reg->type) &&
+	    base_type(src_reg->type) != PTR_TO_BTF_ID &&
+	    base_type(dst_reg->type) != PTR_TO_BTF_ID) {
 		eq_branch_regs = NULL;
 		switch (opcode) {
 		case BPF_JEQ:

base-commit: 7b43df6c6ec38c9097420902a1c8165c4b25bf70
-- 
2.39.0

[PATCH bpf-next v3 2/2] selftests/bpf: check null propagation only neither reg is PTR_TO_BTF_ID

[Hao Sun]

Verify that nullness information is not porpagated in the branches
of register to register JEQ and JNE operations if one of them is
PTR_TO_BTF_ID. Implement this in C level so we can use CO-RE.

Signed-off-by: Hao Sun <sunhao.th@gmail.com>
Suggested-by: Martin KaFai Lau <martin.lau@kernel.org>
---
 .../bpf/prog_tests/jeq_infer_not_null.c       |  9 ++++
 .../bpf/progs/jeq_infer_not_null_fail.c       | 42 +++++++++++++++++++
 2 files changed, 51 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/jeq_infer_not_null.c
 create mode 100644 tools/testing/selftests/bpf/progs/jeq_infer_not_null_fail.c

diff --git a/tools/testing/selftests/bpf/prog_tests/jeq_infer_not_null.c b/tools/testing/selftests/bpf/prog_tests/jeq_infer_not_null.c
new file mode 100644
index 000000000000..3add34df5767
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/jeq_infer_not_null.c
@@ -0,0 +1,9 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <test_progs.h>
+#include "jeq_infer_not_null_fail.skel.h"
+
+void test_jeq_infer_not_null(void)
+{
+	RUN_TESTS(jeq_infer_not_null_fail);
+}
diff --git a/tools/testing/selftests/bpf/progs/jeq_infer_not_null_fail.c b/tools/testing/selftests/bpf/progs/jeq_infer_not_null_fail.c
new file mode 100644
index 000000000000..f46965053acb
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/jeq_infer_not_null_fail.c
@@ -0,0 +1,42 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include "vmlinux.h"
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+
+char _license[] SEC("license") = "GPL";
+
+struct {
+	__uint(type, BPF_MAP_TYPE_HASH);
+	__uint(max_entries, 1);
+	__type(key, u64);
+	__type(value, u64);
+} m_hash SEC(".maps");
+
+SEC("?raw_tp")
+__failure __msg("R8 invalid mem access 'map_value_or_null")
+int jeq_infer_not_null_ptr_to_btfid(void *ctx)
+{
+	struct bpf_map *map = (struct bpf_map *)&m_hash;
+	struct bpf_map *inner_map = map->inner_map_meta;
+	u64 key = 0, ret = 0, *val;
+
+	val = bpf_map_lookup_elem(map, &key);
+	/* Do not mark ptr as non-null if one of them is
+	 * PTR_TO_BTF_ID (R9), reject because of invalid
+	 * access to map value (R8).
+	 *
+	 * Here, we need to inline those insns to access
+	 * R8 directly, since compiler may use other reg
+	 * once it figures out val==inner_map.
+	 */
+	asm volatile("r8 = %[val];\n"
+		     "r9 = %[inner_map];\n"
+		     "if r8 != r9 goto +1;\n"
+		     "%[ret] = *(u64 *)(r8 +0);\n"
+		     : [ret] "+r"(ret)
+		     : [inner_map] "r"(inner_map), [val] "r"(val)
+		     : "r8", "r9");
+
+	return ret;
+}
-- 
2.39.0

Re: [PATCH bpf-next v3 1/2] bpf: fix nullness propagation for reg to reg comparisons

[patchwork-bot+netdevbpf]

Hello:

This series was applied to bpf/bpf.git (master)
by Martin KaFai Lau <martin.lau@kernel.org>:

On Thu, 22 Dec 2022 10:44:13 +0800 you wrote:
> After befae75856ab, the verifier would propagate null information after
> JEQ/JNE, e.g., if two pointers, one is maybe_null and the other is not,
> the former would be marked as non-null in eq path. However, as comment
> "PTR_TO_BTF_ID points to a kernel struct that does not need to be null
> checked by the BPF program ... The verifier must keep this in mind and
> can make no assumptions about null or non-null when doing branch ...".
> If one pointer is maybe_null and the other is PTR_TO_BTF, the former is
> incorrectly marked non-null. The following BPF prog can trigger a
> null-ptr-deref, also see this report for more details[1]:
> 
> [...]

Here is the summary with links:
  - [bpf-next,v3,1/2] bpf: fix nullness propagation for reg to reg comparisons
    https://git.kernel.org/bpf/bpf/c/8374bfd5a3c9
  - [bpf-next,v3,2/2] selftests/bpf: check null propagation only neither reg is PTR_TO_BTF_ID
    https://git.kernel.org/bpf/bpf/c/cedebd74cf38

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

Re: [PATCH bpf-next v3 1/2] bpf: fix nullness propagation for reg to reg comparisons

[Martin KaFai Lau]

On 12/21/22 6:44 PM, Hao Sun wrote:
> After befae75856ab, the verifier would propagate null information after
> JEQ/JNE, e.g., if two pointers, one is maybe_null and the other is not,
> the former would be marked as non-null in eq path. However, as comment
> "PTR_TO_BTF_ID points to a kernel struct that does not need to be null
> checked by the BPF program ... The verifier must keep this in mind and
> can make no assumptions about null or non-null when doing branch ...".
> If one pointer is maybe_null and the other is PTR_TO_BTF, the former is
> incorrectly marked non-null. The following BPF prog can trigger a
> null-ptr-deref, also see this report for more details[1]:
> 
> 	0: (18) r1 = map_fd	        ; R1_w=map_ptr(ks=4, vs=4)
> 	2: (79) r6 = *(u64 *)(r1 +8)    ; R6_w=bpf_map->inner_map_data
> 					; R6 is PTR_TO_BTF_ID
> 					; equals to null at runtime
> 	3: (bf) r2 = r10
> 	4: (07) r2 += -4
> 	5: (62) *(u32 *)(r2 +0) = 0
> 	6: (85) call bpf_map_lookup_elem#1    ; R0_w=map_value_or_null
> 	7: (1d) if r6 == r0 goto pc+1
> 	8: (95) exit
> 	; from 7 to 9: R0=map_value R6=ptr_bpf_map
> 	9: (61) r0 = *(u32 *)(r0 +0)          ; null-ptr-deref
> 	10: (95) exit
> 
> So, make the verifier propagate nullness information for reg to reg
> comparisons only if neither reg is PTR_TO_BTF_ID.
> 
> [1] https://lore.kernel.org/bpf/CACkBjsaFJwjC5oiw-1KXvcazywodwXo4zGYsRHwbr2gSG9WcSw@mail.gmail.com/T/#u
> 
> Fixes: befae75856ab4 ("bpf: propagate nullness information for reg to reg comparisons")
The "Fixes" tag has one more hex digit. I have corrected it and applied to the 
bpf tree.  Thanks.

Please run checkpatch.pl in the future:

WARNING: Please use correct Fixes: style 'Fixes: <12 chars of sha1> ("<title 
line>")' - ie: 'Fixes: befae75856ab ("bpf: propagate nullness information for 
reg to reg comparisons")'
#35:
Fixes: befae75856ab4 ("bpf: propagate nullness information for reg to reg 
comparisons")

Re: [PATCH bpf-next v3 1/2] bpf: fix nullness propagation for reg to reg comparisons

[Hao Sun]

Martin KaFai Lau <martin.lau@linux.dev> 于2022年12月23日周五 09:31写道：
>
> On 12/21/22 6:44 PM, Hao Sun wrote:
> > After befae75856ab, the verifier would propagate null information after
> > JEQ/JNE, e.g., if two pointers, one is maybe_null and the other is not,
> > the former would be marked as non-null in eq path. However, as comment
> > "PTR_TO_BTF_ID points to a kernel struct that does not need to be null
> > checked by the BPF program ... The verifier must keep this in mind and
> > can make no assumptions about null or non-null when doing branch ...".
> > If one pointer is maybe_null and the other is PTR_TO_BTF, the former is
> > incorrectly marked non-null. The following BPF prog can trigger a
> > null-ptr-deref, also see this report for more details[1]:
> >
> >       0: (18) r1 = map_fd             ; R1_w=map_ptr(ks=4, vs=4)
> >       2: (79) r6 = *(u64 *)(r1 +8)    ; R6_w=bpf_map->inner_map_data
> >                                       ; R6 is PTR_TO_BTF_ID
> >                                       ; equals to null at runtime
> >       3: (bf) r2 = r10
> >       4: (07) r2 += -4
> >       5: (62) *(u32 *)(r2 +0) = 0
> >       6: (85) call bpf_map_lookup_elem#1    ; R0_w=map_value_or_null
> >       7: (1d) if r6 == r0 goto pc+1
> >       8: (95) exit
> >       ; from 7 to 9: R0=map_value R6=ptr_bpf_map
> >       9: (61) r0 = *(u32 *)(r0 +0)          ; null-ptr-deref
> >       10: (95) exit
> >
> > So, make the verifier propagate nullness information for reg to reg
> > comparisons only if neither reg is PTR_TO_BTF_ID.
> >
> > [1] https://lore.kernel.org/bpf/CACkBjsaFJwjC5oiw-1KXvcazywodwXo4zGYsRHwbr2gSG9WcSw@mail.gmail.com/T/#u
> >
> > Fixes: befae75856ab4 ("bpf: propagate nullness information for reg to reg comparisons")
> The "Fixes" tag has one more hex digit. I have corrected it and applied to the
> bpf tree.  Thanks.
>
> Please run checkpatch.pl in the future:
>
> WARNING: Please use correct Fixes: style 'Fixes: <12 chars of sha1> ("<title
> line>")' - ie: 'Fixes: befae75856ab ("bpf: propagate nullness information for
> reg to reg comparisons")'
> #35:
> Fixes: befae75856ab4 ("bpf: propagate nullness information for reg to reg
> comparisons")
>

Noted, thanks!