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

[PATCH bpf-next v2 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>
---
 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 a5255a0dcbb6..243d06ce6842 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -11822,10 +11822,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: ef3911a3e4d65d2db617366e79517b896045a6e2
-- 
2.38.1

[PATCH bpf-next v2 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.

Signed-off-by: Hao Sun <sunhao.th@gmail.com>
Acked-by: Yonghong Song <yhs@fb.com>
---
 .../bpf/verifier/jeq_infer_not_null.c         | 22 +++++++++++++++++++
 1 file changed, 22 insertions(+)

diff --git a/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c b/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c
index 67a1c07ead34..b2b215227d97 100644
--- a/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c
+++ b/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c
@@ -172,3 +172,25 @@
 	.prog_type = BPF_PROG_TYPE_XDP,
 	.result = ACCEPT,
 },
+{
+	"jne/jeq infer not null, PTR_TO_MAP_OR_NULL unchanged with PTR_TO_BTF_ID reg",
+	.insns = {
+	BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+	BPF_ST_MEM(BPF_DW, BPF_REG_2, 0, 0),
+	BPF_LD_MAP_FD(BPF_REG_1, 0),
+	/* r6 = bpf_map->inner_map_meta; */
+	BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_1, 8),
+	/* r0 = map_lookup_elem(r1, r2); */
+	BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+	/* if (r0 == r6) read *r0; */
+	BPF_JMP_REG(BPF_JEQ, BPF_REG_6, BPF_REG_0, 1),
+	BPF_EXIT_INSN(),
+	BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.fixup_map_hash_8b = { 3 },
+	.prog_type = BPF_PROG_TYPE_XDP,
+	.result = REJECT,
+	.errstr = "R0 invalid mem access 'map_value_or_null'",
+},
-- 
2.38.1

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

[Martin KaFai Lau]

On 12/12/22 7:04 PM, Hao Sun wrote:
> 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.

Thanks for the fix and test.

> 
> Signed-off-by: Hao Sun <sunhao.th@gmail.com>
> Acked-by: Yonghong Song <yhs@fb.com>
> ---
>   .../bpf/verifier/jeq_infer_not_null.c         | 22 +++++++++++++++++++
>   1 file changed, 22 insertions(+)
> 
> diff --git a/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c b/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c
> index 67a1c07ead34..b2b215227d97 100644
> --- a/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c
> +++ b/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c
> @@ -172,3 +172,25 @@
>   	.prog_type = BPF_PROG_TYPE_XDP,
>   	.result = ACCEPT,
>   },
> +{
> +	"jne/jeq infer not null, PTR_TO_MAP_OR_NULL unchanged with PTR_TO_BTF_ID reg",
> +	.insns = {
> +	BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
> +	BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
> +	BPF_ST_MEM(BPF_DW, BPF_REG_2, 0, 0),
> +	BPF_LD_MAP_FD(BPF_REG_1, 0),
> +	/* r6 = bpf_map->inner_map_meta; */
> +	BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_1, 8),

This bpf_map->inner_map_meta requires CO-RE. It works now but could be fragile 
in different platform and in the future bpf_map changes. Take a look at the 
map_ptr_kern.c which uses "__attribute__((preserve_access_index))" at the 
"struct bpf_map".

Please translate this verifer test into a proper bpf prog in C code such that it 
can use the CO-RE in libbpf.  It should run under test_progs instead of 
test_verifier. The bpf prog can include the "vmlinux.h" to get the 
"__attribute__((preserve_access_index))" for free.  Take a look at 
https://lore.kernel.org/all/20221207201648.2990661-2-andrii@kernel.org/ which 
has example on how to check verifier message in test_progs.


> +	/* r0 = map_lookup_elem(r1, r2); */
> +	BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
> +	/* if (r0 == r6) read *r0; */
> +	BPF_JMP_REG(BPF_JEQ, BPF_REG_6, BPF_REG_0, 1),
> +	BPF_EXIT_INSN(),
> +	BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_0, 0),
> +	BPF_EXIT_INSN(),
> +	},
> +	.fixup_map_hash_8b = { 3 },
> +	.prog_type = BPF_PROG_TYPE_XDP,
> +	.result = REJECT,
> +	.errstr = "R0 invalid mem access 'map_value_or_null'",
> +},

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

