Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.35 as permitted sender) client-ip=23.128.96.35;
MIME-Version: 1.0
References: <20231009-jmp-into-reserved-fields-v1-1-d8006e2ac1f6@gmail.com>
 <6524f6f77b896_66abc2084d@john.notmuch> <92f824ec-9538-501c-e63e-8483ffe14bad@iogearbox.net>
 <CAEf4Bza2s=JwR8b6d_x+bj5Y7iZ+ZDOMOJRNwcXF1ATWzHCxcA@mail.gmail.com>
 <CACkBjsZiaXTANv=c5QE3OvcB=KUgdFuMY8O4ft4Q3h6dDNVarg@mail.gmail.com> <79dd71a5-446d-9b05-7d37-40e49bbf04ae@iogearbox.net>
In-Reply-To: <79dd71a5-446d-9b05-7d37-40e49bbf04ae@iogearbox.net>
From:   Hao Sun <sunhao.th@gmail.com>
Date:   Thu, 12 Oct 2023 08:23:02 +0200
Message-ID: <CACkBjsadVpmppbFE8Dp5eym3DK3zFF2ojvvSpTW3b9PsC6CdgA@mail.gmail.com>
Subject: Re: [PATCH bpf-next] Detect jumping to reserved code during check_cfg()
To:     Daniel Borkmann <daniel@iogearbox.net>
Cc:     Andrii Nakryiko <andrii.nakryiko@gmail.com>,
        John Fastabend <john.fastabend@gmail.com>,
        Alexei Starovoitov <ast@kernel.org>,
        Andrii Nakryiko <andrii@kernel.org>,
        Martin KaFai Lau <martin.lau@linux.dev>,
        Song Liu <song@kernel.org>,
        Yonghong Song <yonghong.song@linux.dev>,
        KP Singh <kpsingh@kernel.org>,
        Stanislav Fomichev <sdf@google.com>,
        Hao Luo <haoluo@google.com>, Jiri Olsa <jolsa@kernel.org>,
        bpf@vger.kernel.org, linux-kernel@vger.kernel.org
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Precedence: bulk

On Wed, Oct 11, 2023 at 4:50=E2=80=AFPM Daniel Borkmann <daniel@iogearbox.n=
et> wrote:
>
> On 10/11/23 8:46 AM, Hao Sun wrote:
> > On Wed, Oct 11, 2023 at 4:42=E2=80=AFAM Andrii Nakryiko
> > <andrii.nakryiko@gmail.com> wrote:
> >> On Tue, Oct 10, 2023 at 1:33=E2=80=AFAM Daniel Borkmann <daniel@iogear=
box.net> wrote:
> >>> On 10/10/23 9:02 AM, John Fastabend wrote:
> >>>> Hao Sun wrote:
> >>>>> Currently, we don't check if the branch-taken of a jump is reserved=
 code of
> >>>>> ld_imm64. Instead, such a issue is captured in check_ld_imm(). The =
verifier
> >>>>> gives the following log in such case:
> >>>>>
> >>>>> func#0 @0
> >>>>> 0: R1=3Dctx(off=3D0,imm=3D0) R10=3Dfp0
> >>>>> 0: (18) r4 =3D 0xffff888103436000       ; R4_w=3Dmap_ptr(off=3D0,ks=
=3D4,vs=3D128,imm=3D0)
> >>>>> 2: (18) r1 =3D 0x1d                     ; R1_w=3D29
> >>>>> 4: (55) if r4 !=3D 0x0 goto pc+4        ; R4_w=3Dmap_ptr(off=3D0,ks=
=3D4,vs=3D128,imm=3D0)
> >>>>> 5: (1c) w1 -=3D w1                      ; R1_w=3D0
> >>>>> 6: (18) r5 =3D 0x32                     ; R5_w=3D50
> >>>>> 8: (56) if w5 !=3D 0xfffffff4 goto pc-2
> >>>>> mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx -1
> >>>>> mark_precise: frame0: regs=3Dr5 stack=3D before 6: (18) r5 =3D 0x32
> >>>>> 7: R5_w=3D50
> >>>>> 7: BUG_ld_00
> >>>>> invalid BPF_LD_IMM insn
> >>>>>
> >>>>> Here the verifier rejects the program because it thinks insn at 7 i=
s an
> >>>>> invalid BPF_LD_IMM, but such a error log is not accurate since the =
issue
> >>>>> is jumping to reserved code not because the program contains invali=
d insn.
> >>>>> Therefore, make the verifier check the jump target during check_cfg=
(). For
> >>>>> the same program, the verifier reports the following log:
> >>>>
> >>>> I think we at least would want a test case for this. Also how did yo=
u create
> >>>> this case? Is it just something you did manually and noticed a stran=
ge error?
> >>>
> >>> Curious as well.
> >>>
> >>> We do have test cases which try to jump into the middle of a double i=
nsn as can
> >>> be seen that this patch breaks BPF CI with regards to log mismatch be=
low (which
> >>> still needs to be adapted, too). Either way, it probably doesn't hurt=
 to also add
