Skip to content

verify scalar ids mapping in regsafe()

Eduard Zingerman bpf 6 versions – Applied

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

  1. v6 Latest4 patches 0 repliesApplied 4/4
  2. v54 patches 7 repliesSuperseded
  3. v44 patches 3 repliesSuperseded
Earlier versions · 3
VersionPostedPatchesRepliesStatus
v34 patches16 repliesSuperseded
v24 patches28 repliesSuperseded
v12 patches5 repliesSuperseded

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 filesSizeRepliesApplied
1/4bpf: use scalar ids in mark_chain_precision()include/linux/bpf_verifier.h kernel/bpf/verifier.c tools/testing/selftests/bpf/verifier/precise.c+128 -50 repliesApplied
2/4selftests/bpf: check if mark_chain_precision() follows scalar idstools/testing/selftests/bpf/prog_tests/verifier.c tools/testing/selftests/bpf/progs/verifier_scalar_ids.c+346 -00 repliesApplied
3/4bpf: verify scalar ids mapping in regsafe() using check_ids()include/linux/bpf_verifier.h kernel/bpf/verifier.c+79 -290 repliesApplied
4/4selftests/bpf: verify that check_ids() is used for scalars in regsafe()tools/testing/selftests/bpf/progs/verifier_scalar_ids.c+315 -00 repliesApplied

Reviews trailers per patch

3 of 4 patches have a Reviewed-by or Acked-by.

PatchAndrii Nakryiko
1/4A-b
2/4A-b
3/4A-b
4/4

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v6 thread

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