[PATCH bpf-next 0/4] bpf: verifier: remove redundant opcode checks

[PATCH bpf-next 0/4] bpf: verifier: remove redundant opcode checks

[Shung-Hsi Yu]

This patch set aims to remove opcode checks in BPF verifier that have
become redundant since commit 5e581dad4fec ("bpf: make unknown opcode
handling more robust"), either remove them entirely, or turn them into
comments in places where the redundancy may not be clear.

The exceptions here are opcode check for BPF_LD_{ABS,IND} and
BPF_JMP_{JA,CALL,EXIT}; they cover opcode validation not done in
bpf_opcode_in_insntable() so is not removed.

After apply the patch set test_verifier passes and does not need further
modification:
  Summary: 1348 PASSED, 635 SKIPPED, 0 FAILED

Also, add comments at places that I find confusing while working on the
removal, namely:

  1. resolve_pseudo_ldimm64() also validates opcode
  2. BPF_SIZE check in check_ld_imm() guards against JMP to the 2nd
     BPF_LD_IMM64 instruction
  3. reason behind why ld_imm64 test cases should be rejected by the
     verifier


Shung-Hsi Yu (4):
  bpf: verifier: update resolve_pseudo_ldimm64() comment
  bpf: verifier: explain opcode check in check_ld_imm()
  bpf: verifier: remove redundant opcode checks
  selftests/bpf: add reason of rejection in ld_imm64

 kernel/bpf/verifier.c                         | 33 ++++++++-----------
 .../testing/selftests/bpf/verifier/ld_imm64.c | 20 ++++++-----
 2 files changed, 25 insertions(+), 28 deletions(-)


base-commit: 68084a13642001b73aade05819584f18945f3297
-- 
2.36.1

[PATCH bpf-next 1/4] bpf: verifier: update resolve_pseudo_ldimm64() comment

[Shung-Hsi Yu]

Since commit 5e581dad4fec ("bpf: make unknown opcode handling more
robust") the verifier also checks for opcode validity while resolving
file descriptor, update the comment to reflect such fact.

Signed-off-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
---
 kernel/bpf/verifier.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 9b59581026f8..79a2695ee2e2 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -12350,7 +12350,8 @@ static bool bpf_map_is_cgroup_storage(struct bpf_map *map)
 		map->map_type == BPF_MAP_TYPE_PERCPU_CGROUP_STORAGE);
 }
 
-/* find and rewrite pseudo imm in ld_imm64 instructions:
+/* check the opcodes of all instructions, and find and rewrite pseudo imm in
+ * ld_imm64 instructions:
  *
  * 1. if it accesses map FD, replace it with actual map pointer.
  * 2. if it accesses btf_id of a VAR, replace it with pointer to the var.
-- 
2.36.1

[PATCH bpf-next 2/4] bpf: verifier: explain opcode check in check_ld_imm()

[Shung-Hsi Yu]

The BPF_SIZE check in the beginning of check_ld_imm() actually guard
against program with JMP instructions that goes to the second
instruction of BPF_LD_IMM64, but may be easily dismissed as an simple
opcode check that's duplicating the effort of bpf_opcode_in_insntable().

Add comment to better reflect the importance of the check.

Signed-off-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
---
 kernel/bpf/verifier.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 79a2695ee2e2..133929751f80 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -9921,6 +9921,10 @@ static int check_ld_imm(struct bpf_verifier_env *env, struct bpf_insn *insn)
 	struct bpf_map *map;
 	int err;
 
+	/* checks that this is not the second part of BPF_LD_IMM64, which is
+	 * skipped over during opcode check, but a JMP with invalid offset may
+	 * cause check_ld_imm() to be called upon it.
+	 */
 	if (BPF_SIZE(insn->code) != BPF_DW) {
 		verbose(env, "invalid BPF_LD_IMM insn\n");
 		return -EINVAL;
-- 
2.36.1

[PATCH bpf-next 3/4] bpf: verifier: remove redundant opcode checks

[Shung-Hsi Yu]

The introduction of opcode validation with bpf_opcode_in_insntable() in
commit 5e581dad4fec ("bpf: make unknown opcode handling more robust")
has made opcode checks done in do_check_common() and its callees
redundant, so either remove them entirely, or turn them into comments in
places where the redundancy may not be clear.

Opcode code check is not removed for BPF_LD_{ABS,IND} in check_ld_abs()
and BPF_JMP_{JA,CALL,EXIT} in do_check() because they cover opcode
validation not done in bpf_opcode_in_insntable().

Signed-off-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
---
 kernel/bpf/verifier.c | 26 ++++++++------------------
 1 file changed, 8 insertions(+), 18 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 133929751f80..d528848083b9 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -4797,11 +4797,6 @@ static int check_atomic(struct bpf_verifier_env *env, int insn_idx, struct bpf_i
 		return -EINVAL;
 	}
 
-	if (BPF_SIZE(insn->code) != BPF_W && BPF_SIZE(insn->code) != BPF_DW) {
-		verbose(env, "invalid atomic operand size\n");
-		return -EINVAL;
-	}
-
 	/* check src1 operand */
 	err = check_reg_arg(env, insn->src_reg, SRC_OP);
 	if (err)
@@ -8793,8 +8788,7 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
 			}
 		} else {
 			if (insn->src_reg != BPF_REG_0 || insn->off != 0 ||
-			    (insn->imm != 16 && insn->imm != 32 && insn->imm != 64) ||
-			    BPF_CLASS(insn->code) == BPF_ALU64) {
+			    (insn->imm != 16 && insn->imm != 32 && insn->imm != 64)) {
 				verbose(env, "BPF_END uses reserved fields\n");
 				return -EINVAL;
 			}
@@ -11874,9 +11868,8 @@ static int do_check(struct bpf_verifier_env *env)
 					return err;
 				env->insn_idx++;
 				continue;
-			}
-
-			if (BPF_MODE(insn->code) != BPF_MEM || insn->imm != 0) {
+			} else if (insn->imm != 0) {
+				/* check for mode is already done, so mode can only be BPF_MEM */
 				verbose(env, "BPF_STX uses reserved fields\n");
 				return -EINVAL;
 			}
