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: <c0ea0e4a-75f4-652c-9967-1de5a4173157@fb.com>
Date:   Mon, 21 Aug 2017 14:18:45 -0700
From:   Alexei Starovoitov <ast@...com>
To:     Edward Cree <ecree@...arflare.com>, <davem@...emloft.net>,
        Alexei Starovoitov <alexei.starovoitov@...il.com>,
        Daniel Borkmann <daniel@...earbox.net>
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 8/21/17 1:24 PM, Edward Cree wrote:
> On 18/08/17 15:16, Edward Cree wrote:
>> On 18/08/17 04:21, Alexei Starovoitov wrote:
>>> It seems you're trying to sort-of do per-fake-basic block liveness
>>> analysis, but our state_list_marks are not correct if we go with
>>> canonical basic block definition, since we mark the jump insn and
>>> not insn after the branch and not every basic block boundary is
>>> properly detected.
>> I think the reason this works is that jump insns can't do writes.
>> [snip]
>> the sl->state will never have any write marks and it'll all just work.
>> But I should really test that!
> I tested this, and found that, no, sl->state can have write marks, and the
>  algorithm will get the wrong answer in that case.  So I've got a patch to
>  make the first iteration ignore write marks, as part of a series which I
>  will post shortly.  When I do so, please re-do your tests with adding
>  state_list_marks in strange and exciting places; it should work wherever
>  you put them.  Like you say, it "magically doesn't depend on proper basic
>  block boundaries", and that's because really pruning is just a kind of
>  checkpointing that just happens to be most effective when done just after
>  a jump (pop_stack).
>
> Can I have a SOB for your "grr" test program, so I can include it in the
>  series?

yes. of course. just give the test some reasonable name :)