Re: [PATCH RFC v2 net-next 10/16] bpf: add eBPF verifier

On Tue, Aug 12, 2014 at 1:10 PM, Andy Lutomirski [off-list ref] wrote:

On Tue, Aug 12, 2014 at 1:00 PM, Alexei Starovoitov [off-list ref] wrote:

quoted

On Tue, Aug 12, 2014 at 12:32 PM, Andy Lutomirski [off-list ref] wrote:

quoted

On Thu, Jul 24, 2014 at 12:25 PM, Alexei Starovoitov [off-list ref] wrote:

quoted

On Thu, Jul 24, 2014 at 11:25 AM, Andy Lutomirski [off-list ref] wrote:

quoted

On Thu, Jul 17, 2014 at 9:20 PM, Alexei Starovoitov [off-list ref] wrote:

quoted

Safety of eBPF programs is statically determined by the verifier, which detects:
- loops
- out of range jumps
- unreachable instructions
- invalid instructions
- uninitialized register access
- uninitialized stack access
- misaligned stack access
- out of range stack access
- invalid calling convention

Is there something that documents exactly what conditions an eBPF
program must satisfy in order to be considered valid?

I did a writeup in the past on things that verifiers checks and gave it
to internal folks to review. Guys have said that now they understand very
well how it works, but in reality it didn't help at all to write valid programs.
What worked is 'verification trace' = the instruction by instruction dump
of verifier state while it's analyzing the program.
I gave few simple examples of it in
'Understanding eBPF verifier messages' section:
https://git.kernel.org/cgit/linux/kernel/git/ast/bpf.git/diff/Documentation/networking/filter.txt?id=b22459133b9f52d2176c8c0f8b5eb036478a40c9
Every example there is what "program must satisfy to be valid"...

Therefore I'm addressing two things:
1. how verifier works and what it checks for.
  that is described in 'eBPF verifier' section of the doc and
  in 200 lines of comments inside verifier.c

That doc is pretty good.  I'll try to read it carefully soon.  Sorry
for the huge delay here -- I've been on vacation.

I've been sitting on v4 for few weeks, since it's a merge window.
So please hold on a careful review. I'll post v4 later today.
Mainly I've split the verifier into several patches to make it
easier to read.
Thanks!

Will you be at KS / LSS / LinuxCon?

I would love to, but I didn't get an invite for KS.
I'll be at plumbers in October.