From: Eduard Zingerman <eddyz87@gmail.com>
To: bpf@vger.kernel.org, ast@kernel.org
Cc: andrii@kernel.org, daniel@iogearbox.net, kernel-team@fb.com,
yhs@fb.com, Eduard Zingerman <eddyz87@gmail.com>
Subject: [RFC bpf-next 0/2] bpf: verify scalar ids mapping in regsafe() using check_ids()
Date: Mon, 28 Nov 2022 18:34:40 +0200 [thread overview]
Message-ID: <20221128163442.280187-1-eddyz87@gmail.com> (raw)
Currently the following test case is considered safe by the 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 ... ; <-- suppose checkpoint state is created here
7: r9 += r7
8: *(u64 *)r9 = Y
This happens because function regsafe() used (indirectly) form
is_state_visited() does not compare id mapping for scalar registers.
The following patch makes two chages:
- regsafe() is updated to use check_ids() for scalar registers;
- registers that obtain their range via find_equal_scalars() are
marked as read in the parent checkpoint states. See
mark_equal_scalars_as_read() for detailed explanation.
However, I'm not sure if mark_equal_scalars_as_read() is sufficient or
mark_chain_precision() should be called / updated as well.
In current form the patch does not have a big impact on the tests
verification time, as checked on BPF object files listed in
tools/testing/selftests/bpf/veristat.cfg and Cilium object files
obtained from [1]:
./veristat -e file,prog,insns,states -f 'insns_diff!=0' -C master.log current.log
File Program Insns (A) Insns (B) Insns (DIFF) States (A) States (B) States (DIFF)
----------- ----------------------- --------- --------- --------------- ---------- ---------- -------------
bpf_host.o cil_from_host 556 603 +47 (+8.45%) 37 41 +4 (+10.81%)
bpf_xdp.o tail_lb_ipv4 77248 77302 +54 (+0.07%) 4643 4646 +3 (+0.06%)
loop6.bpf.o trace_virtqueue_add_sgs 15144 18594 +3450 (+22.78%) 337 403 +66 (+19.58%)
A tweak adding !tnum_is_const(src_reg->var_off) in check_alu_op() is
necessary to achieve this.
[1] git@github.com:anakryiko/cilium.git
Eduard Zingerman (2):
bpf: verify scalar ids mapping in regsafe() using check_ids()
selftests/bpf: verify that check_ids() is used for scalars in
regsafe()
kernel/bpf/verifier.c | 87 ++++++++++++++++++-
.../selftests/bpf/verifier/scalar_ids.c | 61 +++++++++++++
2 files changed, 146 insertions(+), 2 deletions(-)
create mode 100644 tools/testing/selftests/bpf/verifier/scalar_ids.c
--
2.34.1
next reply other threads:[~2022-11-28 16:35 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-11-28 16:34 Eduard Zingerman [this message]
2022-11-28 16:34 ` [RFC bpf-next 1/2] bpf: verify scalar ids mapping in regsafe() using check_ids() Eduard Zingerman
2022-12-01 0:26 ` Andrii Nakryiko
2022-12-01 1:14 ` Eduard Zingerman
2022-12-01 18:33 ` Eduard Zingerman
2022-12-02 22:48 ` Eduard Zingerman
2022-11-28 16:34 ` [RFC bpf-next 2/2] selftests/bpf: verify that check_ids() is used for scalars in regsafe() 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=20221128163442.280187-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=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).