propagate nullness information for reg to reg comparisons
Subsystems (4)
Eduard Zingerman
maintainercover propagate nullness information for reg to reg comparisons
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
Signature · 1 line
2.37.2
Eduard Zingerman
maintainerPATCH 1/2 bpf: propagate nullness information for reg to reg comparisons
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).
--- kernel/bpf/verifier.c | 41 +++++++++++++++++++++++++++++++++++++++-- 1 file changed, 39 insertions(+), 2 deletions(-)
kernel/bpf/verifier.c +39 -2
@@ -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.
Signature · 1 line
2.37.2
Daniel Borkmann
maintainerRe: [PATCH bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons
Quoted 7 lines · 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
[...]
Quoted 8 lines
kernel/bpf/verifier.c | 41 +++++++++++++++++++++++++++++++++++++++-- 1 file changed, 39 insertions(+), 2 deletions(-)kernel/bpf/verifier.c +0
-0
kernel/bpf/verifier.c static bool type_may_be_null(u32 type) · line 478
Quoted 7 lines
kernel/bpf/verifier.c +4
-0@@ -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.
Quoted 47 lines
kernel/bpf/verifier.c +24
-2static 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 */
kernel/bpf/verifier.c static int check_cond_jmp_op(struct bpf_verifier_env *env, · line 10262
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+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.
Quoted 4 lines
kernel/bpf/verifier.c +0
-0/* 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.
Eduard Zingerman
maintainerRe: [PATCH bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons
Hi Daniel,
Thank you for commenting.
Quoted 13 lines · Daniel Borkmann
[...]
Quoted 11 lines
kernel/bpf/verifier.c | 41 +++++++++++++++++++++++++++++++++++++++-- 1 file changed, 39 insertions(+), 2 deletions(-)kernel/bpf/verifier.c +0
-0@@ -472,6 +472,11 @@ static bool type_may_be_null(u32 type)return type &PTR_MAYBE_NULL ; }
Quoted 9 lines
kernel/bpf/verifier.c static bool type_may_be_null(u32 type) · line 478
Quoted 4 lines
kernel/bpf/verifier.c +4
-0+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?
[...]
Quoted 4 lines
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
Quoted 41 lines · Eduard Zingerman
Hi Daniel,
Thank you for commenting.
Quoted 13 lines · Daniel Borkmann
[...]
Quoted 11 lines
kernel/bpf/verifier.c | 41 +++++++++++++++++++++++++++++++++++++++-- 1 file changed, 39 insertions(+), 2 deletions(-)kernel/bpf/verifier.c +0
-0@@ -472,6 +472,11 @@ static bool type_may_be_null(u32 type)return type &PTR_MAYBE_NULL ; }Quoted 9 lines
kernel/bpf/verifier.c static bool type_may_be_null(u32 type) · line 478
Quoted 4 lines
kernel/bpf/verifier.c +4
-0+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;
Review
Quoted 3 lines
(quoted diff) +1
-1- 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.
Quoted 14 lines
And check if there are test cases that have to be added because of the change in the
__is_pointer_valuebehavior (it does not check forNOT_INITright now). Does this sound like a plan?[...]
Quoted 4 lines
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
Quoted 68 lines · Shung-Hsi Yu
Quoted 41 lines · Eduard Zingerman
Hi Daniel,
Thank you for commenting.
Quoted 13 lines · Daniel Borkmann
[...]
Quoted 11 lines
kernel/bpf/verifier.c | 41 +++++++++++++++++++++++++++++++++++++++-- 1 file changed, 39 insertions(+), 2 deletions(-)kernel/bpf/verifier.c +0
-0@@ -472,6 +472,11 @@ static bool type_may_be_null(u32 type)return type &PTR_MAYBE_NULL ; }Quoted 9 lines
kernel/bpf/verifier.c static bool type_may_be_null(u32 type) · line 478
Quoted 4 lines
kernel/bpf/verifier.c +4
-0+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;Review
Quoted 3 lines
(quoted diff) +1
-1- 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; ... } ... }
Quoted 3 lines
In the
check_mem_access()case the semantic ofis_pointer_value()is check whether or not the value *might* be a pointer, and sinceNON_INITcan 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.
Quoted 22 lines
Since the use case seems different, perhaps we could split them up, e.g. a
maybe_pointer_value()and ais_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.Quoted 14 lines
And check if there are test cases that have to be added because of the change in the
__is_pointer_valuebehavior (it does not check forNOT_INITright now). Does this sound like a plan?[...]
Quoted 4 lines
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
Eduard Zingerman
maintainerRe: [PATCH bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons
Quoted 76 lines · Shung-Hsi Yu
Quoted 68 lines · Shung-Hsi Yu
Quoted 41 lines · Eduard Zingerman
Hi Daniel,
Thank you for commenting.
Quoted 13 lines · Daniel Borkmann
[...]
Quoted 11 lines
kernel/bpf/verifier.c | 41 +++++++++++++++++++++++++++++++++++++++-- 1 file changed, 39 insertions(+), 2 deletions(-)kernel/bpf/verifier.c +0
-0@@ -472,6 +472,11 @@ static bool type_may_be_null(u32 type)return type &PTR_MAYBE_NULL ; }Quoted 9 lines
kernel/bpf/verifier.c static bool type_may_be_null(u32 type) · line 478
Quoted 4 lines
kernel/bpf/verifier.c +4
-0+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;Review
Quoted 3 lines
(quoted diff) +1
-1- 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; ... } ... }Quoted 3 lines
In the
check_mem_access()case the semantic ofis_pointer_value()is check whether or not the value *might* be a pointer, and sinceNON_INITcan 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.
Quoted 8 lines
Also, after going back to the previous RFC thread I saw John mention that after making the
is_pointer_value()changes to excludeNOT_INIT, the tests still passes.I guess that comes down to how the verifier rigorously check that the registers are not
NOT_INITusingcheck_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).
Quoted 13 lines
Quoted 13 lines
Since the use case seems different, perhaps we could split them up, e.g. a
maybe_pointer_value()and ais_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.Quoted 4 lines
And check if there are test cases that have to be added because of the change in the
__is_pointer_valuebehavior (it does not check forNOT_INITright now). Does this sound like a plan?
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
[...]
Quoted 4 lines
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, ®s[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
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Thanks,
Eduard
Eduard Zingerman
maintainerPATCH 2/2 selftests/bpf: check nullness propagation for reg to reg comparisons
In reply to Eduard ZingermanVerify that nullness information is porpagated in the branches of register to register JEQ and JNE operations.
--- .../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
tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c new file +166 -0
@@ -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, +},
Signature · 1 line
2.37.2
Re: [PATCH bpf-next 2/2] selftests/bpf: check nullness propagation for reg to reg comparisons
Quoted 10 lines · Eduard Zingerman
Verify that nullness information is porpagated in the branches of register to register JEQ and JNE operations.
Signed-off-by Eduard Zingerman <[email protected]>Acked-by Yonghong Song <[email protected]>--- .../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.
Eduard Zingerman
maintainerRe: [PATCH bpf-next 2/2] selftests/bpf: check nullness propagation for reg to reg comparisons
Quoted 5 lines · Alexei Starovoitov
Quoted 4 lines · Eduard Zingerman
Verify that nullness information is porpagated in the branches of register to register JEQ and JNE operations.
Quoted 8 lines
Quoted 6 lines
Signed-off-by Eduard Zingerman <[email protected]>Acked-by Yonghong Song <[email protected]>--- .../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.cThese 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
Quoted 2 lines
Pls fix and respin.
Re: [PATCH bpf-next 2/2] selftests/bpf: check nullness propagation for reg to reg comparisons
Quoted 45 lines · Eduard Zingerman
Quoted 5 lines · Alexei Starovoitov
Quoted 4 lines · Eduard Zingerman
Verify that nullness information is porpagated in the branches of register to register JEQ and JNE operations.
Quoted 8 lines
Quoted 6 lines
Signed-off-by Eduard Zingerman <[email protected]>Acked-by Yonghong Song <[email protected]>--- .../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.cThese 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 OKTo 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); }
Quoted 3 lines
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.