[PATCH bpf-next 0/2] propagate nullness information for reg to reg comparisons

[PATCH bpf-next 0/2] propagate nullness information for reg to reg comparisons

[Eduard Zingerman]

Changes since RFC:
 - newly added if block in `check_cond_jmp_op` is moved down to keep
   `make_ptr_not_null_reg` actions together;
 - tests rewritten to have a single `r0 = 0; exit;` block.

Original message follows:

Hi Everyone,

This patchset adds ability to propagates nullness information for
branches of register to register equality compare instructions. The
following rules are used:
 - suppose register A maybe null
 - suppose register B is 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

E.g. for program like below:

  r6 = skb->sk;
  r7 = sk_fullsock(r6);
  r0 = sk_fullsock(r6);
  if (r0 == 0) return 0;    (a)
  if (r0 != r7) return 0;   (b)
  *r7->type;                (c)
  return 0;

It is safe to dereference r7 at point (c), because of (a) and (b).

The utility of this change came up while working on BPF CLang backend
issue [1]. Specifically, while debugging issue with selftest
`test_sk_lookup.c`. This test has the following structure:

    int access_ctx_sk(struct bpf_sk_lookup *ctx __CTX__)
    {
        struct bpf_sock *sk1 = NULL, *sk2 = NULL;
        ...
        sk1 = bpf_map_lookup_elem(&redir_map, &KEY_SERVER_A);
        if (!sk1)           // (a)
            goto out;
        ...
        if (ctx->sk != sk1) // (b)
            goto out;
        ...
        if (ctx->sk->family != AF_INET ||     // (c)
            ctx->sk->type != SOCK_STREAM ||
            ctx->sk->state != BPF_TCP_LISTEN)
            goto out;
            ...
    }

- at (a) `sk1` is checked to be not null;
- at (b) `ctx->sk` is verified to be equal to `sk1`;
- at (c) `ctx->sk` is accessed w/o nullness check.

Currently Global Value Numbering pass considers expressions `sk1` and
`ctx->sk` to be identical at point (c) and replaces `ctx->sk` with
`sk1` (not expressions themselves but corresponding SSA values).
Since `sk1` is known to be not null after (b) verifier allows
execution of the program.

However, such optimization is not guaranteed to happen. When it does
not happen verifier reports an error.

[1] https://reviews.llvm.org/D131633#3722231

Thanks,
Eduard

Eduard Zingerman (2):
  bpf: propagate nullness information for reg to reg comparisons
  selftests/bpf: check nullness propagation for reg to reg comparisons

 kernel/bpf/verifier.c                         |  41 ++++-
 .../bpf/verifier/jeq_infer_not_null.c         | 166 ++++++++++++++++++
 2 files changed, 205 insertions(+), 2 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c

-- 
2.37.2

[PATCH bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons

[Eduard Zingerman]

Propagate nullness information for branches of register to register
equality compare instructions. The following rules are used:
- suppose register A maybe null
- suppose register B is 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

E.g. for program like below:

  r6 = skb->sk;
  r7 = sk_fullsock(r6);
  r0 = sk_fullsock(r6);
  if (r0 == 0) return 0;    (a)
  if (r0 != r7) return 0;   (b)
  *r7->type;                (c)
  return 0;

It is safe to dereference r7 at point (c), because of (a) and (b).

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Acked-by: Yonghong Song <yhs@fb.com>
---
 kernel/bpf/verifier.c | 41 +++++++++++++++++++++++++++++++++++++++--
 1 file changed, 39 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 0194a36d0b36..7585288e035b 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -472,6 +472,11 @@ static bool type_may_be_null(u32 type)
 	return type & PTR_MAYBE_NULL;
 }
 