@@ -11909,8 +11902,7 @@ static int do_check(struct bpf_verifier_env *env)
 			}
 
 		} else if (class == BPF_ST) {
-			if (BPF_MODE(insn->code) != BPF_MEM ||
-			    insn->src_reg != BPF_REG_0) {
+			if (insn->src_reg != BPF_REG_0) {
 				verbose(env, "BPF_ST uses reserved fields\n");
 				return -EINVAL;
 			}
@@ -11944,8 +11936,7 @@ static int do_check(struct bpf_verifier_env *env)
 				    (insn->src_reg != BPF_REG_0 &&
 				     insn->src_reg != BPF_PSEUDO_CALL &&
 				     insn->src_reg != BPF_PSEUDO_KFUNC_CALL) ||
-				    insn->dst_reg != BPF_REG_0 ||
-				    class == BPF_JMP32) {
+				    insn->dst_reg != BPF_REG_0) {
 					verbose(env, "BPF_CALL uses reserved fields\n");
 					return -EINVAL;
 				}
@@ -11968,8 +11959,7 @@ static int do_check(struct bpf_verifier_env *env)
 				if (BPF_SRC(insn->code) != BPF_K ||
 				    insn->imm != 0 ||
 				    insn->src_reg != BPF_REG_0 ||
-				    insn->dst_reg != BPF_REG_0 ||
-				    class == BPF_JMP32) {
+				    insn->dst_reg != BPF_REG_0) {
 					verbose(env, "BPF_JA uses reserved fields\n");
 					return -EINVAL;
 				}
@@ -11981,8 +11971,7 @@ static int do_check(struct bpf_verifier_env *env)
 				if (BPF_SRC(insn->code) != BPF_K ||
 				    insn->imm != 0 ||
 				    insn->src_reg != BPF_REG_0 ||
-				    insn->dst_reg != BPF_REG_0 ||
-				    class == BPF_JMP32) {
+				    insn->dst_reg != BPF_REG_0) {
 					verbose(env, "BPF_EXIT uses reserved fields\n");
 					return -EINVAL;
 				}
@@ -14751,6 +14740,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr)
 	if (ret)
 		goto skip_full_check;
 
+	/* checks for validity of opcodes */
 	ret = resolve_pseudo_ldimm64(env);
 	if (ret < 0)
 		goto skip_full_check;
-- 
2.36.1

[PATCH bpf-next 4/4] selftests/bpf: add reason of rejection in ld_imm64

[Shung-Hsi Yu]

It may not be immediately clear why that ld_imm64 test cases are
rejected, especially for test1 and test2 where JMP to the 2nd
instruction of BPF_LD_IMM64 is performed.

Add brief explaination of why each test case in verifier/ld_imm64.c
should be rejected.

Signed-off-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
---
 .../testing/selftests/bpf/verifier/ld_imm64.c | 20 ++++++++++---------
 1 file changed, 11 insertions(+), 9 deletions(-)

diff --git a/tools/testing/selftests/bpf/verifier/ld_imm64.c b/tools/testing/selftests/bpf/verifier/ld_imm64.c
index f9297900cea6..021312641aaf 100644
--- a/tools/testing/selftests/bpf/verifier/ld_imm64.c
+++ b/tools/testing/selftests/bpf/verifier/ld_imm64.c
@@ -1,5 +1,6 @@
+/* Note: BPF_LD_IMM64 is composed of two instructions of class BPF_LD */
 {
-	"test1 ld_imm64",
+	"test1 ld_imm64: reject JMP to 2nd instruction of BPF_LD_IMM64",
 	.insns = {
 	BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 0, 1),
 	BPF_LD_IMM64(BPF_REG_0, 0),
@@ -14,7 +15,7 @@
 	.result = REJECT,
 },
 {
-	"test2 ld_imm64",
+	"test2 ld_imm64: reject JMP to 2nd instruction of BPF_LD_IMM64",
 	.insns = {
 	BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 0, 1),
 	BPF_LD_IMM64(BPF_REG_0, 0),
@@ -28,7 +29,7 @@
 	.result = REJECT,
 },
 {
-	"test3 ld_imm64",
+	"test3 ld_imm64: reject incomplete BPF_LD_IMM64 instruction",
 	.insns = {
 	BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 0, 1),
 	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, 0, 0, 0),
