[PATCH bpf-next v3 0/3] bpf: Detect jumping to reserved code of ld_imm64

[PATCH bpf-next v3 0/3] bpf: Detect jumping to reserved code of ld_imm64

[Hao Sun]

Currently, the verifier rejects a program jumping to reserved code with
the log "invalid BPF_LD_IMM" in check_ld_imm(), which in not accurate,
because the program does not contain any invalid insns. The root cause
is that the verifier does not detect such jump, thus the reserved code
is passed to check_ld_imm().

The first patch makes the verifier detect jump to reserved code during
check_cfg(). Because jump to reserved code is just like jump out bound,
both break the CFG integrity immediately. The second makes the verifier
report internal error if it sees an invlid ld_imm64 in check_ld_imm(),
because we already have bpf_opcode_in_insntable() to check the validity
of insn code. The third patch adapts existing tests to make them pass,
and add a new case to test backward jump to reserved code.

Signed-off-by: Hao Sun <sunhao.th@gmail.com>

---
Changes in v3:
- Separate changes to different commits, change verifier log
- Link to v2: https://lore.kernel.org/r/20231010-jmp-into-reserved-fields-v2-1-3dd5a94d1e21@gmail.com

Changes in v2:
- Adjust existing test cases
- Link to v1: https://lore.kernel.org/bpf/20231009-jmp-into-reserved-fields-v1-1-d8006e2ac1f6@gmail.com/

---
Hao Sun (3):
      bpf: Detect jumping to reserved code during check_cfg()
      bpf: Report internal error on incorrect ld_imm64 in check_ld_imm()
      bpf: Adapt and add tests for detecting jump to reserved code

 kernel/bpf/verifier.c                           | 11 +++++++++--
 tools/testing/selftests/bpf/verifier/ld_imm64.c | 16 ++++++++++++----
 2 files changed, 21 insertions(+), 6 deletions(-)
---
base-commit: 3157b7ce14bbf468b0ca8613322a05c37b5ae25d
change-id: 20231009-jmp-into-reserved-fields-fc1a98a8e7dc

Best regards,
-- 
Hao Sun <sunhao.th@gmail.com>

[PATCH bpf-next v3 1/3] bpf: Detect jumping to reserved code during check_cfg()

[Hao Sun]

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=ctx(off=0,imm=0) R10=fp0
0: (18) r4 = 0xffff888103436000       ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0)
2: (18) r1 = 0x1d                     ; R1_w=29
4: (55) if r4 != 0x0 goto pc+4        ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0)
5: (1c) w1 -= w1                      ; R1_w=0
6: (18) r5 = 0x32                     ; R5_w=50
8: (56) if w5 != 0xfffffff4 goto pc-2
mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx -1
mark_precise: frame0: regs=r5 stack= before 6: (18) r5 = 0x32
7: R5_w=50
7: BUG_ld_00
invalid BPF_LD_IMM insn

Here the verifier rejects the program because it thinks insn at 7 is 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 invalid insn.
Therefore, make the verifier check the jump target during check_cfg(). For
the same program, the verifier reports the following log:

func#0 @0
jump to reserved code from insn 8 to 7

