[PATCH] bpf: fix a bug in verification logic when SUB operation taken on FRAME_PTR

[PATCH] bpf: fix a bug in verification logic when SUB operation taken on FRAME_PTR

[Wang Nan]

Original code has a problem, cause following code failed to pass verifier:

 r1 <- r10
 r1 -= 8
 r2 = 8
 r3 = unsafe pointer
 call BPF_FUNC_probe_read  <-- R1 type=inv expected=fp

However, by replacing 'r1 -= 8' to 'r1 += -8' the above program can be
loaded successfully.

This is because the verifier allows only BPF_ADD instruction on a
FRAME_PTR reigster to forge PTR_TO_STACK register, but makes BPF_SUB
on FRAME_PTR reigster to get a UNKNOWN_VALUE register.

This patch fix it by adding BPF_SUB in stack_relative checking.

Signed-off-by: Wang Nan <wangnan0@huawei.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 a251cf6..6dbdeba 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1020,7 +1020,8 @@ static int check_alu_op(struct reg_state *regs, struct bpf_insn *insn)
 		}
 
 		/* pattern match 'bpf_add Rx, imm' instruction */
-		if (opcode == BPF_ADD && BPF_CLASS(insn->code) == BPF_ALU64 &&
+		if (opcode == BPF_ADD && opcode == BPF_SUB &&
+		    BPF_CLASS(insn->code) == BPF_ALU64 &&
 		    regs[insn->dst_reg].type == FRAME_PTR &&
 		    BPF_SRC(insn->code) == BPF_K)
 			stack_relative = true;
-- 
1.8.3.4

[PATCH v2] bpf: fix a bug in verification logic when SUB operation taken on FRAME_PTR

[Wang Nan]

Original code has a problem, cause following code failed to pass verifier:

 r1 <- r10
 r1 -= 8
 r2 = 8
 r3 = unsafe pointer
 call BPF_FUNC_probe_read  <-- R1 type=inv expected=fp

However, by replacing 'r1 -= 8' to 'r1 += -8' the above program can be
loaded successfully.

This is because the verifier allows only BPF_ADD instruction on a
FRAME_PTR reigster to forge PTR_TO_STACK register, but makes BPF_SUB
on FRAME_PTR reigster to get a UNKNOWN_VALUE register.

This patch fix it by adding BPF_SUB in stack_relative checking.

Signed-off-by: Wang Nan <wangnan0@huawei.com>
---

V1 is incorrect. Please ignore it and consider this one.

---
 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 a251cf6..681ac72 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1020,7 +1020,8 @@ static int check_alu_op(struct reg_state *regs, struct bpf_insn *insn)
 		}
 
 		/* pattern match 'bpf_add Rx, imm' instruction */
-		if (opcode == BPF_ADD && BPF_CLASS(insn->code) == BPF_ALU64 &&
+		if ((opcode == BPF_ADD || opcode == BPF_SUB) &&
+		    BPF_CLASS(insn->code) == BPF_ALU64 &&
 		    regs[insn->dst_reg].type == FRAME_PTR &&
 		    BPF_SRC(insn->code) == BPF_K)
 			stack_relative = true;
-- 
1.8.3.4

Re: [PATCH v2] bpf: fix a bug in verification logic when SUB operation taken on FRAME_PTR

[Alexei Starovoitov]

On Thu, Jun 18, 2015 at 08:31:45AM +0000, Wang Nan wrote:
> Original code has a problem, cause following code failed to pass verifier:
> 
>  r1 <- r10
>  r1 -= 8
>  r2 = 8
>  r3 = unsafe pointer
>  call BPF_FUNC_probe_read  <-- R1 type=inv expected=fp
> 
> However, by replacing 'r1 -= 8' to 'r1 += -8' the above program can be
> loaded successfully.
> 
> This is because the verifier allows only BPF_ADD instruction on a
> FRAME_PTR reigster to forge PTR_TO_STACK register, but makes BPF_SUB
> on FRAME_PTR reigster to get a UNKNOWN_VALUE register.
> 
> This patch fix it by adding BPF_SUB in stack_relative checking.

It's not a bug. It's catching ADD only by design.
If we let it recognize SUB then one might argue we should let it
recognize multiply, shifts and all other arithmetic on pointers.
verifier will be getting bigger and bigger. Where do we stop?
llvm only emits canonical ADD. If you've seen llvm doing SUB,
let's fix it there.
So what piece generated this 'r1 -= 8' ?

Re: [PATCH v2] bpf: fix a bug in verification logic when SUB operation taken on FRAME_PTR

[Wangnan (F)]

On 2015/6/19 0:00, Alexei Starovoitov wrote:
> On Thu, Jun 18, 2015 at 08:31:45AM +0000, Wang Nan wrote:
>> Original code has a problem, cause following code failed to pass verifier:
>>
>>   r1 <- r10
>>   r1 -= 8
>>   r2 = 8
>>   r3 = unsafe pointer
>>   call BPF_FUNC_probe_read  <-- R1 type=inv expected=fp
>>
>> However, by replacing 'r1 -= 8' to 'r1 += -8' the above program can be
>> loaded successfully.
>>
>> This is because the verifier allows only BPF_ADD instruction on a
>> FRAME_PTR reigster to forge PTR_TO_STACK register, but makes BPF_SUB
>> on FRAME_PTR reigster to get a UNKNOWN_VALUE register.
>>
>> This patch fix it by adding BPF_SUB in stack_relative checking.
> It's not a bug. It's catching ADD only by design.
> If we let it recognize SUB then one might argue we should let it
> recognize multiply, shifts and all other arithmetic on pointers.
> verifier will be getting bigger and bigger. Where do we stop?
> llvm only emits canonical ADD. If you've seen llvm doing SUB,
> let's fix it there.
> So what piece generated this 'r1 -= 8' ?
>

I hit this problem when writing code of automatical parameter generator. The
instruction is generated by myself. Now I have corrected my code.

Thank you.