verify scalar ids mapping in regsafe()
Status from this message: This series was applied to bpf/bpf-next.git (master)
Get series with b4
b4 am [email protected]Versions newest first · linked by author and title
- v6 Latest4 patches 0 repliesApplied 4/4
- v54 patches 7 repliesSuperseded
- v44 patches 3 repliesSuperseded
Earlier versions · 3
| Version | Posted | Patches | Replies | Status |
|---|---|---|---|---|
| v3 | 4 patches | 16 replies | Superseded | |
| v2 | 4 patches | 28 replies | Superseded | |
| v1 | 2 patches | 5 replies | Superseded |
Changelog from the cover letter
- V5 -> V6:
- check_ids() is modified to disallow mapping different 'old_id' to
Patches in v6 All 4 applied
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/4 | bpf: use scalar ids in mark_chain_precision()include/ kernel/ tools/ | +128 | 0 replies | Applied |
| 2/4 | selftests/bpf: check if mark_chain_precision() follows scalar idstools/ tools/ | +346 | 0 replies | Applied |
| 3/4 | bpf: verify scalar ids mapping in regsafe() using check_ids()include/ kernel/ | +79 | 0 replies | Applied |
| 4/4 | selftests/bpf: verify that check_ids() is used for scalars in regsafe()tools/ | +315 | 0 replies | Applied |
Reviews trailers per patch
3 of 4 patches have a Reviewed-by or Acked-by.
| Patch | Andrii Nakryiko |
|---|---|
| 1/4 | A-b |
| 2/4 | A-b |
| 3/4 | A-b |
| 4/4 |
Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.
Cover letter [PATCH bpf-next v6 0/4] verify scalar ids mapping in regsafe()
Update regsafe() to use check_ids() for scalar values. Otherwise the following unsafe pattern is accepted by verifier:
1: r9 = ... some pointer with range X ...
2: r6 = ... unbound scalar ID=a ...
3: r7 = ... unbound scalar ID=b ...
4: if (r6 > r7) goto +1
5: r6 = r7
6: if (r6 > X) goto ...
--- checkpoint ---
7: r9 += r7
8: *(u64 *)r9 = Y
This example is unsafe because not all execution paths verify r7 range. Because of the jump at (4) the verifier would arrive at (6) in two states:
I. r6{.id=b}, r7{.id=b} via path 1-6;
II. r6{.id=a}, r7{.id=b} via path 1-4, 6.
Currently regsafe() does not call check_ids() for scalar registers, thus from POV of regsafe() states (I) and (II) are identical.
The change is split in two parts:
- patches #1,2: update for mark_chain_precision() to propagate precision marks through scalar IDs.
- patches #3,4: update for regsafe() to use a special version of check_ids() for precise scalar values.
Changelog:
- V5 -> V6:
- check_ids() is modified to disallow mapping different 'old_id' to
the same 'cur_id', check_scalar_ids() simplified (Andrii);
- idset_push() updated to return -EFAULT instead of -1 (Andrii);
- comments fixed in check_ids_in_regsafe() test case
(Maxim Mikityanskiy); - fixed memset warning in states_equal() reported in [4].
- V4 -> V5 (all changes are based on feedback for V4 from Andrii):
- mark_precise_scalar_ids() error code is updated to EFAULT;
- bpf_verifier_env::idmap_scratch field type is changed to struct
bpf_idmap to encapsulate temporary ID generation counter;
- regsafe() is updated to call scalar_regs_exact() only for env->explore_alu_limits case (this had no measurable impact on verification duration when tested using veristat).
- V3 -> V4:
- check_ids() in regsafe() is replaced by check_scalar_ids(), as discussed with Andrii in [3],
Note: I did not transfer Andrii's ack for patch #3 from V3 because
of the changes to the algorithm.
- reg_id_scratch is renamed to idset_scratch;
- mark_precise_scalar_ids() is modified to propagate error from
idset_push();
- test cases adjusted according to feedback from Andrii for V3.
- V2 -> V3:
- u32_hashset for IDs used for range transfer is removed;
- mark_chain_precision() is updated as discussed with Andrii in [2].
- V1 -> v2:
- 'rold->precise' and 'rold->id' checks are dropped as unsafe
(thanks to discussion with Yonghong);
- patches #3,4 adding tracking of ids used for range transfer in order to mitigate performance impact.
- RFC -> V1:
- Function verifier.c:mark_equal_scalars_as_read() is dropped, as it was an incorrect fix for problem solved by commit [3].
- check_ids() is called only for precise scalar values.
- Test case updated to use inline assembly.
[V1] https://lore.kernel.org/bpf/[email protected]/ [V2] https://lore.kernel.org/bpf/[email protected]/ [V3] https://lore.kernel.org/bpf/[email protected]/ [V4] https://lore.kernel.org/bpf/[email protected]/ [V5] https://lore.kernel.org/bpf/[email protected]/ [RFC] https://lore.kernel.org/bpf/[email protected]/ [1] https://gist.github.com/eddyz87/a32ea7e62a27d3c201117c9a39ab4286 [2] https://lore.kernel.org/bpf/[email protected]/T/#mc21009dcd8574b195c1860a98014bb037f16f450 [3] https://lore.kernel.org/bpf/[email protected]/T/#m89da8eeb2fa8c9ca1202c5d0b6660e1f72e45e04 [4] https://lore.kernel.org/oe-kbuild-all/[email protected]/
Eduard Zingerman (4):
bpf: use scalar ids in mark_chain_precision() selftests/bpf: check if mark_chain_precision() follows scalar ids
bpf: verify scalar ids mapping in regsafe() using check_ids() selftests/bpf: verify that check_ids() is used for scalars in
regsafe()
include/linux/bpf_verifier.h | 25 +- kernel/bpf/verifier.c | 206 +++++- .../selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/verifier_scalar_ids.c | 659 ++++++++++++++++++ .../testing/selftests/bpf/verifier/precise.c | 8 +- 5 files changed, 867 insertions(+), 33 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
Signature · 1 line
2.40.1