Signed-off-by: Hao Sun <sunhao.th@gmail.com>
---
 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, struct bpf_verifier_env *env,
 {
 	int *insn_stack = env->cfg.insn_stack;
 	int *insn_state = env->cfg.insn_state;
+	struct bpf_insn *insns = env->prog->insnsi;
 
 	if (e == FALLTHROUGH && insn_state[t] >= (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 == BRANCH && insns[w].code == 0) {
+		verbose_linfo(env, t, "%d", t);
+		verbose(env, "jump to reserved code from insn %d to %d\n", t, w);
+		return -EINVAL;
+	}
+
 	if (e == BRANCH) {
 		/* mark branch target for state pruning */
 		mark_prune_point(env, w);

-- 
2.34.1

[PATCH bpf-next v3 2/3] bpf: Report internal error on incorrect ld_imm64 in check_ld_imm()

[Hao Sun]

The verifier currently reports "invalid BPF_LD_IMM64 insn" if the size
of ld_imm64 is not BPF_DW. The log is not accurate, bacause we already
have bpf_code_in_insntable() check in resolve_pseudo_idimm64(), which
guarantees the validity of insn code. If the verifier meets an invalid
ld_imm64 in check_ld_imm(), then somewhere else in the verifier must be
wrong. In such case, current log is confusing and does not reflect the
right thing. Therefore, make the verifier report internal error.

Signed-off-by: Hao Sun <sunhao.th@gmail.com>
---
 kernel/bpf/verifier.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 725ac0b464cf..d25838a2c430 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) != BPF_DW) {
-		verbose(env, "invalid BPF_LD_IMM insn\n");
-		return -EINVAL;
+		verbose(env, "verifier internal error: ld_imm64 size is not BPF_DW\n");
+		return -EFAULT;
 	}
 	if (insn->off != 0) {
 		verbose(env, "BPF_LD_IMM64 uses reserved fields\n");

-- 
2.34.1

[PATCH bpf-next v3 3/3] bpf: Adapt and add tests for detecting jump to reserved code

[Hao Sun]

Adapt errstr of existing tests to make them pass, and add a new case
to test backward jump to reserved code.

Signed-off-by: Hao Sun <sunhao.th@gmail.com>
---
 tools/testing/selftests/bpf/verifier/ld_imm64.c | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)

diff --git a/tools/testing/selftests/bpf/verifier/ld_imm64.c b/tools/testing/selftests/bpf/verifier/ld_imm64.c
index f9297900cea6..aa3ada0062d9 100644
--- a/tools/testing/selftests/bpf/verifier/ld_imm64.c
+++ b/tools/testing/selftests/bpf/verifier/ld_imm64.c
@@ -9,8 +9,7 @@
 	BPF_MOV64_IMM(BPF_REG_0, 2),
 	BPF_EXIT_INSN(),
 	},
-	.errstr = "invalid BPF_LD_IMM insn",
-	.errstr_unpriv = "R1 pointer comparison",
+	.errstr = "jump to reserved code",
 	.result = REJECT,
 },
 {
@@ -23,8 +22,7 @@
 	BPF_LD_IMM64(BPF_REG_0, 1),
 	BPF_EXIT_INSN(),
 	},
-	.errstr = "invalid BPF_LD_IMM insn",
-	.errstr_unpriv = "R1 pointer comparison",
+	.errstr = "jump to reserved code",
 	.result = REJECT,
 },
 {
@@ -144,3 +142,13 @@
 	.errstr = "unrecognized bpf_ld_imm64 insn",
 	.result = REJECT,
 },
+{
+	"test15 ld_imm64",
+	.insns = {
+	BPF_LD_IMM64(BPF_REG_0, 0),
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 0, -2),
+	BPF_EXIT_INSN(),
+	},
+	.errstr = "jump to reserved code",
+	.result = REJECT,
+},

-- 
2.34.1

Re: [PATCH bpf-next v3 1/3] bpf: Detect jumping to reserved code during check_cfg()

[Alexei Starovoitov]

