netdev - Re: [PATCH] bpf: fix range arithmetic for bpf map access

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 for Android: free password hash cracker in your pocket

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

Date:   Fri, 11 Nov 2016 14:09:11 -0500
From:   Josef Bacik <jbacik@...com>
To:     Jann Horn <jannh@...gle.com>
CC:     Daniel Borkmann <daniel@...earbox.net>,
        Alexei Starovoitov <ast@...nel.org>,
        "David S. Miller" <davem@...emloft.net>, <netdev@...r.kernel.org>
Subject: Re: [PATCH] bpf: fix range arithmetic for bpf map access

On 11/11/2016 11:36 AM, Jann Horn wrote:
> On Fri, Nov 11, 2016 at 1:18 AM, Josef Bacik <jbacik@...com> wrote:
>> ---
>> Sorry Jann, I saw your response last night and then promptly forgot about it,
>> here's the git-send-email version.
>> ---
>
> A note: This doesn't seem to apply cleanly to current net-next (or I'm
> too stupid to
> use "git am"), so I'm applying it on f41cd11d64b2b21012eb4abffbe579bc0b90467f,
> which is net-next from a few days ago.
>

Yeah Dave pulled in a cleanup fix like right after I rebased onto net-next, I'll 
rebase again before I send the next patch.

>
>> 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.
>
> Yay! As a security person, I am very much in favor of killing unused features.
>

I almost dropped AND but thought better of it ;).

>
>> 2) Fix the logic for BPF_AND.  If the min value is negative then that is the new
>> minimum, otherwise it is unconditionally 0.
>>
>> 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>
>
> A nit: check_mem_access() still has an explicit cast of reg->min_value to s64, I
> think that's not necessary anymore?

Yup just missed that, I'll fix it.

>
>>         case BPF_AND:
>> -               /* & is special since it could end up with 0 bits set. */
>> -               dst_reg->min_value &= min_val;
>> +               /* & is special since it's could be any value within our range,
>> +                * including 0.  But if the thing we're AND'ing against is
>> +                * negative and we're negative then that's the minimum value,
>> +                * otherwise the minimum will always be 0.
>> +                */
>> +               if (min_val < 0 && dst_reg->min_value < 0)
>> +                       dst_reg->min_value = min_t(s64, dst_reg->min_value,
>> +                                                  min_val);
>> +               else
>> +                       dst_reg->min_value = 0;
>>                 dst_reg->max_value = max_val;
>
> I'm not sure whether this is correct when dealing with signed numbers.
> Let's say I have -2 and -3 (as u32: 0xfffffffe and 0xfffffffd) and AND them
> together. The result is 0xfffffffc, or -4, right? So if I just compute
> the AND of
> constant numbers -2 and -3 (known to the verifier), the verifier would
> compute minimum -3 while the actual value is -4, right?
>
> If I am correct about this, I think it might make sense to just reset
> the state to
> unknown in the `min_val < 0 && dst_reg->min_value < 0` case. That shouldn't
> occur in legitimate programs, right?
>

Yeah actually I think you are right, we'll just assume that AND'ing negative 
values means you did something wrong and set it to the RANGE_MIN value.  Thanks!

Josef