[Hao Sun]

> On 20 Dec 2022, at 6:01 AM, Martin KaFai Lau <martin.lau@linux.dev> wrote:
> 
> On 12/12/22 7:04 PM, Hao Sun wrote:
>> 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.
> 
> Thanks for the fix and test.
> 
>> Signed-off-by: Hao Sun <sunhao.th@gmail.com>
>> Acked-by: Yonghong Song <yhs@fb.com>
>> ---
>>  .../bpf/verifier/jeq_infer_not_null.c         | 22 +++++++++++++++++++
>>  1 file changed, 22 insertions(+)
>> diff --git a/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c b/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c
>> index 67a1c07ead34..b2b215227d97 100644
>> --- a/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c
>> +++ b/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c
>> @@ -172,3 +172,25 @@
>>   .prog_type = BPF_PROG_TYPE_XDP,
>>   .result = ACCEPT,
>>  },
>> +{
>> + "jne/jeq infer not null, PTR_TO_MAP_OR_NULL unchanged with PTR_TO_BTF_ID reg",
>> + .insns = {
>> + BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
>> + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
>> + BPF_ST_MEM(BPF_DW, BPF_REG_2, 0, 0),
>> + BPF_LD_MAP_FD(BPF_REG_1, 0),
>> + /* r6 = bpf_map->inner_map_meta; */
>> + BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_1, 8),
> 
> This bpf_map->inner_map_meta requires CO-RE. It works now but could be fragile in different platform and in the future bpf_map changes. Take a look at the map_ptr_kern.c which uses "__attribute__((preserve_access_index))" at the "struct bpf_map".
> 
> Please translate this verifer test into a proper bpf prog in C code such that it can use the CO-RE in libbpf.  It should run under test_progs instead of test_verifier. The bpf prog can include the "vmlinux.h" to get the "__attribute__((preserve_access_index))" for free.  Take a look at https://lore.kernel.org/all/20221207201648.2990661-2-andrii@kernel.org/ which has example on how to check verifier message in test_progs.
> 

Sure, thanks for the hint, will send patch v3 soon.

Thanks
Hao

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

[Hao Sun]

> On 20 Dec 2022, at 6:01 AM, Martin KaFai Lau <martin.lau@linux.dev> wrote:
> 
> On 12/12/22 7:04 PM, Hao Sun wrote:
>> 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.
> 
> Thanks for the fix and test.
> 
>> Signed-off-by: Hao Sun <sunhao.th@gmail.com>
>> Acked-by: Yonghong Song <yhs@fb.com>
>> ---
>>  .../bpf/verifier/jeq_infer_not_null.c         | 22 +++++++++++++++++++
>>  1 file changed, 22 insertions(+)
>> diff --git a/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c b/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c
>> index 67a1c07ead34..b2b215227d97 100644
>> --- a/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c
>> +++ b/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c
>> @@ -172,3 +172,25 @@
>>   .prog_type = BPF_PROG_TYPE_XDP,
>>   .result = ACCEPT,
>>  },
>> +{
>> + "jne/jeq infer not null, PTR_TO_MAP_OR_NULL unchanged with PTR_TO_BTF_ID reg",
>> + .insns = {
>> + BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
>> + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
>> + BPF_ST_MEM(BPF_DW, BPF_REG_2, 0, 0),
>> + BPF_LD_MAP_FD(BPF_REG_1, 0),
>> + /* r6 = bpf_map->inner_map_meta; */
>> + BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_1, 8),
> 
> This bpf_map->inner_map_meta requires CO-RE. It works now but could be fragile in different platform and in the future bpf_map changes. Take a look at the map_ptr_kern.c which uses "__attribute__((preserve_access_index))" at the "struct bpf_map".
> 
> Please translate this verifer test into a proper bpf prog in C code such that it can use the CO-RE in libbpf.  It should run under test_progs instead of test_verifier. The bpf prog can include the "vmlinux.h" to get the "__attribute__((preserve_access_index))" for free.  Take a look at https://lore.kernel.org/all/20221207201648.2990661-2-andrii@kernel.org/ which has example on how to check verifier message in test_progs.
> 

Hi,

I’ve tried something like the bellow, but soon realized that this
won’t work because once compiler figures out `inner_map` equals
to `val`, it can choose either reg to write into in the following
path, meaning that this program can be rejected due to writing
into read-only PTR_TO_BTF_ID reg, and this makes the test useless.

Essentially, we want two regs, one points to PTR_TO_BTD_ID, one
points to MAP_VALUR_OR_NULL, then compare them and deref map val.
It’s hard to implement this in C level because compilers decide
which reg to use but not us, maybe we can just drop this test. 

thoughts? 
  
+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("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, reject because of invalid access
+	 * to map value.
+	 */
+	if (val == inner_map)
+		ret = *val;
+
+	return ret;
+}

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

[Martin KaFai Lau]

On 12/21/22 5:46 AM, Hao Sun wrote:
> Hi,
> 
> I’ve tried something like the bellow, but soon realized that this
> won’t work because once compiler figures out `inner_map` equals
> to `val`, it can choose either reg to write into in the following
> path, meaning that this program can be rejected due to writing
> into read-only PTR_TO_BTF_ID reg, and this makes the test useless.

hmm... I read the above a few times but I still don't quite get it.  In 
particular, '...can be rejected due to writing into read-only PTR_TO_BTF_ID 
reg...'.  Where is it writing into a read-only PTR_TO_BTF_ID reg in the 
following bpf prog?  Did I overlook something?

> 
> Essentially, we want two regs, one points to PTR_TO_BTD_ID, one
> points to MAP_VALUR_OR_NULL, then compare them and deref map val.

If I read this request correctly, I guess the compiler has changed 'ret = *val' 
to 'ret = *inner_map'?  Thus, the verifier did not reject because it deref a 
PTR_TO_BTF_ID?

> It’s hard to implement this in C level because compilers decide
> which reg to use but not us, maybe we can just drop this test.

Have you tried inline assembly.  Something like this (untested):

         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");

Please attach the verifier output in the future.  It will be easier to understand.

> 
> thoughts?
>    
> +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("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, reject because of invalid access
> +	 * to map value.
> +	 */
> +	if (val == inner_map)
> +		ret = *val;
> +
> +	return ret;
> +}

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

[Hao Sun]

Martin KaFai Lau <martin.lau@linux.dev> 于2022年12月22日周四 05:21写道：
>
> On 12/21/22 5:46 AM, Hao Sun wrote:
> > Hi,
> >
> > I’ve tried something like the bellow, but soon realized that this
> > won’t work because once compiler figures out `inner_map` equals
> > to `val`, it can choose either reg to write into in the following
> > path, meaning that this program can be rejected due to writing
> > into read-only PTR_TO_BTF_ID reg, and this makes the test useless.
>
> hmm... I read the above a few times but I still don't quite get it.  In
> particular, '...can be rejected due to writing into read-only PTR_TO_BTF_ID
> reg...'.  Where is it writing into a read-only PTR_TO_BTF_ID reg in the
> following bpf prog?  Did I overlook something?
>
> >
> > Essentially, we want two regs, one points to PTR_TO_BTD_ID, one
> > points to MAP_VALUR_OR_NULL, then compare them and deref map val.
>
> If I read this request correctly, I guess the compiler has changed 'ret = *val'
> to 'ret = *inner_map'?  Thus, the verifier did not reject because it deref a
> PTR_TO_BTF_ID?
>

Yes, and if we do "*val = 0", it's rejected due to writing to read-only
PTR_TO_BTF_ID reg.

> > It’s hard to implement this in C level because compilers decide
> > which reg to use but not us, maybe we can just drop this test.
>
> Have you tried inline assembly.  Something like this (untested):
>
>          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");
>

This would work, didn't realize that I can inline BPF insns this way.
Thanks!

> Please attach the verifier output in the future.  It will be easier to understand.
>

Will do the next time.