From: Eduard Zingerman <eddyz87@gmail.com>
To: bpf@vger.kernel.org, ast@kernel.org
Cc: andrii@kernel.org, daniel@iogearbox.net, martin.lau@linux.dev,
kernel-team@fb.com, yhs@fb.com,
Eduard Zingerman <eddyz87@gmail.com>
Subject: [PATCH bpf-next v5 0/4] verify scalar ids mapping in regsafe()
Date: Mon, 12 Jun 2023 19:07:57 +0300 [thread overview]
Message-ID: <20230612160801.2804666-1-eddyz87@gmail.com> (raw)
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:
- 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/20230526184126.3104040-1-eddyz87@gmail.com/
[V2] https://lore.kernel.org/bpf/20230530172739.447290-1-eddyz87@gmail.com/T/
[V3] https://lore.kernel.org/bpf/20230606222411.1820404-1-eddyz87@gmail.com/T/
[V4] https://lore.kernel.org/bpf/20230609210143.2625430-1-eddyz87@gmail.com/
[RFC] https://lore.kernel.org/bpf/20221128163442.280187-1-eddyz87@gmail.com/
[1] https://gist.github.com/eddyz87/a32ea7e62a27d3c201117c9a39ab4286
[2] https://lore.kernel.org/bpf/20230530172739.447290-1-eddyz87@gmail.com/T/#mc21009dcd8574b195c1860a98014bb037f16f450
[3] https://lore.kernel.org/bpf/20230606222411.1820404-1-eddyz87@gmail.com/T/#m89da8eeb2fa8c9ca1202c5d0b6660e1f72e45e04
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 | 223 +++++-
.../selftests/bpf/prog_tests/verifier.c | 2 +
.../selftests/bpf/progs/verifier_scalar_ids.c | 657 ++++++++++++++++++
.../testing/selftests/bpf/verifier/precise.c | 8 +-
5 files changed, 883 insertions(+), 32 deletions(-)
create mode 100644 tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
--
2.40.1
next reply other threads:[~2023-06-12 16:08 UTC|newest]
Thread overview: 13+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-06-12 16:07 Eduard Zingerman [this message]
2023-06-12 16:07 ` [PATCH bpf-next v5 1/4] bpf: use scalar ids in mark_chain_precision() Eduard Zingerman
2023-06-12 19:56 ` Andrii Nakryiko
2023-06-12 16:07 ` [PATCH bpf-next v5 2/4] selftests/bpf: check if mark_chain_precision() follows scalar ids Eduard Zingerman
2023-06-12 16:08 ` [PATCH bpf-next v5 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids() Eduard Zingerman
2023-06-12 19:56 ` Andrii Nakryiko
2023-06-12 21:01 ` Eduard Zingerman
2023-06-13 0:10 ` Eduard Zingerman
2023-06-13 0:28 ` Andrii Nakryiko
2023-06-13 8:02 ` kernel test robot
2023-06-12 16:08 ` [PATCH bpf-next v5 4/4] selftests/bpf: verify that check_ids() is used for scalars in regsafe() Eduard Zingerman
2023-06-12 17:40 ` Maxim Mikityanskiy
2023-06-12 19:42 ` Eduard Zingerman
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20230612160801.2804666-1-eddyz87@gmail.com \
--to=eddyz87@gmail.com \
--cc=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=kernel-team@fb.com \
--cc=martin.lau@linux.dev \
--cc=yhs@fb.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).