On Mon, Dec 10, 2018 at 11:35:12AM -0800, 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.
>
> v1: don't unnecessarily link caller saved regs (Jiong)
>
> Fixes: f4d7e40a5b71 ("bpf: introduce function calls (verification)")
> Reported-by: David Beckett <david.beck...@netronome.com>
> Signed-off-by: Jakub Kicinski <jakub.kicin...@netronome.com>
> Reviewed-by: Jiong Wang <jiong.w...@netronome.com>
> ---
> resend with netdev included
> ---
> kernel/bpf/verifier.c | 10 +++++++-
> tools/testing/selftests/bpf/test_verifier.c | 28 +++++++++++++++++++++
> 2 files changed, 37 insertions(+), 1 deletion(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index fc760d00a38c..60d57d9d3663 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -5114,11 +5114,19 @@ static int is_state_visited(struct bpf_verifier_env
> *env, int insn_idx)
> for (i = 0; i < BPF_REG_FP; i++)
> cur->frame[cur->curframe]->regs[i].live = REG_LIVE_NONE;
>
> - /* all stack frames are accessible from callee, clear them all */
> + /* connect new state to parentage chain:
> + * - all stack frames are accessible from callee
> + * - even though other stack frames' registers are not accessible
> + * liveness must propagate through the callees' states otherwise
> + * not knowing the liveness callee may prune caller
> + */
> for (j = 0; j <= cur->curframe; j++) {
> struct bpf_func_state *frame = cur->frame[j];
> struct bpf_func_state *newframe = new->frame[j];
>
> + for (i = BPF_REG_6; i < BPF_REG_FP; i++)
> + frame->regs[i].parent = &newframe->regs[i];
> +
excellent catch! thanks a lot for the analysis.
Only odd bit that parent pointers are connected twice
(by first loop just above this hunk and by this new one)
How about something like this instead:
- for (i = 0; i < BPF_REG_FP; i++)
- cur_regs(env)[i].parent = &new->frame[new->curframe]->regs[i];
+ for (j = 0; j <= cur->curframe; j++)
+ for (i = j < cur->curframe ? BPF_REG_6 : 0; i < BPF_REG_FP; i++)
+ cur->frame[j]->regs[i].parent = &new->frame[j]->regs[i];
with appropriate comments...
