netdev - Re: [PATCH bpf-next 09/10] bpf: Add a helper to issue timestamp cookies in XDP

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]

Date:   Tue, 2 Nov 2021 19:10:45 -0700
From:   Yonghong Song <yhs@...com>
To:     Maxim Mikityanskiy <maximmi@...dia.com>,
        Toke Høiland-Jørgensen <toke@...hat.com>,
        Lorenz Bauer <lmb@...udflare.com>,
        Alexei Starovoitov <ast@...nel.org>
CC:     Daniel Borkmann <daniel@...earbox.net>,
        Andrii Nakryiko <andrii@...nel.org>,
        Martin KaFai Lau <kafai@...com>,
        Song Liu <songliubraving@...com>,
        John Fastabend <john.fastabend@...il.com>,
        KP Singh <kpsingh@...nel.org>,
        Eric Dumazet <edumazet@...gle.com>,
        "David S. Miller" <davem@...emloft.net>,
        Jakub Kicinski <kuba@...nel.org>,
        Hideaki YOSHIFUJI <yoshfuji@...ux-ipv6.org>,
        David Ahern <dsahern@...nel.org>,
        Jesper Dangaard Brouer <hawk@...nel.org>,
        Nathan Chancellor <nathan@...nel.org>,
        Nick Desaulniers <ndesaulniers@...gle.com>,
        Brendan Jackman <jackmanb@...gle.com>,
        Florent Revest <revest@...omium.org>,
        Joe Stringer <joe@...ium.io>, Tariq Toukan <tariqt@...dia.com>,
        Networking <netdev@...r.kernel.org>, bpf <bpf@...r.kernel.org>,
        <clang-built-linux@...glegroups.com>
Subject: Re: [PATCH bpf-next 09/10] bpf: Add a helper to issue timestamp
 cookies in XDP



On 11/1/21 4:14 AM, Maxim Mikityanskiy wrote:
> On 2021-10-20 19:16, Toke Høiland-Jørgensen wrote:
>> Lorenz Bauer <lmb@...udflare.com> writes:
>>
>>>> +bool cookie_init_timestamp_raw(struct tcphdr *th, __be32 *tsval, 
>>>> __be32 *tsecr)
>>>
>>> I'm probably missing context, Is there something in this function that
>>> means you can't implement it in BPF?
>>
>> I was about to reply with some other comments but upon closer inspection
>> I ended up at the same conclusion: this helper doesn't seem to be needed
>> at all?
> 
> After trying to put this code into BPF (replacing the underlying 
> ktime_get_ns with ktime_get_mono_fast_ns), I experienced issues with 
> passing the verifier.
> 
> In addition to comparing ptr to end, I had to add checks that compare 
> ptr to data_end, because the verifier can't deduce that end <= data_end. 
> More branches will add a certain slowdown (not measured).
> 
> A more serious issue is the overall program complexity. Even though the 
> loop over the TCP options has an upper bound, and the pointer advances 
> by at least one byte every iteration, I had to limit the total number of 
> iterations artificially. The maximum number of iterations that makes the 
> verifier happy is 10. With more iterations, I have the following error:
> 
> BPF program is too large. Processed 1000001 insn
> 
>                         processed 1000001 insns (limit 1000000) 
> max_states_per_insn 29 total_states 35489 peak_states 596 mark_read 45
> 
> I assume that BPF_COMPLEXITY_LIMIT_INSNS (1 million) is the accumulated 
> amount of instructions that the verifier can process in all branches, is 
> that right? It doesn't look realistic that my program can run 1 million 
> instructions in a single run, but it might be that if you take all 
> possible flows and add up the instructions from these flows, it will 
> exceed 1 million.
> 
> The limitation of maximum 10 TCP options might be not enough, given that 
> valid packets are permitted to include more than 10 NOPs. An alternative 
> of using bpf_load_hdr_opt and calling it three times doesn't look good 
> either, because it will be about three times slower than going over the 
> options once. So maybe having a helper for that is better than trying to 
> fit it into BPF?
> 
> One more interesting fact is the time that it takes for the verifier to 
> check my program. If it's limited to 10 iterations, it does it pretty 
> fast, but if I try to increase the number to 11 iterations, it takes 
> several minutes for the verifier to reach 1 million instructions and 
> print the error then. I also tried grouping the NOPs in an inner loop to 
> count only 10 real options, and the verifier has been running for a few 
> hours without any response. Is it normal? 

Maxim, this may expose a verifier bug. Do you have a reproducer I can 
access? I would like to debug this to see what is the root case. Thanks!

> Commit c04c0d2b968a ("bpf: 
> increase complexity limit and maximum program size") says it shouldn't 
> take more than one second in any case.
> 
> Thanks,
> Max