netdev - Re: [PATCH net-next 3/4] bpf/verifier: when pruning a branch, ignore its write marks

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: <97f3da2d-abb0-ba1f-07ca-ea426f30c7fb@solarflare.com>
Date:   Tue, 22 Aug 2017 16:50:46 +0100
From:   Edward Cree <ecree@...arflare.com>
To:     Alexei Starovoitov <ast@...com>, <davem@...emloft.net>,
        Alexei Starovoitov <alexei.starovoitov@...il.com>,
        Daniel Borkmann <daniel@...earbox.net>
CC:     <netdev@...r.kernel.org>,
        iovisor-dev <iovisor-dev@...ts.iovisor.org>
Subject: Re: [PATCH net-next 3/4] bpf/verifier: when pruning a branch, ignore
 its write marks

On 22/08/17 16:24, Alexei Starovoitov wrote:
> On 8/22/17 6:27 AM, Edward Cree wrote:
>> The fact that writes occurred in reaching the continuation state does
>>  not screen off its reads from us, because we're not really its parent.
>> So detect 'not really the parent' in do_propagate_liveness, and ignore
>>  write marks in that case.
>>
>> Fixes: dc503a8ad984 ("bpf/verifier: track liveness for pruning")
>> Signed-off-by: Edward Cree <ecree@...arflare.com>
>> ---
>>  kernel/bpf/verifier.c | 9 +++++++--
>>  1 file changed, 7 insertions(+), 2 deletions(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 1e3f56c..711bdbd 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -3420,6 +3420,7 @@ static bool states_equal(struct bpf_verifier_env *env,
>>  static bool do_propagate_liveness(const struct bpf_verifier_state *state,
>>                    struct bpf_verifier_state *parent)
>>  {
>> +    bool writes = parent == state->parent; /* Observe write marks */
>>      bool touched = false; /* any changes made? */
>>      int i;
>>
>> @@ -3431,7 +3432,9 @@ static bool do_propagate_liveness(const struct bpf_verifier_state *state,
>>      for (i = 0; i < BPF_REG_FP; i++) {
>>          if (parent->regs[i].live & REG_LIVE_READ)
>>              continue;
>> -        if (state->regs[i].live == REG_LIVE_READ) {
>> +        if (writes && (state->regs[i].live & REG_LIVE_WRITTEN))
>> +            continue;
>> +        if (state->regs[i].live & REG_LIVE_READ) {
>
> makes sense to me.
> if i understand correctly it not only should make the liveness marking
> correct, but improve the numbers, since smaller number of states
> will have READ marks.
Other way round; it means we sometimes ignore WRITTEN marks, so more states
 get READ marks.  On the cilium progs, the bpf_lxc.o get about 100 extra
 insns processed, the others are unchanged.
> Do you have a test case for this by any chance?
I haven't constructed one; my test was just to put in some debug code that
 checked on each propagate_liveness call whether there were any write marks
 in the first state.
I think something like
    if (cond)
        r0=0;
    if (cond)
        r0=0;
    return r0;
might tickle the bug, but I'm not sure.