+static bool type_is_pointer(enum bpf_reg_type type)
+{
+	return type != NOT_INIT && type != SCALAR_VALUE;
+}
+
 static bool is_acquire_function(enum bpf_func_id func_id,
 				const struct bpf_map *map)
 {
@@ -10064,6 +10069,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
 	struct bpf_verifier_state *other_branch;
 	struct bpf_reg_state *regs = this_branch->frame[this_branch->curframe]->regs;
 	struct bpf_reg_state *dst_reg, *other_branch_regs, *src_reg = NULL;
+	struct bpf_reg_state *eq_branch_regs;
 	u8 opcode = BPF_OP(insn->code);
 	bool is_jmp32;
 	int pred = -1;
@@ -10173,8 +10179,8 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
 	/* detect if we are comparing against a constant value so we can adjust
 	 * our min/max values for our dst register.
 	 * this is only legit if both are scalars (or pointers to the same
-	 * object, I suppose, but we don't support that right now), because
-	 * otherwise the different base pointers mean the offsets aren't
+	 * object, I suppose, see the PTR_MAYBE_NULL related if block below),
+	 * because otherwise the different base pointers mean the offsets aren't
 	 * comparable.
 	 */
 	if (BPF_SRC(insn->code) == BPF_X) {
@@ -10223,6 +10229,37 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
 		find_equal_scalars(other_branch, &other_branch_regs[insn->dst_reg]);
 	}
 
+	/* if one pointer register is compared to another pointer
+	 * register check if PTR_MAYBE_NULL could be lifted.
+	 * E.g. register A - maybe null
+	 *      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.
+	 */
+	if (!is_jmp32 &&
+	    BPF_SRC(insn->code) == BPF_X &&
+	    type_is_pointer(src_reg->type) && type_is_pointer(dst_reg->type) &&
+	    type_may_be_null(src_reg->type) != type_may_be_null(dst_reg->type)) {
+		eq_branch_regs = NULL;
+		switch (opcode) {
+		case BPF_JEQ:
+			eq_branch_regs = other_branch_regs;
+			break;
+		case BPF_JNE:
+			eq_branch_regs = regs;
+			break;
+		default:
+			/* do nothing */
+			break;
+		}
+		if (eq_branch_regs) {
+			if (type_may_be_null(src_reg->type))
+				mark_ptr_not_null_reg(&eq_branch_regs[insn->src_reg]);
+			else
+				mark_ptr_not_null_reg(&eq_branch_regs[insn->dst_reg]);
+		}
+	}
+
 	/* detect if R == 0 where R is returned from bpf_map_lookup_elem().
 	 * NOTE: these optimizations below are related with pointer comparison
 	 *       which will never be JMP32.
-- 
2.37.2

[PATCH bpf-next 2/2] selftests/bpf: check nullness propagation for reg to reg comparisons

[Eduard Zingerman]

Verify that nullness information is porpagated in the branches of
register to register JEQ and JNE operations.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Acked-by: Yonghong Song <yhs@fb.com>
---
 .../bpf/verifier/jeq_infer_not_null.c         | 166 ++++++++++++++++++
 1 file changed, 166 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c

diff --git a/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c b/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c
new file mode 100644
index 000000000000..d73f6198d544
--- /dev/null
+++ b/tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c
@@ -0,0 +1,166 @@
+{
+	/* This is equivalent to the following program:
+	 *
+	 *   r6 = skb->sk;
+	 *   r7 = sk_fullsock(r6);
+	 *   r0 = sk_fullsock(r6);
+	 *   if (r0 == 0) return 0;    (a)
+	 *   if (r0 != r7) return 0;   (b)
+	 *   *r7->type;                (c)
+	 *   return 0;
+	 *
+	 * It is safe to dereference r7 at point (c), because of (a) and (b).
+	 * The test verifies that relation r0 == r7 is propagated from (b) to (c).
+	 */
+	"jne/jeq infer not null, PTR_TO_SOCKET_OR_NULL -> PTR_TO_SOCKET for JNE false branch",
+	.insns = {
+	/* r6 = skb->sk; */
+	BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_1, offsetof(struct __sk_buff, sk)),
+	/* if (r6 == 0) return 0; */
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_6, 0, 8),
+	/* r7 = sk_fullsock(skb); */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
+	BPF_EMIT_CALL(BPF_FUNC_sk_fullsock),
+	BPF_MOV64_REG(BPF_REG_7, BPF_REG_0),
+	/* r0 = sk_fullsock(skb); */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
+	BPF_EMIT_CALL(BPF_FUNC_sk_fullsock),
+	/* if (r0 == null) return 0; */
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
+	/* if (r0 == r7) r0 = *(r7->type); */
+	BPF_JMP_REG(BPF_JNE, BPF_REG_0, BPF_REG_7, 1), /* Use ! JNE ! */
+	BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_7, offsetof(struct bpf_sock, type)),
+	/* return 0 */
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.prog_type = BPF_PROG_TYPE_CGROUP_SKB,
+	.result = ACCEPT,
+},
+{
+	/* Same as above, but verify that another branch of JNE still
+	 * prohibits access to PTR_MAYBE_NULL.
+	 */
+	"jne/jeq infer not null, PTR_TO_SOCKET_OR_NULL unchanged for JNE true branch",
+	.insns = {
+	/* r6 = skb->sk */
+	BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_1, offsetof(struct __sk_buff, sk)),
+	/* if (r6 == 0) return 0; */
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_6, 0, 9),
+	/* r7 = sk_fullsock(skb); */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
+	BPF_EMIT_CALL(BPF_FUNC_sk_fullsock),
+	BPF_MOV64_REG(BPF_REG_7, BPF_REG_0),
+	/* r0 = sk_fullsock(skb); */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
+	BPF_EMIT_CALL(BPF_FUNC_sk_fullsock),
+	/* if (r0 == null) return 0; */
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 3),
+	/* if (r0 == r7) return 0; */
+	BPF_JMP_REG(BPF_JNE, BPF_REG_0, BPF_REG_7, 1), /* Use ! JNE ! */
+	BPF_JMP_IMM(BPF_JA, 0, 0, 1),
+	/* r0 = *(r7->type); */
+	BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_7, offsetof(struct bpf_sock, type)),
+	/* return 0 */
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.prog_type = BPF_PROG_TYPE_CGROUP_SKB,
+	.result = REJECT,
+	.errstr = "R7 invalid mem access 'sock_or_null'",
+},
+{
+	/* Same as a first test, but not null should be inferred for JEQ branch */
+	"jne/jeq infer not null, PTR_TO_SOCKET_OR_NULL -> PTR_TO_SOCKET for JEQ true branch",
+	.insns = {
+	/* r6 = skb->sk; */
+	BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_1, offsetof(struct __sk_buff, sk)),
+	/* if (r6 == null) return 0; */
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_6, 0, 9),
+	/* r7 = sk_fullsock(skb); */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
+	BPF_EMIT_CALL(BPF_FUNC_sk_fullsock),
+	BPF_MOV64_REG(BPF_REG_7, BPF_REG_0),
+	/* r0 = sk_fullsock(skb); */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
+	BPF_EMIT_CALL(BPF_FUNC_sk_fullsock),
+	/* if (r0 == null) return 0; */
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 3),
+	/* if (r0 != r7) return 0; */
+	BPF_JMP_REG(BPF_JEQ, BPF_REG_0, BPF_REG_7, 1), /* Use ! JEQ ! */
+	BPF_JMP_IMM(BPF_JA, 0, 0, 1),
+	/* r0 = *(r7->type); */
+	BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_7, offsetof(struct bpf_sock, type)),
+	/* return 0; */
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.prog_type = BPF_PROG_TYPE_CGROUP_SKB,
+	.result = ACCEPT,
+},
+{
+	/* Same as above, but verify that another branch of JNE still
+	 * prohibits access to PTR_MAYBE_NULL.
+	 */
+	"jne/jeq infer not null, PTR_TO_SOCKET_OR_NULL unchanged for JEQ false branch",
+	.insns = {
+	/* r6 = skb->sk; */
+	BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_1, offsetof(struct __sk_buff, sk)),
+	/* if (r6 == null) return 0; */
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_6, 0, 8),
+	/* r7 = sk_fullsock(skb); */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
+	BPF_EMIT_CALL(BPF_FUNC_sk_fullsock),
+	BPF_MOV64_REG(BPF_REG_7, BPF_REG_0),
+	/* r0 = sk_fullsock(skb); */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
+	BPF_EMIT_CALL(BPF_FUNC_sk_fullsock),
+	/* if (r0 == null) return 0; */
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
+	/* if (r0 != r7) r0 = *(r7->type); */
+	BPF_JMP_REG(BPF_JEQ, BPF_REG_0, BPF_REG_7, 1), /* Use ! JEQ ! */
+	BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_7, offsetof(struct bpf_sock, type)),
+	/* return 0; */
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.prog_type = BPF_PROG_TYPE_CGROUP_SKB,
+	.result = REJECT,
+	.errstr = "R7 invalid mem access 'sock_or_null'",
+},
+{
+	/* Maps are treated in a different branch of `mark_ptr_not_null_reg`,
+	 * so separate test for maps case.
+	 */
+	"jne/jeq infer not null, PTR_TO_MAP_VALUE_OR_NULL -> PTR_TO_MAP_VALUE",
+	.insns = {
+	/* r9 = &some stack to use as key */
+	BPF_ST_MEM(BPF_W, BPF_REG_10, -8, 0),
+	BPF_MOV64_REG(BPF_REG_9, BPF_REG_10),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_9, -8),
+	/* r8 = process local map */
+	BPF_LD_MAP_FD(BPF_REG_8, 0),
+	/* r6 = map_lookup_elem(r8, r9); */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_8),
+	BPF_MOV64_REG(BPF_REG_2, BPF_REG_9),
+	BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+	BPF_MOV64_REG(BPF_REG_6, BPF_REG_0),
+	/* r7 = map_lookup_elem(r8, r9); */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_8),
+	BPF_MOV64_REG(BPF_REG_2, BPF_REG_9),
+	BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+	BPF_MOV64_REG(BPF_REG_7, BPF_REG_0),
+	/* if (r6 == 0) return 0; */
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_6, 0, 2),
+	/* if (r6 != r7) return 0; */
+	BPF_JMP_REG(BPF_JNE, BPF_REG_6, BPF_REG_7, 1),
+	/* read *r7; */
+	BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_7, offsetof(struct bpf_xdp_sock, queue_id)),
+	/* return 0; */
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.fixup_map_xskmap = { 3 },
+	.prog_type = BPF_PROG_TYPE_XDP,
+	.result = ACCEPT,
+},
-- 
2.37.2

