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>
In-Reply-To: <92f824ec-9538-501c-e63e-8483ffe14bad@iogearbox.net>
From:   Hao Sun <sunhao.th@gmail.com>
Date:   Tue, 10 Oct 2023 11:17:33 +0200
Message-ID: <CACkBjsbM8=NLwwEUea21vqCrn-w9cn21gL3BNpU4AupYnuCvJg@mail.gmail.com>
Subject: Re: [PATCH bpf-next] Detect jumping to reserved code during check_cfg()
To:     Daniel Borkmann <daniel@iogearbox.net>
Cc:     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 Tue, Oct 10, 2023 at 10:33=E2=80=AFAM Daniel Borkmann <daniel@iogearbox.=
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 co=
de of
> >> ld_imm64. Instead, such a issue is captured in check_ld_imm(). The ver=
ifier
> >> 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=3D=
4,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=3D=
4,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 is a=
n
> >> invalid BPF_LD_IMM, but such a error log is not accurate since the iss=
ue
> >> is jumping to reserved code not because the program contains invalid i=
nsn.
> >> 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 you c=
reate
> > this case? Is it just something you did manually and noticed a strange =
error?
>
> Curious as well.

I just wrote a testing tool for the verifier, which uses a test oracle
to capture
incorrect verifier's states, capturing incorrect verifier logs is a
bonus from this.
The bug is captured during testing the testing tool :). I will publish
the work when
I think it's useful enough and ready.

>
> We do have test cases which try to jump into the middle of a double insn =
as can
> be seen that this patch breaks BPF CI with regards to log mismatch below =
(which
> still needs to be adapted, too). Either way, it probably doesn't hurt to =
also add
> the above snippet as a test.
>

Will add a test case for this, and try to fix these broken tests, in patch =
v2.

> Hao, as I understand, the patch here is an usability improvement (not a f=
ix per se)
> where we reject such cases earlier during cfg check rather than at a late=
r point
> where we validate ld_imm instruction. Or are there cases you found which =
were not
> yet captured via current check_ld_imm()?
>

I regard this as a fix, because the verifier log is not correct, since
the program does
not contain any invalid ld_imm64 instructions in this case.

I haven't met other cases not captured via check_ld_imm(), but somehow, I t=
hink
we probably want to convert the check there as an internal bug,
because we already
have bpf_opcode_in_insntable() check in resolve_pseudo_ldimm64(). Once we m=
eet
invalid insn code here, then somewhere else in the verifier is
probably wrong. But
I'm not sure, maybe something like this:

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index eed7350e15f4..bed97de568a5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -14532,8 +14532,8 @@ static int check_ld_imm(struct
bpf_verifier_env *env, struct bpf_insn *insn)
        int err;

        if (BPF_SIZE(insn->code) !=3D BPF_DW) {
-               verbose(env, "invalid BPF_LD_IMM insn\n");
-               return -EINVAL;
+               verbose(env, "verifier internal bug, invalid BPF_LD_IMM\n")=
;
+               return -EFAULT;
        }
        if (insn->off !=3D 0) {
                verbose(env, "BPF_LD_IMM64 uses reserved fields\n");

> 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_states 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_states 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_states 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_states 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_states 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_states 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_states 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_states 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.
>

Noted.

> >> ---
> >>   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, stru=
ct 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 | FALL=
THROUGH))
> >>              return DONE_EXPLORING;
> >> @@ -14993,6 +14994,12 @@ static int push_insn(int t, int w, int e, str=
uct 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.
>
> >>      if (e =3D=3D BRANCH) {
> >>              /* mark branch target for state pruning */
> >>              mark_prune_point(env, w);
> >>