On Thu, Jun 10, 2021 at 1:40 AM Yonghong Song <yhs@xxxxxx> 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@xxxxxxxxx> wrote: > >>> On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@xxxxxx> 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@xxxxxxxxxxxxxxxxxxxxxxxxx > >>>>> Signed-off-by: Kurt Manucredo <fuzzybritches0@xxxxxxxxx> > >>>>> --- > >>>>> > >>>>> 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()?
