netdev - Re: [RFC bpf-next 06/11] bpf: Add reference tracking to verifier

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]

Message-ID: <CAOftzPhCARknDqn=Nt3evr-4j4fCE_OVUNHrKW-M6qjBgHFyVw@mail.gmail.com>
Date:   Wed, 16 May 2018 18:05:04 -0700
From:   Joe Stringer <joe@...d.net.nz>
To:     Alexei Starovoitov <alexei.starovoitov@...il.com>
Cc:     Joe Stringer <joe@...d.net.nz>, daniel@...earbox.net,
        netdev <netdev@...r.kernel.org>, ast@...nel.org,
        john fastabend <john.fastabend@...il.com>,
        Martin KaFai Lau <kafai@...com>
Subject: Re: [RFC bpf-next 06/11] bpf: Add reference tracking to verifier

On 14 May 2018 at 20:04, Alexei Starovoitov
<alexei.starovoitov@...il.com> wrote:
> On Wed, May 09, 2018 at 02:07:04PM -0700, Joe Stringer wrote:
>> Allow helper functions to acquire a reference and return it into a
>> register. Specific pointer types such as the PTR_TO_SOCKET will
>> implicitly represent such a reference. The verifier must ensure that
>> these references are released exactly once in each path through the
>> program.
>>
>> To achieve this, this commit assigns an id to the pointer and tracks it
>> in the 'bpf_func_state', then when the function or program exits,
>> verifies that all of the acquired references have been freed. When the
>> pointer is passed to a function that frees the reference, it is removed
>> from the 'bpf_func_state` and all existing copies of the pointer in
>> registers are marked invalid.
>>
>> Signed-off-by: Joe Stringer <joe@...d.net.nz>
>> ---
>>  include/linux/bpf_verifier.h |  18 ++-
>>  kernel/bpf/verifier.c        | 295 ++++++++++++++++++++++++++++++++++++++++---
>>  2 files changed, 292 insertions(+), 21 deletions(-)
>>
>> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
>> index 9dcd87f1d322..8dbee360b3ec 100644
>> --- a/include/linux/bpf_verifier.h
>> +++ b/include/linux/bpf_verifier.h
>> @@ -104,6 +104,11 @@ struct bpf_stack_state {
>>       u8 slot_type[BPF_REG_SIZE];
>>  };
>>
>> +struct bpf_reference_state {
>> +     int id;
>> +     int insn_idx; /* allocation insn */
>
> the insn_idx is for more verbose messages, right?
> It doesn't seem to affect the safety of algorithm.
> Please add a comment to clarify that.

Yup, will do.

>> +/* Acquire a pointer id from the env and update the state->refs to include
>> + * this new pointer reference.
>> + * On success, returns a valid pointer id to associate with the register
>> + * On failure, returns a negative errno.
>> + */
>> +static int acquire_reference_state(struct bpf_verifier_env *env, int insn_idx)
>> +{
>> +     struct bpf_func_state *state = cur_func(env);
>> +     int new_ofs = state->acquired_refs;
>> +     int id, err;
>> +
>> +     err = realloc_reference_state(state, state->acquired_refs + 1, true);
>> +     if (err)
>> +             return err;
>> +     id = ++env->id_gen;
>> +     state->refs[new_ofs].id = id;
>> +     state->refs[new_ofs].insn_idx = insn_idx;
>
> I thought that we may avoid this extra 'ref_state' array if we store
> 'id' into 'aux' array which is one to one to array of instructions
> and avoid this expensive reallocs, but then I realized we can go
> through the same instruction that returns a pointer to socket
> multiple times and every time it needs to be different 'id' and
> tracked indepdently, so yeah. All that infra is necessary.
> Would be good to document the algorithm a bit more.

Good point, I'll add these details to the bpf_reference_state definition.
Will consider other areas that could receive some docs attention.

>> @@ -2498,6 +2711,15 @@ static int check_helper_call(struct bpf_verifier_env *env, int func_id, int insn
>>                       return err;
>>       }
>>
>> +     /* If the function is a release() function, mark all copies of the same
>> +      * pointer as "freed" in all registers and in the stack.
>> +      */
>> +     if (is_release_function(func_id)) {
>> +             err = release_reference(env);
>
> I think this can be improved if check_func_arg() stores ptr_id into meta.
> Then this loop
>  for (i = BPF_REG_1; i < BPF_REG_6; i++) {
>        if (reg_is_refcounted(&regs[i])) {
> in release_reference() won't be needed.

That's a nice cleanup.

> Also the macros from the previous patch look ugly, but considering this patch
> I guess it's justified. At least I don't see a better way of doing it.

Completely agree, ugly, but I also didn't see a great alternative.