lkml.org 
[lkml]   [2021]   [Jun]   [10]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    SubjectRe: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run
    From
    Date


    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.


    \
     
     \ /
      Last update: 2021-06-10 08:07    [W:9.408 / U:0.032 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site