Messages in this thread | | | Subject | Re: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run | From | Yonghong Song <> | Date | Wed, 9 Jun 2021 23:06:31 -0700 |
| |
On 6/9/21 10:32 PM, Dmitry Vyukov wrote: > On Thu, Jun 10, 2021 at 1:40 AM Yonghong Song <yhs@fb.com> wrote: >> On 6/9/21 11:20 AM, Kees Cook wrote: >>> On Mon, Jun 07, 2021 at 09:38:43AM +0200, 'Dmitry Vyukov' via Clang Built Linux wrote: >>>> On Sat, Jun 5, 2021 at 9:10 PM Alexei Starovoitov >>>> <alexei.starovoitov@gmail.com> wrote: >>>>> On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@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@syzkaller.appspotmail.com >>>>>>> Signed-off-by: Kurt Manucredo <fuzzybritches0@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. >>>>> >>>>>> 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. >>>> >>>> Hi Alexei, >>>> >>>> The report is produced by KUBSAN. I thought there was an agreement on >>>> cleaning up KUBSAN reports from the kernel (the subset enabled on >>>> syzbot at least). >>>> What exactly cases should KUBSAN ignore? >>>> +linux-hardening/kasan-dev for KUBSAN false positive >>> >>> Can check_shl_overflow() be used at all? Best to just make things >>> readable and compiler-happy, whatever the implementation. :) >> >> This is not a compile issue. If the shift amount is a constant, >> compiler should have warned and user should fix the warning. >> >> This is because user code has >> something like >> a << s; >> where s is a unknown variable and >> verifier just marked the result of a << s as unknown value. >> Verifier may not reject the code depending on how a << s result >> is used. >> >> If bpf program writer uses check_shl_overflow() or some kind >> of checking for shift value and won't do shifting if the >> shifting may cause an undefined result, there should not >> be any kubsan warning. > > I guess the main question: what should happen if a bpf program writer > does _not_ use compiler nor check_shl_overflow()?
If kubsan is not enabled, everything should work as expected even with shl overflow may cause undefined result.
if kubsan is enabled, the reported shift-out-of-bounds warning should be ignored. You could disasm the insn to ensure that there indeed exists a potential shl overflow.
| |