Verifier callback handling
Subsystems (4)
Kumar Kartikeya Dwivedi
maintainercover Verifier callback handling
Hi, these are fixes for issues I noticed while working on the callback code. It is an RFC because I would like to discuss how to fix one other problem, I have a rough idea but would like to discuss before working on it, since it isn't trivial. The conservative fix doesn't pass existing selftests.
It seems like the problem anticipated in [0] actually exists with all the current callback based loop helpers, in a different form. The main reason is that callback function is only explored as if it was executing once.
There are some example cases included in selftests to show the problem, and make sure we keep catching and rejecting them. Since callback which is loop body is only verified once, once the for_each helper returns the execution state from verifier's perspective is as if callback executed once, but ofcourse it may execute multiple times, unknowable statically.
Patch 1 fixes the case of acquiring and releasing references, unless I missed some corner case it seems to mostly work fine.
In the future when we have a case where a sycnhronous callback will only be executed once by a helper, we can improve this case by relaxing these restrictions, so transfer of references and verifying callback as if it executes only once can be done. For now, all in_callback_fn function get executed multiple times, hence that change is left for when it will be needed.
Now, the important part:
------------------------
The included selftest will fail/crash, as one fix is missing from the series. Whatever I tried so far wasn't backwards compatible with existing selftests (e.g. conservatively marking all reads as UNKNOWN, and all writes scrubbing stack slots). Some tests e.g. read skb pointer from ptr_to_stack passed to callback.
It is not clear to me what the correct fix would be to handle reads and writes from the stack inside callback function. If a stack slot is never touched inside the callback in any of the states, it should be safe to allow it to load spilled registers from caller's stack frame, even allowing precise scalars would be safe if they are read from untouched slots.
The idea I have is roughly:
In the first pass, verify as if callback is executing once. This is the same case as of now, this may e.g. load a spilled precise scalar, then overwrite it, so insns before the store doing overwrite verification consider register as precise. In reality, in later loop iterations though this assumption may be wrong.
For e.g.
int i = 1;
int arr[2] = {0};
bpf_loop(100, cb, &i, 0);
cb:
int i = *ctx; // seen as 1 func(*((int *)ctx - i)); // stack read ok, arr[1] *ctx = i + 1; // i is now 2
verification ends here, but this would start reading uninit stack in later iterations.
To fix this, we keep a bitmap of scratched slots for the stack in caller frame. Once we see BPF_EXIT, we do reverification of the callback, but this time mark _any_ register reading from slots that were scratched the first time around as mark_reg_unknown (i.e. not precise). Moreover, in the caller stack it will be marked STACK_MISC. It might not be able to track <8 byte writes but I guess that is fine (since that would require 512 bits instead of 64).
The big problem I can see in this is that the precise register guards another write in another branch that was not taken the first time around. In that case push_stack is not done to explore the other branch, and is_branch_taken is used to predict the outcome.
But: if this has to cause a problem, the precise reg guarding the branch must change its value (and that we can see if it is being from a scratched slot read), so by doing another pass we would get rid of this problem. I.e. one more pass would be needed after downgrading precise registers to unknown.
If I can get some hints for new ideas or feedback on whether this would be the correct approach, I can work on a proper fix for this case.
It seems like roughly the same approach will be required for open coded iteration mentioned in [0], so we might be able to kill two birds with one shot.
Thanks!
[0]: https://lore.kernel.org/bpf/[email protected]
Kumar Kartikeya Dwivedi (3):
bpf: Move bpf_loop and bpf_for_each_map_elem under CAP_BPF
bpf: Fix reference state management for synchronous callbacks selftests/bpf: Add tests for callbacks fixes
include/linux/bpf_verifier.h | 11 ++ kernel/bpf/helpers.c | 8 +- kernel/bpf/verifier.c | 42 +++-- .../selftests/bpf/prog_tests/cb_refs.c | 49 ++++++ tools/testing/selftests/bpf/progs/cb_refs.c | 152 ++++++++++++++++++ 5 files changed, 249 insertions(+), 13 deletions(-) create mode 100644 tools/testing/selftests/bpf/prog_tests/cb_refs.c create mode 100644 tools/testing/selftests/bpf/progs/cb_refs.c
Signature · 1 line
2.34.1
Kumar Kartikeya Dwivedi
maintainerRFC PATCH 1/3 bpf: Move bpf_loop and bpf_for_each_map_elem under CAP_BPF
They would require func_info which needs prog BTF anyway, which requires bpf_capable, so just to be double sure move both these helpers taking callback under CAP_BPF protection as well.
--- kernel/bpf/helpers.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)
kernel/bpf/helpers.c +4 -4
@@ -1633,10 +1633,6 @@ bpf_base_func_proto(enum bpf_func_id func_id)return &bpf_ringbuf_submit_dynptr_proto;case BPF_FUNC_ringbuf_discard_dynptr:return &bpf_ringbuf_discard_dynptr_proto; -case BPF_FUNC_for_each_map_elem: -return &bpf_for_each_map_elem_proto; -case BPF_FUNC_loop: -return &bpf_loop_proto;case BPF_FUNC_strncmp:return &bpf_strncmp_proto;case BPF_FUNC_dynptr_from_mem:
@@ -1675,6 +1671,10 @@ bpf_base_func_proto(enum bpf_func_id func_id)return &bpf_timer_cancel_proto;case BPF_FUNC_kptr_xchg:return &bpf_kptr_xchg_proto; +case BPF_FUNC_for_each_map_elem: +return &bpf_for_each_map_elem_proto; +case BPF_FUNC_loop: +return &bpf_loop_proto;default :break ; }
Signature · 1 line
2.34.1
Kumar Kartikeya Dwivedi
maintainerRFC PATCH 2/3 bpf: Fix reference state management for synchronous callbacks
In reply to Kumar Kartikeya DwivediCurrently, verifier verifies callback functions (sync and async) as if they will be executed once, (i.e. it explores execution state as if the function was being called once). The next insn to explore is set to start of subprog and the exit from nested frame is handled using curframe > 0 and prepare_func_exit. In case of async callback it uses a customized variant of push_stack simulating a kind of branch to set up custom state and execution context for the async callback.
While this approach is simple and works when callback really will be executed only once, it is unsafe for all of our current helpers which are for_each style, i.e. they execute the callback multiple times.
A callback releasing acquired references of the caller may do so multiple times, but currently verifier sees it as one call inside the frame, which then returns to caller. Hence, it thinks it released some reference that the cb e.g. got access through callback_ctx (register filled inside cb from spilled typed register on stack).
Similarly, it may see that an acquire call is unpaired inside the callback, so the caller will copy the reference state of callback and then will have to release the register with new ref_obj_ids. But again, the callback may execute multiple times, but the verifier will only account for acquired references for a single symbolic execution of the callback.
Note that for async callback case, things are different. While currently we have bpf_timer_set_callback which only executes it once, even for multiple executions it would be safe, as reference state is NULL and check_reference_leak would force program to release state before BPF_EXIT. The state is also unaffected by analysis for the caller frame. Hence async callback is safe.
To fix this, we disallow callbacks to transfer acquired references back to caller. They must be released before callback hits BPF_EXIT, since the number of times callback is invoked is not known to the verifier, it cannot reliably track how many references will be created. Likewise, it is not allowed to release caller reference state, since we don't know how many times the callback will be invoked.
Lastly, now that callback function cannot change reference state it copied from its parent, there is no need to copy reference state back to the parent, since it won't change. It may be changed for the callee frame but that state must match parent reference state by the time callee exits, and it is going to be discarded anyway. So skip this copy too. To be clear, it won't be incorrect if the copy was done, but it would be inefficient and may be confusing to people reading the code.
--- include/linux/bpf_verifier.h | 11 ++++++++++ kernel/bpf/verifier.c | 42 ++++++++++++++++++++++++++++-------- 2 files changed, 44 insertions(+), 9 deletions(-)
include/linux/bpf_verifier.h +11 -0
@@ -212,6 +212,17 @@ struct bpf_reference_state {* is used purely to inform the user of a reference leak. */ int insn_idx; +/* There can be a case like: +* main (frame 0) +* cb (frame 1) +* func (frame 3) +* cb (frame 4) +* Hence for frame 4, if callback_ref just stored boolean, it would be +* impossible to distinguish nested callback refs. Hence store the +* frameno and compare that to callback_ref in check_reference_leak when +* exiting a callback function. +*/ +int callback_ref; };/* state of the program:
kernel/bpf/verifier.c +33 -9
84 lines not on this page · raw message
Signature · 1 line
2.34.1
Re: [PATCH RFC bpf v1 2/3] bpf: Fix reference state management for synchronous callbacks
Quoted 108 lines · Kumar Kartikeya Dwivedi
Currently, verifier verifies callback functions (sync and async) as if they will be executed once, (i.e. it explores execution state as if the function was being called once). The next insn to explore is set to start of subprog and the exit from nested frame is handled using curframe > 0 and
prepare_func_exit. In case of async callback it uses a customized variant ofpush_stacksimulating a kind of branch to set up custom state and execution context for the async callback.While this approach is simple and works when callback really will be executed only once, it is unsafe for all of our current helpers which are
for_eachstyle, i.e. they execute the callback multiple times.A callback releasing acquired references of the caller may do so multiple times, but currently verifier sees it as one call inside the frame, which then returns to caller. Hence, it thinks it released some reference that the cb e.g. got access through
callback_ctx(register filled inside cb from spilled typed register on stack).Similarly, it may see that an acquire call is unpaired inside the callback, so the caller will copy the reference state of callback and then will have to release the register with new
ref_obj_ids. But again, the callback may execute multiple times, but the verifier will only account for acquired references for a single symbolic execution of the callback.Note that for async callback case, things are different. While currently we have
bpf_timer_set_callbackwhich only executes it once, even for multiple executions it would be safe, as reference state is NULL andcheck_reference_leakwould force program to release state beforeBPF_EXIT. The state is also unaffected by analysis for the caller frame. Hence async callback is safe.To fix this, we disallow callbacks to transfer acquired references back to caller. They must be released before callback hits
BPF_EXIT, since the number of times callback is invoked is not known to the verifier, it cannot reliably track how many references will be created. Likewise, it is not allowed to release caller reference state, since we don't know how many times the callback will be invoked.Lastly, now that callback function cannot change reference state it copied from its parent, there is no need to copy reference state back to the parent, since it won't change. It may be changed for the callee frame but that state must match parent reference state by the time callee exits, and it is going to be discarded anyway. So skip this copy too. To be clear, it won't be incorrect if the copy was done, but it would be inefficient and may be confusing to people reading the code.
Fixes 69c87ba6225 ("bpf: Add bpf_for_each_map_elem() helper")Signed-off-by Kumar Kartikeya Dwivedi <[email protected]>--- include/linux/bpf_verifier.h | 11 ++++++++++ kernel/bpf/verifier.c | 42 ++++++++++++++++++++++++++++-------- 2 files changed, 44 insertions(+), 9 deletions(-)include/linux/bpf_verifier.h +11
-0@@ -212,6 +212,17 @@ struct bpf_reference_state {* is used purely to inform the user of a reference leak. */ int insn_idx; +/* There can be a case like: +* main (frame 0) +* cb (frame 1) +* func (frame 3) +* cb (frame 4) +* Hence for frame 4, if callback_ref just stored boolean, it would be +* impossible to distinguish nested callback refs. Hence store the +* frameno and compare that to callback_ref in check_reference_leak when +* exiting a callback function. +*/ +int callback_ref; };/* state of the program: kernel/bpf/verifier.c +5
-4@@ -1086,6 +1086,7 @@ static int acquire_reference_state(struct bpf_verifier_env *env, int insn_idx) id = ++env->id_gen; state->refs[new_ofs].id = id; state->refs[new_ofs].insn_idx = insn_idx; + state->refs[new_ofs].callback_ref = state->in_callback_fn ? state->frameno :0 ;return id; }@@ -1098,6 +1099,9 @@ static int release_reference_state(struct bpf_func_state *state, int ptr_id) last_idx = state->acquired_refs -1 ;for (i =0 ; i < state->acquired_refs; i++) {if (state->refs[i].id == ptr_id) { +/* Cannot release caller references in callbacks */ +if (state->in_callback_fn && state->refs[i].callback_ref != state->frameno) +return -EINVAL ;if (last_idx && i != last_idx)memcpy (&state->refs[i], &state->refs[last_idx],sizeof (*state->refs));@@ -6938,10 +6942,17 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx) caller->regs[BPF_REG_0 ] = *r0; } -/* Transfer references to the caller */ - err =copy_reference_state (caller, callee); -if (err) -return err; +/* callback_fn frame should have released its own additions to parent's
kernel/bpf/verifier.c static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx) · line 6955
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+* reference state at this point, or check_reference_leak would +* complain, hence it must be the same as the caller. There is no need +* to copy it back. +*/ +if (!callee->in_callback_fn) { +/* Transfer references to the caller */ + err =copy_reference_state (caller, callee); +if (err) +return err; + }
This part makes sense.
Quoted 6 lines
kernel/bpf/verifier.c +0
-0*insn_idx = callee->callsite +1 ;if (env->log.level &BPF_LOG_LEVEL ) {@@ -7065,13 +7076,20 @@ record_func_key(struct bpf_verifier_env *env, struct bpf_call_arg_meta *meta,static int check_reference_leak (struct bpf_verifier_env *env) {
kernel/bpf/verifier.c record_func_key(struct bpf_verifier_env *env, struct bpf_call_arg_meta *meta, · line 7087
Quoted 10 lines
kernel/bpf/verifier.c +6
-0struct bpf_func_state *state =cur_func (env); +bool refs_lingering = false;int i; +if (state->frameno && !state->in_callback_fn) +return 0 ; +for (i =0 ; i < state->acquired_refs; i++) { +if (state->in_callback_fn && state->refs[i].callback_ref != state->frameno) +continue ;
This part I don't understand.
Why remember callback_ref at all?
if (state->in_callback_fn)
and there is something in acquired_refs it means that callback acquired refs and since we're not transferring them then we can error right away.
Quoted 40 lines
kernel/bpf/verifier.c +12
-6verbose (env,"Unreleased reference id=%d alloc_insn=%d\n" , state->refs[i].id, state->refs[i].insn_idx); + refs_lingering = true; } -return state->acquired_refs ? -EINVAL :0 ; +return refs_lingering ? -EINVAL :0 ; } static int check_bpf_snprintf_call(struct bpf_verifier_env *env,@@ -12332,6 +12350,16 @@ static int do_check(struct bpf_verifier_env *env)return -EINVAL ; } +/* We must do check_reference_leak here before +* prepare_func_exit to handle the case when +* state->curframe > 0, it may be a callback +* function, for which reference_state must +* match caller reference state when it exits. +*/ + err =check_reference_leak (env); +if (err) +return err; +if (state->curframe) {/* exit from nested function */ err =prepare_func_exit (env, &env->insn_idx);@@ -12341,10 +12369,6 @@ static int do_check(struct bpf_verifier_env *env)continue ; } - err =check_reference_leak (env); -if (err) -return err; - err =check_return_code (env);if (err)return err; --2.34.1
Kumar Kartikeya Dwivedi
maintainerRe: [PATCH RFC bpf v1 2/3] bpf: Fix reference state management for synchronous callbacks
Quoted 134 lines · Alexei Starovoitov
Quoted 108 lines · Kumar Kartikeya Dwivedi
Currently, verifier verifies callback functions (sync and async) as if they will be executed once, (i.e. it explores execution state as if the function was being called once). The next insn to explore is set to start of subprog and the exit from nested frame is handled using curframe > 0 and
prepare_func_exit. In case of async callback it uses a customized variant ofpush_stacksimulating a kind of branch to set up custom state and execution context for the async callback.While this approach is simple and works when callback really will be executed only once, it is unsafe for all of our current helpers which are
for_eachstyle, i.e. they execute the callback multiple times.A callback releasing acquired references of the caller may do so multiple times, but currently verifier sees it as one call inside the frame, which then returns to caller. Hence, it thinks it released some reference that the cb e.g. got access through
callback_ctx(register filled inside cb from spilled typed register on stack).Similarly, it may see that an acquire call is unpaired inside the callback, so the caller will copy the reference state of callback and then will have to release the register with new
ref_obj_ids. But again, the callback may execute multiple times, but the verifier will only account for acquired references for a single symbolic execution of the callback.Note that for async callback case, things are different. While currently we have
bpf_timer_set_callbackwhich only executes it once, even for multiple executions it would be safe, as reference state is NULL andcheck_reference_leakwould force program to release state beforeBPF_EXIT. The state is also unaffected by analysis for the caller frame. Hence async callback is safe.To fix this, we disallow callbacks to transfer acquired references back to caller. They must be released before callback hits
BPF_EXIT, since the number of times callback is invoked is not known to the verifier, it cannot reliably track how many references will be created. Likewise, it is not allowed to release caller reference state, since we don't know how many times the callback will be invoked.Lastly, now that callback function cannot change reference state it copied from its parent, there is no need to copy reference state back to the parent, since it won't change. It may be changed for the callee frame but that state must match parent reference state by the time callee exits, and it is going to be discarded anyway. So skip this copy too. To be clear, it won't be incorrect if the copy was done, but it would be inefficient and may be confusing to people reading the code.
Fixes 69c87ba6225 ("bpf: Add bpf_for_each_map_elem() helper")Signed-off-by Kumar Kartikeya Dwivedi <[email protected]>--- include/linux/bpf_verifier.h | 11 ++++++++++ kernel/bpf/verifier.c | 42 ++++++++++++++++++++++++++++-------- 2 files changed, 44 insertions(+), 9 deletions(-)include/linux/bpf_verifier.h +11
-0@@ -212,6 +212,17 @@ struct bpf_reference_state {* is used purely to inform the user of a reference leak. */ int insn_idx; +/* There can be a case like: +* main (frame 0) +* cb (frame 1) +* func (frame 3) +* cb (frame 4) +* Hence for frame 4, if callback_ref just stored boolean, it would be +* impossible to distinguish nested callback refs. Hence store the +* frameno and compare that to callback_ref in check_reference_leak when +* exiting a callback function. +*/ +int callback_ref; };/* state of the program: kernel/bpf/verifier.c +5
-4@@ -1086,6 +1086,7 @@ static int acquire_reference_state(struct bpf_verifier_env *env, int insn_idx) id = ++env->id_gen; state->refs[new_ofs].id = id; state->refs[new_ofs].insn_idx = insn_idx; + state->refs[new_ofs].callback_ref = state->in_callback_fn ? state->frameno :0 ;return id; }@@ -1098,6 +1099,9 @@ static int release_reference_state(struct bpf_func_state *state, int ptr_id) last_idx = state->acquired_refs -1 ;for (i =0 ; i < state->acquired_refs; i++) {if (state->refs[i].id == ptr_id) { +/* Cannot release caller references in callbacks */ +if (state->in_callback_fn && state->refs[i].callback_ref != state->frameno) +return -EINVAL ;if (last_idx && i != last_idx)memcpy (&state->refs[i], &state->refs[last_idx],sizeof (*state->refs));@@ -6938,10 +6942,17 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx) caller->regs[BPF_REG_0 ] = *r0; } -/* Transfer references to the caller */ - err =copy_reference_state (caller, callee); -if (err) -return err; +/* callback_fn frame should have released its own additions to parent's kernel/bpf/verifier.c static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx) · line 6955
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+* reference state at this point, or check_reference_leak would +* complain, hence it must be the same as the caller. There is no need +* to copy it back. +*/ +if (!callee->in_callback_fn) { +/* Transfer references to the caller */ + err =copy_reference_state (caller, callee); +if (err) +return err; + }This part makes sense.
Quoted 10 lines
kernel/bpf/verifier.c +1
-0*insn_idx = callee->callsite +1 ;if (env->log.level &BPF_LOG_LEVEL ) {@@ -7065,13 +7076,20 @@ record_func_key(struct bpf_verifier_env *env, struct bpf_call_arg_meta *meta,static int check_reference_leak (struct bpf_verifier_env *env) {struct bpf_func_state *state =cur_func (env); +bool refs_lingering = false;int i;
Quoted 14 lines
kernel/bpf/verifier.c record_func_key(struct bpf_verifier_env *env, struct bpf_call_arg_meta *meta, · line 7087
Quoted 6 lines
kernel/bpf/verifier.c +5
-0+if (state->frameno && !state->in_callback_fn) +return 0 ; +for (i =0 ; i < state->acquired_refs; i++) { +if (state->in_callback_fn && state->refs[i].callback_ref != state->frameno) +continue ;This part I don't understand.
Why remembercallback_refat all?
if (state->in_callback_fn)
and there is something inacquired_refsit means that callback acquired refs and since we're not transferring them then we can error right away.
Consider that a prog has 3 acquired_refs, with ids 1, 2, 3.
When you invoke the callback, you still want it to be able to load pointers spilled to the stack with a ref_obj_id and pass them to helpers. Hence, we do copy acquired_refs to the callback after initializing bpf_func_state. However, since we don't know how many times it will be invoked, it is unsafe to allow it to acquire refs it doesn't release before its bpf_exit, or release the callers ref. The former can lead to leaks (since if we only copy refs acquired in one iteration, and if we release we only release refs released in one iteration).
Hence, this patch completely disallows callback from mutating the state of refs it copied from its parent. It can however acquire its own refs and release them before bpf_exit. Hence, check_reference_leak now errors if it sees we are in callback_fn and we have not released callback_ref refs. Since there can be multiple nested callbacks, like frame 0 -> cb1 -> cb2 etc. we need to also distinguish between whether this particular ref belongs to this callback frame or parent, and only error for our own, so we store state->frameno (which is always non-zero for callbacks).
TLDR; callbacks can read parent reference_state, but cannot mutate it, to be able to use pointers acquired by the caller. They must only undo their changes (by releasing their own acquired_refs before bpf_exit) on top of caller reference_state before returning (at which point the caller and callback state will match anyway, so no need to copy back).
Re: [PATCH RFC bpf v1 2/3] bpf: Fix reference state management for synchronous callbacks
Quoted 151 lines · Kumar Kartikeya Dwivedi
Quoted 134 lines · Alexei Starovoitov
Quoted 108 lines · Kumar Kartikeya Dwivedi
Currently, verifier verifies callback functions (sync and async) as if they will be executed once, (i.e. it explores execution state as if the function was being called once). The next insn to explore is set to start of subprog and the exit from nested frame is handled using curframe > 0 and
prepare_func_exit. In case of async callback it uses a customized variant ofpush_stacksimulating a kind of branch to set up custom state and execution context for the async callback.While this approach is simple and works when callback really will be executed only once, it is unsafe for all of our current helpers which are
for_eachstyle, i.e. they execute the callback multiple times.A callback releasing acquired references of the caller may do so multiple times, but currently verifier sees it as one call inside the frame, which then returns to caller. Hence, it thinks it released some reference that the cb e.g. got access through
callback_ctx(register filled inside cb from spilled typed register on stack).Similarly, it may see that an acquire call is unpaired inside the callback, so the caller will copy the reference state of callback and then will have to release the register with new
ref_obj_ids. But again, the callback may execute multiple times, but the verifier will only account for acquired references for a single symbolic execution of the callback.Note that for async callback case, things are different. While currently we have
bpf_timer_set_callbackwhich only executes it once, even for multiple executions it would be safe, as reference state is NULL andcheck_reference_leakwould force program to release state beforeBPF_EXIT. The state is also unaffected by analysis for the caller frame. Hence async callback is safe.To fix this, we disallow callbacks to transfer acquired references back to caller. They must be released before callback hits
BPF_EXIT, since the number of times callback is invoked is not known to the verifier, it cannot reliably track how many references will be created. Likewise, it is not allowed to release caller reference state, since we don't know how many times the callback will be invoked.Lastly, now that callback function cannot change reference state it copied from its parent, there is no need to copy reference state back to the parent, since it won't change. It may be changed for the callee frame but that state must match parent reference state by the time callee exits, and it is going to be discarded anyway. So skip this copy too. To be clear, it won't be incorrect if the copy was done, but it would be inefficient and may be confusing to people reading the code.
Fixes 69c87ba6225 ("bpf: Add bpf_for_each_map_elem() helper")Signed-off-by Kumar Kartikeya Dwivedi <[email protected]>--- include/linux/bpf_verifier.h | 11 ++++++++++ kernel/bpf/verifier.c | 42 ++++++++++++++++++++++++++++-------- 2 files changed, 44 insertions(+), 9 deletions(-)include/linux/bpf_verifier.h +11
-0@@ -212,6 +212,17 @@ struct bpf_reference_state {* is used purely to inform the user of a reference leak. */ int insn_idx; +/* There can be a case like: +* main (frame 0) +* cb (frame 1) +* func (frame 3) +* cb (frame 4) +* Hence for frame 4, if callback_ref just stored boolean, it would be +* impossible to distinguish nested callback refs. Hence store the +* frameno and compare that to callback_ref in check_reference_leak when +* exiting a callback function. +*/ +int callback_ref; };/* state of the program: kernel/bpf/verifier.c +5
-4@@ -1086,6 +1086,7 @@ static int acquire_reference_state(struct bpf_verifier_env *env, int insn_idx) id = ++env->id_gen; state->refs[new_ofs].id = id; state->refs[new_ofs].insn_idx = insn_idx; + state->refs[new_ofs].callback_ref = state->in_callback_fn ? state->frameno :0 ;return id; }@@ -1098,6 +1099,9 @@ static int release_reference_state(struct bpf_func_state *state, int ptr_id) last_idx = state->acquired_refs -1 ;for (i =0 ; i < state->acquired_refs; i++) {if (state->refs[i].id == ptr_id) { +/* Cannot release caller references in callbacks */ +if (state->in_callback_fn && state->refs[i].callback_ref != state->frameno) +return -EINVAL ;if (last_idx && i != last_idx)memcpy (&state->refs[i], &state->refs[last_idx],sizeof (*state->refs));@@ -6938,10 +6942,17 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx) caller->regs[BPF_REG_0 ] = *r0; } -/* Transfer references to the caller */ - err =copy_reference_state (caller, callee); -if (err) -return err; +/* callback_fn frame should have released its own additions to parent's kernel/bpf/verifier.c static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx) · line 6955
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+* reference state at this point, or check_reference_leak would +* complain, hence it must be the same as the caller. There is no need +* to copy it back. +*/ +if (!callee->in_callback_fn) { +/* Transfer references to the caller */ + err =copy_reference_state (caller, callee); +if (err) +return err; + }This part makes sense.
Quoted 10 lines
kernel/bpf/verifier.c +1
-0*insn_idx = callee->callsite +1 ;if (env->log.level &BPF_LOG_LEVEL ) {@@ -7065,13 +7076,20 @@ record_func_key(struct bpf_verifier_env *env, struct bpf_call_arg_meta *meta,static int check_reference_leak (struct bpf_verifier_env *env) {struct bpf_func_state *state =cur_func (env); +bool refs_lingering = false;int i;Quoted 14 lines
kernel/bpf/verifier.c record_func_key(struct bpf_verifier_env *env, struct bpf_call_arg_meta *meta, · line 7087
Quoted 6 lines
kernel/bpf/verifier.c +5
-0+if (state->frameno && !state->in_callback_fn) +return 0 ; +for (i =0 ; i < state->acquired_refs; i++) { +if (state->in_callback_fn && state->refs[i].callback_ref != state->frameno) +continue ;This part I don't understand.
Why remembercallback_refat all?
if (state->in_callback_fn)
and there is something inacquired_refsit means that callback acquired refs and since we're not transferring them then we can error right away.
Quoted 6 lines
Consider that a prog has 3
acquired_refs, with ids 1, 2, 3.When you invoke the callback, you still want it to be able to load pointers spilled to the stack with a
ref_obj_idand pass them to helpers. Hence, we do copyacquired_refsto the callback after initializingbpf_func_state.
Ahh. I see. We do copy_reference_state() and the verifier state in the caller's frame is indeed accessible through callback_ctx pointer passed into the callee.
Quoted 6 lines
However, since we don't know how many
times it will be invoked, it is unsafe to allow it to acquire refs it doesn't release before itsbpf_exit, or release the callers ref. The former can lead to leaks (since if we only copy refs acquired in one iteration, and if we release we only release refs released in one iteration).
Right.
Quoted 10 lines
Hence, this patch completely disallows callback from mutating the state of refs it copied from its parent. It can however acquire its own refs and release them before
bpf_exit. Hence,check_reference_leaknow errors if it sees we are incallback_fnand we have not releasedcallback_refrefs. Since there can be multiple nested callbacks, like frame 0 -> cb1 -> cb2 etc. we need to also distinguish between whether this particular ref belongs to this callback frame or parent, and only error for our own, so we storestate->frameno(which is always non-zero for callbacks).
Right.
Quoted 5 lines
TLDR; callbacks can read parent
reference_state, but cannot mutate it, to be able to use pointers acquired by the caller. They must only undo their changes (by releasing their ownacquired_refsbeforebpf_exit) on top of callerreference_statebefore returning (at which point the caller and callback state will match anyway, so no need to copy back).
Please add all these details to the commit log.
Kumar Kartikeya Dwivedi
maintainerRFC PATCH 3/3 selftests/bpf: Add tests for callbacks fixes
In reply to Kumar Kartikeya DwivediThese are regression tests to ensure we don't end up in invalid runtime state for helpers that execute callbacks multiple times. It exercises the fixes to verifier callback handling in previous patches.
--- .../selftests/bpf/prog_tests/cb_refs.c | 49 ++++++ tools/testing/selftests/bpf/progs/cb_refs.c | 152 ++++++++++++++++++ 2 files changed, 201 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/cb_refs.c create mode 100644 tools/testing/selftests/bpf/progs/cb_refs.c
tools/testing/selftests/bpf/prog_tests/cb_refs.c new file +49 -0
@@ -0,0 +1,49 @@ +// SPDX-License-Identifier: GPL-2.0 +#include "bpf/libbpf.h" +#include <test_progs.h> +#include <network_helpers.h> + +#include "cb_refs.skel.h" + +static char log_buf[1024 *1024 ]; + +struct { +const char *prog_name; +const char *err_msg; +} cb_refs_tests[] = { + {"underflow_prog" ,"reference has not been acquired before" }, + {"leak_prog" ,"Unreleased reference" }, + {"nested_cb" ,"Unreleased reference id=2 alloc_insn=16" }, + {"oob_access" ,"TBD..." }, + {"write" ,"TBD..." }, +}; + +void test_cb_refs (void ) +{ + LIBBPF_OPTS(bpf_object_open_opts, opts, .kernel_log_buf = log_buf, + .kernel_log_size = sizeof(log_buf), + .kernel_log_level = 1); +struct bpf_program *prog; +struct cb_refs *skel; +int i; + +for (i =0 ; i <ARRAY_SIZE (cb_refs_tests); i++) { +LIBBPF_OPTS (bpf_test_run_opts, run_opts, + .data_in = &pkt_v4, + .data_size_in = sizeof(pkt_v4), + .repeat = 1, + ); + skel =cb_refs__open_opts (&opts); +if (!ASSERT_OK_PTR (skel,"cb_refs__open_and_load" )) +return ; + prog =bpf_object__find_program_by_name (skel->obj, cb_refs_tests[i].prog_name); +bpf_program__set_autoload (prog, true); +if (!ASSERT_ERR (cb_refs__load (skel),"cb_refs__load" )) +bpf_prog_test_run_opts (bpf_program__fd (prog), &run_opts); +if (!ASSERT_OK_PTR (strstr (log_buf, cb_refs_tests[i].err_msg),"expected error message" )) { +fprintf (stderr,"Expected: %s\n" , cb_refs_tests[i].err_msg); +fprintf (stderr,"Verifier: %s\n" , log_buf); + } +cb_refs__destroy (skel); + } +}
tools/testing/selftests/bpf/progs/cb_refs.c new file +152 -0
152 lines not on this page · raw message
Signature · 1 line
2.34.1
Quoted 79 lines · Kumar Kartikeya Dwivedi
Hi, these are fixes for issues I noticed while working on the callback code. It is an RFC because I would like to discuss how to fix one other problem, I have a rough idea but would like to discuss before working on it, since it isn't trivial. The conservative fix doesn't pass existing selftests.
It seems like the problem anticipated in [0] actually exists with all the current callback based loop helpers, in a different form. The main reason is that callback function is only explored as if it was executing once.
There are some example cases included in selftests to show the problem, and make sure we keep catching and rejecting them. Since callback which is loop body is only verified once, once the
for_eachhelper returns the execution state from verifier's perspective is as if callback executed once, but ofcourse it may execute multiple times, unknowable statically.Patch 1 fixes the case of acquiring and releasing references, unless I missed some corner case it seems to mostly work fine.
In the future when we have a case where a sycnhronous callback will only be executed once by a helper, we can improve this case by relaxing these restrictions, so transfer of references and verifying callback as if it executes only once can be done. For now, all
in_callback_fnfunction get executed multiple times, hence that change is left for when it will be needed.Now, the important part:
------------------------The included selftest will fail/crash, as one fix is missing from the series. Whatever I tried so far wasn't backwards compatible with existing selftests (e.g. conservatively marking all reads as UNKNOWN, and all writes scrubbing stack slots). Some tests e.g. read skb pointer from
ptr_to_stackpassed to callback.It is not clear to me what the correct fix would be to handle reads and writes from the stack inside callback function. If a stack slot is never touched inside the callback in any of the states, it should be safe to allow it to load spilled registers from caller's stack frame, even allowing precise scalars would be safe if they are read from untouched slots.
The idea I have is roughly:
In the first pass, verify as if callback is executing once. This is the same case as of now, this may e.g. load a spilled precise scalar, then overwrite it, so insns before the store doing overwrite verification consider register as precise. In reality, in later loop iterations though this assumption may be wrong.
For e.g.
int i = 1;
int arr[2] = {0};
bpf_loop(100, cb, &i, 0);cb:
int i = *ctx; // seen as 1
func(*((int *)ctx - i)); // stack read ok, arr[1]
*ctx = i + 1; // i is now 2verification ends here, but this would start reading uninit stack in later iterations.
To fix this, we keep a bitmap of scratched slots for the stack in caller frame. Once we see
BPF_EXIT, we do reverification of the callback, but this time mark _any_ register reading from slots that were scratched the first time around asmark_reg_unknown(i.e. not precise). Moreover, in the caller stack it will be markedSTACK_MISC. It might not be able to track <8 byte writes but I guess that is fine (since that would require 512 bits instead of 64).The big problem I can see in this is that the precise register guards another write in another branch that was not taken the first time around. In that case
push_stackis not done to explore the other branch, andis_branch_takenis used to predict the outcome.But: if this has to cause a problem, the precise reg guarding the branch must change its value (and that we can see if it is being from a scratched slot read), so by doing another pass we would get rid of this problem. I.e. one more pass would be needed after downgrading precise registers to unknown.
Quoted 6 lines
If I can get some hints for new ideas or feedback on whether this would be the correct approach, I can work on a proper fix for this case.
It seems like roughly the same approach will be required for open coded iteration mentioned in [0], so we might be able to kill two birds with one shot.
Keep in mind that callbacks, just like open-coded iteration loops (which I plan to work on as soon as I dig myself out of BPF mailing list email hole), might be executed not just 1 or >1 times, they might be executed exactly zero times (e.g., pass invalid arguments to bpf_loop or any other such helper and your callback won't be executed). And as such, in principle, any write to a new stack slot and marking it as "initialized" is invalid.
So generally only state modifications that keep state with equivalent (and not more) amount of information should be allowed. I.e., writing to an already written stack slot and not adding more specific knowledge to known register state should be ok regardless if callback was called 0, 1, or N times. E.g, if we knew that r1 is [100, 200] precise range and inside the callback we update that to [150, 175] -- it's fine. We just need to restore original [100, 200] state once we are done validating callback. If parent's stack was non-precise and internally callback makes it precise for internal use -- that's also fine, but we need to restore that slot to original imprecise state after callback validation. Similarly, if stack slot was uninitialized, it's ok if callback uses that slot for something, but we should forget that something once callback is done.
Iterators will also have an additional restriction that we don't actually create a new frame for each inner loop (so what you did for callbacks in this patch set won't be usable as-is directly, but it's fine).
In short, possibility of zero executions makes everything much clearer. We can't assume we know what callback writes into parent's stack (as this write might never happen). As to how to make this a bit more practical, we'll need to work this out in a bit more details, I haven't spent too much time on this yet.
But I think the approach (which you are right will be conceptually very similar to open-coded iterators) should be to do two passes:
a) pass that assumes no callback happened and no parent function's
stack modifications happened. Program should still be correctly verifiable (and as such, any program that assumes that callback sets some stack slot to some known value from inside the callback is invalid; that slot has to be initialized with some default value).
b) pass that simulates exactly 1 execution. Once we are done with
this, let's remember this state.
c) third pass that simulates N executions. We pass state from step
b) as input state. We validate with that state. Assuming it's successful, we end up with some new state of the parent function. At this point we should check that end state from step b) and state from this step c) are "equivalent" (according to my explanation above, there should be no expansion of knowledge of the state).
The latter state is what we do for BPF infinite loop detection. The fun part is here we actually want to see that it would cause infinite loop (states shouldn't differ). At this point we can just assume that it's fine to execute N callbacks and we just pop state c), go back to state b), and continue parent program verification.
I might be missing some details, but that's a rough idea and a plan I have.
Quoted 21 lines
Thanks!
[0]: https://lore.kernel.org/bpf/[email protected]
Kumar Kartikeya Dwivedi (3):
bpf: Movebpf_loopandbpf_for_each_map_elemunderCAP_BPF
bpf: Fix reference state management for synchronous callbacks selftests/bpf: Add tests for callbacks fixesinclude/linux/bpf_verifier.h | 11 ++ kernel/bpf/helpers.c | 8 +- kernel/bpf/verifier.c | 42 +++-- .../selftests/bpf/prog_tests/cb_refs.c | 49 ++++++ tools/testing/selftests/bpf/progs/cb_refs.c | 152 ++++++++++++++++++ 5 files changed, 249 insertions(+), 13 deletions(-) create mode 100644 tools/testing/selftests/bpf/prog_tests/cb_refs.c create mode 100644 tools/testing/selftests/bpf/progs/cb_refs.c--
2.34.1
Kumar Kartikeya Dwivedi
maintainerQuoted 111 lines · Andrii Nakryiko
Quoted 79 lines · Kumar Kartikeya Dwivedi
Hi, these are fixes for issues I noticed while working on the callback code. It is an RFC because I would like to discuss how to fix one other problem, I have a rough idea but would like to discuss before working on it, since it isn't trivial. The conservative fix doesn't pass existing selftests.
It seems like the problem anticipated in [0] actually exists with all the current callback based loop helpers, in a different form. The main reason is that callback function is only explored as if it was executing once.
There are some example cases included in selftests to show the problem, and make sure we keep catching and rejecting them. Since callback which is loop body is only verified once, once the
for_eachhelper returns the execution state from verifier's perspective is as if callback executed once, but ofcourse it may execute multiple times, unknowable statically.Patch 1 fixes the case of acquiring and releasing references, unless I missed some corner case it seems to mostly work fine.
In the future when we have a case where a sycnhronous callback will only be executed once by a helper, we can improve this case by relaxing these restrictions, so transfer of references and verifying callback as if it executes only once can be done. For now, all
in_callback_fnfunction get executed multiple times, hence that change is left for when it will be needed.Now, the important part:
------------------------The included selftest will fail/crash, as one fix is missing from the series. Whatever I tried so far wasn't backwards compatible with existing selftests (e.g. conservatively marking all reads as UNKNOWN, and all writes scrubbing stack slots). Some tests e.g. read skb pointer from
ptr_to_stackpassed to callback.It is not clear to me what the correct fix would be to handle reads and writes from the stack inside callback function. If a stack slot is never touched inside the callback in any of the states, it should be safe to allow it to load spilled registers from caller's stack frame, even allowing precise scalars would be safe if they are read from untouched slots.
The idea I have is roughly:
In the first pass, verify as if callback is executing once. This is the same case as of now, this may e.g. load a spilled precise scalar, then overwrite it, so insns before the store doing overwrite verification consider register as precise. In reality, in later loop iterations though this assumption may be wrong.
For e.g.
int i = 1;
int arr[2] = {0};
bpf_loop(100, cb, &i, 0);cb:
int i = *ctx; // seen as 1
func(*((int *)ctx - i)); // stack read ok, arr[1]
*ctx = i + 1; // i is now 2verification ends here, but this would start reading uninit stack in later iterations.
To fix this, we keep a bitmap of scratched slots for the stack in caller frame. Once we see
BPF_EXIT, we do reverification of the callback, but this time mark _any_ register reading from slots that were scratched the first time around asmark_reg_unknown(i.e. not precise). Moreover, in the caller stack it will be markedSTACK_MISC. It might not be able to track <8 byte writes but I guess that is fine (since that would require 512 bits instead of 64).The big problem I can see in this is that the precise register guards another write in another branch that was not taken the first time around. In that case
push_stackis not done to explore the other branch, andis_branch_takenis used to predict the outcome.But: if this has to cause a problem, the precise reg guarding the branch must change its value (and that we can see if it is being from a scratched slot read), so by doing another pass we would get rid of this problem. I.e. one more pass would be needed after downgrading precise registers to unknown.
Quoted 6 lines
If I can get some hints for new ideas or feedback on whether this would be the correct approach, I can work on a proper fix for this case.
It seems like roughly the same approach will be required for open coded iteration mentioned in [0], so we might be able to kill two birds with one shot.
Keep in mind that callbacks, just like open-coded iteration loops (which I plan to work on as soon as I dig myself out of BPF mailing list email hole), might be executed not just 1 or >1 times, they might be executed exactly zero times (e.g., pass invalid arguments to
bpf_loopor any other such helper and your callback won't be executed). And as such, in principle, any write to a new stack slot and marking it as "initialized" is invalid.So generally only state modifications that keep state with equivalent (and not more) amount of information should be allowed. I.e., writing to an already written stack slot and not adding more specific knowledge to known register state should be ok regardless if callback was called 0, 1, or N times. E.g, if we knew that r1 is [100, 200] precise range and inside the callback we update that to [150, 175] -- it's fine. We just need to restore original [100, 200] state once we are done validating callback. If parent's stack was non-precise and internally callback makes it precise for internal use -- that's also fine, but we need to restore that slot to original imprecise state after callback validation. Similarly, if stack slot was uninitialized, it's ok if callback uses that slot for something, but we should forget that something once callback is done.
Quoted 8 lines
Iterators will also have an additional restriction that we don't actually create a new frame for each inner loop (so what you did for callbacks in this patch set won't be usable as-is directly, but it's fine).
In short, possibility of zero executions makes everything much clearer. We can't assume we know what callback writes into parent's
Indeed, 0 callback executions seems like a significant insight.
There needs to be an exploration without actually exploring the loop body, and we need to check whether the rest of the program passes verification like that.
It seems that case should be handled even right now? It is like how we handle branches, so you will push_stack pointing to the first instruction of subprog in one exploration path (which simulates execution once and continues back in parent from bpf_exit). While for the 0 callback case, you continue verifying after the callback helper call insn.
It seems orthogonal to the N times case. So maybe we should fix that now while thinking about how to handle N explorations? Thoughts?
Right now, we verify the callback as if it executes once. So callback may e.g. spill some register variable and mark it precise (bounded, or even constant). Then we will verify the rest of the program using that precise scalar. But it could happen that the callback never runs and it will simply use that unbounded scalar thinking it is bounded.
Quoted 6 lines
stack (as this write might never happen). As to how to make this a bit more practical, we'll need to work this out in a bit more details, I haven't spent too much time on this yet.
But I think the approach (which you are right will be conceptually very similar to open-coded iterators) should be to do two passes:
You mean three, right? ;-)
Quoted 15 lines
a) pass that assumes no callback happened and no parent function's
stack modifications happened. Program should still be correctly verifiable (and as such, any program that assumes that callback sets some stack slot to some known value from inside the callback is invalid; that slot has to be initialized with some default value).
b) pass that simulates exactly 1 execution. Once we are done with
this, let's remember this state.
c) third pass that simulates N executions. We pass state from step
b) as input state. We validate with that state. Assuming it's successful, we end up with some new state of the parent function. At this point we should check that end state from step b) and state from this step c) are "equivalent" (according to my explanation above, there should be no expansion of knowledge of the state).
Quoted 9 lines
The latter state is what we do for BPF infinite loop detection. The fun part is here we actually want to see that it would cause infinite loop (states shouldn't differ). At this point we can just assume that it's fine to execute N callbacks and we just pop state c), go back to state b), and continue parent program verification.
I might be missing some details, but that's a rough idea and a plan I have.
Thanks for articulating your ideas. Looking forward to the patches. It does seem like checking whether states will be equal should be enough, even though it might not allow all kinds of loops. We already ensure when pruning search that the new state is 'safe' given an old already explored safe state so it should still allow some state modification inside the loop.
Choosing the number of times to repeat this process will be the hard part, some value that isn't too conservative and yet still not too high to end up consuming too much time and memory during verification, since we might not start seeing equivalent states immediately on 2nd exploration. Maybe the callback helpers themselves can give some hints to tune the value of N. The other improvement might be identifying the register involved in the condition used to break out of loops, if scalar then learning the bounds from the branch containing the bpf_exit with R0 set to callback return value, which might allow exploring complicated cases without bounding to fixed N limit in verifier.