From: Alexei Starovoitov <ast@fb.com>
To: Andrii Nakryiko <andrii.nakryiko@gmail.com>,
Alexei Starovoitov <ast@kernel.org>
Cc: "David S. Miller" <davem@davemloft.net>,
Daniel Borkmann <daniel@iogearbox.net>,
Networking <netdev@vger.kernel.org>, bpf <bpf@vger.kernel.org>,
Kernel Team <Kernel-team@fb.com>
Subject: Re: [PATCH v3 bpf-next 0/9] bpf: bounded loops and other features
Date: Mon, 17 Jun 2019 18:57:40 +0000 [thread overview]
Message-ID: <70187096-9876-b004-0ccb-8293618f384f@fb.com> (raw)
In-Reply-To: <CAEf4BzY_w-tTQFy_MfSvRwS4uDziNLRN+Jax4WXidP9R-s961w@mail.gmail.com>
On 6/17/19 9:39 AM, Andrii Nakryiko wrote:
> On Sat, Jun 15, 2019 at 12:12 PM Alexei Starovoitov <ast@kernel.org> wrote:
>>
>> v2->v3: fixed issues in backtracking pointed out by Andrii.
>> The next step is to add a lot more tests for backtracking.
>>
>
> Tests would be great, verifier complexity is at the level, where it's
> very easy to miss issues.
>
> Was fuzzying approach ever discussed for BPF verifier? I.e., have a
> fuzzer to generate both legal and illegal random small programs. Then
> re-implement verifier as user-level program with straightforward
> recursive exhaustive verification (so no state pruning logic, no
> precise/coarse, etc, just register/stack state tracking) of all
> possible branches. If kernel verifier's verdict differs from
> user-level verifier's verdict - flag that as a test case and figure
> out why they differ. Obviously that would work well only for small
> programs, but that should be a good first step already.
>
> In addition, if this is done, that user-land verifier can be a HUGE
> help to BPF application developers, as libbpf would (potentially) be
> able to generate better error messages using it as well.
In theory that sounds good, but doesn't work in practice.
The kernel verifier keeps changing faster than user space can catch up.
It's also relying on loaded maps and all sorts of callbacks that
check context, allowed helpers, maps, combinations of them from all
over the kernel.
The last effort to build kernel verifier as-is into .o and link
with kmalloc/map wrappers in user space was here:
https://github.com/iovisor/bpf-fuzzer
It was fuzzing the verifier and was able to find few minor bugs.
But it quickly bit rotted.
Folks brought up in the past the idea to collect user space
verifiers from different kernels, so that user space tooling can
check whether particular program will load on a set of kernels
without need to run them in VMs.
Even if such feature existed today it won't really solve this production
headache, since all kernels prior to today will not be covered.
I think syzbot is still generating bpf programs. iirc it found
one bug in the past in the verifier core.
I think the only way to make verifier more robust is to keep
adding new test cases manually.
Most interesting bugs we found by humans.
Another approach to 'better error message' that was considered
in the past was to teach llvm to recognize things that verifier
will reject and let llvm warn on them.
But it's also not practical. We had llvm error on calls.
Then we added them to the verifier and had to change llvm.
If we had llvm error on loops, now we'd need to change it.
imo it's better to let llvm handle everything.
next prev parent reply other threads:[~2019-06-17 18:58 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-06-15 19:12 [PATCH v3 bpf-next 0/9] bpf: bounded loops and other features Alexei Starovoitov
2019-06-15 19:12 ` [PATCH v3 bpf-next 1/9] bpf: track spill/fill of constants Alexei Starovoitov
2019-06-20 0:24 ` John Fastabend
2019-06-20 3:35 ` Alexei Starovoitov
2019-06-20 5:04 ` John Fastabend
2019-06-20 15:37 ` Alexei Starovoitov
2019-06-15 19:12 ` [PATCH v3 bpf-next 2/9] selftests/bpf: fix tests due to const spill/fill Alexei Starovoitov
2019-06-20 5:40 ` John Fastabend
2019-06-15 19:12 ` [PATCH v3 bpf-next 3/9] bpf: extend is_branch_taken to registers Alexei Starovoitov
2019-06-20 6:01 ` John Fastabend
2019-06-15 19:12 ` [PATCH v3 bpf-next 4/9] bpf: introduce bounded loops Alexei Starovoitov
2019-06-20 9:59 ` [bpf] 9fe4f05d33: kernel_selftests.bpf.test_verifier.fail kernel test robot
2019-06-15 19:12 ` [PATCH v3 bpf-next 5/9] bpf: fix callees pruning callers Alexei Starovoitov
2019-06-15 19:12 ` [PATCH v3 bpf-next 6/9] selftests/bpf: fix tests Alexei Starovoitov
2019-06-15 19:12 ` [PATCH v3 bpf-next 7/9] selftests/bpf: add basic verifier tests for loops Alexei Starovoitov
2019-06-15 19:12 ` [PATCH v3 bpf-next 8/9] selftests/bpf: add realistic loop tests Alexei Starovoitov
2019-06-15 19:12 ` [PATCH v3 bpf-next 9/9] bpf: precise scalar_value tracking Alexei Starovoitov
2019-06-17 17:20 ` Andrii Nakryiko
2019-06-17 16:39 ` [PATCH v3 bpf-next 0/9] bpf: bounded loops and other features Andrii Nakryiko
2019-06-17 18:57 ` Alexei Starovoitov [this message]
2019-06-17 19:06 ` Andrii Nakryiko
2019-06-18 14:05 ` Paul Chaignon
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=70187096-9876-b004-0ccb-8293618f384f@fb.com \
--to=ast@fb.com \
--cc=Kernel-team@fb.com \
--cc=andrii.nakryiko@gmail.com \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=davem@davemloft.net \
--cc=netdev@vger.kernel.org \
/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).