This series updates verifier logic for callback functions handling.
Current master simulates callback body execution exactly once,
which leads to verifier not detecting unsafe programs like below:
static int unsafe_on_zero_iter_cb(__u32 idx, struct num_context *ctx)
{
ctx->i = 0;
return 0;
}
SEC("?raw_tp")
int unsafe_on_zero_iter(void *unused)
{
struct num_context loop_ctx = { .i = 32 };
__u8 choice_arr[2] = { 0, 1 };
bpf_loop(100, unsafe_on_zero_iter_cb, &loop_ctx, 0);
return choice_arr[loop_ctx.i];
}
This was reported previously in [0].
The basic idea of the fix is to schedule callback entry state for
verification in env->head until some identical, previously visited
state in current DFS state traversal is found. Same logic as with open
coded iterators, and builds on top recent fixes [1] for those.
The series is structured as follows:
- patches #1,2,3 update strobemeta, xdp_synproxy selftests and
bpf_loop_bench benchmark to allow convergence of the bpf_loop
callback states;
- patches #4,5 just shuffle the code a bit;
- patch #6 is the main part of the series;
- patch #7 adds test cases for #6;
- patch #8 extend patch #6 with same speculative scalar widening
logic, as used for open coded iterators;
- patch #9 adds test cases for #8;
- patch #10 extends patch #6 to track maximal number of callback
executions specifically for bpf_loop();
- patch #11 adds test cases for #10.
Veristat results comparing this series to master+patches #1,2,3 using selftests
show the following difference:
File Program States (A) States (B) States (DIFF)
------------------------- ------------- ---------- ---------- -------------
bpf_loop_bench.bpf.o benchmark 1 2 +1 (+100.00%)
pyperf600_bpf_loop.bpf.o on_event 322 407 +85 (+26.40%)
strobemeta_bpf_loop.bpf.o on_event 113 151 +38 (+33.63%)
xdp_synproxy_kern.bpf.o syncookie_tc 341 291 -50 (-14.66%)
xdp_synproxy_kern.bpf.o syncookie_xdp 344 301 -43 (-12.50%)
Veristat results comparing this series to master using Tetragon BPF
files [2] also show some differences.
States diff varies from +2% to +15% on 23 programs out of 186,
no new failures.
Changelog:
- V3 [5] -> V4, changes suggested by Andrii:
- validate mark_chain_precision() result in patch #10;
- renaming s/cumulative_callback_depth/callback_unroll_depth/.
- V2 [4] -> V3:
- fixes in expected log messages for test cases:
- callback_result_precise;
- parent_callee_saved_reg_precise_with_callback;
- parent_stack_slot_precise_with_callback;
- renamings (suggested by Alexei):
- s/callback_iter_depth/cumulative_callback_depth/
- s/is_callback_iter_next/calls_callback/
- s/mark_callback_iter_next/mark_calls_callback/
- prepare_func_exit() updated to exit with -EFAULT when
callee->in_callback_fn is true but calls_callback() is not true
for callsite;
- test case 'bpf_loop_iter_limit_nested' rewritten to use return
value check instead of verifier log message checks
(suggested by Alexei).
- V1 [3] -> V2, changes suggested by Andrii:
- small changes for error handling code in __check_func_call();
- callback body processing log is now matched in relevant
verifier_subprog_precision.c tests;
- R1 passed to bpf_loop() is now always marked as precise;
- log level 2 message for bpf_loop() iteration termination instead of
iteration depth messages;
- __no_msg macro removed;
- bpf_loop_iter_limit_nested updated to avoid using __no_msg;
- commit message for patch #3 updated according to Alexei's request.
[0] https://lore.kernel.org/bpf/CA+vRuzPChFNXmouzGG+wsy=6eMcfr1mFG0F3g7rbg-sedGKW3w@xxxxxxxxxxxxxx/
[1] https://lore.kernel.org/bpf/20231024000917.12153-1-eddyz87@xxxxxxxxx/
[2] git@xxxxxxxxxx:cilium/tetragon.git
[3] https://lore.kernel.org/bpf/20231116021803.9982-1-eddyz87@xxxxxxxxx/T/#t
[4] https://lore.kernel.org/bpf/20231118013355.7943-1-eddyz87@xxxxxxxxx/T/#t
[5] https://lore.kernel.org/bpf/20231120225945.11741-1-eddyz87@xxxxxxxxx/T/#t
Eduard Zingerman (11):
selftests/bpf: track tcp payload offset as scalar in xdp_synproxy
selftests/bpf: track string payload offset as scalar in strobemeta
selftests/bpf: fix bpf_loop_bench for new callback verification scheme
bpf: extract __check_reg_arg() utility function
bpf: extract setup_func_entry() utility function
bpf: verify callbacks as if they are called unknown number of times
selftests/bpf: tests for iterating callbacks
bpf: widening for callback iterators
selftests/bpf: test widening for iterating callbacks
bpf: keep track of max number of bpf_loop callback iterations
selftests/bpf: check if max number of bpf_loop iterations is tracked
include/linux/bpf_verifier.h | 16 +
kernel/bpf/verifier.c | 402 ++++++++++++------
.../selftests/bpf/prog_tests/verifier.c | 2 +
.../selftests/bpf/progs/bpf_loop_bench.c | 13 +-
tools/testing/selftests/bpf/progs/cb_refs.c | 1 +
.../selftests/bpf/progs/exceptions_fail.c | 2 +
.../testing/selftests/bpf/progs/strobemeta.h | 78 ++--
.../bpf/progs/verifier_iterating_callbacks.c | 242 +++++++++++
.../bpf/progs/verifier_subprog_precision.c | 86 +++-
.../selftests/bpf/progs/xdp_synproxy_kern.c | 84 ++--
10 files changed, 709 insertions(+), 217 deletions(-)
create mode 100644 tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
--
2.42.1
