Re: [PATCH bpf 1/2] bpf: fix an incorrect branch elimination by verifier

[Daniel Borkmann <daniel@iogearbox.net>]

On 6/30/20 9:18 PM, Andrii Nakryiko wrote:
> On Tue, Jun 30, 2020 at 11:46 AM Yonghong Song <yhs@fb.com> wrote:
>>
>> Wenbo reported an issue in [1] where a checking of null
>> pointer is evaluated as always false. In this particular
>> case, the program type is tp_btf and the pointer to
>> compare is a PTR_TO_BTF_ID.
>>
>> The current verifier considers PTR_TO_BTF_ID always
>> reprents a non-null pointer, hence all PTR_TO_BTF_ID compares
>> to 0 will be evaluated as always not-equal, which resulted
>> in the branch elimination.
>>
>> For example,
>>   struct bpf_fentry_test_t {
>>       struct bpf_fentry_test_t *a;
>>   };
>>   int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
>>   {
>>       if (arg == 0)
>>           test7_result = 1;
>>       return 0;
>>   }
>>   int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
>>   {
>>       if (arg->a == 0)
>>           test8_result = 1;
>>       return 0;
>>   }
>>
>> In above bpf programs, both branch arg == 0 and arg->a == 0
>> are removed. This may not be what developer expected.
>>
>> The bug is introduced by Commit cac616db39c2 ("bpf: Verifier
>> track null pointer branch_taken with JNE and JEQ"),
>> where PTR_TO_BTF_ID is considered to be non-null when evaluting
>> pointer vs. scalar comparison. This may be added
>> considering we have PTR_TO_BTF_ID_OR_NULL in the verifier
>> as well.
>>
>> PTR_TO_BTF_ID_OR_NULL is added to explicitly requires
>> a non-NULL testing in selective cases. The current generic
>> pointer tracing framework in verifier always
>> assigns PTR_TO_BTF_ID so users does not need to
>> check NULL pointer at every pointer level like a->b->c->d.
>>
>> We may not want to assign every PTR_TO_BTF_ID as
>> PTR_TO_BTF_ID_OR_NULL as this will require a null test
>> before pointer dereference which may cause inconvenience
>> for developers. But we could avoid branch elimination
>> to preserve original code intention.
>>
>> This patch simply removed PTR_TO_BTD_ID from reg_type_not_null()
>> in verifier, which prevented the above branches from being eliminated.
>>
>>   [1]: https://lore.kernel.org/bpf/79dbb7c0-449d-83eb-5f4f-7af0cc269168@fb.com/T/
>>
>> Fixes: cac616db39c2 ("bpf: Verifier track null pointer branch_taken with JNE and JEQ")
>> Cc: Andrii Nakryiko <andriin@fb.com>
>> Cc: John Fastabend <john.fastabend@gmail.com>
>> Cc: Wenbo Zhang <ethercflow@gmail.com>
>> Signed-off-by: Yonghong Song <yhs@fb.com>
>> ---
> 
> You missed Reported-by: tag, please add.

Agree, fixed up manually (and also pulled in your ACKs, Andrii).

Thanks,
Daniel