linux-kernel - Re: [PATCH v3 net-next] bpf/verifier: track liveness for pruning

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]

Message-ID: <599B49DB.6010008@iogearbox.net>
Date:   Mon, 21 Aug 2017 23:00:11 +0200
From:   Daniel Borkmann <daniel@...earbox.net>
To:     Edward Cree <ecree@...arflare.com>,
        Alexei Starovoitov <ast@...com>, davem@...emloft.net,
        Alexei Starovoitov <alexei.starovoitov@...il.com>
CC:     netdev@...r.kernel.org, linux-kernel@...r.kernel.org,
        iovisor-dev <iovisor-dev@...ts.iovisor.org>
Subject: Re: [PATCH v3 net-next] bpf/verifier: track liveness for pruning

On 08/21/2017 10:44 PM, Edward Cree wrote:
> On 21/08/17 21:27, Daniel Borkmann wrote:
>> On 08/21/2017 08:36 PM, Edward Cree wrote:
>>> On 19/08/17 00:37, Alexei Starovoitov wrote:
>> [...]
>>> I'm tempted to just rip out env->varlen_map_value_access and always check
>>>    the whole thing, because honestly I don't know what it was meant to do
>>>    originally or how it can ever do any useful pruning.  While drastic, it
>>>    does cause your test case to pass.
>>
>> Original intention from 484611357c19 ("bpf: allow access into map
>> value arrays") was that it wouldn't potentially make pruning worse
>> if PTR_TO_MAP_VALUE_ADJ was not used, meaning that we wouldn't need
>> to take reg state's min_value and max_value into account for state
>> checking; this was basically due to min_value / max_value is being
>> adjusted/tracked on every alu/jmp ops for involved regs (e.g.
>> adjust_reg_min_max_vals() and others that mangle them) even if we
>> have the case that no actual dynamic map access is used throughout
>> the program. To give an example on net tree, the bpf_lxc.o prog's
>> section increases from 36,386 to 68,226 when env->varlen_map_value_access
>> is always true, so it does have an effect. Did you do some checks
>> on this on net-next?
> I tested with the cilium progs and saw no change in insn count.  I
>   suspect that for the normal case I already killed this optimisation
>   when I did my unification patch, it was previously about ignoring
>   min/max values on all regs (including scalars), whereas on net-next
>   it only ignores them on map_value pointers; in practice this is
>   useless because we tend to still have the offset scalar sitting in
>   a register somewhere.  (Come to think of it, this may have been
>   behind a large chunk of the #insn increase that my patches caused.)

Yeah, this would seem plausible.

> Since we use umax_value in find_good_pkt_pointers() now (to check
>   against MAX_PACKET_OFF and ensure our reg->range is really ok), we
>   can't just stop caring about all min/max values just because we
>   haven't done any variable map accesses.
> I don't see a way around this.

Agree, was thinking the same. If there's not really a regression in
terms of complexity, then lets kill the flag.