bpf: track find_equal_scalars history on per-instruction level
Subsystems (4)
Eduard Zingerman
maintainerv3 cover bpf: track find_equal_scalars history on per-instruction level
This is a fix for precision tracking bug reported in [0]. It supersedes my previous attempt to fix similar issue in commit [1]. Here is a minimized test case from [0]:
0: call bpf_get_prandom_u32;
1: r7 = r0;
2: r8 = r0;
3: call bpf_get_prandom_u32;
4: if r0 > 1 goto +0;
/* --- checkpoint #1: r7.id=1, r8.id=1 --- */
5: if r8 >= r0 goto 9f;
6: r8 += r8;
/* --- checkpoint #2: r7.id=1, r8.id=0 --- */
7: if r7 == 0 goto 9f;
8: r0 /= 0;
/* --- checkpoint #3 --- */
9: r0 = 42;
10: exit;W/o this fix verifier incorrectly assumes that instruction at label
(8) is unreachable. The issue is caused by failure to infer precision mark for r0 at checkpoint #1:
- first verification path is:
- (0-4): r0 range [0,1];
- (5): r8 range [0,0], propagated to r7;
- (6): r8.id is reset;
- (7): jump is predicted to happen;
- (9-10): safe exit.
- when jump at (7) is predicted mark_chain_precision() for r7 is called and backtrack_insn() proceeds as follows:
- at (7) r7 is marked as precise;
- at (5) r8 is not currently tracked and thus r0 is not marked;
- at (4-5) boundary logic from [1] is triggered and r7,r8 are marked
as precise;
- => r0 precision mark is missed.
- when second branch of (4) is considered, verifier prunes the state because r0 is not marked as precise in the visited state.
Basically, backtracking logic fails to notice that at (5) range information is gained for both r7 and r8, and thus both r8 and r0 have to be marked as precise.
This happens because [1] can only account for such range transfers at parent/child state boundaries.
The solution suggested by Andrii Nakryiko in [0] is to use jump history to remember which registers gained range as a result of find_equal_scalars() [renamed to sync_linked_regs()] and use this information in backtrack_insn().
Which is what this patch-set does.
The patch-set uses u64 value as a vector of 10-bit values that identify registers gaining range in find_equal_scalars(). This amounts to maximum of 6 possible values.
To check if such capacity is sufficient I've instrumented kernel to track a histogram for maximal amount of registers that gain range in find_equal_scalars per program verification [2]. Measurements done for verifier selftests and Cilium bpf object files from [3] show that number of such registers is *always* <= 4 and in 98% of cases it is <= 2.
When tested on a subset of selftests identified by selftests/bpf/veristat.cfg and Cilium bpf object files from [3] this patch-set has minimal verification performance impact:
File Program Insns (DIFF) States (DIFF) ------------------------ ------------------------ -------------- ------------- bpf_host.o tail_handle_nat_fwd_ipv4 -75 (-0.61%) -3 (-0.39%) pyperf600_nounroll.bpf.o on_event +1673 (+0.33%) +3 (+0.01%)
[0] https://lore.kernel.org/bpf/CAEf4BzZ0xidVCqB47XnkXcNhkPWF6_nTV7yt+_Lf0kcFEut2Mg@mail.gmail.com/
[1] commit 904e6ddf4133 ("bpf: Use scalar ids in mark_chain_precision()")
[2] https://github.com/eddyz87/bpf/tree/find-equal-scalars-in-jump-history-with-stats
[3] https://github.com/anakryiko/cilium
Changes:
- v2 -> v3:
A number of stylistic changes suggested by Andrii:
- renamings:
- struct reg_or_spill -> linked_reg;
- find_equal_scalars() -> collect_linked_regs;
- copy_known_reg() -> sync_linked_regs;
- collect_linked_regs() now returns linked regs set of
size 2 or larger; - dropped usage of bit fields in struct linked_reg;
- added a patch changing references to find_equal_scalars() in selftests comments.
- v1 -> v2:
- patch "bpf: replace env->cur_hist_ent with a getter function" is
dropped (Andrii);
- added structure linked_regs and helper functions to [de]serialize
u64 value as such structure (Andrii); - bt_set_equal_scalars() renamed to bt_sync_linked_regs(), moved to start and end of backtrack_insn() in order to untie linked register logic from conditional jumps backtracking. Andrii requested a more radical change of moving linked registers processing to bt_set_xxx() functions, I did an experiment in this direction:
https://github.com/eddyz87/bpf/tree/find-equal-scalars-in-jump-history--linked-regs-in-bt-set-reg
the end result of the experiment seems much uglier than version presented in v2.
Revisions:
- v1: https://lore.kernel.org/bpf/[email protected]/
- v2: https://lore.kernel.org/bpf/[email protected]/
Eduard Zingerman (4):
bpf: track equal scalars history on per-instruction level
bpf: remove mark_precise_scalar_ids()
selftests/bpf: tests for per-insn sync_linked_regs() precision
tracking
selftests/bpf: update comments find_equal_scalars->sync_linked_regs
include/linux/bpf_verifier.h | 4 + kernel/bpf/verifier.c | 363 +++++++++++------- .../selftests/bpf/progs/verifier_scalar_ids.c | 256 ++++++++---- .../selftests/bpf/progs/verifier_spill_fill.c | 16 +- .../bpf/progs/verifier_subprog_precision.c | 2 +- .../testing/selftests/bpf/verifier/precise.c | 28 +- 6 files changed, 434 insertions(+), 235 deletions(-)
Signature · 1 line
2.45.2
Eduard Zingerman
maintainerPATCH v3 1/4 bpf: track equal scalars history on per-instruction level
Use bpf_verifier_state->jmp_history to track which registers were updated by find_equal_scalars() (renamed to collect_linked_regs()) when conditional jump was verified. Use recorded information in backtrack_insn() to propagate precision.
E.g. for the following program:
while verifying instructions
1: r1 = r0 | 2: if r1 < 8 goto ... | push r0,r1 as linked registers in jmp_history 3: if r0 > 16 goto ... | push r0,r1 as linked registers in jmp_history 4: r2 = r10 | 5: r2 += r0 v mark_chain_precision(r0)
while doing mark_chain_precision(r0)
5: r2 += r0 | mark r0 precise 4: r2 = r10 | 3: if r0 > 16 goto ... | mark r0,r1 as precise 2: if r1 < 8 goto ... | mark r0,r1 as precise 1: r1 = r0 v
Technically, do this as follows:
- Use 10 bits to identify each register that gains range because of sync_linked_regs():
- 3 bits for frame number;
- 6 bits for register or stack slot number;
- 1 bit to indicate if register is spilled.
- Use u64 as a vector of 6 such records + 4 bits for vector length.
- Augment struct bpf_jmp_history_entry with a field 'linked_regs' representing such vector.
- When doing check_cond_jmp_op() remember up to 6 registers that gain range because of sync_linked_regs() in such a vector.
- Don't propagate range information and reset IDs for registers that don't fit in 6-value vector.
- Push a pair {instruction index, linked registers vector} to bpf_verifier_state->jmp_history.
- When doing backtrack_insn() check if any of recorded linked registers is currently marked precise, if so mark all linked registers as precise.
This also requires fixes for two test_verifier tests:
- precise: test 1
- precise: test 2
Both tests contain the following instruction sequence:
19: (bf) r2 = r9 ; R2=scalar(id=3) R9=scalar(id=3)
20: (a5) if r2 < 0x8 goto pc+1 ; R2=scalar(id=3,umin=8)
21: (95) exit
22: (07) r2 += 1 ; R2_w=scalar(id=3+1,...) 23: (bf) r1 = r10 ; R1_w=fp0 R10=fp0 24: (07) r1 += -8 ; R1_w=fp-8 25: (b7) r3 = 0 ; R3_w=0
26: (85) call bpf_probe_read_kernel#113
The call to bpf_probe_read_kernel() at (26) forces r2 to be precise. Previously, this forced all registers with same id to become precise immediately when mark_chain_precision() is called.
After this change, the precision is propagated to registers sharing same id only when 'if' instruction is backtracked.
Hence verification log for both tests is changed:
regs=r2,r9 -> regs=r2 for instructions 25..20.
--- include/linux/bpf_verifier.h | 4 + kernel/bpf/verifier.c | 248 ++++++++++++++++-- .../bpf/progs/verifier_subprog_precision.c | 2 +- .../testing/selftests/bpf/verifier/precise.c | 20 +- 4 files changed, 242 insertions(+), 32 deletions(-)
include/linux/bpf_verifier.h +4 -0
@@ -371,6 +371,10 @@ struct bpf_jmp_history_entry { u32 prev_idx : 22;/* special flags, e.g., whether insn is doing register stack spill/load */ u32 flags : 10; +/* additional registers that need precision tracking when this +* jump is backtracked, vector of six 10-bit records +*/ +u64 linked_regs; };/* Maximum number of register states that can exist at once */
kernel/bpf/verifier.c +227 -21
395 lines not on this page · raw message
tools/testing/selftests/bpf/progs/verifier_subprog_precision.c +1 -1
@@ -278,7 +278,7 @@ __msg("mark_precise: frame0: last_idx 14 first_idx 9") __msg("mark_precise: frame0: regs=r6 stack= before 13: (bf) r1 = r7") __msg("mark_precise: frame0: regs=r6 stack= before 12: (27) r6 *= 4") __msg("mark_precise: frame0: regs=r6 stack= before 11: (25) if r6 > 0x3 goto pc+4") -__msg("mark_precise: frame0: regs=r6 stack= before 10: (bf) r6 = r0") +__msg("mark_precise: frame0: regs=r0,r6 stack= before 10: (bf) r6 = r0")__msg ("mark_precise: frame0: regs=r0 stack= before 9: (85) call bpf_loop" ) /* State entering callback body popped from states stack */__msg ("from 9 to 17: frame1:" )
tools/testing/selftests/bpf/verifier/precise.c +10 -10
@@ -39,11 +39,11 @@ .result = VERBOSE_ACCEPT, .errstr ="mark_precise: frame0: last_idx 26 first_idx 20\ -mark_precise: frame0: regs=r2,r9 stack= before 25\ -mark_precise: frame0: regs=r2,r9 stack= before 24\ -mark_precise: frame0: regs=r2,r9 stack= before 23\ -mark_precise: frame0: regs=r2,r9 stack= before 22\ -mark_precise: frame0: regs=r2,r9 stack= before 20\ +mark_precise: frame0: regs=r2 stack= before 25\ +mark_precise: frame0: regs=r2 stack= before 24\ +mark_precise: frame0: regs=r2 stack= before 23\ +mark_precise: frame0: regs=r2 stack= before 22\ +mark_precise: frame0: regs=r2 stack= before 20\ mark_precise: frame0: parent state regs=r2,r9 stack=:\ mark_precise: frame0: last_idx 19 first_idx 10\ mark_precise: frame0: regs=r2,r9 stack= before 19\
@@ -100,11 +100,11 @@ .errstr ="26: (85) call bpf_probe_read_kernel#113\ mark_precise: frame0: last_idx 26 first_idx 22\ -mark_precise: frame0: regs=r2,r9 stack= before 25\ -mark_precise: frame0: regs=r2,r9 stack= before 24\ -mark_precise: frame0: regs=r2,r9 stack= before 23\ -mark_precise: frame0: regs=r2,r9 stack= before 22\ -mark_precise: frame0: parent state regs=r2,r9 stack=:\ +mark_precise: frame0: regs=r2 stack= before 25\ +mark_precise: frame0: regs=r2 stack= before 24\ +mark_precise: frame0: regs=r2 stack= before 23\ +mark_precise: frame0: regs=r2 stack= before 22\ +mark_precise: frame0: parent state regs=r2 stack=:\ mark_precise: frame0: last_idx 20 first_idx 20\ mark_precise: frame0: regs=r2,r9 stack= before 20\ mark_precise: frame0: parent state regs=r2,r9 stack=:\
Signature · 1 line
2.45.2
Re: [bpf-next v3 1/4] bpf: track equal scalars history on per-instruction level
Quoted 76 lines · Eduard Zingerman
Use
bpf_verifier_state->jmp_historyto track which registers were updated byfind_equal_scalars()(renamed tocollect_linked_regs()) when conditional jump was verified. Use recorded information inbacktrack_insn()to propagate precision.E.g. for the following program:
while verifying instructions
1: r1 = r0 | 2: if r1 < 8 goto ... | push r0,r1 as linked registers in jmp_history 3: if r0 > 16 goto ... | push r0,r1 as linked registers in jmp_history 4: r2 = r10 | 5: r2 += r0 v mark_chain_precision(r0)while doing
mark_chain_precision(r0)5: r2 += r0 | mark r0 precise 4: r2 = r10 | 3: if r0 > 16 goto ... | mark r0,r1 as precise 2: if r1 < 8 goto ... | mark r0,r1 as precise 1: r1 = r0 vTechnically, do this as follows:
- Use 10 bits to identify each register that gains range because ofsync_linked_regs():
- 3 bits for frame number;
- 6 bits for register or stack slot number;
- 1 bit to indicate if register is spilled.
- Use u64 as a vector of 6 such records + 4 bits for vector length.
- Augment structbpf_jmp_history_entrywith a field 'linked_regs' representing such vector.
- When doingcheck_cond_jmp_op()remember up to 6 registers that gain range because ofsync_linked_regs()in such a vector.
- Don't propagate range information and reset IDs for registers that don't fit in 6-value vector.
- Push a pair {instruction index, linked registers vector} tobpf_verifier_state->jmp_history.
- When doingbacktrack_insn()check if any of recorded linked registers is currently marked precise, if so mark all linked registers as precise.This also requires fixes for two
test_verifiertests:
- precise: test 1
- precise: test 2Both tests contain the following instruction sequence:
19: (bf) r2 = r9 ; R2=scalar(id=3) R9=scalar(id=3)
20: (a5) if r2 <0x8goto pc+1 ; R2=scalar(id=3,umin=8)
21: (95) exit22: (07) r2 += 1 ; R2_w=scalar(id=3+1,...) 23: (bf) r1 = r10 ; R1_w=fp0 R10=fp0 24: (07) r1 += -8 ; R1_w=fp-8 25: (b7) r3 = 0 ; R3_w=026: (85) call bpf_probe_read_kernel#113
The call to
bpf_probe_read_kernel()at (26) forces r2 to be precise. Previously, this forced all registers with same id to become precise immediately whenmark_chain_precision()is called.
After this change, the precision is propagated to registers sharing same id only when 'if' instruction is backtracked.
Hence verification log for both tests is changed:
regs=r2,r9 -> regs=r2 for instructions 25..20.Fixes 904e6ddf4133 ("bpf: Use scalar ids in mark_chain_precision()")Reported-by Hao Sun <[email protected]>Closes https://lore.kernel.org/bpf/CAEf4BzZ0xidVCqB47XnkXcNhkPWF6_nTV7yt+_Lf0kcFEut2Mg@mail.gmail.com/ open hereSuggested-by Andrii Nakryiko <[email protected]>Signed-off-by Eduard Zingerman <[email protected]>--- include/linux/bpf_verifier.h | 4 + kernel/bpf/verifier.c | 248 ++++++++++++++++-- .../bpf/progs/verifier_subprog_precision.c | 2 +- .../testing/selftests/bpf/verifier/precise.c | 20 +- 4 files changed, 242 insertions(+), 32 deletions(-)
[...]
Quoted 18 lines
kernel/bpf/verifier.c +18
-0+/* For all R being scalar registers or spilled scalar registers +* in verifier state, save R in linked_regs if R->id == id. +* If there are too many Rs sharing same id, reset id for leftover Rs. +*/ +static void collect_linked_regs (struct bpf_verifier_state *vstate,u32 id, +struct linked_regs *linked_regs) +{ +struct bpf_func_state *func; +struct bpf_reg_state *reg; +int i, j; + + id = id & ~BPF_ADD_CONST ; +for (i = vstate->curframe; i >=0 ; i--) { + func = vstate->frame[i]; +for (j =0 ; j <BPF_REG_FP ; j++) { + reg = &func->regs[j]; +__collect_linked_regs (linked_regs, reg, id, i, j, true); + }
kernel/bpf/verifier.c static bool try_match_pkt_pointers(const struct bpf_insn *insn, · line 15270
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+for (j =0 ; j < func->allocated_stack /BPF_REG_SIZE ; j++) { +if (!is_spilled_reg (&func->stack[j])) +continue ; + reg = &func->stack[j].spilled_ptr; +__collect_linked_regs (linked_regs, reg, id, i, j, false); + } + } + +if (linked_regs->cnt ==1 ) + linked_regs->cnt =0 ;
We discussed this rather ugly condition w/ Eduard offline. I agreed to drop it and change the condition linked_regs.cnt > 0 below to linked_regs.cnt > 1. It's unfortunate we can have one "self-linked" register, but it seems like unlinking the last remaining register would be prohibitively expensive (as we don't track how many linked registers for a given ID is there).
Anyways, if we ever come to solve this, we can update > 1 condition to a proper > 0 one. For now they are equivalent, so it doesn't really matter much.
Quoted 22 lines
kernel/bpf/verifier.c +13
-2+} + +/* For all R in linked_regs, copy known_reg range into R +* if R->id == known_reg->id. +*/ +static void sync_linked_regs (struct bpf_verifier_state *vstate,struct bpf_reg_state *known_reg, +struct linked_regs *linked_regs) {struct bpf_reg_state fake_reg; -struct bpf_func_state *state;struct bpf_reg_state *reg; +struct linked_reg *e; +int i; - bpf_for_each_reg_in_vstate(vstate, state, reg, ({ +for (i =0 ; i < linked_regs->cnt; ++i) { + e = &linked_regs->entries[i]; + reg = e->is_reg ? &vstate->frame[e->frameno]->regs[e->regno] + : &vstate->frame[e->frameno]->stack[e->spi].spilled_ptr;if (reg->type !=SCALAR_VALUE || reg == known_reg)continue ;if ((reg->id & ~BPF_ADD_CONST ) != (known_reg->id & ~BPF_ADD_CONST ))
[...]
Eduard Zingerman
maintainerPATCH v3 2/4 bpf: remove mark_precise_scalar_ids()
In reply to Eduard ZingermanFunction mark_precise_scalar_ids() is superseded by bt_sync_linked_regs() and equal scalars tracking in jump history. mark_precise_scalar_ids() propagates precision over registers sharing same ID on parent/child state boundaries, while jump history records allow bt_sync_linked_regs() to propagate same information with instruction level granularity, which is strictly more precise.
This commit removes mark_precise_scalar_ids() and updates test cases in progs/verifier_scalar_ids to reflect new verifier behavior.
The tests are updated in the following manner:
- mark_precise_scalar_ids() propagated precision regardless of presence of conditional jumps, while new jump history based logic only kicks in when conditional jumps are present.
Hence test cases are augmented with conditional jumps to still trigger precision propagation.
- As equal scalars tracking no longer relies on parent/child state boundaries some test cases are no longer interesting, such test cases are removed, namely:
- precision_same_state and precision_cross_state are superseded by
linked_regs_bpf_k;
- precision_same_state_broken_link and equal_scalars_broken_link are superseded by linked_regs_broken_link.
--- kernel/bpf/verifier.c | 115 ------------ .../selftests/bpf/progs/verifier_scalar_ids.c | 171 ++++++------------ .../testing/selftests/bpf/verifier/precise.c | 8 +- 3 files changed, 59 insertions(+), 235 deletions(-)
kernel/bpf/verifier.c +0 -115
@@ -4124,96 +4124,6 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ } } -static bool idset_contains (struct bpf_idset *s,u32 id) -{ -u32 i; - -for (i =0 ; i < s->count; ++i) -if (s->ids[i] == (id & ~BPF_ADD_CONST )) -return true; - -return false; -} - -static int idset_push (struct bpf_idset *s,u32 id) -{ -if (WARN_ON_ONCE (s->count >=ARRAY_SIZE (s->ids))) -return -EFAULT ; - s->ids[s->count++] = id & ~BPF_ADD_CONST ; -return 0 ; -} - -static void idset_reset (struct bpf_idset *s) -{ - s->count =0 ; -} - -/* Collect a set of IDs for all registers currently marked as precise in env->bt. -* Mark all registers with these IDs as precise. -*/ -static int mark_precise_scalar_ids (struct bpf_verifier_env *env,struct bpf_verifier_state *st) -{ -struct bpf_idset *precise_ids = &env->idset_scratch; -struct backtrack_state *bt = &env->bt; -struct bpf_func_state *func; -struct bpf_reg_state *reg; -DECLARE_BITMAP (mask,64 ); -int i, fr; - -idset_reset (precise_ids); - -for (fr = bt->frame; fr >=0 ; fr--) { - func = st->frame[fr]; - -bitmap_from_u64 (mask,bt_frame_reg_mask (bt, fr)); -for_each_set_bit (i, mask,32 ) { - reg = &func->regs[i]; -if (!reg->id || reg->type !=SCALAR_VALUE ) -continue ; -if (idset_push (precise_ids, reg->id)) -return -EFAULT ; - } - -bitmap_from_u64 (mask,bt_frame_stack_mask (bt, fr)); -for_each_set_bit (i, mask,64 ) { -if (i >= func->allocated_stack /BPF_REG_SIZE ) -break ; -if (!is_spilled_scalar_reg (&func->stack[i])) -continue ; - reg = &func->stack[i].spilled_ptr; -if (!reg->id) -continue ; -if (idset_push (precise_ids, reg->id)) -return -EFAULT ; - } - } - -for (fr =0 ; fr <= st->curframe; ++fr) { - func = st->frame[fr]; - -for (i =BPF_REG_0 ; i <BPF_REG_10 ; ++i) { - reg = &func->regs[i]; -if (!reg->id) -continue ; -if (!idset_contains (precise_ids, reg->id)) -continue ; -bt_set_frame_reg (bt, fr, i); - } -for (i =0 ; i < func->allocated_stack /BPF_REG_SIZE ; ++i) { -if (!is_spilled_scalar_reg (&func->stack[i])) -continue ; - reg = &func->stack[i].spilled_ptr; -if (!reg->id) -continue ; -if (!idset_contains (precise_ids, reg->id)) -continue ; -bt_set_frame_slot (bt, fr, i); - } - } - -return 0 ; -} -/* * __mark_chain_precision() backtracks BPF program instruction sequence and * chain of verifier states making sure that register *regno* (if regno >= 0)
@@ -4346,31 +4256,6 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno) bt->frame, last_idx, first_idx, subseq_idx); } -/* If some register with scalar ID is marked as precise, -* make sure that all registers sharing this ID are also precise. -* This is needed to estimate effect of find_equal_scalars(). -* Do this at the last instruction of each state, -* bpf_reg_state::id fields are valid for these instructions. -* -* Allows to track precision in situation like below: -* -* r2 = unknown value -* ... -* --- state #0 --- -* ... -* r1 = r2 // r1 and r2 now share the same ID -* ... -* --- state #1 {r1.id = A, r2.id = A} --- -* ... -* if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1 -* ... -* --- state #2 {r1.id = A, r2.id = A} --- -* r3 = r10 -* r3 += r1 // need to mark both r1 and r2 -*/ -if (mark_precise_scalar_ids (env, st)) -return -EFAULT ; -if (last_idx <0 ) {/* we are at the entry into subprog, which * is expected for global funcs, but only if
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c +55 -116
263 lines not on this page · raw message
tools/testing/selftests/bpf/verifier/precise.c +4 -4
@@ -106,7 +106,7 @@ mark_precise: frame0: regs=r2 stack= before 22\ mark_precise: frame0: parent state regs=r2 stack=:\ mark_precise: frame0: last_idx 20 first_idx 20\ - mark_precise: frame0: regs=r2,r9 stack= before 20\ + mark_precise: frame0: regs=r2 stack= before 20\ mark_precise: frame0: parent state regs=r2,r9 stack=:\ mark_precise: frame0: last_idx 19 first_idx 17\ mark_precise: frame0: regs=r2,r9 stack= before 19\
@@ -183,10 +183,10 @@ .prog_type = BPF_PROG_TYPE_XDP, .flags = BPF_F_TEST_STATE_FREQ, .errstr ="mark_precise: frame0: last_idx 7 first_idx 7\ -mark_precise: frame0: parent state regs=r4 stack=-8:\ +mark_precise: frame0: parent state regs=r4 stack=:\ mark_precise: frame0: last_idx 6 first_idx 4\ -mark_precise: frame0: regs=r4 stack=-8 before 6: (b7) r0 = -1\ -mark_precise: frame0: regs=r4 stack=-8 before 5: (79) r4 = *(u64 *)(r10 -8)\ +mark_precise: frame0: regs=r4 stack= before 6: (b7) r0 = -1\ +mark_precise: frame0: regs=r4 stack= before 5: (79) r4 = *(u64 *)(r10 -8)\ mark_precise: frame0: regs= stack=-8 before 4: (7b) *(u64 *)(r3 -8) = r0\ mark_precise: frame0: parent state regs=r0 stack=:\ mark_precise: frame0: last_idx 3 first_idx 3\
Signature · 1 line
2.45.2
Eduard Zingerman
maintainerPATCH v3 3/4 selftests/bpf: tests for per-insn sync_linked_regs() precision tracking
In reply to Eduard ZingermanAdd a few test cases to verify precision tracking for scalars gaining range because of sync_linked_regs():
- check what happens when more than 6 registers might gain range in sync_linked_regs();
- check if precision is propagated correctly when operand of conditional jump gained range in sync_linked_regs() and one of linked registers is marked precise;
- check if precision is propagated correctly when operand of conditional jump gained range in sync_linked_regs() and a other-linked operand of the conditional jump is marked precise;
- add a minimized reproducer for precision tracking bug reported in [0];
- Check that mark_chain_precision() for one of the conditional jump operands does not trigger equal scalars precision propagation.
[0] https://lore.kernel.org/bpf/CAEf4BzZ0xidVCqB47XnkXcNhkPWF6_nTV7yt+_Lf0kcFEut2Mg@mail.gmail.com/
--- .../selftests/bpf/progs/verifier_scalar_ids.c | 165 ++++++++++++++++++ 1 file changed, 165 insertions(+)
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c +165 -0
@@ -47,6 +47,72 @@ __naked void linked_regs_bpf_k(void) : __clobber_all); } +/* Registers r{0,1,2} share same ID when 'if r1 > ...' insn is processed, +* check that verifier marks r{1,2} as precise while backtracking +* 'if r1 > ...' with r0 already marked. +*/ +SEC("socket") +__success __log_level(2) +__flag(BPF_F_TEST_STATE_FREQ) +__msg("frame0: regs=r0 stack= before 5: (2d) if r1 > r3 goto pc+0") +__msg("frame0: parent state regs=r0,r1,r2,r3 stack=:") +__msg("frame0: regs=r0,r1,r2,r3 stack= before 4: (b7) r3 = 7") +__naked void linked_regs_bpf_x_src (void ) +{ + asmvolatile ( +/* r0 = random number up to 0xff */ +"call %[bpf_ktime_get_ns];" +"r0 &= 0xff;" +/* tie r0.id == r1.id == r2.id */ +"r1 = r0;" +"r2 = r0;" +"r3 = 7;" +"if r1 > r3 goto +0;" +/* force r0 to be precise, this eventually marks r1 and r2 as +* precise as well because of shared IDs +*/ +"r4 = r10;" +"r4 += r0;" +"r0 = 0;" +"exit;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} + +/* Registers r{0,1,2} share same ID when 'if r1 > r3' insn is processed, +* check that verifier marks r{0,1,2} as precise while backtracking +* 'if r1 > r3' with r3 already marked. +*/ +SEC("socket") +__success __log_level(2) +__flag(BPF_F_TEST_STATE_FREQ) +__msg("frame0: regs=r3 stack= before 5: (2d) if r1 > r3 goto pc+0") +__msg("frame0: parent state regs=r0,r1,r2,r3 stack=:") +__msg("frame0: regs=r0,r1,r2,r3 stack= before 4: (b7) r3 = 7") +__naked void linked_regs_bpf_x_dst (void ) +{ + asmvolatile ( +/* r0 = random number up to 0xff */ +"call %[bpf_ktime_get_ns];" +"r0 &= 0xff;" +/* tie r0.id == r1.id == r2.id */ +"r1 = r0;" +"r2 = r0;" +"r3 = 7;" +"if r1 > r3 goto +0;" +/* force r0 to be precise, this eventually marks r1 and r2 as +* precise as well because of shared IDs +*/ +"r4 = r10;" +"r4 += r3;" +"r0 = 0;" +"exit;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} +/* Same as linked_regs_bpf_k, but break one of the * links, note that r1 is absent from regs=... in __msg below. */
@@ -280,6 +346,105 @@ __naked void precision_two_ids(void) : __clobber_all); } +SEC("socket") +__success __log_level(2) +__flag(BPF_F_TEST_STATE_FREQ) +/* check thar r0 and r6 have different IDs after 'if', + * collect_linked_regs() can't tie more than 6 registers for a single insn. + */ +__msg("8: (25) if r0 > 0x7 goto pc+0 ; R0=scalar(id=1") +__msg ("9: (bf) r6 = r6 ; R6_w=scalar(id=2" ) +/* check that r{0-5} are marked precise after 'if' */ +__msg("frame0: regs=r0 stack= before 8: (25) if r0 > 0x7 goto pc+0") +__msg("frame0: parent state regs=r0,r1,r2,r3,r4,r5 stack=:") +__naked void linked_regs_too_many_regs (void ) +{ + asmvolatile ( +/* r0 = random number up to 0xff */ +"call %[bpf_ktime_get_ns];" +"r0 &= 0xff;" +/* tie r{0-6} IDs */ +"r1 = r0;" +"r2 = r0;" +"r3 = r0;" +"r4 = r0;" +"r5 = r0;" +"r6 = r0;" +/* propagate range for r{0-6} */ +"if r0 > 7 goto +0;" +/* make r6 appear in the log */ +"r6 = r6;" +/* force r0 to be precise, +* this would cause r{0-4} to be precise because of shared IDs +*/ +"r7 = r10;" +"r7 += r0;" +"r0 = 0;" +"exit;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} + +SEC("socket") +__failure __log_level(2) +__flag(BPF_F_TEST_STATE_FREQ) +__msg("regs=r7 stack= before 5: (3d) if r8 >= r0") +__msg("parent state regs=r0,r7,r8") +__msg("regs=r0,r7,r8 stack= before 4: (25) if r0 > 0x1") +__msg("div by zero") +__naked void linked_regs_broken_link_2 (void ) +{ + asmvolatile ( +"call %[bpf_get_prandom_u32];" +"r7 = r0;" +"r8 = r0;" +"call %[bpf_get_prandom_u32];" +"if r0 > 1 goto +0;" +/* r7.id == r8.id, +* thus r7 precision implies r8 precision, +* which implies r0 precision because of the conditional below. +*/ +"if r8 >= r0 goto 1f;" +/* break id relation between r7 and r8 */ +"r8 += r8;" +/* make r7 precise */ +"if r7 == 0 goto 1f;" +"r0 /= 0;" +"1:" +"r0 = 42;" +"exit;" + : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* Check that mark_chain_precision() for one of the conditional jump +* operands does not trigger equal scalars precision propagation. +*/ +SEC("socket") +__success __log_level(2) +__msg("3: (25) if r1 > 0x100 goto pc+0") +__msg("frame0: regs=r1 stack= before 2: (bf) r1 = r0") +__naked void cjmp_no_linked_regs_trigger (void ) +{ + asmvolatile ( +/* r0 = random number up to 0xff */ +"call %[bpf_ktime_get_ns];" +"r0 &= 0xff;" +/* tie r0.id == r1.id */ +"r1 = r0;" +/* the jump below would be predicted, thus r1 would be marked precise, +* this should not imply precision mark for r0 +*/ +"if r1 > 256 goto +0;" +"r0 = 0;" +"exit;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} +/* Verify that check_ids() is used by regsafe() for scalars. * * r9 = ... some pointer with range X ...
Signature · 1 line
2.45.2
Eduard Zingerman
maintainerPATCH v3 4/4 selftests/bpf: update comments find_equal_scalars->sync_linked_regs
In reply to Eduard Zingermanfind_equal_scalars() is renamed to sync_linked_regs(), this commit updates existing references in the selftests comments.
--- .../selftests/bpf/progs/verifier_spill_fill.c | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-)
tools/testing/selftests/bpf/progs/verifier_spill_fill.c +8 -8
@@ -402,7 +402,7 @@ __naked void spill_32bit_of_64bit_fail(void) *(u32 *)(r10 -8 ) = r1; \/* 32-bit fill r2 from stack. */ \ r2 = *(u32 *)(r10 -8 ); \ -/* Compare r2 with another register to trigger find_equal_scalars.\ +/* Compare r2 with another register to trigger sync_linked_regs.\ * Having one random bit is important here, otherwise the verifier cuts\ * the corners. If the ID was mistakenly preserved on spill, this would\ * cause the verifier to think that r1 is also equal to zero in one of\
@@ -441,7 +441,7 @@ __naked void spill_16bit_of_32bit_fail(void) *(u16 *)(r10 -8 ) = r1; \/* 16-bit fill r2 from stack. */ \ r2 = *(u16 *)(r10 -8 ); \ -/* Compare r2 with another register to trigger find_equal_scalars.\ +/* Compare r2 with another register to trigger sync_linked_regs.\ * Having one random bit is important here, otherwise the verifier cuts\ * the corners. If the ID was mistakenly preserved on spill, this would\ * cause the verifier to think that r1 is also equal to zero in one of\
@@ -833,7 +833,7 @@ __naked void spill_64bit_of_64bit_ok(void) *(u64 *)(r10 -8 ) = r0; \/* 64-bit fill r1 from stack - should preserve the ID. */ \ r1 = *(u64 *)(r10 -8 ); \ -/* Compare r1 with another register to trigger find_equal_scalars.\ +/* Compare r1 with another register to trigger sync_linked_regs.\ * Having one random bit is important here, otherwise the verifier cuts\ * the corners. \ */ \
@@ -866,7 +866,7 @@ __naked void spill_32bit_of_32bit_ok(void) *(u32 *)(r10 -8 ) = r0; \/* 32-bit fill r1 from stack - should preserve the ID. */ \ r1 = *(u32 *)(r10 -8 ); \ -/* Compare r1 with another register to trigger find_equal_scalars.\ +/* Compare r1 with another register to trigger sync_linked_regs.\ * Having one random bit is important here, otherwise the verifier cuts\ * the corners. \ */ \
@@ -899,7 +899,7 @@ __naked void spill_16bit_of_16bit_ok(void) *(u16 *)(r10 -8 ) = r0; \/* 16-bit fill r1 from stack - should preserve the ID. */ \ r1 = *(u16 *)(r10 -8 ); \ -/* Compare r1 with another register to trigger find_equal_scalars.\ +/* Compare r1 with another register to trigger sync_linked_regs.\ * Having one random bit is important here, otherwise the verifier cuts\ * the corners. \ */ \
@@ -932,7 +932,7 @@ __naked void spill_8bit_of_8bit_ok(void) *(u8 *)(r10 -8 ) = r0; \/* 8-bit fill r1 from stack - should preserve the ID. */ \ r1 = *(u8 *)(r10 -8 ); \ -/* Compare r1 with another register to trigger find_equal_scalars.\ +/* Compare r1 with another register to trigger sync_linked_regs.\ * Having one random bit is important here, otherwise the verifier cuts\ * the corners. \ */ \
@@ -1029,7 +1029,7 @@ __naked void fill_32bit_after_spill_64bit_preserve_id(void)"r1 = *(u32*)(r10 - 4);" #endif" \ -/* Compare r1 with another register to trigger find_equal_scalars. */\ +/* Compare r1 with another register to trigger sync_linked_regs. */\ r2 = 0; \ if r1 != r2 goto l0_%=; \ /* The result of this comparison is predefined. */\
@@ -1070,7 +1070,7 @@ __naked void fill_32bit_after_spill_64bit_clear_id(void)"r2 = *(u32*)(r10 - 4);" #endif" \ -/* Compare r2 with another register to trigger find_equal_scalars.\ +/* Compare r2 with another register to trigger sync_linked_regs.\ * Having one random bit is important here, otherwise the verifier cuts\ * the corners. If the ID was mistakenly preserved on fill, this would\ * cause the verifier to think that r1 is also equal to zero in one of\
Signature · 1 line
2.45.2
This series was applied to bpf/bpf-next.git (master) by Andrii Nakryiko <[email protected]>:
Hello:
This series was applied to bpf/bpf-next.git (master) by Andrii Nakryiko <[email protected]>:
Quoted 19 lines · On Thu, 18 Jul 2024 13:23:52 -0700 you wrote:
This is a fix for precision tracking bug reported in [0]. It supersedes my previous attempt to fix similar issue in commit [1]. Here is a minimized test case from [0]:
0: call bpf_get_prandom_u32; 1: r7 = r0; 2: r8 = r0; 3: call bpf_get_prandom_u32; 4: if r0 > 1 goto +0; /* --- checkpoint #1: r7.id=1, r8.id=1 --- */ 5: if r8 >= r0 goto 9f; 6: r8 += r8; /* --- checkpoint #2: r7.id=1, r8.id=0 --- */ 7: if r7 == 0 goto 9f; 8: r0 /= 0; /* --- checkpoint #3 --- */ 9: r0 = 42; 10: exit;
Quoted 1 line
[...]
Here is the summary with links:
- [bpf-next,v3,1/4] bpf: track equal scalars history on per-instruction level
https://git.kernel.org/bpf/bpf-next/c/2b7350d7ca65 - [bpf-next,v3,2/4] bpf: remove mark_precise_scalar_ids() https://git.kernel.org/bpf/bpf-next/c/cb0f94d85874 - [bpf-next,v3,3/4] selftests/bpf: tests for per-insn sync_linked_regs() precision tracking https://git.kernel.org/bpf/bpf-next/c/c0087d59e504 - [bpf-next,v3,4/4] selftests/bpf: update comments find_equal_scalars->sync_linked_regs https://git.kernel.org/bpf/bpf-next/c/f081cd17c0bc
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html