On Wed, Oct 11, 2023 at 2:01 AM Hao Sun <sunhao.th@gmail.com> 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=ctx(off=0,imm=0) R10=fp0
> 0: (18) r4 = 0xffff888103436000       ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0)
> 2: (18) r1 = 0x1d                     ; R1_w=29
> 4: (55) if r4 != 0x0 goto pc+4        ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0)
> 5: (1c) w1 -= w1                      ; R1_w=0
> 6: (18) r5 = 0x32                     ; R5_w=50
> 8: (56) if w5 != 0xfffffff4 goto pc-2
> mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx -1
> mark_precise: frame0: regs=r5 stack= before 6: (18) r5 = 0x32
> 7: R5_w=50
> 7: BUG_ld_00
> invalid BPF_LD_IMM insn
>
> Here the verifier rejects the program because it thinks insn at 7 is 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 invalid insn.
> Therefore, make the verifier check the jump target during check_cfg(). For
> the same program, the verifier reports the following log:
>
> func#0 @0
> jump to reserved code from insn 8 to 7
>
> Signed-off-by: Hao Sun <sunhao.th@gmail.com>
> ---
>  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, struct bpf_verifier_env *env,
>  {
>         int *insn_stack = env->cfg.insn_stack;
>         int *insn_state = env->cfg.insn_state;
> +       struct bpf_insn *insns = env->prog->insnsi;
>
>         if (e == FALLTHROUGH && insn_state[t] >= (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 == BRANCH && insns[w].code == 0) {
> +               verbose_linfo(env, t, "%d", t);
> +               verbose(env, "jump to reserved code from insn %d to %d\n", t, w);
> +               return -EINVAL;
> +       }

I don't think we should be changing the verifier to make
fuzzer logs more readable.

Same with patch 2. The code is fine as-is.

Re: [PATCH bpf-next v3 1/3] bpf: Detect jumping to reserved code during check_cfg()

[Hao Sun]

On Wed, Oct 11, 2023 at 3:39 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Wed, Oct 11, 2023 at 2:01 AM Hao Sun <sunhao.th@gmail.com> 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=ctx(off=0,imm=0) R10=fp0
> > 0: (18) r4 = 0xffff888103436000       ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0)
> > 2: (18) r1 = 0x1d                     ; R1_w=29
> > 4: (55) if r4 != 0x0 goto pc+4        ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0)
> > 5: (1c) w1 -= w1                      ; R1_w=0
> > 6: (18) r5 = 0x32                     ; R5_w=50
> > 8: (56) if w5 != 0xfffffff4 goto pc-2
> > mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx -1
> > mark_precise: frame0: regs=r5 stack= before 6: (18) r5 = 0x32
> > 7: R5_w=50
> > 7: BUG_ld_00
> > invalid BPF_LD_IMM insn
> >
> > Here the verifier rejects the program because it thinks insn at 7 is 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 invalid insn.
> > Therefore, make the verifier check the jump target during check_cfg(). For
> > the same program, the verifier reports the following log:
> >
> > func#0 @0
> > jump to reserved code from insn 8 to 7
> >
> > Signed-off-by: Hao Sun <sunhao.th@gmail.com>
> > ---
> >  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, struct bpf_verifier_env *env,
> >  {
> >         int *insn_stack = env->cfg.insn_stack;
> >         int *insn_state = env->cfg.insn_state;
> > +       struct bpf_insn *insns = env->prog->insnsi;
> >
> >         if (e == FALLTHROUGH && insn_state[t] >= (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 == BRANCH && insns[w].code == 0) {
> > +               verbose_linfo(env, t, "%d", t);
> > +               verbose(env, "jump to reserved code from insn %d to %d\n", t, w);
> > +               return -EINVAL;
> > +       }
>
> I don't think we should be changing the verifier to make
> fuzzer logs more readable.
>
> Same with patch 2. The code is fine as-is.

Confused, the changes are not for fuzzer logs but to handle jumping to
the middle of ld_imm64. Like jumping out of bounds, both are similar
issues and can be handled in one place.

The current code handles such incorrect jumps in check_ld_imm(), which
is strange, and the error log "BAD_LD_IMM" rather than "bad jump" is
also strange.

The second one is just for verifier debugging because the only
caller of check_ld_imm() is do_check(), before which we already
have resolve_pseudo_ldimm64() which has opcode_in_insntable()
to check the validity of insn code. The only reason we could see
an invalid ld_imm64 in check_id_imm() is errors somewhere else.

Re: [PATCH bpf-next v3 1/3] bpf: Detect jumping to reserved code during check_cfg()

[Shung-Hsi Yu]

On Wed, Oct 11, 2023 at 06:38:56AM -0700, Alexei Starovoitov wrote:
> On Wed, Oct 11, 2023 at 2:01 AM Hao Sun <sunhao.th@gmail.com> 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=ctx(off=0,imm=0) R10=fp0
> > 0: (18) r4 = 0xffff888103436000       ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0)
> > 2: (18) r1 = 0x1d                     ; R1_w=29
> > 4: (55) if r4 != 0x0 goto pc+4        ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0)
> > 5: (1c) w1 -= w1                      ; R1_w=0
> > 6: (18) r5 = 0x32                     ; R5_w=50
> > 8: (56) if w5 != 0xfffffff4 goto pc-2
> > mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx -1
> > mark_precise: frame0: regs=r5 stack= before 6: (18) r5 = 0x32
> > 7: R5_w=50
> > 7: BUG_ld_00
> > invalid BPF_LD_IMM insn
> >
> > Here the verifier rejects the program because it thinks insn at 7 is 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 invalid insn.
> > Therefore, make the verifier check the jump target during check_cfg(). For
> > the same program, the verifier reports the following log:
> >
> > func#0 @0
> > jump to reserved code from insn 8 to 7
> >
> > Signed-off-by: Hao Sun <sunhao.th@gmail.com>
> > ---
> >  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, struct bpf_verifier_env *env,
> >  {
> >         int *insn_stack = env->cfg.insn_stack;
> >         int *insn_state = env->cfg.insn_state;
> > +       struct bpf_insn *insns = env->prog->insnsi;
> >
> >         if (e == FALLTHROUGH && insn_state[t] >= (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 == BRANCH && insns[w].code == 0) {
> > +               verbose_linfo(env, t, "%d", t);
> > +               verbose(env, "jump to reserved code from insn %d to %d\n", t, w);
> > +               return -EINVAL;
> > +       }
> 
> I don't think we should be changing the verifier to make
> fuzzer logs more readable.

Taking fuzzer out of consideration, giving users clearer explanation for
such verifier rejection could save a lot of head scratching.

Compiler shouldn't generate such program, but its plausible to forget to
account that BPF_LD_IMM64 consists of two instructions when writing
assembly (especially with filter.h-like macros) and have it jump to the 2nd
part of BPF_LD_IMM64.

> Same with patch 2. The code is fine as-is.

The only way BPF_SIZE(insn->code) != BPF_DW conditional in check_ld_imm()
can be met right now is when we have a jump to the 2nd part of LD_IMM64; but
what this conditional actually guard against is not straight-forward and
quite confusing[1].


Shung-Hsi

1: https://lore.kernel.org/bpf/0cf50c32-ab67-ef23-7b84-ef1d4e007c33@fb.com/

Re: [PATCH bpf-next v3 1/3] bpf: Detect jumping to reserved code during check_cfg()

[Alexei Starovoitov]

On Thu, Oct 12, 2023 at 1:14 AM Shung-Hsi Yu <shung-hsi.yu@suse.com> wrote:
>
> On Wed, Oct 11, 2023 at 06:38:56AM -0700, Alexei Starovoitov wrote:
> > On Wed, Oct 11, 2023 at 2:01 AM Hao Sun <sunhao.th@gmail.com> 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=ctx(off=0,imm=0) R10=fp0
> > > 0: (18) r4 = 0xffff888103436000       ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0)
> > > 2: (18) r1 = 0x1d                     ; R1_w=29
> > > 4: (55) if r4 != 0x0 goto pc+4        ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0)
> > > 5: (1c) w1 -= w1                      ; R1_w=0
> > > 6: (18) r5 = 0x32                     ; R5_w=50
> > > 8: (56) if w5 != 0xfffffff4 goto pc-2
> > > mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx -1
> > > mark_precise: frame0: regs=r5 stack= before 6: (18) r5 = 0x32
> > > 7: R5_w=50
> > > 7: BUG_ld_00
> > > invalid BPF_LD_IMM insn
> > >
> > > Here the verifier rejects the program because it thinks insn at 7 is 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 invalid insn.
> > > Therefore, make the verifier check the jump target during check_cfg(). For
> > > the same program, the verifier reports the following log:
> > >
> > > func#0 @0
> > > jump to reserved code from insn 8 to 7
> > >
> > > Signed-off-by: Hao Sun <sunhao.th@gmail.com>
> > > ---
> > >  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, struct bpf_verifier_env *env,
> > >  {
> > >         int *insn_stack = env->cfg.insn_stack;
> > >         int *insn_state = env->cfg.insn_state;
> > > +       struct bpf_insn *insns = env->prog->insnsi;
> > >
> > >         if (e == FALLTHROUGH && insn_state[t] >= (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 == BRANCH && insns[w].code == 0) {
> > > +               verbose_linfo(env, t, "%d", t);
> > > +               verbose(env, "jump to reserved code from insn %d to %d\n", t, w);
> > > +               return -EINVAL;
> > > +       }
> >
> > I don't think we should be changing the verifier to make
> > fuzzer logs more readable.
>
> Taking fuzzer out of consideration, giving users clearer explanation for
> such verifier rejection could save a lot of head scratching.

Users won't see such errors unless they are actively doing what
is not recommended.

> Compiler shouldn't generate such program, but its plausible to forget to
> account that BPF_LD_IMM64 consists of two instructions when writing
> assembly (especially with filter.h-like macros) and have it jump to the 2nd
> part of BPF_LD_IMM64.

Using macros to write bpf asm code is highly discouraged.
All kinds of errors are possible.
Bogus jump is just one of such mistakes.
Use naked functions and inline asm in C code that
both GCC and clang understand then you won't see bad jumps.
See selftets/bpf/verifier_*.c as an example.

> > Same with patch 2. The code is fine as-is.
>
> The only way BPF_SIZE(insn->code) != BPF_DW conditional in check_ld_imm()
> can be met right now is when we have a jump to the 2nd part of LD_IMM64; but
> what this conditional actually guard against is not straight-forward and
> quite confusing[1].

There are plenty of cases in the verifier where we print
an error message. Some of them should be impossible due
to prior checks. In such cases we don't yell "verifier bug"
and are not going to do that in this case either.

Re: [PATCH bpf-next v3 1/3] bpf: Detect jumping to reserved code during check_cfg()

[Shung-Hsi Yu]

On Thu, Oct 12, 2023 at 08:02:00AM -0700, Alexei Starovoitov wrote:
> On Thu, Oct 12, 2023 at 1:14 AM Shung-Hsi Yu <shung-hsi.yu@suse.com> wrote:
> > On Wed, Oct 11, 2023 at 06:38:56AM -0700, Alexei Starovoitov wrote:
> > > On Wed, Oct 11, 2023 at 2:01 AM Hao Sun <sunhao.th@gmail.com> 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=ctx(off=0,imm=0) R10=fp0
> > > > 0: (18) r4 = 0xffff888103436000       ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0)
> > > > 2: (18) r1 = 0x1d                     ; R1_w=29
> > > > 4: (55) if r4 != 0x0 goto pc+4        ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0)
> > > > 5: (1c) w1 -= w1                      ; R1_w=0
> > > > 6: (18) r5 = 0x32                     ; R5_w=50
> > > > 8: (56) if w5 != 0xfffffff4 goto pc-2
> > > > mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx -1
> > > > mark_precise: frame0: regs=r5 stack= before 6: (18) r5 = 0x32
> > > > 7: R5_w=50
> > > > 7: BUG_ld_00
> > > > invalid BPF_LD_IMM insn
> > > >
> > > > Here the verifier rejects the program because it thinks insn at 7 is 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 invalid insn.
> > > > Therefore, make the verifier check the jump target during check_cfg(). For
> > > > the same program, the verifier reports the following log:
> > > >
> > > > func#0 @0
> > > > jump to reserved code from insn 8 to 7
> > > >
> > > > Signed-off-by: Hao Sun <sunhao.th@gmail.com>
> > > > ---
> > > >  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, struct bpf_verifier_env *env,
> > > >  {
> > > >         int *insn_stack = env->cfg.insn_stack;
> > > >         int *insn_state = env->cfg.insn_state;
> > > > +       struct bpf_insn *insns = env->prog->insnsi;
> > > >
> > > >         if (e == FALLTHROUGH && insn_state[t] >= (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 == BRANCH && insns[w].code == 0) {
> > > > +               verbose_linfo(env, t, "%d", t);
> > > > +               verbose(env, "jump to reserved code from insn %d to %d\n", t, w);
> > > > +               return -EINVAL;
> > > > +       }
> > >
> > > I don't think we should be changing the verifier to make
> > > fuzzer logs more readable.
> >
> > Taking fuzzer out of consideration, giving users clearer explanation for
> > such verifier rejection could save a lot of head scratching.
> 
> Users won't see such errors unless they are actively doing what
> is not recommended.
> 
> > Compiler shouldn't generate such program, but its plausible to forget to
> > account that BPF_LD_IMM64 consists of two instructions when writing
> > assembly (especially with filter.h-like macros) and have it jump to the 2nd
> > part of BPF_LD_IMM64.
> 
> Using macros to write bpf asm code is highly discouraged.
> All kinds of errors are possible.
> Bogus jump is just one of such mistakes.
> Use naked functions and inline asm in C code that
> both GCC and clang understand then you won't see bad jumps.
> See selftets/bpf/verifier_*.c as an example.

Understood, thanks for the explanation!

Found them under progs/verifier_*.c inside the bpf selftest directory.

> > > Same with patch 2. The code is fine as-is.
> >
> > The only way BPF_SIZE(insn->code) != BPF_DW conditional in check_ld_imm()
> > can be met right now is when we have a jump to the 2nd part of LD_IMM64; but
> > what this conditional actually guard against is not straight-forward and
> > quite confusing[1].
> 
> There are plenty of cases in the verifier where we print
> an error message. Some of them should be impossible due
> to prior checks. In such cases we don't yell "verifier bug"
> and are not going to do that in this case either.

I agree, without patch 1 applied, the change to "verfier bug" in patch 2
doesn't make sense and is just wrong. The point I'm trying to make is that
the checks done by verifier are generally clear, you can make sense of why
certain check are in place just by looking at the code, but
BPF_SIZE(insn->code) != BPF_DW is _not_ one of them.

I got confused, (reading between the lines I believe) this had Hao puzzled,
and even Yongsong had to look twice[1] back then; so this check is certainly
not on-par with others we have in the verifier in terms of clarity, which
leads to patches here as well as mine a while back.

Perhaps we could reconsider making it more obvious how verifier prevents
jump to reserved code/2nd instruction of LD_IMM64?


1: the same https://lore.kernel.org/bpf/0cf50c32-ab67-ef23-7b84-ef1d4e007c33@fb.com/

Re: [PATCH bpf-next v3 1/3] bpf: Detect jumping to reserved code during check_cfg()

[Alexei Starovoitov]

On Thu, Oct 12, 2023 at 8:28 PM Shung-Hsi Yu <shung-hsi.yu@suse.com> wrote:
>
> On Thu, Oct 12, 2023 at 08:02:00AM -0700, Alexei Starovoitov wrote:
> > On Thu, Oct 12, 2023 at 1:14 AM Shung-Hsi Yu <shung-hsi.yu@suse.com> wrote:
> > > On Wed, Oct 11, 2023 at 06:38:56AM -0700, Alexei Starovoitov wrote:
> > > > On Wed, Oct 11, 2023 at 2:01 AM Hao Sun <sunhao.th@gmail.com> 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=ctx(off=0,imm=0) R10=fp0
> > > > > 0: (18) r4 = 0xffff888103436000       ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0)
> > > > > 2: (18) r1 = 0x1d                     ; R1_w=29
> > > > > 4: (55) if r4 != 0x0 goto pc+4        ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0)
> > > > > 5: (1c) w1 -= w1                      ; R1_w=0
> > > > > 6: (18) r5 = 0x32                     ; R5_w=50
> > > > > 8: (56) if w5 != 0xfffffff4 goto pc-2
> > > > > mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx -1
> > > > > mark_precise: frame0: regs=r5 stack= before 6: (18) r5 = 0x32
> > > > > 7: R5_w=50
> > > > > 7: BUG_ld_00
> > > > > invalid BPF_LD_IMM insn
> > > > >
> > > > > Here the verifier rejects the program because it thinks insn at 7 is 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 invalid insn.
> > > > > Therefore, make the verifier check the jump target during check_cfg(). For
> > > > > the same program, the verifier reports the following log:
> > > > >
> > > > > func#0 @0
> > > > > jump to reserved code from insn 8 to 7
> > > > >
> > > > > Signed-off-by: Hao Sun <sunhao.th@gmail.com>
> > > > > ---
> > > > >  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, struct bpf_verifier_env *env,
> > > > >  {
> > > > >         int *insn_stack = env->cfg.insn_stack;
> > > > >         int *insn_state = env->cfg.insn_state;
> > > > > +       struct bpf_insn *insns = env->prog->insnsi;
> > > > >
> > > > >         if (e == FALLTHROUGH && insn_state[t] >= (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 == BRANCH && insns[w].code == 0) {
> > > > > +               verbose_linfo(env, t, "%d", t);
> > > > > +               verbose(env, "jump to reserved code from insn %d to %d\n", t, w);
> > > > > +               return -EINVAL;
> > > > > +       }
> > > >
> > > > I don't think we should be changing the verifier to make
> > > > fuzzer logs more readable.
> > >
> > > Taking fuzzer out of consideration, giving users clearer explanation for
> > > such verifier rejection could save a lot of head scratching.
> >
> > Users won't see such errors unless they are actively doing what
> > is not recommended.
> >
> > > Compiler shouldn't generate such program, but its plausible to forget to
> > > account that BPF_LD_IMM64 consists of two instructions when writing
> > > assembly (especially with filter.h-like macros) and have it jump to the 2nd
> > > part of BPF_LD_IMM64.
> >
> > Using macros to write bpf asm code is highly discouraged.
> > All kinds of errors are possible.
> > Bogus jump is just one of such mistakes.
> > Use naked functions and inline asm in C code that
> > both GCC and clang understand then you won't see bad jumps.
> > See selftets/bpf/verifier_*.c as an example.
>
> Understood, thanks for the explanation!
>
> Found them under progs/verifier_*.c inside the bpf selftest directory.
>
> > > > Same with patch 2. The code is fine as-is.
> > >
> > > The only way BPF_SIZE(insn->code) != BPF_DW conditional in check_ld_imm()
> > > can be met right now is when we have a jump to the 2nd part of LD_IMM64; but
> > > what this conditional actually guard against is not straight-forward and
> > > quite confusing[1].
> >
> > There are plenty of cases in the verifier where we print
> > an error message. Some of them should be impossible due
> > to prior checks. In such cases we don't yell "verifier bug"
> > and are not going to do that in this case either.
>
> I agree, without patch 1 applied, the change to "verfier bug" in patch 2
> doesn't make sense and is just wrong. The point I'm trying to make is that
> the checks done by verifier are generally clear, you can make sense of why
> certain check are in place just by looking at the code, but
> BPF_SIZE(insn->code) != BPF_DW is _not_ one of them.
>
> I got confused, (reading between the lines I believe) this had Hao puzzled,
> and even Yongsong had to look twice[1] back then; so this check is certainly
> not on-par with others we have in the verifier in terms of clarity, which
> leads to patches here as well as mine a while back.
>
> Perhaps we could reconsider making it more obvious how verifier prevents
> jump to reserved code/2nd instruction of LD_IMM64?

I agree that the message is confusing.
My point is that people see it only when they code in asm with macros.
Anyone who was doing that a lot saw that message and probably debugged
much worse issues while inserting an asm macro and forgetting to
adjust constants in branches. The code might even load, but will
execute something totally different.
asm macros are a nightmare to debug. Adding more code to the verifier
to help with one particular case is not going to help much.
Use inline asm in C is the right answer for folks that still need asm.

UX of the verifier sucks and we need to improve. So please focus on impactful
improvements instead of hacking on niche cases.

Re: [PATCH bpf-next v3 1/3] bpf: Detect jumping to reserved code during check_cfg()

[Shung-Hsi Yu]

On Thu, Oct 19, 2023 at 05:25:26PM -0700, Alexei Starovoitov wrote:
> On Thu, Oct 12, 2023 at 8:28 PM Shung-Hsi Yu <shung-hsi.yu@suse.com> wrote:
> > On Thu, Oct 12, 2023 at 08:02:00AM -0700, Alexei Starovoitov wrote:
> > > On Thu, Oct 12, 2023 at 1:14 AM Shung-Hsi Yu <shung-hsi.yu@suse.com> wrote:
> > > > On Wed, Oct 11, 2023 at 06:38:56AM -0700, Alexei Starovoitov wrote:
> > > > > On Wed, Oct 11, 2023 at 2:01 AM Hao Sun <sunhao.th@gmail.com> 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=ctx(off=0,imm=0) R10=fp0
> > > > > > 0: (18) r4 = 0xffff888103436000       ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0)
> > > > > > 2: (18) r1 = 0x1d                     ; R1_w=29
> > > > > > 4: (55) if r4 != 0x0 goto pc+4        ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0)
> > > > > > 5: (1c) w1 -= w1                      ; R1_w=0
> > > > > > 6: (18) r5 = 0x32                     ; R5_w=50
> > > > > > 8: (56) if w5 != 0xfffffff4 goto pc-2
> > > > > > mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx -1
> > > > > > mark_precise: frame0: regs=r5 stack= before 6: (18) r5 = 0x32
> > > > > > 7: R5_w=50
> > > > > > 7: BUG_ld_00
> > > > > > invalid BPF_LD_IMM insn
> > > > > >
> > > > > > Here the verifier rejects the program because it thinks insn at 7 is 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 invalid insn.
> > > > > > Therefore, make the verifier check the jump target during check_cfg(). For
> > > > > > the same program, the verifier reports the following log:
> > > > > >
> > > > > > func#0 @0
> > > > > > jump to reserved code from insn 8 to 7
> > > > > >
> > > > > > Signed-off-by: Hao Sun <sunhao.th@gmail.com>
> > > > > > ---
> > > > > >  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, struct bpf_verifier_env *env,
> > > > > >  {
> > > > > >         int *insn_stack = env->cfg.insn_stack;
> > > > > >         int *insn_state = env->cfg.insn_state;
> > > > > > +       struct bpf_insn *insns = env->prog->insnsi;
> > > > > >
> > > > > >         if (e == FALLTHROUGH && insn_state[t] >= (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 == BRANCH && insns[w].code == 0) {
> > > > > > +               verbose_linfo(env, t, "%d", t);
> > > > > > +               verbose(env, "jump to reserved code from insn %d to %d\n", t, w);
> > > > > > +               return -EINVAL;
> > > > > > +       }
> > > > >
> > > > > I don't think we should be changing the verifier to make
> > > > > fuzzer logs more readable.
> > > >
> > > > Taking fuzzer out of consideration, giving users clearer explanation for
> > > > such verifier rejection could save a lot of head scratching.
> > >
> > > Users won't see such errors unless they are actively doing what
> > > is not recommended.
> > >
> > > > Compiler shouldn't generate such program, but its plausible to forget to
> > > > account that BPF_LD_IMM64 consists of two instructions when writing
> > > > assembly (especially with filter.h-like macros) and have it jump to the 2nd
> > > > part of BPF_LD_IMM64.
> > >
> > > Using macros to write bpf asm code is highly discouraged.
> > > All kinds of errors are possible.
> > > Bogus jump is just one of such mistakes.
> > > Use naked functions and inline asm in C code that
> > > both GCC and clang understand then you won't see bad jumps.
> > > See selftets/bpf/verifier_*.c as an example.
> >
> > Understood, thanks for the explanation!
> >
> > Found them under progs/verifier_*.c inside the bpf selftest directory.
> >
> > > > > Same with patch 2. The code is fine as-is.
> > > >
> > > > The only way BPF_SIZE(insn->code) != BPF_DW conditional in check_ld_imm()
> > > > can be met right now is when we have a jump to the 2nd part of LD_IMM64; but
> > > > what this conditional actually guard against is not straight-forward and
> > > > quite confusing[1].
> > >
> > > There are plenty of cases in the verifier where we print
> > > an error message. Some of them should be impossible due
> > > to prior checks. In such cases we don't yell "verifier bug"
> > > and are not going to do that in this case either.
> >
> > I agree, without patch 1 applied, the change to "verfier bug" in patch 2
> > doesn't make sense and is just wrong. The point I'm trying to make is that
> > the checks done by verifier are generally clear, you can make sense of why
> > certain check are in place just by looking at the code, but
> > BPF_SIZE(insn->code) != BPF_DW is _not_ one of them.
> >
> > I got confused, (reading between the lines I believe) this had Hao puzzled,
> > and even Yongsong had to look twice[1] back then; so this check is certainly
> > not on-par with others we have in the verifier in terms of clarity, which
> > leads to patches here as well as mine a while back.
> >
> > Perhaps we could reconsider making it more obvious how verifier prevents
> > jump to reserved code/2nd instruction of LD_IMM64?
> 
> I agree that the message is confusing.
> My point is that people see it only when they code in asm with macros.
> Anyone who was doing that a lot saw that message and probably debugged
> much worse issues while inserting an asm macro and forgetting to
> adjust constants in branches. The code might even load, but will
> execute something totally different.
> asm macros are a nightmare to debug. Adding more code to the verifier
> to help with one particular case is not going to help much.
> Use inline asm in C is the right answer for folks that still need asm.
> 
> UX of the verifier sucks and we need to improve. So please focus on impactful
> improvements instead of hacking on niche cases.

Ok, can't say I agree entirely, but it's a niche case alright, and I'll
leave this alone.