@@ -42,7 +43,7 @@
 	.result = REJECT,
 },
 {
-	"test4 ld_imm64",
+	"test4 ld_imm64: reject incomplete BPF_LD_IMM64 instruction",
 	.insns = {
 	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, 0, 0, 0),
 	BPF_EXIT_INSN(),
@@ -70,7 +71,7 @@
 	.retval = 1,
 },
 {
-	"test8 ld_imm64",
+	"test8 ld_imm64: reject 1st off!=0",
 	.insns = {
 	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, 0, 1, 1),
 	BPF_RAW_INSN(0, 0, 0, 0, 1),
@@ -80,7 +81,7 @@
 	.result = REJECT,
 },
 {
-	"test9 ld_imm64",
+	"test9 ld_imm64: reject 2nd off!=0",
 	.insns = {
 	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, 0, 0, 1),
 	BPF_RAW_INSN(0, 0, 0, 1, 1),
@@ -90,7 +91,7 @@
 	.result = REJECT,
 },
 {
-	"test10 ld_imm64",
+	"test10 ld_imm64: reject 2nd dst_reg!=0",
 	.insns = {
 	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, 0, 0, 1),
 	BPF_RAW_INSN(0, BPF_REG_1, 0, 0, 1),
@@ -100,7 +101,7 @@
 	.result = REJECT,
 },
 {
-	"test11 ld_imm64",
+	"test11 ld_imm64: reject 2nd src_reg!=0",
 	.insns = {
 	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, 0, 0, 1),
 	BPF_RAW_INSN(0, 0, BPF_REG_1, 0, 1),
@@ -113,6 +114,7 @@
 	"test12 ld_imm64",
 	.insns = {
 	BPF_MOV64_IMM(BPF_REG_1, 0),
+	/* BPF_REG_1 is interpreted as BPF_PSEUDO_MAP_FD */
 	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, BPF_REG_1, 0, 1),
 	BPF_RAW_INSN(0, 0, 0, 0, 0),
 	BPF_EXIT_INSN(),
@@ -121,7 +123,7 @@
 	.result = REJECT,
 },
 {
-	"test13 ld_imm64",
+	"test13 ld_imm64: 2nd src_reg!=0",
 	.insns = {
 	BPF_MOV64_IMM(BPF_REG_1, 0),
 	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, BPF_REG_1, 0, 1),
-- 
2.36.1

Re: [PATCH bpf-next 3/4] bpf: verifier: remove redundant opcode checks

[Alexei Starovoitov]

On Fri, May 20, 2022 at 4:38 AM Shung-Hsi Yu <shung-hsi.yu@suse.com> wrote:
>
> The introduction of opcode validation with bpf_opcode_in_insntable() in
> commit 5e581dad4fec ("bpf: make unknown opcode handling more robust")
> has made opcode checks done in do_check_common() and its callees
> redundant, so either remove them entirely, or turn them into comments in
> places where the redundancy may not be clear.

I prefer to keep the existing checks.
They help readability on what is actually expected at this point.
These checks cost close to nothing in run-time.

Re: [PATCH bpf-next 2/4] bpf: verifier: explain opcode check in check_ld_imm()

[Yonghong Song]

On 5/20/22 4:37 AM, Shung-Hsi Yu wrote:
> The BPF_SIZE check in the beginning of check_ld_imm() actually guard
> against program with JMP instructions that goes to the second
> instruction of BPF_LD_IMM64, but may be easily dismissed as an simple
> opcode check that's duplicating the effort of bpf_opcode_in_insntable().
> 
> Add comment to better reflect the importance of the check.
> 
> Signed-off-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
> ---
>   kernel/bpf/verifier.c | 4 ++++
>   1 file changed, 4 insertions(+)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 79a2695ee2e2..133929751f80 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -9921,6 +9921,10 @@ static int check_ld_imm(struct bpf_verifier_env *env, struct bpf_insn *insn)
>   	struct bpf_map *map;
>   	int err;
>   
> +	/* checks that this is not the second part of BPF_LD_IMM64, which is
> +	 * skipped over during opcode check, but a JMP with invalid offset may
> +	 * cause check_ld_imm() to be called upon it.
> +	 */

The check_ld_imm() call context is:

                 } else if (class == BPF_LD) {
                         u8 mode = BPF_MODE(insn->code);

                         if (mode == BPF_ABS || mode == BPF_IND) {
                                 err = check_ld_abs(env, insn);
                                 if (err)
                                         return err;

                         } else if (mode == BPF_IMM) {
                                 err = check_ld_imm(env, insn);
                                 if (err)
                                         return err;

                                 env->insn_idx++;
                                 sanitize_mark_insn_seen(env);
                         } else {
                                 verbose(env, "invalid BPF_LD mode\n");
                                 return -EINVAL;
                         }
                 }

which is a normal checking of LD_imm64 insn.

I think the to-be-added comment is incorrect and unnecessary.

