All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH bpf v3 00/11] verify callbacks as if they are called unknown number of times
@ 2023-11-20 22:59 Eduard Zingerman
  2023-11-20 22:59 ` [PATCH bpf v3 01/11] selftests/bpf: track tcp payload offset as scalar in xdp_synproxy Eduard Zingerman
                   ` (10 more replies)
  0 siblings, 11 replies; 19+ messages in thread
From: Eduard Zingerman @ 2023-11-20 22:59 UTC (permalink / raw)
  To: bpf, ast
  Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song, memxor,
	awerner32, Eduard Zingerman

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:
- 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@mail.gmail.com/
[1] https://lore.kernel.org/bpf/20231024000917.12153-1-eddyz87@gmail.com/
[2] git@github.com:cilium/tetragon.git
[3] https://lore.kernel.org/bpf/20231116021803.9982-1-eddyz87@gmail.com/T/#t
[4] https://lore.kernel.org/bpf/20231118013355.7943-1-eddyz87@gmail.com/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                         | 400 ++++++++++++------
 .../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, 707 insertions(+), 217 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c

-- 
2.42.1


^ permalink raw reply	[flat|nested] 19+ messages in thread
end of thread, other threads:[~2023-11-21  1:35 UTC | newest]

Thread overview: 19+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2023-11-20 22:59 [PATCH bpf v3 00/11] verify callbacks as if they are called unknown number of times Eduard Zingerman
2023-11-20 22:59 ` [PATCH bpf v3 01/11] selftests/bpf: track tcp payload offset as scalar in xdp_synproxy Eduard Zingerman
2023-11-20 22:59 ` [PATCH bpf v3 02/11] selftests/bpf: track string payload offset as scalar in strobemeta Eduard Zingerman
2023-11-20 22:59 ` [PATCH bpf v3 03/11] selftests/bpf: fix bpf_loop_bench for new callback verification scheme Eduard Zingerman
2023-11-20 22:59 ` [PATCH bpf v3 04/11] bpf: extract __check_reg_arg() utility function Eduard Zingerman
2023-11-20 22:59 ` [PATCH bpf v3 05/11] bpf: extract setup_func_entry() " Eduard Zingerman
2023-11-20 22:59 ` [PATCH bpf v3 06/11] bpf: verify callbacks as if they are called unknown number of times Eduard Zingerman
2023-11-21  1:00   ` Andrii Nakryiko
2023-11-21  1:06     ` Eduard Zingerman
2023-11-20 22:59 ` [PATCH bpf v3 07/11] selftests/bpf: tests for iterating callbacks Eduard Zingerman
2023-11-20 22:59 ` [PATCH bpf v3 08/11] bpf: widening for callback iterators Eduard Zingerman
2023-11-20 22:59 ` [PATCH bpf v3 09/11] selftests/bpf: test widening for iterating callbacks Eduard Zingerman
2023-11-20 22:59 ` [PATCH bpf v3 10/11] bpf: keep track of max number of bpf_loop callback iterations Eduard Zingerman
2023-11-21  1:04   ` Andrii Nakryiko
2023-11-21  1:09     ` Eduard Zingerman
2023-11-21  1:14       ` Andrii Nakryiko
2023-11-21  1:26         ` Alexei Starovoitov
2023-11-21  1:35           ` Eduard Zingerman
2023-11-20 22:59 ` [PATCH bpf v3 11/11] selftests/bpf: check if max number of bpf_loop iterations is tracked Eduard Zingerman

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.