> >>> the above snippet as a test.
> >>>
> >>> Hao, as I understand, the patch here is an usability improvement (not=
 a fix per se)
> >>> where we reject such cases earlier during cfg check rather than at a =
later point
> >>> where we validate ld_imm instruction. Or are there cases you found wh=
ich were not
> >>> yet captured via current check_ld_imm()?
> >>>
> >>> test_verifier failure log :
> >>>
> >>>     #458/u test1 ld_imm64 FAIL
> >>>     Unexpected verifier log!
> >>>     EXP: R1 pointer comparison
> >>>     RES:
> >>>     FAIL
> >>>     Unexpected error message!
> >>>          EXP: R1 pointer comparison
> >>>          RES: jump to reserved code from insn 0 to 2
> >>>     verification time 22 usec
> >>>     stack depth 0
> >>>     processed 0 insns (limit 1000000) max_states_per_insn 0 total_sta=
tes 0 peak_states 0 mark_read 0
> >>>
> >>>     jump to reserved code from insn 0 to 2
> >>>     verification time 22 usec
> >>>     stack depth 0
> >>>     processed 0 insns (limit 1000000) max_states_per_insn 0 total_sta=
tes 0 peak_states 0 mark_read 0
> >>>     #458/p test1 ld_imm64 FAIL
> >>>     Unexpected verifier log!
> >>>     EXP: invalid BPF_LD_IMM insn
> >>>     RES:
> >>>     FAIL
> >>>     Unexpected error message!
> >>>          EXP: invalid BPF_LD_IMM insn
> >>>          RES: jump to reserved code from insn 0 to 2
> >>>     verification time 9 usec
> >>>     stack depth 0
> >>>     processed 0 insns (limit 1000000) max_states_per_insn 0 total_sta=
tes 0 peak_states 0 mark_read 0
> >>>
> >>>     jump to reserved code from insn 0 to 2
> >>>     verification time 9 usec
> >>>     stack depth 0
> >>>     processed 0 insns (limit 1000000) max_states_per_insn 0 total_sta=
tes 0 peak_states 0 mark_read 0
> >>>     #459/u test2 ld_imm64 FAIL
> >>>     Unexpected verifier log!
> >>>     EXP: R1 pointer comparison
> >>>     RES:
> >>>     FAIL
> >>>     Unexpected error message!
> >>>          EXP: R1 pointer comparison
> >>>          RES: jump to reserved code from insn 0 to 2
> >>>     verification time 11 usec
> >>>     stack depth 0
> >>>     processed 0 insns (limit 1000000) max_states_per_insn 0 total_sta=
tes 0 peak_states 0 mark_read 0
> >>>
> >>>     jump to reserved code from insn 0 to 2
> >>>     verification time 11 usec
> >>>     stack depth 0
> >>>     processed 0 insns (limit 1000000) max_states_per_insn 0 total_sta=
tes 0 peak_states 0 mark_read 0
> >>>     #459/p test2 ld_imm64 FAIL
> >>>     Unexpected verifier log!
> >>>     EXP: invalid BPF_LD_IMM insn
> >>>     RES:
> >>>     FAIL
> >>>     Unexpected error message!
> >>>          EXP: invalid BPF_LD_IMM insn
> >>>          RES: jump to reserved code from insn 0 to 2
> >>>     verification time 8 usec
> >>>     stack depth 0
> >>>     processed 0 insns (limit 1000000) max_states_per_insn 0 total_sta=
tes 0 peak_states 0 mark_read 0
> >>>
> >>>     jump to reserved code from insn 0 to 2
> >>>     verification time 8 usec
> >>>     stack depth 0
> >>>     processed 0 insns (limit 1000000) max_states_per_insn 0 total_sta=
tes 0 peak_states 0 mark_read 0
> >>>     #460/u test3 ld_imm64 OK
> >>>
> >>>>> func#0 @0
> >>>>> jump to reserved code from insn 8 to 7
> >>>>>
> >>>>> Signed-off-by: Hao Sun <sunhao.th@gmail.com>
> >>>
> >>> nit: This needs to be before the "---" line.
> >>>
> >>>>> ---
> >>>>>    kernel/bpf/verifier.c | 7 +++++++
> >>>>>    1 file changed, 7 insertions(+)
> >>>>>
> >>>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> >>>>> index eed7350e15f4..725ac0b464cf 100644
> >>>>> --- a/kernel/bpf/verifier.c
> >>>>> +++ b/kernel/bpf/verifier.c
> >>>>> @@ -14980,6 +14980,7 @@ static int push_insn(int t, int w, int e, s=
truct bpf_verifier_env *env,
> >>>>>    {
> >>>>>       int *insn_stack =3D env->cfg.insn_stack;
> >>>>>       int *insn_state =3D env->cfg.insn_state;
> >>>>> +    struct bpf_insn *insns =3D env->prog->insnsi;
> >>>>>
> >>>>>       if (e =3D=3D FALLTHROUGH && insn_state[t] >=3D (DISCOVERED | =
FALLTHROUGH))
> >>>>>               return DONE_EXPLORING;
> >>>>> @@ -14993,6 +14994,12 @@ static int push_insn(int t, int w, int e, =
struct bpf_verifier_env *env,
> >>>>>               return -EINVAL;
> >>>>>       }
> >>>>>
> >>>>> +    if (e =3D=3D BRANCH && insns[w].code =3D=3D 0) {
> >>>>> +            verbose_linfo(env, t, "%d", t);
> >>>>> +            verbose(env, "jump to reserved code from insn %d to %d=
\n", t, w);
> >>>>> +            return -EINVAL;
> >>>>> +    }
> >>>
> >>> Other than that, lgtm.
> >>
> >> We do rely quite a lot on verifier not complaining eagerly about some
> >> potentially invalid instructions if it's provable that some portion of
> >> the code won't ever be reached (think using .rodata variables for
> >> feature gating, poisoning intructions due to failed CO-RE relocation,
> >> which libbpf does actively, except it's using a call to non-existing
> >> helper). As such, check_cfg() is a wrong place to do such validity
> >> checks because some of the branches might never be run and validated
> >> in practice.
> >
> > Don't really agree. Jump to the middle of ld_imm64 is just like jumping
> > out of bounds, both break the CFG integrity immediately. For those
> > apparently incorrect  jumps, rejecting early makes everything simple;
> > otherwise, we probably need some rewrite in the end.
>
> Could you elaborate on the 'breaking CFG integrity immediately'? This was
> what I was trying to gather earlier with log improvement vs actual fix.
>
> Do you mean /potentially/ breaking CFG integrity, if, say, we had a doubl=
e
> insn jump in future and there is a back-jump to the 2nd part of the insn?
>

I mean jumping to the middle of ld_imm64 is similar to jumping out-of-bound=
,
both are CFG-related issues and can be handled early in one place.

For the case you mentioned, the current code would handle such an issue in
check_ld_imm64(), and again gives "BAD_LD_IMM" log, which is strange.

> > Also, as you mentioned, libbpf relies on non-existing helpers, not jump
> > to the middle of ld_imm64. It seems better and easier to not leave this
> > hole.
>
> Thanks,
> Daniel