>   	if (BPF_SIZE(insn->code) != BPF_DW) {
>   		verbose(env, "invalid BPF_LD_IMM insn\n");
>   		return -EINVAL;

Re: [PATCH bpf-next 2/4] bpf: verifier: explain opcode check in check_ld_imm()

[Yonghong Song]

On 5/20/22 4:50 PM, Yonghong Song wrote:
> 
> 
> On 5/20/22 4:37 AM, Shung-Hsi Yu wrote:
>> The BPF_SIZE check in the beginning of check_ld_imm() actually guard
>> against program with JMP instructions that goes to the second
>> instruction of BPF_LD_IMM64, but may be easily dismissed as an simple
>> opcode check that's duplicating the effort of bpf_opcode_in_insntable().
>>
>> Add comment to better reflect the importance of the check.
>>
>> Signed-off-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
>> ---
>>   kernel/bpf/verifier.c | 4 ++++
>>   1 file changed, 4 insertions(+)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 79a2695ee2e2..133929751f80 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -9921,6 +9921,10 @@ static int check_ld_imm(struct bpf_verifier_env 
>> *env, struct bpf_insn *insn)
>>       struct bpf_map *map;
>>       int err;
>> +    /* checks that this is not the second part of BPF_LD_IMM64, which is
>> +     * skipped over during opcode check, but a JMP with invalid 
>> offset may
>> +     * cause check_ld_imm() to be called upon it.
>> +     */
> 
> The check_ld_imm() call context is:
> 
>                  } else if (class == BPF_LD) {
>                          u8 mode = BPF_MODE(insn->code);
> 
>                          if (mode == BPF_ABS || mode == BPF_IND) {
>                                  err = check_ld_abs(env, insn);
>                                  if (err)
>                                          return err;
> 
>                          } else if (mode == BPF_IMM) {
>                                  err = check_ld_imm(env, insn);
>                                  if (err)
>                                          return err;
> 
>                                  env->insn_idx++;
>                                  sanitize_mark_insn_seen(env);
>                          } else {
>                                  verbose(env, "invalid BPF_LD mode\n");
>                                  return -EINVAL;
>                          }
>                  }
> 
> which is a normal checking of LD_imm64 insn.
> 
> I think the to-be-added comment is incorrect and unnecessary.

Okay, double check again and now I understand what happens
when hitting the second insn of ldimm64 with a branch target.
Here we have BPF_LD = 0 and BPF_IMM = 0, so for a branch
target to the 2nd part of ldimm64, it will come to
check_ld_imm() and have error "invalid BPF_LD_IMM insn"

So check_ld_imm() is to check whether the insn is a
*legal* insn for the first part of ldimm64.

So the comment may be rewritten as below.

This is to verify whether an insn is a BPF_LD_IMM64
or not. But since BPF_LD = 0 and BPF_IMM = 0, if the branch
target comes to the second part of BPF_LD_IMM64,
the control may come here as well.

