Message-ID: <20181212160210.45b2b1ff@cakuba.netronome.com>
Date:   Wed, 12 Dec 2018 16:02:10 -0800
From:   Jakub Kicinski <jakub.kicinski@...ronome.com>
To:     Edward Cree <ecree@...arflare.com>
Cc:     <alexei.starovoitov@...il.com>, <daniel@...earbox.net>,
        <oss-drivers@...ronome.com>, <netdev@...r.kernel.org>
Subject: Re: [PATCH bpf] bpf: verifier: make sure callees don't prune with
 caller differences

On Wed, 12 Dec 2018 20:28:07 +0000, Edward Cree wrote:
> On 10/12/18 19:35, Jakub Kicinski wrote:
> > Currently for liveness and state pruning the register parentage
> > chains don't include states of the callee.  This makes some sense
> > as the callee can't access those registers.  However, this means
> > that READs done after the callee returns will not propagate into
> > the states of the callee.  Callee will then perform pruning
> > disregarding differences in caller state.
> >
> > Example:
> >
> >    0: (85) call bpf_user_rnd_u32
> >    1: (b7) r8 = 0
> >    2: (55) if r0 != 0x0 goto pc+1
> >    3: (b7) r8 = 1
> >    4: (bf) r1 = r8
> >    5: (85) call pc+4
> >    6: (15) if r8 == 0x1 goto pc+1
> >    7: (05) *(u64 *)(r9 - 8) = r3
> >    8: (b7) r0 = 0
> >    9: (95) exit
> >
> >    10: (15) if r1 == 0x0 goto pc+0
> >    11: (95) exit
> >
> > Here we acquire unknown state with call to get_random() [1].  Then
> > we store this random state in r8 (either 0 or 1) [1 - 3], and make
> > a call on line 5.  Callee does nothing but a trivial conditional
> > jump (to create a pruning point).  Upon return caller checks the
> > state of r8 and either performs an unsafe read or not.
> >
> > Verifier will first explore the path with r8 == 1, creating a pruning
> > point at [11].  The parentage chain for r8 will include only callers
> > states so once verifier reaches [6] it will mark liveness only on states
> > in the caller, and not [11].  Now when verifier walks the paths with
> > r8 == 0 it will reach [11] and since REG_LIVE_READ on r8 was not
> > propagated there it will prune the walk entirely (stop walking
> > the entire program, not just the callee).  Since [6] was never walked
> > with r8 == 0, [7] will be considered dead and replaced with "goto -1"
> > causing hang at runtime.
> >
> > This patch weaves the callee's explored states onto the callers
> > parentage chain.  
> Could you describe this in a little more detail?
> 
> In particular I'm not sure why anything that knows the difference between
>  caller- and callee-saved regs belongs in is_state_visited() rather than
>  check_func_call().  

I will put those two "diagrams" into the next revision, I think they
help (these are rough, placement of SLs on 1 and 4 is not precise but
otherwise it's hard to draw):

Parentage before:

[0] [1] [2] [3] [4] [5]   [10]      [11]      [6]      [7]
     |           |      ,---|----.    |        |        |
  sl0:         sl0:    / sl0:     \ sl0:      sl0:     sl0: 
  fr0: r8 <-- fr0: r8<+--fr0: r8   `fr0: r8  ,fr0: r8<-fr0: r8
                       \ fr1: r8 <- fr1: r8 /
                        \__________________/

Parentage after:

[0] [1] [2] [3] [4] [5]   [10]      [11]      [6]      [7]
     |           |          |         |        |        |
  sl0:         sl0:      sl0:       sl0:      sl0:     sl0: 
  fr0: r8 <-- fr0: r8 <- fr0: r8 <- fr0: r8 <-fr0: r8<-fr0: r8
                         fr1: r8 <- fr1: r8 

The simplest explanation I could come up with is that
is_state_visited() connects into parentage chains all live things
(regs, and stack).  The caller's r6 - r9 are actually alive, they have
just been pushed onto the stack by the JIT.  And therefore, since they
are just live things, it's is_state_visited()'s responsibility to
connect them.

> Is that just an optimisation that we can do because we know caller's
> r1-r5 were scratched by the call?

r0 - r5 of the caller will not be pushed to the stack by JITs and
therefore those are really dead.  It is an optimization.  We could've
connected them but they are already marked as WRITTEN in
check_func_call().

> It looks like, without that, the change is "every reg in all frames
> needs to be parented to the new-state", which is somewhat easier to
> understand (though I did have to think for quite a long time before
> it made sense to me why even that was necessary ;-)

Ack, that was my initial patch actually, but Jiong pointed out it's
unnecessary and I didn't argue :)  r1 - r5 are marked as WRITTEN and
UNINIT anyway, and r0 gets its parent from the callees frame
(prepare_func_exit() links callers r0 parentage chain to previous
states in the callee).

> So please add more to the patch description, and maybe a comment above
>  the loop explaining why it's r6-r9 only; then I'll be happy to Ack.

Good point, I will beef up the comment.

> > v1: don't unnecessarily link caller saved regs (Jiong)
> >
> > Fixes: f4d7e40a5b71 ("bpf: introduce function calls (verification)")
> > Reported-by: David Beckett <david.beckett@...ronome.com>
> > Signed-off-by: Jakub Kicinski <jakub.kicinski@...ronome.com>
> > Reviewed-by: Jiong Wang <jiong.wang@...ronome.com>  

Powered by blists - more mailing lists