[PATCH v2] bpf: verifier: MOV64 don't mark dst reg unbounded
When check_alu_op() handles a BPF_MOV64 between two registers,
it calls check_reg_arg(DST_OP) on the dst register, marking it as unbounded.
If the src and dst register are the same, this marks the src as
unbounded, which can lead to unexpected errors for further checks that
rely on bounds info. For example:
BPF_MOV64_IMM(BPF_REG_2, 0),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_2),
BPF_ALU64_REG(BPF_ADD, BPF_REG_1, BPF_REG_2),
BPF_MOV64_IMM(BPF_REG_0, 0),
BPF_EXIT_INSN(),
results in:
"math between ctx pointer and register with unbounded min value is not
allowed"
check_alu_op() now uses check_reg_arg(DST_OP_NO_MARK), and MOVs
that need to mark the dst register (MOVIMM, MOV32) do so.
Added a test case for MOV64 dst == src, and dst != src.
Signed-off-by: Arthur Fabre
---
v2: Add mov64 tests, always use DST_OP_NO_MARK
kernel/bpf/verifier.c | 6 +++--
tools/testing/selftests/bpf/test_verifier.c | 26 +
2 files changed, 30 insertions(+), 2 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 63aaac52a265..ec63b56be4af 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3238,8 +3238,8 @@ static int check_alu_op(struct bpf_verifier_env *env,
struct bpf_insn *insn)
}
}
- /* check dest operand */
- err = check_reg_arg(env, insn->dst_reg, DST_OP);
+ /* check dest operand, mark as required later */
+ err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK);
if (err)
return err;
@@ -3265,6 +3265,8 @@ static int check_alu_op(struct bpf_verifier_env *env,
struct bpf_insn *insn)
/* case: R = imm
* remember the value we stored into this reg
*/
+ /* clear any state __mark_reg_known doesn't set */
+ mark_reg_unknown(env, regs, insn->dst_reg);
regs[insn->dst_reg].type = SCALAR_VALUE;
if (BPF_CLASS(insn->code) == BPF_ALU64) {
__mark_reg_known(regs + insn->dst_reg,
diff --git a/tools/testing/selftests/bpf/test_verifier.c
b/tools/testing/selftests/bpf/test_verifier.c
index 41106d9d5cc7..79f10e95e7df 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -12372,6 +12372,32 @@ static struct bpf_test tests[] = {
.result = REJECT,
.errstr = "variable ctx access var_off=(0x0; 0x4)",
},
+ {
+ "mov64 src == dst",
+ .insns = {
+ BPF_MOV64_IMM(BPF_REG_2, 0),
+ BPF_MOV64_REG(BPF_REG_2, BPF_REG_2),
+ // Check bounds are OK
+ BPF_ALU64_REG(BPF_ADD, BPF_REG_1, BPF_REG_2),
+ BPF_MOV64_IMM(BPF_REG_0, 0),
+ BPF_EXIT_INSN(),
+ },
+ .prog_type = BPF_PROG_TYPE_SCHED_CLS,
+ .result = ACCEPT,
+ },
+ {
+ "mov64 src != dst",
+ .insns = {
+ BPF_MOV64_IMM(BPF_REG_3, 0),
+ BPF_MOV64_REG(BPF_REG_2, BPF_REG_3),
+ // Check bounds are OK
+ BPF_ALU64_REG(BPF_ADD, BPF_REG_1, BPF_REG_2),
+ BPF_MOV64_IMM(BPF_REG_0, 0),
+ BPF_EXIT_INSN(),
+ },
+ .prog_type = BPF_PROG_TYPE_SCHED_CLS,
+ .result = ACCEPT,
+ },
};
static int probe_filter_length(const struct bpf_insn *fp)
--
2.18.0
Re: [PATCH] bpf: verifier: BPF_MOV don't mark dst reg if src == dst
On Mon, Jul 30, 2018 at 10:10 AM, Daniel Borkmann wrote: > On 07/30/2018 09:44 AM, Arthur Fabre wrote: >> On Sun, Jul 29, 2018 at 4:59 PM, Alexei Starovoitov >> wrote: >>> On Thu, Jul 26, 2018 at 1:08 AM, Arthur Fabre wrote: >>>> When check_alu_op() handles a BPF_MOV between two registers, >>>> it calls check_reg_arg() on the dst register, marking it as unbounded. >>>> If the src and dst register are the same, this marks the src as >>>> unbounded, which can lead to unexpected errors for further checks that >>>> rely on bounds info. >>>> >>>> check_alu_op() now only marks the dst register as unbounded if it >>>> different from the src register. >>>> >>>> Signed-off-by: Arthur Fabre >>>> --- >>>> kernel/bpf/verifier.c | 5 +++-- >>>> 1 file changed, 3 insertions(+), 2 deletions(-) >>>> >>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c >>>> index 63aaac52a265..ddfe3c544a80 100644 >>>> --- a/kernel/bpf/verifier.c >>>> +++ b/kernel/bpf/verifier.c >>>> @@ -3238,8 +3238,9 @@ static int check_alu_op(struct bpf_verifier_env >>>> *env, struct bpf_insn *insn) >>>> } >>>> } >>>> >>>> - /* check dest operand */ >>>> - err = check_reg_arg(env, insn->dst_reg, DST_OP); >>>> + /* check dest operand, only mark if dest != src */ >>>> + err = check_reg_arg(env, insn->dst_reg, >>>> + insn->dst_reg == insn->src_reg ? >>>> DST_OP_NO_MARK : DST_OP); >>> >>> that doesn't look correct for 32-bit mov. >>> Is that the case you're trying to improve? >> >> The patch was originally for 64-bit mov only > > Hmm, I'm not sure that is infact the case. The check_alu_op() is handled for > 32 and 64 bit alu op case. So in the opcode == BPF_MOV case the > check_reg_arg() > on the dst register is done for both at that point, whereas retaining any > current state should only be valid in 64 bit mov case, e.g. think of pointer > types, these really need to be scratched here. I think it would make sense > that > after checking src operand we hold a temporary copy of its state and use that > for setting regs[insn->dst_reg] later on under BPF_ALU64. The check_alu_op() call handles 32bit and 64bit cases, but then in the 32bit case mark_reg_unknown() is called, discarding all the dst register state. I think this is equivalent to keeping a copy of dst and always marking dst as unknown. I think we could actually always use check_reg_arg() with DST_OP_NO_MARK: In the 32bit case, we call mark_reg_unknown() anyways. In the 64bit case, we copy src to dst, so marking dst as unknown is pointless. For plain BPF, we call __mark_reg_known() anyways.
Re: [PATCH] bpf: verifier: BPF_MOV don't mark dst reg if src == dst
On Sun, Jul 29, 2018 at 4:59 PM, Alexei Starovoitov wrote: > On Thu, Jul 26, 2018 at 1:08 AM, Arthur Fabre wrote: >> When check_alu_op() handles a BPF_MOV between two registers, >> it calls check_reg_arg() on the dst register, marking it as unbounded. >> If the src and dst register are the same, this marks the src as >> unbounded, which can lead to unexpected errors for further checks that >> rely on bounds info. >> >> check_alu_op() now only marks the dst register as unbounded if it >> different from the src register. >> >> Signed-off-by: Arthur Fabre >> --- >> kernel/bpf/verifier.c | 5 +++-- >> 1 file changed, 3 insertions(+), 2 deletions(-) >> >> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c >> index 63aaac52a265..ddfe3c544a80 100644 >> --- a/kernel/bpf/verifier.c >> +++ b/kernel/bpf/verifier.c >> @@ -3238,8 +3238,9 @@ static int check_alu_op(struct bpf_verifier_env >> *env, struct bpf_insn *insn) >> } >> } >> >> - /* check dest operand */ >> - err = check_reg_arg(env, insn->dst_reg, DST_OP); >> + /* check dest operand, only mark if dest != src */ >> + err = check_reg_arg(env, insn->dst_reg, >> + insn->dst_reg == insn->src_reg ? >> DST_OP_NO_MARK : DST_OP); > > that doesn't look correct for 32-bit mov. > Is that the case you're trying to improve? The patch was originally for 64-bit mov only
Re: [PATCH] bpf: verifier: BPF_MOV don't mark dst reg if src == dst
On Fri, Jul 27, 2018 at 12:21 AM, Y Song wrote: > The SMIN/UMIN still should be 0 since there is no negative here due to > smaller width? Yes that makes sense. > We can do better than unbounded for dst register of mov32, which is > the code already > doing? coerce_reg_to_size() will preserve the bounds if they fit in a u32, which is better than setting the bounds to [0, 2^32-1]. mark_reg_unknown() is called before for mov32 though, resetting the bounds. Consequently using mov32 always results in the bounds being [0, 2^32-1]. > Could you explain (and add to the commit messages eventually) what > are these unexpected errors? A good example is: BPF_MOV32_IMM(BPF_REG_2, 0), BPF_MOV32_REG(BPF_REG_2, BPF_REG_2), BPF_ALU64_REG(BPF_ADD, BPF_REG_1, BPF_REG_2), BPF_MOV64_IMM(BPF_REG_0, 0), BPF_EXIT_INSN(), The 3rd instruction results in: math between ctx pointer and register with unbounded min value is not allowed
Re: [PATCH] bpf: verifier: BPF_MOV don't mark dst reg if src == dst
Oops, gmail seems to have mangled everything. Will resend using git send-email. I've added the test cases for mov64, but I'm not sure of the expected mov32 behavior. Currently coerce_reg_to_size() is called after mark_reg_unknown(), which sets the bounds to 64bits. coerce_reg_to_size() resets the bounds again, as they're too "wide" to fit the new size. It sets SMIN = UMIN = 0, which seems weird. Shouldn't SMIN be 1 << (size * 8 - 1)? Same applies for SMAX. Should mov32 always mark the dst as unbounded? On Thu, Jul 26, 2018 at 1:42 AM, Daniel Borkmann wrote: > On 07/26/2018 12:08 AM, Arthur Fabre wrote: > > When check_alu_op() handles a BPF_MOV between two registers, > > it calls check_reg_arg() on the dst register, marking it as unbounded. > > If the src and dst register are the same, this marks the src as > > unbounded, which can lead to unexpected errors for further checks that > > rely on bounds info. > > > > check_alu_op() now only marks the dst register as unbounded if it > > different from the src register. > > > > Signed-off-by: Arthur Fabre > > --- > > kernel/bpf/verifier.c | 5 +++-- > > 1 file changed, 3 insertions(+), 2 deletions(-) > > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > > index 63aaac52a265..ddfe3c544a80 100644 > > --- a/kernel/bpf/verifier.c > > +++ b/kernel/bpf/verifier.c > > @@ -3238,8 +3238,9 @@ static int check_alu_op(struct bpf_verifier_env > > *env, struct bpf_insn *insn) > > } > > } > > > > - /* check dest operand */ > > - err = check_reg_arg(env, insn->dst_reg, DST_OP); > > + /* check dest operand, only mark if dest != src */ > > + err = check_reg_arg(env, insn->dst_reg, > > + insn->dst_reg == insn->src_reg ? > > DST_OP_NO_MARK : DST_OP); > > if (err) > > return err; > > > > Thanks a lot for the patch! Looks like it's corrupted wrt newline. > > Please also add test cases to tools/testing/selftests/bpf/test_verifier.c > for the cases of mov64 and mov32 where in each src==dst and src!=dst; mov32 > should mark it as unbounded but not former, so would be good to keep > tracking > that in selftests. >
[PATCH] bpf: verifier: BPF_MOV don't mark dst reg if src == dst
When check_alu_op() handles a BPF_MOV between two registers, it calls check_reg_arg() on the dst register, marking it as unbounded. If the src and dst register are the same, this marks the src as unbounded, which can lead to unexpected errors for further checks that rely on bounds info. check_alu_op() now only marks the dst register as unbounded if it different from the src register. Signed-off-by: Arthur Fabre --- kernel/bpf/verifier.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 63aaac52a265..ddfe3c544a80 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -3238,8 +3238,9 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) } } - /* check dest operand */ - err = check_reg_arg(env, insn->dst_reg, DST_OP); + /* check dest operand, only mark if dest != src */ + err = check_reg_arg(env, insn->dst_reg, + insn->dst_reg == insn->src_reg ? DST_OP_NO_MARK : DST_OP); if (err) return err; -- 2.18.0
