| 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
| ||
|
Message-ID: <4f6d6d58-303b-0165-6e7d-1c04d658e737@fb.com>
Date: Mon, 14 Nov 2016 13:52:51 -0500
From: Josef Bacik <jbacik@...com>
To: Alexei Starovoitov <alexei.starovoitov@...il.com>
CC: <jannh@...gle.com>, <ast@...nel.org>, <daniel@...earbox.net>,
<davem@...emloft.net>, <netdev@...r.kernel.org>
Subject: Re: [PATCH net-next] bpf: fix range arithmetic for bpf map access
On 11/11/2016 10:13 PM, Alexei Starovoitov wrote:
> On Fri, Nov 11, 2016 at 04:47:39PM -0500, Josef Bacik wrote:
>> I made some invalid assumptions with BPF_AND and BPF_MOD that could result in
>> invalid accesses to bpf map entries. Fix this up by doing a few things
>>
>> 1) Kill BPF_MOD support. This doesn't actually get used by the compiler in real
>> life and just adds extra complexity.
>>
>> 2) Fix the logic for BPF_AND, don't allow AND of negative numbers and set the
>> minimum value to 0 for positive AND's.
>>
>> 3) Don't do operations on the ranges if they are set to the limits, as they are
>> by definition undefined, and allowing arithmetic operations on those values
>> could make them appear valid when they really aren't.
>>
>> This fixes the testcase provided by Jann as well as a few other theoretical
>> problems.
>>
>> Reported-by: Jann Horn <jannh@...gle.com>
>> Signed-off-by: Josef Bacik <jbacik@...com>
>> ---
>> include/linux/bpf_verifier.h | 3 +-
>> kernel/bpf/verifier.c | 70 +++++++++++++++++++++++++++++---------------
>> 2 files changed, 49 insertions(+), 24 deletions(-)
>>
>> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
>> index ac5b393..15ceb7f 100644
>> --- a/include/linux/bpf_verifier.h
>> +++ b/include/linux/bpf_verifier.h
>> @@ -22,7 +22,8 @@ struct bpf_reg_state {
>> * Used to determine if any memory access using this register will
>> * result in a bad access.
>> */
>> - u64 min_value, max_value;
>> + s64 min_value;
>> + u64 max_value;
>> u32 id;
>> union {
>> /* valid when type == CONST_IMM | PTR_TO_STACK | UNKNOWN_VALUE */
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 89f787c..709fe0e 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -234,8 +234,8 @@ static void print_verifier_state(struct bpf_verifier_state *state)
>> reg->map_ptr->value_size,
>> reg->id);
>> if (reg->min_value != BPF_REGISTER_MIN_RANGE)
>> - verbose(",min_value=%llu",
>> - (unsigned long long)reg->min_value);
>> + verbose(",min_value=%lld",
>> + (long long)reg->min_value);
>> if (reg->max_value != BPF_REGISTER_MAX_RANGE)
>> verbose(",max_value=%llu",
>> (unsigned long long)reg->max_value);
>> @@ -778,7 +778,7 @@ static int check_mem_access(struct bpf_verifier_env *env, u32 regno, int off,
>> * index'es we need to make sure that whatever we use
>> * will have a set floor within our range.
>> */
>> - if ((s64)reg->min_value < 0) {
>> + if (reg->min_value < 0) {
>> verbose("R%d min value is negative, either use unsigned index or do a if (index >=0) check.\n",
>> regno);
>> return -EACCES;
>> @@ -1490,7 +1490,8 @@ static void check_reg_overflow(struct bpf_reg_state *reg)
>> {
>> if (reg->max_value > BPF_REGISTER_MAX_RANGE)
>> reg->max_value = BPF_REGISTER_MAX_RANGE;
>> - if ((s64)reg->min_value < BPF_REGISTER_MIN_RANGE)
>> + if (reg->min_value < BPF_REGISTER_MIN_RANGE ||
>> + reg->min_value > BPF_REGISTER_MAX_RANGE)
>> reg->min_value = BPF_REGISTER_MIN_RANGE;
>> }
>>
>> @@ -1498,7 +1499,8 @@ static void adjust_reg_min_max_vals(struct bpf_verifier_env *env,
>> struct bpf_insn *insn)
>> {
>> struct bpf_reg_state *regs = env->cur_state.regs, *dst_reg;
>> - u64 min_val = BPF_REGISTER_MIN_RANGE, max_val = BPF_REGISTER_MAX_RANGE;
>> + s64 min_val = BPF_REGISTER_MIN_RANGE;
>> + u64 max_val = BPF_REGISTER_MAX_RANGE;
>> u8 opcode = BPF_OP(insn->code);
>>
>> dst_reg = ®s[insn->dst_reg];
>> @@ -1532,22 +1534,43 @@ static void adjust_reg_min_max_vals(struct bpf_verifier_env *env,
>> return;
>> }
>>
>> + /* If one of our values was at the end of our ranges then we can't just
>> + * do our normal operations to the register, we need to set the values
>> + * to the min/max since they are undefined.
>> + */
>> + if (min_val == BPF_REGISTER_MIN_RANGE)
>> + dst_reg->min_value = BPF_REGISTER_MIN_RANGE;
>> + if (max_val == BPF_REGISTER_MAX_RANGE)
>> + dst_reg->max_value = BPF_REGISTER_MAX_RANGE;
>> +
>> switch (opcode) {
>> case BPF_ADD:
>> - dst_reg->min_value += min_val;
>> - dst_reg->max_value += max_val;
>> + if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE)
>> + dst_reg->min_value += min_val;
>> + if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE)
>> + dst_reg->max_value += max_val;
>> break;
>> case BPF_SUB:
>> - dst_reg->min_value -= min_val;
>> - dst_reg->max_value -= max_val;
>> + if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE)
>> + dst_reg->min_value -= min_val;
>> + if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE)
>> + dst_reg->max_value -= max_val;
>> break;
>> case BPF_MUL:
>> - dst_reg->min_value *= min_val;
>> - dst_reg->max_value *= max_val;
>> + if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE)
>> + dst_reg->min_value *= min_val;
>
> looks to be few issues here with negative values as well.
> If dst_reg range [-2, 5] and right hand side range is [-2, 10],
> then above will be computed as -2 * -2 == 4
> but even if we do -1 * abs(dst_reg->min) * abs(min), it's still
> incorrect, since dst_reg could be 5 and multiplied by -2 (== -10),
> it will be less than above simple math on min values...
> so I'd suggest to disable negative values everywhere.
>
>> + if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE)
>> + dst_reg->max_value *= max_val;
>> break;
>> case BPF_AND:
>> - /* & is special since it could end up with 0 bits set. */
>> - dst_reg->min_value &= min_val;
>> + /* Disallow AND'ing of negative numbers, ain't nobody got time
>> + * for that. Otherwise the minimum is 0 and the max is the max
>> + * value we could AND against.
>> + */
>> + if (min_val < 0)
>> + dst_reg->min_value = BPF_REGISTER_MIN_RANGE;
>> + else
>> + dst_reg->min_value = 0;
>> dst_reg->max_value = max_val;
>> break;
>> case BPF_LSH:
>> @@ -1557,24 +1580,25 @@ static void adjust_reg_min_max_vals(struct bpf_verifier_env *env,
>> */
>> if (min_val > ilog2(BPF_REGISTER_MAX_RANGE))
>> dst_reg->min_value = BPF_REGISTER_MIN_RANGE;
>> - else
>> + else if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE)
>> dst_reg->min_value <<= min_val;
>>
>> if (max_val > ilog2(BPF_REGISTER_MAX_RANGE))
>> dst_reg->max_value = BPF_REGISTER_MAX_RANGE;
>> - else
>> + else if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE)
>> dst_reg->max_value <<= max_val;
>> break;
>> case BPF_RSH:
>> - dst_reg->min_value >>= min_val;
>> - dst_reg->max_value >>= max_val;
>> - break;
>> - case BPF_MOD:
>> - /* % is special since it is an unsigned modulus, so the floor
>> - * will always be 0.
>> + /* RSH by a negative number is undefined, and the BPF_RSH is an
>> + * unsigned shift, so make the appropriate casts.
>> */
>> - dst_reg->min_value = 0;
>> - dst_reg->max_value = max_val - 1;
>> + if (min_val < 0)
>> + dst_reg->min_value = BPF_REGISTER_MIN_RANGE;
>> + else if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE)
>> + dst_reg->min_value =
>> + (u64)(dst_reg->min_value) >> min_val;
>
> when min_val is negative both >> and << are undefined,
> so we need to avoid negative values for these cases as well.
>
>> + if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE)
>> + dst_reg->max_value >>= max_val;
>
> and for max_val too we need to make sure that max_val >= 0.
Well it's unsigned, so if somebody sets it to a negative value it'll be >
BPF_REGISTER_MAX_RANGE and that'll get caught by the overflow logic above.
>
> To address all of it I'm thinking it will be easier to set
> BPF_REGISTER_MIN_RANGE to -1.
> I don't think we can kill tracking of min_val completely
> and assume valid min starts at zero, since we need either min
> tracking or boolean flag that indicates negative overflow and
> min tracking is imo cleaner (though valid min will always be >=0
> and invalid min is -1)
>
> Also this patch has to go to 'net' tree, so rebasing with net-next
> wasn't necessary.
>
Yeah I'm fine with killing negative values altogether, it does seem a bit silly
to support it and isn't likely to be used in any sort of normal scenario. Thanks,
Josef
Powered by blists - more mailing lists