netdev - Re: [PATCH bpf] bpf: verifier: make sure callees don't prune with caller differences

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

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

On Mon, 10 Dec 2018 11:35:12 -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.beckett@...ronome.com>
> Signed-off-by: Jakub Kicinski <jakub.kicinski@...ronome.com>
> Reviewed-by: Jiong Wang <jiong.wang@...ronome.com>
> ---
> resend with netdev included

And CC Ed, sorry..

>  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];
> +
>  		for (i = 0; i < frame->allocated_stack / BPF_REG_SIZE; i++) {
>  			frame->stack[i].spilled_ptr.live = REG_LIVE_NONE;
>  			frame->stack[i].spilled_ptr.parent =
> diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
> index df6f751cc1e8..373611ae9f52 100644
> --- a/tools/testing/selftests/bpf/test_verifier.c
> +++ b/tools/testing/selftests/bpf/test_verifier.c
> @@ -13915,6 +13915,34 @@ static struct bpf_test tests[] = {
>  		.result_unpriv = REJECT,
>  		.result = ACCEPT,
>  	},
> +	{
> +		"calls: cross frame pruning",
> +		.insns = {
> +			/* r8 = !!random();
> +			 * call pruner()
> +			 * if (r8)
> +			 *     do something bad;
> +			 */
> +			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
> +				     BPF_FUNC_get_prandom_u32),
> +			BPF_MOV64_IMM(BPF_REG_8, 0),
> +			BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1),
> +			BPF_MOV64_IMM(BPF_REG_8, 1),
> +			BPF_MOV64_REG(BPF_REG_1, BPF_REG_8),
> +			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 4),
> +			BPF_JMP_IMM(BPF_JEQ, BPF_REG_8, 1, 1),
> +			BPF_LDX_MEM(BPF_B, BPF_REG_9, BPF_REG_1, 0),
> +			BPF_MOV64_IMM(BPF_REG_0, 0),
> +			BPF_EXIT_INSN(),
> +			BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 0, 0),
> +			BPF_EXIT_INSN(),
> +		},
> +		.prog_type = BPF_PROG_TYPE_SOCKET_FILTER,
> +		.errstr_unpriv = "function calls to other bpf functions are allowed for root only",
> +		.result_unpriv = REJECT,
> +		.errstr = "!read_ok",
> +		.result = REJECT,
> +	},
>  };
>  
>  static int probe_filter_length(const struct bpf_insn *fp)