Re: [PATCH bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons

[Daniel Borkmann]

On 8/26/22 7:29 PM, Eduard Zingerman wrote:
> Propagate nullness information for branches of register to register
> equality compare instructions. The following rules are used:
> - suppose register A maybe null
> - suppose register B is 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
> 
[...]
>   kernel/bpf/verifier.c | 41 +++++++++++++++++++++++++++++++++++++++--
>   1 file changed, 39 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 0194a36d0b36..7585288e035b 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -472,6 +472,11 @@ static bool type_may_be_null(u32 type)
>   	return type & PTR_MAYBE_NULL;
>   }
>   
> +static bool type_is_pointer(enum bpf_reg_type type)
> +{
> +	return type != NOT_INIT && type != SCALAR_VALUE;
> +}

We also have is_pointer_value(), semantics there are a bit different (and mainly to
prevent leakage under unpriv), but I wonder if this can be refactored to accommodate
both. My worry is that if in future we extend one but not the other bugs might slip
in.

>   static bool is_acquire_function(enum bpf_func_id func_id,
>   				const struct bpf_map *map)
>   {
> @@ -10064,6 +10069,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
>   	struct bpf_verifier_state *other_branch;
>   	struct bpf_reg_state *regs = this_branch->frame[this_branch->curframe]->regs;
>   	struct bpf_reg_state *dst_reg, *other_branch_regs, *src_reg = NULL;
> +	struct bpf_reg_state *eq_branch_regs;
>   	u8 opcode = BPF_OP(insn->code);
>   	bool is_jmp32;
>   	int pred = -1;
> @@ -10173,8 +10179,8 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
>   	/* detect if we are comparing against a constant value so we can adjust
>   	 * our min/max values for our dst register.
>   	 * this is only legit if both are scalars (or pointers to the same
> -	 * object, I suppose, but we don't support that right now), because
> -	 * otherwise the different base pointers mean the offsets aren't
> +	 * object, I suppose, see the PTR_MAYBE_NULL related if block below),
> +	 * because otherwise the different base pointers mean the offsets aren't
>   	 * comparable.
>   	 */
>   	if (BPF_SRC(insn->code) == BPF_X) {
> @@ -10223,6 +10229,37 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
>   		find_equal_scalars(other_branch, &other_branch_regs[insn->dst_reg]);
>   	}
>   
> +	/* if one pointer register is compared to another pointer
> +	 * register check if PTR_MAYBE_NULL could be lifted.
> +	 * E.g. register A - maybe null
> +	 *      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.
> +	 */
> +	if (!is_jmp32 &&
> +	    BPF_SRC(insn->code) == BPF_X &&
> +	    type_is_pointer(src_reg->type) && type_is_pointer(dst_reg->type) &&
> +	    type_may_be_null(src_reg->type) != type_may_be_null(dst_reg->type)) {
> +		eq_branch_regs = NULL;
> +		switch (opcode) {
> +		case BPF_JEQ:
> +			eq_branch_regs = other_branch_regs;
> +			break;
> +		case BPF_JNE:
> +			eq_branch_regs = regs;
> +			break;
> +		default:
> +			/* do nothing */
> +			break;
> +		}
> +		if (eq_branch_regs) {
> +			if (type_may_be_null(src_reg->type))
> +				mark_ptr_not_null_reg(&eq_branch_regs[insn->src_reg]);
> +			else
> +				mark_ptr_not_null_reg(&eq_branch_regs[insn->dst_reg]);
> +		}
> +	}
> +

Could we consolidate the logic above with the one below which deals with R == 0 checks?
There are some similarities, e.g. !is_jmp32, both test for jeq/jne and while one is based
on K, the other one on X, though we could also add check X == 0 for below. Anyway, just
a though that it may be nice to consolidate the handling.

>   	/* detect if R == 0 where R is returned from bpf_map_lookup_elem().
>   	 * NOTE: these optimizations below are related with pointer comparison
>   	 *       which will never be JMP32.
> 

Re: [PATCH bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons

[Eduard Zingerman]

Hi Daniel,

Thank you for commenting.

> On Mon, 2022-08-29 at 16:23 +0200, Daniel Borkmann wrote:
> [...]
> >   kernel/bpf/verifier.c | 41 +++++++++++++++++++++++++++++++++++++++--
> >   1 file changed, 39 insertions(+), 2 deletions(-)
> > 
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 0194a36d0b36..7585288e035b 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -472,6 +472,11 @@ static bool type_may_be_null(u32 type)
> >   	return type & PTR_MAYBE_NULL;
> >   }
> >   
> > +static bool type_is_pointer(enum bpf_reg_type type)
> > +{
> > +	return type != NOT_INIT && type != SCALAR_VALUE;
> > +}
> 
> We also have is_pointer_value(), semantics there are a bit different (and mainly to
> prevent leakage under unpriv), but I wonder if this can be refactored to accommodate
> both. My worry is that if in future we extend one but not the other bugs might slip
> in.

John was concerned about this as well, guess I won't not dodging it :)
Suppose I do the following modification:

    static bool type_is_pointer(enum bpf_reg_type type)
    {
    	return type != NOT_INIT && type != SCALAR_VALUE;
    }
    
    static bool __is_pointer_value(bool allow_ptr_leaks,
    			       const struct bpf_reg_state *reg)
    {
    	if (allow_ptr_leaks)
    		return false;

-    	return reg->type != SCALAR_VALUE;
+    	return type_is_pointer(reg->type);
    }
    
And check if there are test cases that have to be added because of the
change in the __is_pointer_value behavior (it does not check for
`NOT_INIT` right now). Does this sound like a plan?

[...]
> Could we consolidate the logic above with the one below which deals with R == 0 checks?
> There are some similarities, e.g. !is_jmp32, both test for jeq/jne and while one is based
> on K, the other one on X, though we could also add check X == 0 for below. Anyway, just
> a though that it may be nice to consolidate the handling.

Ok, I will try to consolidate those.

Thanks,
Eduard

Re: [PATCH bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons

[Shung-Hsi Yu]

On Tue, Aug 30, 2022 at 01:41:28PM +0300, Eduard Zingerman wrote:
> Hi Daniel,
> 
> Thank you for commenting.
> 
> > On Mon, 2022-08-29 at 16:23 +0200, Daniel Borkmann wrote:
> > [...]
> > >   kernel/bpf/verifier.c | 41 +++++++++++++++++++++++++++++++++++++++--
> > >   1 file changed, 39 insertions(+), 2 deletions(-)
> > > 
> > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > index 0194a36d0b36..7585288e035b 100644
> > > --- a/kernel/bpf/verifier.c
> > > +++ b/kernel/bpf/verifier.c
> > > @@ -472,6 +472,11 @@ static bool type_may_be_null(u32 type)
> > >   	return type & PTR_MAYBE_NULL;
> > >   }
> > >   
> > > +static bool type_is_pointer(enum bpf_reg_type type)
> > > +{
> > > +	return type != NOT_INIT && type != SCALAR_VALUE;
> > > +}
> > 
> > We also have is_pointer_value(), semantics there are a bit different (and mainly to
> > prevent leakage under unpriv), but I wonder if this can be refactored to accommodate
> > both. My worry is that if in future we extend one but not the other bugs might slip
> > in.
> 
> John was concerned about this as well, guess I won't not dodging it :)
> Suppose I do the following modification:
> 
>     static bool type_is_pointer(enum bpf_reg_type type)
>     {
>     	return type != NOT_INIT && type != SCALAR_VALUE;
>     }
>     
>     static bool __is_pointer_value(bool allow_ptr_leaks,
>     			       const struct bpf_reg_state *reg)
>     {
>     	if (allow_ptr_leaks)
>     		return false;
> 
> -    	return reg->type != SCALAR_VALUE;
> +    	return type_is_pointer(reg->type);
>     }
     
The verifier is using the wrapped is_pointer_value() to guard against
pointer leak.

  static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regno,
  			    int off, int bpf_size, enum bpf_access_type t,
  			    int value_regno, bool strict_alignment_once)
  {
      ...
  	if (reg->type == PTR_TO_MAP_KEY) {
  		...
  	} else if (reg->type == PTR_TO_MAP_VALUE) {
  		struct bpf_map_value_off_desc *kptr_off_desc = NULL;
  
  		if (t == BPF_WRITE && value_regno >= 0 &&
  		    is_pointer_value(env, value_regno)) {
  			verbose(env, "R%d leaks addr into map\n", value_regno);
  			return -EACCES;
          ...
  	}
      ...
  }

In the check_mem_access() case the semantic of is_pointer_value() is check
whether or not the value *might* be a pointer, and since NON_INIT can be
potentially anything, it should not be excluded.

Since the use case seems different, perhaps we could split them up, e.g. a
maybe_pointer_value() and a is_pointer_value(), or something along that
line.

The former is equivalent to type != SCALAR_VALUE, and the latter equivalent
to type != NOT_INIT && type != SCALAR_VALUE. The latter can be used here for
implementing nullness propogation.

> And check if there are test cases that have to be added because of the
> change in the __is_pointer_value behavior (it does not check for
> `NOT_INIT` right now). Does this sound like a plan?
> 
> [...]
> > Could we consolidate the logic above with the one below which deals with R == 0 checks?
> > There are some similarities, e.g. !is_jmp32, both test for jeq/jne and while one is based
> > on K, the other one on X, though we could also add check X == 0 for below. Anyway, just
> > a though that it may be nice to consolidate the handling.
> 
> Ok, I will try to consolidate those.
> 
> Thanks,
> Eduard

Re: [PATCH bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons

[Shung-Hsi Yu]

On Thu, Sep 01, 2022 at 04:13:22PM +0800, Shung-Hsi Yu wrote:
> On Tue, Aug 30, 2022 at 01:41:28PM +0300, Eduard Zingerman wrote:
> > Hi Daniel,
> > 
> > Thank you for commenting.
> > 
> > > On Mon, 2022-08-29 at 16:23 +0200, Daniel Borkmann wrote:
> > > [...]
> > > >   kernel/bpf/verifier.c | 41 +++++++++++++++++++++++++++++++++++++++--
> > > >   1 file changed, 39 insertions(+), 2 deletions(-)
> > > > 
> > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > > index 0194a36d0b36..7585288e035b 100644
> > > > --- a/kernel/bpf/verifier.c
> > > > +++ b/kernel/bpf/verifier.c
> > > > @@ -472,6 +472,11 @@ static bool type_may_be_null(u32 type)
> > > >   	return type & PTR_MAYBE_NULL;
> > > >   }
> > > >   
> > > > +static bool type_is_pointer(enum bpf_reg_type type)
> > > > +{
> > > > +	return type != NOT_INIT && type != SCALAR_VALUE;
> > > > +}
> > > 
> > > We also have is_pointer_value(), semantics there are a bit different (and mainly to
> > > prevent leakage under unpriv), but I wonder if this can be refactored to accommodate
> > > both. My worry is that if in future we extend one but not the other bugs might slip
> > > in.
> > 
> > John was concerned about this as well, guess I won't not dodging it :)
> > Suppose I do the following modification:
> > 
> >     static bool type_is_pointer(enum bpf_reg_type type)
> >     {
> >     	return type != NOT_INIT && type != SCALAR_VALUE;
> >     }
> >     
> >     static bool __is_pointer_value(bool allow_ptr_leaks,
> >     			       const struct bpf_reg_state *reg)
> >     {
> >     	if (allow_ptr_leaks)
> >     		return false;
> > 
> > -    	return reg->type != SCALAR_VALUE;
> > +    	return type_is_pointer(reg->type);
> >     }
>      
> The verifier is using the wrapped is_pointer_value() to guard against
> pointer leak.
> 
>   static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regno,
>   			    int off, int bpf_size, enum bpf_access_type t,
>   			    int value_regno, bool strict_alignment_once)
>   {
>       ...
>   	if (reg->type == PTR_TO_MAP_KEY) {
>   		...
>   	} else if (reg->type == PTR_TO_MAP_VALUE) {
>   		struct bpf_map_value_off_desc *kptr_off_desc = NULL;
>   
>   		if (t == BPF_WRITE && value_regno >= 0 &&
>   		    is_pointer_value(env, value_regno)) {
>   			verbose(env, "R%d leaks addr into map\n", value_regno);
>   			return -EACCES;
>           ...
>   	}
>       ...
>   }
> 
> In the check_mem_access() case the semantic of is_pointer_value() is check
> whether or not the value *might* be a pointer, and since NON_INIT can be
> potentially anything, it should not be excluded.

I wasn't reading the threads carefully enough, apologies, just realized
Daniel had already mention the above point further up.

Also, after going back to the previous RFC thread I saw John mention that
after making the is_pointer_value() changes to exclude NOT_INIT, the tests
still passes.

I guess that comes down to how the verifier rigorously check that the
registers are not NOT_INIT using check_reg_arg(..., SRC_OP), before moving
on to more specific checks. So I'm a bit less sure about the split
{maybe,is}_pointer_value() approach proposed below now.

> Since the use case seems different, perhaps we could split them up, e.g. a
> maybe_pointer_value() and a is_pointer_value(), or something along that
> line.
> 
> The former is equivalent to type != SCALAR_VALUE, and the latter equivalent
> to type != NOT_INIT && type != SCALAR_VALUE. The latter can be used here for
> implementing nullness propogation.
> 
> > And check if there are test cases that have to be added because of the
> > change in the __is_pointer_value behavior (it does not check for
> > `NOT_INIT` right now). Does this sound like a plan?
> > 
> > [...]
> > > Could we consolidate the logic above with the one below which deals with R == 0 checks?
> > > There are some similarities, e.g. !is_jmp32, both test for jeq/jne and while one is based
> > > on K, the other one on X, though we could also add check X == 0 for below. Anyway, just
> > > a though that it may be nice to consolidate the handling.
> > 
> > Ok, I will try to consolidate those.
> > 
> > Thanks,
> > Eduard

Re: [PATCH bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons

[Eduard Zingerman]

On Thu, 2022-09-01 at 17:01 +0800, Shung-Hsi Yu wrote:
> On Thu, Sep 01, 2022 at 04:13:22PM +0800, Shung-Hsi Yu wrote:
> > On Tue, Aug 30, 2022 at 01:41:28PM +0300, Eduard Zingerman wrote:
> > > Hi Daniel,
> > > 
> > > Thank you for commenting.
> > > 
> > > > On Mon, 2022-08-29 at 16:23 +0200, Daniel Borkmann wrote:
> > > > [...]
> > > > >   kernel/bpf/verifier.c | 41 +++++++++++++++++++++++++++++++++++++++--
> > > > >   1 file changed, 39 insertions(+), 2 deletions(-)
> > > > > 
> > > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > > > index 0194a36d0b36..7585288e035b 100644
> > > > > --- a/kernel/bpf/verifier.c
> > > > > +++ b/kernel/bpf/verifier.c
> > > > > @@ -472,6 +472,11 @@ static bool type_may_be_null(u32 type)
> > > > >   	return type & PTR_MAYBE_NULL;
> > > > >   }
> > > > >   
> > > > > +static bool type_is_pointer(enum bpf_reg_type type)
> > > > > +{
> > > > > +	return type != NOT_INIT && type != SCALAR_VALUE;
> > > > > +}
> > > > 
> > > > We also have is_pointer_value(), semantics there are a bit different (and mainly to
> > > > prevent leakage under unpriv), but I wonder if this can be refactored to accommodate
> > > > both. My worry is that if in future we extend one but not the other bugs might slip
> > > > in.
> > > 
> > > John was concerned about this as well, guess I won't not dodging it :)
> > > Suppose I do the following modification:
> > > 
> > >     static bool type_is_pointer(enum bpf_reg_type type)
> > >     {
> > >     	return type != NOT_INIT && type != SCALAR_VALUE;
> > >     }
> > >     
> > >     static bool __is_pointer_value(bool allow_ptr_leaks,
> > >     			       const struct bpf_reg_state *reg)
> > >     {
> > >     	if (allow_ptr_leaks)
> > >     		return false;
> > > 
> > > -    	return reg->type != SCALAR_VALUE;
> > > +    	return type_is_pointer(reg->type);
> > >     }
> >      
> > The verifier is using the wrapped is_pointer_value() to guard against
> > pointer leak.
> > 
> >   static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regno,
> >   			    int off, int bpf_size, enum bpf_access_type t,
> >   			    int value_regno, bool strict_alignment_once)
> >   {
> >       ...
> >   	if (reg->type == PTR_TO_MAP_KEY) {
> >   		...
> >   	} else if (reg->type == PTR_TO_MAP_VALUE) {
> >   		struct bpf_map_value_off_desc *kptr_off_desc = NULL;
> >   
> >   		if (t == BPF_WRITE && value_regno >= 0 &&
> >   		    is_pointer_value(env, value_regno)) {
> >   			verbose(env, "R%d leaks addr into map\n", value_regno);
> >   			return -EACCES;
> >           ...
> >   	}
> >       ...
> >   }
> > 
> > In the check_mem_access() case the semantic of is_pointer_value() is check
> > whether or not the value *might* be a pointer, and since NON_INIT can be
> > potentially anything, it should not be excluded.
> 
> I wasn't reading the threads carefully enough, apologies, just realized
> Daniel had already mention the above point further up.
> 
> Also, after going back to the previous RFC thread I saw John mention that
> after making the is_pointer_value() changes to exclude NOT_INIT, the tests
> still passes.
> 
> I guess that comes down to how the verifier rigorously check that the
> registers are not NOT_INIT using check_reg_arg(..., SRC_OP), before moving
> on to more specific checks. So I'm a bit less sure about the split
> {maybe,is}_pointer_value() approach proposed below now.

Hi Shung-Hsi, Daniel,

Sorry for a long delay. I'd like to revive this small change.

Thank you for pointing out the part regarding rigorous checks and
check_reg_arg. I've examined all places where __is_pointer_value(...)
and is_pointer_value(...) are invoked in the verifier code and came to
the conclusion that NOT_INIT can never reach the __is_pointer_value.
I also double checked this by modifying __is_pointer_value as follows:

 static bool __is_pointer_value(bool allow_ptr_leaks,
			       const struct bpf_reg_state *reg)
 {
+	BUG_ON(reg->type == NOT_INIT);
 	...
 }

And running the BPF selftests. None triggered the BUG_ON condition.

The place where I use type_is_pointer in check_cond_jmp_op is after
the check_reg_arg(..., SRC_OP) for both src and dst registers. Thus I
want to delete the type_is_pointer function from the patch and use
__is_pointer_value(false, ...) instead (as NOT_INIT check was
unnecessary from the beginning).

> 
> > Since the use case seems different, perhaps we could split them up, e.g. a
> > maybe_pointer_value() and a is_pointer_value(), or something along that
> > line.
> > 
> > The former is equivalent to type != SCALAR_VALUE, and the latter equivalent
> > to type != NOT_INIT && type != SCALAR_VALUE. The latter can be used here for
> > implementing nullness propogation.
> > 
> > > And check if there are test cases that have to be added because of the
> > > change in the __is_pointer_value behavior (it does not check for
> > > `NOT_INIT` right now). Does this sound like a plan?
> > > 
> > > [...]
> > > > Could we consolidate the logic above with the one below which deals with R == 0 checks?
> > > > There are some similarities, e.g. !is_jmp32, both test for jeq/jne and while one is based
> > > > on K, the other one on X, though we could also add check X == 0 for below. Anyway, just
> > > > a though that it may be nice to consolidate the handling.
> > > 
> > > Ok, I will try to consolidate those.

After some contemplating I don't think that it would be good to
consolidate these two parts.

The part that I want to add merely propagates the nullness
information:

	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)) {
            // ... save non-null part for one of the regs ...
        }

However, the part that is already present is actually a pointer leak
check that exempts comparison with zero (and exemption for comparison
with zero is stated as goal of commit 1be7f75d1668 that added
is_pointer_value back in 2015):

	/* detect if R == 0 where R is returned from bpf_map_lookup_elem()...
	 */
	if (!is_jmp32 && BPF_SRC(insn->code) == BPF_K &&
	    insn->imm == 0 && (opcode == BPF_JEQ || opcode == BPF_JNE) &&
	    type_may_be_null(dst_reg->type)) {
		/* Mark all identical registers in each branch as either
		 * safe or unknown depending R == 0 or R != 0 conditional.
		 */
                // ...
	} else if (!try_match_pkt_pointers(insn, dst_reg, &regs[insn->src_reg],
					   this_branch, other_branch) &&
leak check -->	   is_pointer_value(env, insn->dst_reg)) {
		verbose(env, "R%d pointer comparison prohibited\n",
			insn->dst_reg);
		return -EACCES;
	}

Merging these conditionals would be confusing, imo.

If you don't have objections I will post the v2 removing
type_is_pointer from the patch.

Thanks,
Eduard

> > > 
> > > Thanks,
> > > Eduard

Re: [PATCH bpf-next 2/2] selftests/bpf: check nullness propagation for reg to reg comparisons

[Alexei Starovoitov]

On Fri, Aug 26, 2022 at 10:30 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> Verify that nullness information is porpagated in the branches of
> register to register JEQ and JNE operations.
>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> Acked-by: Yonghong Song <yhs@fb.com>
> ---
>  .../bpf/verifier/jeq_infer_not_null.c         | 166 ++++++++++++++++++
>  1 file changed, 166 insertions(+)
>  create mode 100644 tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c

These 4 new tests are failing in unpriv.

Pls fix and respin.

Re: [PATCH bpf-next 2/2] selftests/bpf: check nullness propagation for reg to reg comparisons

[Eduard Zingerman]

On Mon, 2022-11-14 at 10:01 -0800, Alexei Starovoitov wrote:
> On Fri, Aug 26, 2022 at 10:30 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > Verify that nullness information is porpagated in the branches of
> > register to register JEQ and JNE operations.
> > 
> > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > Acked-by: Yonghong Song <yhs@fb.com>
> > ---
> >  .../bpf/verifier/jeq_infer_not_null.c         | 166 ++++++++++++++++++
> >  1 file changed, 166 insertions(+)
> >  create mode 100644 tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c
> 
> These 4 new tests are failing in unpriv.

This is interesting. 'test_verifier' passed for me because of
kernel.unprivileged_bpf_disabled = 1 on my test VM.
But It also passed on CI ([1]) with the following log:

2022-11-06T21:15:53.2873411Z #686/u jne/jeq infer not null, PTR_TO_SOCKET_OR_NULL -> PTR_TO_SOCKET for JNE false branch SKIP
2022-11-06T21:15:53.2908232Z #686/p jne/jeq infer not null, PTR_TO_SOCKET_OR_NULL -> PTR_TO_SOCKET for JNE false branch OK

To skip or not to skip is decided by test_verifier.c:do_test:

		if (test_as_unpriv(test) && unpriv_disabled) {
			printf("#%d/u %s SKIP\n", i, test->descr);
			skips++;
		}

The 'test_as_unpriv(test)' is true for my tests because of the
.prog_type == BPF_PROG_TYPE_CGROUP_SKB.
'unpriv_disabled' is a global set by test_verifier.c:get_unpriv_disabled:

static void get_unpriv_disabled()
{
	char buf[2];
	FILE *fd;

	fd = fopen("/proc/sys/"UNPRIV_SYSCTL, "r");
        // ...
	if (fgets(buf, 2, fd) == buf && atoi(buf))
		unpriv_disabled = true;
	fclose(fd);
}

Might it be the case that CI configuration needs an update as below:
sysctl kernel.unprivileged_bpf_disabled=0
?

[1] https://github.com/kernel-patches/bpf/actions/runs/3405978658/jobs/5664441527

> 
> Pls fix and respin.

Re: [PATCH bpf-next 2/2] selftests/bpf: check nullness propagation for reg to reg comparisons

[Alexei Starovoitov]

On 11/15/22 12:31 PM, Eduard Zingerman wrote:
> On Mon, 2022-11-14 at 10:01 -0800, Alexei Starovoitov wrote:
>> On Fri, Aug 26, 2022 at 10:30 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>>>
>>> Verify that nullness information is porpagated in the branches of
>>> register to register JEQ and JNE operations.
>>>
>>> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
>>> Acked-by: Yonghong Song <yhs@fb.com>
>>> ---
>>>   .../bpf/verifier/jeq_infer_not_null.c         | 166 ++++++++++++++++++
>>>   1 file changed, 166 insertions(+)
>>>   create mode 100644 tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c
>>
>> These 4 new tests are failing in unpriv.
> 
> This is interesting. 'test_verifier' passed for me because of
> kernel.unprivileged_bpf_disabled = 1 on my test VM.
> But It also passed on CI ([1]) with the following log:
> 
> 2022-11-06T21:15:53.2873411Z #686/u jne/jeq infer not null, PTR_TO_SOCKET_OR_NULL -> PTR_TO_SOCKET for JNE false branch SKIP
> 2022-11-06T21:15:53.2908232Z #686/p jne/jeq infer not null, PTR_TO_SOCKET_OR_NULL -> PTR_TO_SOCKET for JNE false branch OK
> 
> To skip or not to skip is decided by test_verifier.c:do_test:
> 
> 		if (test_as_unpriv(test) && unpriv_disabled) {
> 			printf("#%d/u %s SKIP\n", i, test->descr);
> 			skips++;
> 		}
> 
> The 'test_as_unpriv(test)' is true for my tests because of the
> .prog_type == BPF_PROG_TYPE_CGROUP_SKB.
> 'unpriv_disabled' is a global set by test_verifier.c:get_unpriv_disabled:
> 
> static void get_unpriv_disabled()
> {
> 	char buf[2];
> 	FILE *fd;
> 
> 	fd = fopen("/proc/sys/"UNPRIV_SYSCTL, "r");
>          // ...
> 	if (fgets(buf, 2, fd) == buf && atoi(buf))
> 		unpriv_disabled = true;
> 	fclose(fd);
> }
> 
> Might it be the case that CI configuration needs an update as below:
> sysctl kernel.unprivileged_bpf_disabled=0
> ?

Yeah. Makes sense to enable unpriv in CI, since it's missing tests
in the current form.