[PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run

[Yonghong Song]

On 6/5/21 12:10 PM, Alexei Starovoitov wrote:
> On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs at fb.com> wrote:
>>
>>
>>
>> On 6/5/21 8:01 AM, Kurt Manucredo wrote:
>>> Syzbot detects a shift-out-of-bounds in ___bpf_prog_run()
>>> kernel/bpf/core.c:1414:2.
>>
>> This is not enough. We need more information on why this happens
>> so we can judge whether the patch indeed fixed the issue.
>>
>>>
>>> I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid
>>> missing them and return with error when detected.
>>>
>>> Reported-and-tested-by: syzbot+bed360704c521841c85d at syzkaller.appspotmail.com
>>> Signed-off-by: Kurt Manucredo <fuzzybritches0 at gmail.com>
>>> ---
>>>
>>> https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231
>>>
>>> Changelog:
>>> ----------
>>> v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
>>>        Fix commit message.
>>> v3 - Make it clearer what the fix is for.
>>> v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
>>>        check in check_alu_op() in verifier.c.
>>> v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
>>>        check in ___bpf_prog_run().
>>>
>>> thanks
>>>
>>> kind regards
>>>
>>> Kurt
>>>
>>>    kernel/bpf/verifier.c | 30 +++++++++---------------------
>>>    1 file changed, 9 insertions(+), 21 deletions(-)
>>>
>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>>> index 94ba5163d4c5..ed0eecf20de5 100644
>>> --- a/kernel/bpf/verifier.c
>>> +++ b/kernel/bpf/verifier.c
>>> @@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>>>        u32_min_val = src_reg.u32_min_value;
>>>        u32_max_val = src_reg.u32_max_value;
>>>
>>> +     if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
>>> +                     umax_val >= insn_bitness) {
>>> +             /* Shifts greater than 31 or 63 are undefined.
>>> +              * This includes shifts by a negative number.
>>> +              */
>>> +             verbose(env, "invalid shift %lld\n", umax_val);
>>> +             return -EINVAL;
>>> +     }
>>
>> I think your fix is good. I would like to move after
> 
> I suspect such change will break valid programs that do shift by register.

Oh yes, you are correct. We should guard it with src_known.
But this should be extremely rare with explicit shifting amount being
greater than 31/64 and if it is the case, the compiler will has a
warning.

> 
>> the following code though:
>>
>>           if (!src_known &&
>>               opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
>>                   __mark_reg_unknown(env, dst_reg);
>>                   return 0;
>>           }
>>
>>> +
>>>        if (alu32) {
>>>                src_known = tnum_subreg_is_const(src_reg.var_off);
>>>                if ((src_known &&
>>> @@ -7592,39 +7601,18 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>>>                scalar_min_max_xor(dst_reg, &src_reg);
>>>                break;
>>>        case BPF_LSH:
>>> -             if (umax_val >= insn_bitness) {
>>> -                     /* Shifts greater than 31 or 63 are undefined.
>>> -                      * This includes shifts by a negative number.
>>> -                      */
>>> -                     mark_reg_unknown(env, regs, insn->dst_reg);
>>> -                     break;
>>> -             }
>>
>> I think this is what happens. For the above case, we simply
>> marks the dst reg as unknown and didn't fail verification.
>> So later on at runtime, the shift optimization will have wrong
>> shift value (> 31/64). Please correct me if this is not right
>> analysis. As I mentioned in the early please write detailed
>> analysis in commit log.
> 
> The large shift is not wrong. It's just undefined.
> syzbot has to ignore such cases.

Agree. This makes sense.