From mboxrd@z Thu Jan  1 00:00:00 1970
From: Daniel Borkmann <daniel@iogearbox.net>
Subject: Re: [PATCH bpf v2 8/9] bpf: prevent out of bounds speculation on
 pointer arithmetic
Date: Thu, 3 Jan 2019 00:37:36 +0100
Message-ID: <388f895c-0247-d977-9e72-dfec39a5125d@iogearbox.net>
References: <20190101232046.2880-1-daniel@iogearbox.net>
 <20190101232046.2880-9-daniel@iogearbox.net>
 <20190102141101.58e28b28@cakuba.hsd1.ca.comcast.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
Cc: ast@kernel.org, jannh@google.com, davem@davemloft.net,
        netdev@vger.kernel.org
To: Jakub Kicinski <jakub.kicinski@netronome.com>
Return-path: <netdev-owner@vger.kernel.org>
Received: from www62.your-server.de ([213.133.104.62]:40886 "EHLO
        www62.your-server.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org
        with ESMTP id S1726640AbfABXhp (ORCPT
        <rfc822;netdev@vger.kernel.org>); Wed, 2 Jan 2019 18:37:45 -0500
In-Reply-To: <20190102141101.58e28b28@cakuba.hsd1.ca.comcast.net>
Content-Language: en-US
Sender: netdev-owner@vger.kernel.org
List-ID: <netdev.vger.kernel.org>

On 01/02/2019 11:11 PM, Jakub Kicinski wrote:
> On Wed,  2 Jan 2019 00:20:45 +0100, Daniel Borkmann wrote:
>> Jann reported that the original commit back in b2157399cc98
>> ("bpf: prevent out-of-bounds speculation") was not sufficient
>> to stop CPU from speculating out of bounds memory access:
>> While b2157399cc98 only focussed on masking array map access
>> for unprivileged users for tail calls and data access such
>> that the user provided index gets sanitized from BPF program
>> and syscall side, there is still a more generic form affected
>> from BPF programs that applies to most maps that hold user
>> data in relation to dynamic map access when dealing with
>> unknown scalars or "slow" known scalars as access offset...
> 
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 8e5da1c..448a828 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -5499,6 +5610,13 @@ static bool states_equal(struct bpf_verifier_env *env,
>>  	if (old->curframe != cur->curframe)
>>  		return false;
>>  
>> +	/* Verification state from speculative execution simulation
>> +	 * must never prune a non-speculative execution one.
>> +	 */
>> +	if (old->speculative != cur->speculative ||
>> +	    (old->speculative && !cur->speculative))
>> +		return false;
> 
> nit: if I read this correctly it looks more conservative than the
>      comment suggests. 
> 
>      The second case (old->speculative && !cur->speculative) implies 
>      the first case (old->speculative != cur->speculative).
>      Perhaps:
> 
> 	if (old->speculative && !cur->speculative)
> 
>      Or:
> 
> 	if (old->speculative > cur->speculative)

Agree, and first one looks more readable.

>> +
>>  	/* for states to be equal callsites have to be the same
>>  	 * and all frame states need to be equivalent
>>  	 */
>> @@ -5530,6 +5648,11 @@ static int propagate_liveness(struct bpf_verifier_env *env,
>>  		     vparent->curframe, vstate->curframe);
>>  		return -EFAULT;
>>  	}
>> +
>> +	/* Don't propagate to non-speculative parent. */
>> +	if (vparent->speculative != vstate->speculative)
> 
> I haven't thought this trough fully, but is this really necessary?
> Do we assume the CPU will not speculate twice?  It seems not impossible
> to have a register only accessed on the speculation path, and therefore
> if we don't propagate liveness non-speculative walk may prune
> speculative checks.

This indeed needs to be removed from the patch, excellent catch; we definitely
don't want to run the risk of a reg being marked non-init in such case. I'll
spin v3 with both fixed up. Thanks for review!

>> +		return 0;
>> +
>>  	/* Propagate read liveness of registers... */
>>  	BUILD_BUG_ON(BPF_REG_FP + 1 != MAX_BPF_REG);
>>  	/* We don't need to worry about FP liveness because it's read-only */