> 
>>       if (BPF_SIZE(insn->code) != BPF_DW) {
>>           verbose(env, "invalid BPF_LD_IMM insn\n");
>>           return -EINVAL;

Re: [PATCH bpf-next 4/4] selftests/bpf: add reason of rejection in ld_imm64

[Yonghong Song]

On 5/20/22 4:37 AM, Shung-Hsi Yu wrote:
> It may not be immediately clear why that ld_imm64 test cases are
> rejected, especially for test1 and test2 where JMP to the 2nd
> instruction of BPF_LD_IMM64 is performed.
> 
> Add brief explaination of why each test case in verifier/ld_imm64.c
> should be rejected.
> 
> Signed-off-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
> ---
>   .../testing/selftests/bpf/verifier/ld_imm64.c | 20 ++++++++++---------
>   1 file changed, 11 insertions(+), 9 deletions(-)
> 
> diff --git a/tools/testing/selftests/bpf/verifier/ld_imm64.c b/tools/testing/selftests/bpf/verifier/ld_imm64.c
> index f9297900cea6..021312641aaf 100644
> --- a/tools/testing/selftests/bpf/verifier/ld_imm64.c
> +++ b/tools/testing/selftests/bpf/verifier/ld_imm64.c
> @@ -1,5 +1,6 @@
> +/* Note: BPF_LD_IMM64 is composed of two instructions of class BPF_LD */

> [...]LD | BPF_IMM | BPF_DW, 0, 0, 0, 0),
> @@ -42,7 +43,7 @@
>   	.result = REJECT,
>   },
>   {
> -	"test4 ld_imm64",
> +	"test4 ld_imm64: reject incomplete BPF_LD_IMM64 instruction",
>   	.insns = {
>   	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, 0, 0, 0),
>   	BPF_EXIT_INSN(),
> @@ -70,7 +71,7 @@
>   	.retval = 1,
>   },
>   {
> -	"test8 ld_imm64",
> +	"test8 ld_imm64: reject 1st off!=0",

Let add some space like 'off != 0'. The same for
some of later test names.

>   	.insns = {
>   	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, 0, 1, 1),
>   	BPF_RAW_INSN(0, 0, 0, 0, 1),
> @@ -80,7 +81,7 @@
>   	.result = REJECT,
>   },
>   {
> -	"test9 ld_imm64",
> +	"test9 ld_imm64: reject 2nd off!=0",
>   	.insns = {
>   	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, 0, 0, 1),
>   	BPF_RAW_INSN(0, 0, 0, 1, 1),
> @@ -90,7 +91,7 @@
>   	.result = REJECT,
>   },
>   {
> -	"test10 ld_imm64",
> +	"test10 ld_imm64: reject 2nd dst_reg!=0",
>   	.insns = {
>   	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, 0, 0, 1),
>   	BPF_RAW_INSN(0, BPF_REG_1, 0, 0, 1),
> @@ -100,7 +101,7 @@
>   	.result = REJECT,
>   },
>   {
> -	"test11 ld_imm64",
> +	"test11 ld_imm64: reject 2nd src_reg!=0",
>   	.insns = {
>   	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, 0, 0, 1),
>   	BPF_RAW_INSN(0, 0, BPF_REG_1, 0, 1),
> @@ -113,6 +114,7 @@
>   	"test12 ld_imm64",
>   	.insns = {
>   	BPF_MOV64_IMM(BPF_REG_1, 0),
> +	/* BPF_REG_1 is interpreted as BPF_PSEUDO_MAP_FD */
>   	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, BPF_REG_1, 0, 1),
>   	BPF_RAW_INSN(0, 0, 0, 0, 0),
>   	BPF_EXIT_INSN(),
> @@ -121,7 +123,7 @@
>   	.result = REJECT,
>   },
>   {
> -	"test13 ld_imm64",
> +	"test13 ld_imm64: 2nd src_reg!=0",
>   	.insns = {
>   	BPF_MOV64_IMM(BPF_REG_1, 0),
>   	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, BPF_REG_1, 0, 1),

Re: [PATCH bpf-next 4/4] selftests/bpf: add reason of rejection in ld_imm64

[Shung-Hsi Yu]

On Fri, May 20, 2022 at 05:27:12PM -0700, Yonghong Song wrote:
> 
> 
> On 5/20/22 4:37 AM, Shung-Hsi Yu wrote:
> > It may not be immediately clear why that ld_imm64 test cases are
> > rejected, especially for test1 and test2 where JMP to the 2nd
> > instruction of BPF_LD_IMM64 is performed.
> > 
> > Add brief explaination of why each test case in verifier/ld_imm64.c
> > should be rejected.
> > 
> > Signed-off-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
> > ---
> >   .../testing/selftests/bpf/verifier/ld_imm64.c | 20 ++++++++++---------
> >   1 file changed, 11 insertions(+), 9 deletions(-)
> > 
> > diff --git a/tools/testing/selftests/bpf/verifier/ld_imm64.c b/tools/testing/selftests/bpf/verifier/ld_imm64.c
> > index f9297900cea6..021312641aaf 100644
> > --- a/tools/testing/selftests/bpf/verifier/ld_imm64.c
> > +++ b/tools/testing/selftests/bpf/verifier/ld_imm64.c
> > @@ -1,5 +1,6 @@
> > +/* Note: BPF_LD_IMM64 is composed of two instructions of class BPF_LD */
> 
> > [...]LD | BPF_IMM | BPF_DW, 0, 0, 0, 0),
> > @@ -42,7 +43,7 @@
> >   	.result = REJECT,
> >   },
> >   {
> > -	"test4 ld_imm64",
> > +	"test4 ld_imm64: reject incomplete BPF_LD_IMM64 instruction",
> >   	.insns = {
> >   	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, 0, 0, 0),
> >   	BPF_EXIT_INSN(),
> > @@ -70,7 +71,7 @@
> >   	.retval = 1,
> >   },
> >   {
> > -	"test8 ld_imm64",
> > +	"test8 ld_imm64: reject 1st off!=0",
> 
> Let add some space like 'off != 0'. The same for
> some of later test names.

Okay, will do that in the next version. Thanks!

> >   	.insns = {
> >   	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, 0, 1, 1),
> >   	BPF_RAW_INSN(0, 0, 0, 0, 1),
> > @@ -80,7 +81,7 @@
> >   	.result = REJECT,
> >   },
> >   {
> > -	"test9 ld_imm64",
> > +	"test9 ld_imm64: reject 2nd off!=0",
> >   	.insns = {
> >   	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, 0, 0, 1),
> >   	BPF_RAW_INSN(0, 0, 0, 1, 1),
> > @@ -90,7 +91,7 @@
> >   	.result = REJECT,
> >   },
> >   {
> > -	"test10 ld_imm64",
> > +	"test10 ld_imm64: reject 2nd dst_reg!=0",
> >   	.insns = {
> >   	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, 0, 0, 1),
> >   	BPF_RAW_INSN(0, BPF_REG_1, 0, 0, 1),
> > @@ -100,7 +101,7 @@
> >   	.result = REJECT,
> >   },
> >   {
> > -	"test11 ld_imm64",
> > +	"test11 ld_imm64: reject 2nd src_reg!=0",
> >   	.insns = {
> >   	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, 0, 0, 1),
> >   	BPF_RAW_INSN(0, 0, BPF_REG_1, 0, 1),
> > @@ -113,6 +114,7 @@
> >   	"test12 ld_imm64",
> >   	.insns = {
> >   	BPF_MOV64_IMM(BPF_REG_1, 0),
> > +	/* BPF_REG_1 is interpreted as BPF_PSEUDO_MAP_FD */
> >   	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, BPF_REG_1, 0, 1),
> >   	BPF_RAW_INSN(0, 0, 0, 0, 0),
> >   	BPF_EXIT_INSN(),
> > @@ -121,7 +123,7 @@
> >   	.result = REJECT,
> >   },
> >   {
> > -	"test13 ld_imm64",
> > +	"test13 ld_imm64: 2nd src_reg!=0",
> >   	.insns = {
> >   	BPF_MOV64_IMM(BPF_REG_1, 0),
> >   	BPF_RAW_INSN(BPF_LD | BPF_IMM | BPF_DW, 0, BPF_REG_1, 0, 1),
> 

Re: [PATCH bpf-next 2/4] bpf: verifier: explain opcode check in check_ld_imm()

[Shung-Hsi Yu]

On Fri, May 20, 2022 at 05:25:36PM -0700, Yonghong Song wrote:
> On 5/20/22 4:50 PM, Yonghong Song wrote:
> > On 5/20/22 4:37 AM, Shung-Hsi Yu wrote:
> > > The BPF_SIZE check in the beginning of check_ld_imm() actually guard
> > > against program with JMP instructions that goes to the second
> > > instruction of BPF_LD_IMM64, but may be easily dismissed as an simple
> > > opcode check that's duplicating the effort of bpf_opcode_in_insntable().
> > > 
> > > Add comment to better reflect the importance of the check.
> > > 
> > > Signed-off-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
> > > ---
> > >   kernel/bpf/verifier.c | 4 ++++
> > >   1 file changed, 4 insertions(+)
> > > 
> > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > index 79a2695ee2e2..133929751f80 100644
> > > --- a/kernel/bpf/verifier.c
> > > +++ b/kernel/bpf/verifier.c
> > > @@ -9921,6 +9921,10 @@ static int check_ld_imm(struct
> > > bpf_verifier_env *env, struct bpf_insn *insn)
> > >       struct bpf_map *map;
> > >       int err;
> > > +    /* checks that this is not the second part of BPF_LD_IMM64, which is
> > > +     * skipped over during opcode check, but a JMP with invalid
> > > offset may
> > > +     * cause check_ld_imm() to be called upon it.
> > > +     */
> > 
> > The check_ld_imm() call context is:
> > 
> >                  } else if (class == BPF_LD) {
> >                          u8 mode = BPF_MODE(insn->code);
> > 
> >                          if (mode == BPF_ABS || mode == BPF_IND) {
> >                                  err = check_ld_abs(env, insn);
> >                                  if (err)
> >                                          return err;
> > 
> >                          } else if (mode == BPF_IMM) {
> >                                  err = check_ld_imm(env, insn);
> >                                  if (err)
> >                                          return err;
> > 
> >                                  env->insn_idx++;
> >                                  sanitize_mark_insn_seen(env);
> >                          } else {
> >                                  verbose(env, "invalid BPF_LD mode\n");
> >                                  return -EINVAL;
> >                          }
> >                  }
> > 
> > which is a normal checking of LD_imm64 insn.
> > 
> > I think the to-be-added comment is incorrect and unnecessary.
> 
> Okay, double check again and now I understand what happens
> when hitting the second insn of ldimm64 with a branch target.
> Here we have BPF_LD = 0 and BPF_IMM = 0, so for a branch
> target to the 2nd part of ldimm64, it will come to
> check_ld_imm() and have error "invalid BPF_LD_IMM insn"

Yes, the 2nd instruction uses the reserved opcode 0, which could be
interpreted as BPF_LD | BPF_W | BPF_IMM.

> So check_ld_imm() is to check whether the insn is a
> *legal* insn for the first part of ldimm64.
> 
> So the comment may be rewritten as below.
> 
> This is to verify whether an insn is a BPF_LD_IMM64
> or not. But since BPF_LD = 0 and BPF_IMM = 0, if the branch
> target comes to the second part of BPF_LD_IMM64,
> the control may come here as well.
> 
> > >       if (BPF_SIZE(insn->code) != BPF_DW) {
> > >           verbose(env, "invalid BPF_LD_IMM insn\n");
> > >           return -EINVAL;

After giving it a bit more though, maybe it'd be clearer if we simply detect
such case in the JMP branch of do_check().

Something like this instead. Though I haven't tested yet, and it still check
the jump destination even it's a dead branch.

---
 kernel/bpf/verifier.c | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index aedac2ac02b9..59228806884e 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -12191,6 +12191,25 @@ static int do_check(struct bpf_verifier_env *env)
 			u8 opcode = BPF_OP(insn->code);
 
 			env->jmps_processed++;
+
+			/* check jump offset */
+			if (opcode != BPF_CALL && opcode != BPF_EXIT) {
+				u32 dst_insn_idx = env->insn_idx + insn->off + 1;
+				struct bpf_insn *dst_insn = &insns[dst_insn_idx];
+
+				if (dst_insn_idx > insn_cnt) {
+					verbose(env, "invalid JMP idx %d off %d beyond end of program insn_cnt %d\n", env->insn_idx, insn->off, insn_cnt);
+					return -EFAULT;
+				}
+				if (!bpf_opcode_in_insntable(dst_insn->code)) {
+					/* Should we simply tell the user that it's a
+					 * jump to the 2nd LD_IMM64 instruction
+					 * here? */
+					verbose(env, "idx %d JMP to idx %d with unknown opcode %02x\n", env->insn_idx, dst_insn_idx, insn->code);
+					return -EINVAL;
+				}
+			}
+
 			if (opcode == BPF_CALL) {
 				if (BPF_SRC(insn->code) != BPF_K ||
 				    (insn->src_reg != BPF_PSEUDO_KFUNC_CALL
-- 
2.36.1

Re: [PATCH bpf-next 2/4] bpf: verifier: explain opcode check in check_ld_imm()

[Alexei Starovoitov]

On Tue, May 24, 2022 at 12:11 AM Shung-Hsi Yu <shung-hsi.yu@suse.com> wrote:
>
> On Fri, May 20, 2022 at 05:25:36PM -0700, Yonghong Song wrote:
> > On 5/20/22 4:50 PM, Yonghong Song wrote:
> > > On 5/20/22 4:37 AM, Shung-Hsi Yu wrote:
> > > > The BPF_SIZE check in the beginning of check_ld_imm() actually guard
> > > > against program with JMP instructions that goes to the second
> > > > instruction of BPF_LD_IMM64, but may be easily dismissed as an simple
> > > > opcode check that's duplicating the effort of bpf_opcode_in_insntable().
> > > >
> > > > Add comment to better reflect the importance of the check.
> > > >
> > > > Signed-off-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
> > > > ---
> > > >   kernel/bpf/verifier.c | 4 ++++
> > > >   1 file changed, 4 insertions(+)
> > > >
> > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > > index 79a2695ee2e2..133929751f80 100644
> > > > --- a/kernel/bpf/verifier.c
> > > > +++ b/kernel/bpf/verifier.c
> > > > @@ -9921,6 +9921,10 @@ static int check_ld_imm(struct
> > > > bpf_verifier_env *env, struct bpf_insn *insn)
> > > >       struct bpf_map *map;
> > > >       int err;
> > > > +    /* checks that this is not the second part of BPF_LD_IMM64, which is
> > > > +     * skipped over during opcode check, but a JMP with invalid
> > > > offset may
> > > > +     * cause check_ld_imm() to be called upon it.
> > > > +     */
> > >
> > > The check_ld_imm() call context is:
> > >
> > >                  } else if (class == BPF_LD) {
> > >                          u8 mode = BPF_MODE(insn->code);
> > >
> > >                          if (mode == BPF_ABS || mode == BPF_IND) {
> > >                                  err = check_ld_abs(env, insn);
> > >                                  if (err)
> > >                                          return err;
> > >
> > >                          } else if (mode == BPF_IMM) {
> > >                                  err = check_ld_imm(env, insn);
> > >                                  if (err)
> > >                                          return err;
> > >
> > >                                  env->insn_idx++;
> > >                                  sanitize_mark_insn_seen(env);
> > >                          } else {
> > >                                  verbose(env, "invalid BPF_LD mode\n");
> > >                                  return -EINVAL;
> > >                          }
> > >                  }
> > >
> > > which is a normal checking of LD_imm64 insn.
> > >
> > > I think the to-be-added comment is incorrect and unnecessary.
> >
> > Okay, double check again and now I understand what happens
> > when hitting the second insn of ldimm64 with a branch target.
> > Here we have BPF_LD = 0 and BPF_IMM = 0, so for a branch
> > target to the 2nd part of ldimm64, it will come to
> > check_ld_imm() and have error "invalid BPF_LD_IMM insn"
>
> Yes, the 2nd instruction uses the reserved opcode 0, which could be
> interpreted as BPF_LD | BPF_W | BPF_IMM.
>
> > So check_ld_imm() is to check whether the insn is a
> > *legal* insn for the first part of ldimm64.
> >
> > So the comment may be rewritten as below.
> >
> > This is to verify whether an insn is a BPF_LD_IMM64
> > or not. But since BPF_LD = 0 and BPF_IMM = 0, if the branch
> > target comes to the second part of BPF_LD_IMM64,
> > the control may come here as well.
> >
> > > >       if (BPF_SIZE(insn->code) != BPF_DW) {
> > > >           verbose(env, "invalid BPF_LD_IMM insn\n");
> > > >           return -EINVAL;
>
> After giving it a bit more though, maybe it'd be clearer if we simply detect
> such case in the JMP branch of do_check().
>
> Something like this instead. Though I haven't tested yet, and it still check
> the jump destination even it's a dead branch.
>
> ---
>  kernel/bpf/verifier.c | 19 +++++++++++++++++++
>  1 file changed, 19 insertions(+)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index aedac2ac02b9..59228806884e 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -12191,6 +12191,25 @@ static int do_check(struct bpf_verifier_env *env)
>                         u8 opcode = BPF_OP(insn->code);
>
>                         env->jmps_processed++;
> +
> +                       /* check jump offset */
> +                       if (opcode != BPF_CALL && opcode != BPF_EXIT) {
> +                               u32 dst_insn_idx = env->insn_idx + insn->off + 1;
> +                               struct bpf_insn *dst_insn = &insns[dst_insn_idx];
> +
> +                               if (dst_insn_idx > insn_cnt) {
> +                                       verbose(env, "invalid JMP idx %d off %d beyond end of program insn_cnt %d\n", env->insn_idx, insn->off, insn_cnt);
> +                                       return -EFAULT;
> +                               }
> +                               if (!bpf_opcode_in_insntable(dst_insn->code)) {
> +                                       /* Should we simply tell the user that it's a
> +                                        * jump to the 2nd LD_IMM64 instruction
> +                                        * here? */
> +                                       verbose(env, "idx %d JMP to idx %d with unknown opcode %02x\n", env->insn_idx, dst_insn_idx, insn->code);
> +                                       return -EINVAL;
> +                               }
> +                       }
> +

This makes the code worse.
There is no need for these patches.

Re: [PATCH bpf-next 2/4] bpf: verifier: explain opcode check in check_ld_imm()

[Shung-Hsi Yu]

On Tue, May 24, 2022 at 08:12:24AM -0700, Alexei Starovoitov wrote:
> On Tue, May 24, 2022 at 12:11 AM Shung-Hsi Yu <shung-hsi.yu@suse.com> wrote:
> > On Fri, May 20, 2022 at 05:25:36PM -0700, Yonghong Song wrote:
> > > On 5/20/22 4:50 PM, Yonghong Song wrote:
> > > > On 5/20/22 4:37 AM, Shung-Hsi Yu wrote:
> > > > > The BPF_SIZE check in the beginning of check_ld_imm() actually guard
> > > > > against program with JMP instructions that goes to the second
> > > > > instruction of BPF_LD_IMM64, but may be easily dismissed as an simple
> > > > > opcode check that's duplicating the effort of bpf_opcode_in_insntable().
> > > > >
> > > > > Add comment to better reflect the importance of the check.
> > > > >
> > > > > Signed-off-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
> > > > > ---
> > > > >   kernel/bpf/verifier.c | 4 ++++
> > > > >   1 file changed, 4 insertions(+)
> > > > >
> > > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > > > index 79a2695ee2e2..133929751f80 100644
> > > > > --- a/kernel/bpf/verifier.c
> > > > > +++ b/kernel/bpf/verifier.c
> > > > > @@ -9921,6 +9921,10 @@ static int check_ld_imm(struct
> > > > > bpf_verifier_env *env, struct bpf_insn *insn)
> > > > >       struct bpf_map *map;
> > > > >       int err;
> > > > > +    /* checks that this is not the second part of BPF_LD_IMM64, which is
> > > > > +     * skipped over during opcode check, but a JMP with invalid
> > > > > offset may
> > > > > +     * cause check_ld_imm() to be called upon it.
> > > > > +     */
> > > >
> > > > The check_ld_imm() call context is:
> > > >
> > > >                  } else if (class == BPF_LD) {
> > > >                          u8 mode = BPF_MODE(insn->code);
> > > >
> > > >                          if (mode == BPF_ABS || mode == BPF_IND) {
> > > >                                  err = check_ld_abs(env, insn);
> > > >                                  if (err)
> > > >                                          return err;
> > > >
> > > >                          } else if (mode == BPF_IMM) {
> > > >                                  err = check_ld_imm(env, insn);
> > > >                                  if (err)
> > > >                                          return err;
> > > >
> > > >                                  env->insn_idx++;
> > > >                                  sanitize_mark_insn_seen(env);
> > > >                          } else {
> > > >                                  verbose(env, "invalid BPF_LD mode\n");
> > > >                                  return -EINVAL;
> > > >                          }
> > > >                  }
> > > >
> > > > which is a normal checking of LD_imm64 insn.
> > > >
> > > > I think the to-be-added comment is incorrect and unnecessary.
> > >
> > > Okay, double check again and now I understand what happens
> > > when hitting the second insn of ldimm64 with a branch target.
> > > Here we have BPF_LD = 0 and BPF_IMM = 0, so for a branch
> > > target to the 2nd part of ldimm64, it will come to
> > > check_ld_imm() and have error "invalid BPF_LD_IMM insn"
> >
> > Yes, the 2nd instruction uses the reserved opcode 0, which could be
> > interpreted as BPF_LD | BPF_W | BPF_IMM.
> >
> > > So check_ld_imm() is to check whether the insn is a
> > > *legal* insn for the first part of ldimm64.
> > >
> > > So the comment may be rewritten as below.
> > >
> > > This is to verify whether an insn is a BPF_LD_IMM64
> > > or not. But since BPF_LD = 0 and BPF_IMM = 0, if the branch
> > > target comes to the second part of BPF_LD_IMM64,
> > > the control may come here as well.
> > >
> > > > >       if (BPF_SIZE(insn->code) != BPF_DW) {
> > > > >           verbose(env, "invalid BPF_LD_IMM insn\n");
> > > > >           return -EINVAL;
> >
> > After giving it a bit more though, maybe it'd be clearer if we simply detect
> > such case in the JMP branch of do_check().
> >
> > Something like this instead. Though I haven't tested yet, and it still check
> > the jump destination even it's a dead branch.
> >
> > ---
> >  kernel/bpf/verifier.c | 19 +++++++++++++++++++
> >  1 file changed, 19 insertions(+)
> >
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index aedac2ac02b9..59228806884e 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -12191,6 +12191,25 @@ static int do_check(struct bpf_verifier_env *env)
> >                         u8 opcode = BPF_OP(insn->code);
> >
> >                         env->jmps_processed++;
> > +
> > +                       /* check jump offset */
> > +                       if (opcode != BPF_CALL && opcode != BPF_EXIT) {
> > +                               u32 dst_insn_idx = env->insn_idx + insn->off + 1;
> > +                               struct bpf_insn *dst_insn = &insns[dst_insn_idx];
> > +
> > +                               if (dst_insn_idx > insn_cnt) {
> > +                                       verbose(env, "invalid JMP idx %d off %d beyond end of program insn_cnt %d\n", env->insn_idx, insn->off, insn_cnt);
> > +                                       return -EFAULT;
> > +                               }
> > +                               if (!bpf_opcode_in_insntable(dst_insn->code)) {
> > +                                       /* Should we simply tell the user that it's a
> > +                                        * jump to the 2nd LD_IMM64 instruction
> > +                                        * here? */
> > +                                       verbose(env, "idx %d JMP to idx %d with unknown opcode %02x\n", env->insn_idx, dst_insn_idx, insn->code);
> > +                                       return -EINVAL;
> > +                               }
> > +                       }
> > +
> 
> This makes the code worse.

Could you elaborate a bit more on the reason? I'd like to try avoid
submitting patch like this in the future.

In hindsight I'd guess it's because it adds more branching into do_check()
and more lines of code, making it harder to understand, but at the same time
the added checks is mostly repeating existing

 1. insn_cnt check in the beginning of do_check() loop
 2. BPF_SIZE check in check_ld_imm()

While it has the benefit of adding more specific error message, such error
message is too specific to be useful in general, thus does not outweigh the
cost of added complexity?

> There is no need for these patches.

Just to be clear, "these" refers to the added checks do_check()
<Yoxjvvm9poTC3Atv@syu-laptop> only, or does it also includes the to-be-added
comment inside check_ld_imm() of patch 2?