On Sat, 5 Jun 2021 14:39:57 -0700, Yonghong Song <yhs@xxxxxx> wrote: > > > > On 6/5/21 12:10 PM, Alexei Starovoitov 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 %lldn", 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. Thanks for your input. If you find I should look closer into this bug just let me know. I'd love to help. If not it's fine, too. :-) kind regards, Kurt Manucredo
