Re: [iovisor-dev] BPF verifier: cannot add integer value with 0 upper zero bits to ptr_to_packet

2017-02-24 Thread Daniel Borkmann via iovisor-dev 

On 02/23/2017 11:00 PM, William Tu wrote:

Hi Daniel,

Thanks for the reply! I understand the workaround, can you suggest a
way to try it? Should I compile the C source into llvm IR bitcode, add
thie "r0 &= 0x", then assembly it to bpf target binary.


Hmm, problem with C code is that we might have no control over when llvm
decides to spill to stack where this workaround would then be needed. Your
suggestion could work, maybe an llvm expert can jump in here if we have
some other, easier options at hand?

Second case is to preserve the type in verifier when spilled, but will make
pruning ineffective to the point that we could see regressions of programs
not loading anymore (due to running over BPF_COMPLEXITY_LIMIT_INSNS).
states_equal() wrt probing stack space doesn't have much optimizations
thus far either; certainly this path would need a careful evaluation.


On Wed, Feb 22, 2017 at 9:08 AM, Daniel Borkmann  wrote:

On 02/17/2017 06:07 PM, William Tu via iovisor-dev wrote:


Hi,

I encountered another BPF verifier issue related to my previous one
https://lists.iovisor.org/pipermail/iovisor-dev/2017-January/000603.html

My guess is that when register spills to stack and restore, the state
of imm upper zero bits does not get restore? Any comments are
appreciated!

This time the verifier shows:
---
   R0=imm0,min_value=0,max_value=0 R1=imm58,min_value=58,max_value=58
R3=pkt(id=0,off=58,r=58) R4=inv61 R5=pkt_end
R6=imm144,min_value=144,max_value=144 R7=imm0,min_value=0,max_value=0
R8=ctx R9=pkt(id=0,off=0,r=58) R10=fp
260: (bf) r5 = r6
261: (47) r5 |= 12
262: (bf) r1 = r5
263: (07) r1 += 44
264: (77) r1 >>= 3
265: (7b) *(u64 *)(r10 -64) = r1
266: (bf) r7 = r5
267: (07) r7 += 36
268: (77) r7 >>= 3
269: (bf) r0 = r5
270: (07) r0 += 20
271: (77) r0 >>= 3
272: (bf) r1 = r5
273: (07) r1 += 52
274: (77) r1 >>= 3
275: (77) r6 >>= 3
276: (79) r2 = *(u64 *)(r10 -24)
277: (bf) r2 = r5
278: (77) r2 >>= 3
279: (7b) *(u64 *)(r10 -184) = r2
280: (07) r5 += 180
281: (77) r5 >>= 3
282: (bf) r4 = r9
283: (0f) r4 += r5
284: (47) r5 |= 1
285: (bf) r3 = r9
286: (0f) r3 += r6
287: (bf) r6 = r9
288: (0f) r6 += r1
289: (47) r1 |= 1
290: (bf) r2 = r9
291: (0f) r2 += r0
292: (7b) *(u64 *)(r10 -312) = r2
293: (bf) r2 = r9
294: (79) r0 = *(u64 *)(r10 -184)
295: (0f) r2 += r0
cannot add integer value with 0 upper zero bits to ptr_to_packet


Right, so lines 260, 261 r5 is imm type, which in 277 is transferred
to r2 and eventually in 279 spilled to stack. check_stack_write() would
see that type is not spillable, so it will be stored as regular data
to stack (STACK_MISC). Later read in 294 will restore that to r0.
check_stack_read() sees that stack was marked as STACK_MISC and marks
reg as unknown, where you'll later get the error when added to ptr_to_packet
as no overflow protection can be guaranteed (imm is 0). Afaik (Alexei,
might correct me if I'm wrong), if we would support spilling imm, this
could have a non-trivial increase in complexity, where verifier would
need to do a lot more work due to pruning not taking effect. If you
look at evaluate_reg_alu(), you could try to work around it for the time
being by doing r0 &= 0x right before the r2 += r0.

Thanks,
Daniel

___
iovisor-dev mailing list
iovisor-dev@lists.iovisor.org
https://lists.iovisor.org/mailman/listinfo/iovisor-dev

Re: [iovisor-dev] BPF verifier: cannot add integer value with 0 upper zero bits to ptr_to_packet

2017-02-23 Thread William Tu via iovisor-dev 
Hi Daniel,

Thanks for the reply! I understand the workaround, can you suggest a
way to try it? Should I compile the C source into llvm IR bitcode, add
thie "r0 &= 0x", then assembly it to bpf target binary.

Thanks
William


On Wed, Feb 22, 2017 at 9:08 AM, Daniel Borkmann  wrote:
> On 02/17/2017 06:07 PM, William Tu via iovisor-dev wrote:
>>
>> Hi,
>>
>> I encountered another BPF verifier issue related to my previous one
>> https://lists.iovisor.org/pipermail/iovisor-dev/2017-January/000603.html
>>
>> My guess is that when register spills to stack and restore, the state
>> of imm upper zero bits does not get restore? Any comments are
>> appreciated!
>>
>> This time the verifier shows:
>> ---
>>   R0=imm0,min_value=0,max_value=0 R1=imm58,min_value=58,max_value=58
>> R3=pkt(id=0,off=58,r=58) R4=inv61 R5=pkt_end
>> R6=imm144,min_value=144,max_value=144 R7=imm0,min_value=0,max_value=0
>> R8=ctx R9=pkt(id=0,off=0,r=58) R10=fp
>> 260: (bf) r5 = r6
>> 261: (47) r5 |= 12
>> 262: (bf) r1 = r5
>> 263: (07) r1 += 44
>> 264: (77) r1 >>= 3
>> 265: (7b) *(u64 *)(r10 -64) = r1
>> 266: (bf) r7 = r5
>> 267: (07) r7 += 36
>> 268: (77) r7 >>= 3
>> 269: (bf) r0 = r5
>> 270: (07) r0 += 20
>> 271: (77) r0 >>= 3
>> 272: (bf) r1 = r5
>> 273: (07) r1 += 52
>> 274: (77) r1 >>= 3
>> 275: (77) r6 >>= 3
>> 276: (79) r2 = *(u64 *)(r10 -24)
>> 277: (bf) r2 = r5
>> 278: (77) r2 >>= 3
>> 279: (7b) *(u64 *)(r10 -184) = r2
>> 280: (07) r5 += 180
>> 281: (77) r5 >>= 3
>> 282: (bf) r4 = r9
>> 283: (0f) r4 += r5
>> 284: (47) r5 |= 1
>> 285: (bf) r3 = r9
>> 286: (0f) r3 += r6
>> 287: (bf) r6 = r9
>> 288: (0f) r6 += r1
>> 289: (47) r1 |= 1
>> 290: (bf) r2 = r9
>> 291: (0f) r2 += r0
>> 292: (7b) *(u64 *)(r10 -312) = r2
>> 293: (bf) r2 = r9
>> 294: (79) r0 = *(u64 *)(r10 -184)
>> 295: (0f) r2 += r0
>> cannot add integer value with 0 upper zero bits to ptr_to_packet
>
>
> Right, so lines 260, 261 r5 is imm type, which in 277 is transferred
> to r2 and eventually in 279 spilled to stack. check_stack_write() would
> see that type is not spillable, so it will be stored as regular data
> to stack (STACK_MISC). Later read in 294 will restore that to r0.
> check_stack_read() sees that stack was marked as STACK_MISC and marks
> reg as unknown, where you'll later get the error when added to ptr_to_packet
> as no overflow protection can be guaranteed (imm is 0). Afaik (Alexei,
> might correct me if I'm wrong), if we would support spilling imm, this
> could have a non-trivial increase in complexity, where verifier would
> need to do a lot more work due to pruning not taking effect. If you
> look at evaluate_reg_alu(), you could try to work around it for the time
> being by doing r0 &= 0x right before the r2 += r0.
>
> Thanks,
> Daniel
___
iovisor-dev mailing list
iovisor-dev@lists.iovisor.org
https://lists.iovisor.org/mailman/listinfo/iovisor-dev

Re: [iovisor-dev] BPF verifier: cannot add integer value with 0 upper zero bits to ptr_to_packet

2017-01-19 Thread Daniel Borkmann via iovisor-dev 

On 01/19/2017 04:53 PM, William Tu wrote:

thanks for the patch, it works.


Thanks a lot, I'll see to cook a proper patch then.


from 52 to 80: R0=imm1,min_value=1,max_value=1 R1=pkt(id=0,off=0,r=34)
R2=pkt_end R3=inv R4=imm272 R5=inv56,min_value=17,max_value=17
R6=pkt(id=0,off=26,r=34) R10=fp
80: (07) r4 += 71
81: (18) r5 = 0xfff8
83: (5f) r4 &= r5
84: (77) r4 >>= 3
85: (0f) r1 += r4
cannot add integer value with 3 upper zero bits to ptr_to_packet

I have no idea why this time the compiler wants to do "and" then
"right shift", instead of directly shit right 3 bit. R5's type is
UNKNOWN_VALUE, So in addition to your patch, I add



But what the compiler is doing here is still correct eventually I assume?


Yes, it zero out the least significant 3 bits first, then shift right 3 bits.


We could also add BPF_AND, but that r5's type is UNKNOWN_VALUE doesn't
seem right if I'm not mistaken. That r5 = 0xfff8 should be a dw imm
load, print_bpf_insn() seems only to print first part. So next r4 &= r5
should be purely imm operation as well and thus trackable. Only that we
need to teach verifier to keep the dw imm when not used with analyzer_ops
(nfp related).

Could you try the below (only compile tested here) to see whether the
verifier can now analyze that part?

Thanks,
Daniel

  kernel/bpf/verifier.c   | 35
++---
  tools/testing/selftests/bpf/test_verifier.c | 24 
  2 files changed, 51 insertions(+), 8 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index d60e12c..777ef0a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1567,19 +1567,44 @@ static int evaluate_reg_imm_alu(struct
bpf_verifier_env *env,

 struct bpf_reg_state *src_reg = [insn->src_reg];
 u8 opcode = BPF_OP(insn->code);

-   /* dst_reg->type == CONST_IMM here, simulate execution of 'add'/'or'
-* insn. Don't care about overflow or negative values, just add them
+   /* dst_reg->type == CONST_IMM here, simulate execution of
'add'/'or'/...
+* insn. Don't care about overflow or negative values, just add
them.
  */
 if (opcode == BPF_ADD && BPF_SRC(insn->code) == BPF_K)
 dst_reg->imm += insn->imm;
 else if (opcode == BPF_ADD && BPF_SRC(insn->code) == BPF_X &&
  src_reg->type == CONST_IMM)
 dst_reg->imm += src_reg->imm;
+   else if (opcode == BPF_SUB && BPF_SRC(insn->code) == BPF_K)
+   dst_reg->imm -= insn->imm;
+   else if (opcode == BPF_SUB && BPF_SRC(insn->code) == BPF_X &&
+src_reg->type == CONST_IMM)
+   dst_reg->imm -= src_reg->imm;
+   else if (opcode == BPF_MUL && BPF_SRC(insn->code) == BPF_K)
+   dst_reg->imm *= insn->imm;
+   else if (opcode == BPF_MUL && BPF_SRC(insn->code) == BPF_X &&
+src_reg->type == CONST_IMM)
+   dst_reg->imm *= src_reg->imm;
 else if (opcode == BPF_OR && BPF_SRC(insn->code) == BPF_K)
 dst_reg->imm |= insn->imm;
 else if (opcode == BPF_OR && BPF_SRC(insn->code) == BPF_X &&
  src_reg->type == CONST_IMM)
 dst_reg->imm |= src_reg->imm;
+   else if (opcode == BPF_AND && BPF_SRC(insn->code) == BPF_K)
+   dst_reg->imm &= insn->imm;
+   else if (opcode == BPF_AND && BPF_SRC(insn->code) == BPF_X &&
+src_reg->type == CONST_IMM)
+   dst_reg->imm &= src_reg->imm;


Thanks, with this patch. now r5 is CONST_IMM, not UNKNOWN_VALUE.

Regards,
William



+   else if (opcode == BPF_RSH && BPF_SRC(insn->code) == BPF_K)
+   dst_reg->imm >>= insn->imm;
+   else if (opcode == BPF_RSH && BPF_SRC(insn->code) == BPF_X &&
+src_reg->type == CONST_IMM)
+   dst_reg->imm >>= src_reg->imm;
+   else if (opcode == BPF_LSH && BPF_SRC(insn->code) == BPF_K)
+   dst_reg->imm <<= insn->imm;
+   else if (opcode == BPF_LSH && BPF_SRC(insn->code) == BPF_X &&
+src_reg->type == CONST_IMM)
+   dst_reg->imm <<= src_reg->imm;
 else
 mark_reg_unknown_value(regs, insn->dst_reg);
 return 0;
@@ -2225,14 +2250,8 @@ static int check_ld_imm(struct bpf_verifier_env *env,
struct bpf_insn *insn)
 return err;

 if (insn->src_reg == 0) {
-   /* generic move 64-bit immediate into a register,
-* only analyzer needs to collect the ld_imm value.
-*/
 u64 imm = ((u64)(insn + 1)->imm << 32) | (u32)insn->imm;

-   if (!env->analyzer_ops)
-   return 0;
-
 regs[insn->dst_reg].type = CONST_IMM;
 regs[insn->dst_reg].imm = imm;

 return 0;
diff --git a/tools/testing/selftests/bpf/test_verifier.c
b/tools/testing/selftests/bpf/test_verifier.c
index 1aa7324..d60bd07 100644
---

Re: [iovisor-dev] BPF verifier: cannot add integer value with 0 upper zero bits to ptr_to_packet

2017-01-18 Thread Daniel Borkmann via iovisor-dev 

On 01/18/2017 06:29 PM, William Tu wrote:

Hi Daniel,
Thanks for the patch. Yes, it solves my issue. Then there is another
related due to BPF_AND

LBB0_12:
; if (ebpf_packetEnd < ebpf_packetStart + BYTES(ebpf_packetOffsetInBits + 64)) {

from 52 to 80: R0=imm1,min_value=1,max_value=1 R1=pkt(id=0,off=0,r=34)
R2=pkt_end R3=inv R4=imm272 R5=inv56,min_value=17,max_value=17
R6=pkt(id=0,off=26,r=34) R10=fp
80: (07) r4 += 71
81: (18) r5 = 0xfff8
83: (5f) r4 &= r5
84: (77) r4 >>= 3
85: (0f) r1 += r4
cannot add integer value with 3 upper zero bits to ptr_to_packet

I have no idea why this time the compiler wants to do "and" then
"right shift", instead of directly shit right 3 bit. R5's type is
UNKNOWN_VALUE, So in addition to your patch, I add


But what the compiler is doing here is still correct eventually I assume?
We could also add BPF_AND, but that r5's type is UNKNOWN_VALUE doesn't
seem right if I'm not mistaken. That r5 = 0xfff8 should be a dw imm
load, print_bpf_insn() seems only to print first part. So next r4 &= r5
should be purely imm operation as well and thus trackable. Only that we
need to teach verifier to keep the dw imm when not used with analyzer_ops
(nfp related).

Could you try the below (only compile tested here) to see whether the
verifier can now analyze that part?

Thanks,
Daniel

 kernel/bpf/verifier.c   | 35 ++---
 tools/testing/selftests/bpf/test_verifier.c | 24 
 2 files changed, 51 insertions(+), 8 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index d60e12c..777ef0a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1567,19 +1567,44 @@ static int evaluate_reg_imm_alu(struct bpf_verifier_env 
*env,
struct bpf_reg_state *src_reg = [insn->src_reg];
u8 opcode = BPF_OP(insn->code);

-   /* dst_reg->type == CONST_IMM here, simulate execution of 'add'/'or'
-* insn. Don't care about overflow or negative values, just add them
+   /* dst_reg->type == CONST_IMM here, simulate execution of 'add'/'or'/...
+* insn. Don't care about overflow or negative values, just add them.
 */
if (opcode == BPF_ADD && BPF_SRC(insn->code) == BPF_K)
dst_reg->imm += insn->imm;
else if (opcode == BPF_ADD && BPF_SRC(insn->code) == BPF_X &&
 src_reg->type == CONST_IMM)
dst_reg->imm += src_reg->imm;
+   else if (opcode == BPF_SUB && BPF_SRC(insn->code) == BPF_K)
+   dst_reg->imm -= insn->imm;
+   else if (opcode == BPF_SUB && BPF_SRC(insn->code) == BPF_X &&
+src_reg->type == CONST_IMM)
+   dst_reg->imm -= src_reg->imm;
+   else if (opcode == BPF_MUL && BPF_SRC(insn->code) == BPF_K)
+   dst_reg->imm *= insn->imm;
+   else if (opcode == BPF_MUL && BPF_SRC(insn->code) == BPF_X &&
+src_reg->type == CONST_IMM)
+   dst_reg->imm *= src_reg->imm;
else if (opcode == BPF_OR && BPF_SRC(insn->code) == BPF_K)
dst_reg->imm |= insn->imm;
else if (opcode == BPF_OR && BPF_SRC(insn->code) == BPF_X &&
 src_reg->type == CONST_IMM)
dst_reg->imm |= src_reg->imm;
+   else if (opcode == BPF_AND && BPF_SRC(insn->code) == BPF_K)
+   dst_reg->imm &= insn->imm;
+   else if (opcode == BPF_AND && BPF_SRC(insn->code) == BPF_X &&
+src_reg->type == CONST_IMM)
+   dst_reg->imm &= src_reg->imm;
+   else if (opcode == BPF_RSH && BPF_SRC(insn->code) == BPF_K)
+   dst_reg->imm >>= insn->imm;
+   else if (opcode == BPF_RSH && BPF_SRC(insn->code) == BPF_X &&
+src_reg->type == CONST_IMM)
+   dst_reg->imm >>= src_reg->imm;
+   else if (opcode == BPF_LSH && BPF_SRC(insn->code) == BPF_K)
+   dst_reg->imm <<= insn->imm;
+   else if (opcode == BPF_LSH && BPF_SRC(insn->code) == BPF_X &&
+src_reg->type == CONST_IMM)
+   dst_reg->imm <<= src_reg->imm;
else
mark_reg_unknown_value(regs, insn->dst_reg);
return 0;
@@ -2225,14 +2250,8 @@ static int check_ld_imm(struct bpf_verifier_env *env, 
struct bpf_insn *insn)
return err;

if (insn->src_reg == 0) {
-   /* generic move 64-bit immediate into a register,
-* only analyzer needs to collect the ld_imm value.
-*/
u64 imm = ((u64)(insn + 1)->imm << 32) | (u32)insn->imm;

-   if (!env->analyzer_ops)
-   return 0;
-
regs[insn->dst_reg].type = CONST_IMM;
regs[insn->dst_reg].imm = imm;
return 0;
diff --git a/tools/testing/selftests/bpf/test_verifier.c 
b/tools/testing/selftests/bpf/test_verifier.c
index 1aa7324..d60bd07 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++

Re: [iovisor-dev] BPF verifier: cannot add integer value with 0 upper zero bits to ptr_to_packet

2017-01-18 Thread William Tu via iovisor-dev 
Hi Daniel,
Thanks for the patch. Yes, it solves my issue. Then there is another
related due to BPF_AND

LBB0_12:
; if (ebpf_packetEnd < ebpf_packetStart + BYTES(ebpf_packetOffsetInBits + 64)) {

from 52 to 80: R0=imm1,min_value=1,max_value=1 R1=pkt(id=0,off=0,r=34)
R2=pkt_end R3=inv R4=imm272 R5=inv56,min_value=17,max_value=17
R6=pkt(id=0,off=26,r=34) R10=fp
80: (07) r4 += 71
81: (18) r5 = 0xfff8
83: (5f) r4 &= r5
84: (77) r4 >>= 3
85: (0f) r1 += r4
cannot add integer value with 3 upper zero bits to ptr_to_packet

I have no idea why this time the compiler wants to do "and" then
"right shift", instead of directly shit right 3 bit. R5's type is
UNKNOWN_VALUE, So in addition to your patch, I add

--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1489,11 +1489,46 @@ static int evaluate_reg_imm_alu(struct
bpf_verifier_env *env,
else if (opcode == BPF_OR && BPF_SRC(insn->code) == BPF_K)
dst_reg->imm |= insn->imm;
else if (opcode == BPF_OR && BPF_SRC(insn->code) == BPF_X &&
 src_reg->type == CONST_IMM)
dst_reg->imm |= src_reg->imm;
+
+   else if (opcode == BPF_AND && BPF_SRC(insn->code) == BPF_K)
+   dst_reg->imm &= insn->imm;
+   else if (opcode == BPF_AND && BPF_SRC(insn->code) == BPF_X &&
+   src_reg->type == CONST_IMM)
+   dst_reg->imm &= src_reg->imm;
+
+   else if (opcode == BPF_AND && BPF_SRC(insn->code) == BPF_X &&
+   src_reg->type == UNKNOWN_VALUE)
+   {
+   dst_reg->min_value &= src_reg->min_value;
+   dst_reg->max_value &= src_reg->max_value;
+   }

Then it passes verifier.

William

On Tue, Jan 17, 2017 at 3:16 PM, Daniel Borkmann  wrote:
> Hi William,
>
>
> On 01/12/2017 07:32 PM, William Tu via iovisor-dev wrote:
>>
>> Hi,
>> I encounter the following BPF verifier error:
>>
>> from 28 to 30: R0=imm1,min_value=1,max_value=1 R1=pkt(id=0,off=0,r=22)
>> R2=pkt_end R3=imm144,min_value=144,max_value=144
>> R4=imm0,min_value=0,max_value=0 R5=inv48,min_value=2054,max_value=2054
>> R10=fp
>> 30: (bf) r5 = r3
>> 31: (07) r5 += 23
>> 32: (77) r5 >>= 3
>> 33: (bf) r6 = r1
>> 34: (0f) r6 += r5
>> cannot add integer value with 0 upper zero bits to ptr_to_packet
>> ---
>> Shouldn't the r5 be an imm value? since it comes from r3=144 and just
>> doing +=23 and shift right 3 bits?
>> ---
>> the C code is doing data and data_end checking:
>> ebpf_filter:
>> ; int ebpf_filter(struct xdp_md* skb){
>> 0: r2 = *(u32 *)(r1 + 4)
>> ; void *data = (void *)(long)skb->data;
>> 1: r1 = *(u32 *)(r1 + 0)
>> ; u32 ebpf_zero = 0;
>> 2: r3 = 0
>> 3: *(u32 *)(r10 - 4) = r3
>> 4: r0 = 1
>> ; if (data_end < data + BYTES(ebpf_packetOffsetInBits + 48)) {
>> 5: r3 = r1
>> 6: r3 += 6
>> 7: if r3 > r2 goto 1
>> 8: goto 1
>> ...
>> LBB0_1:
>> ; if (data_end < data + BYTES(ebpf_packetOffsetInBits + 16)) {
>>30: r5 = r3
>>31: r5 += 23
>>32: r5 >>= 3
>>33: r6 = r1
>>34: r6 += r5
>>35: if r6 > r2 goto 65509
>> ; if (data_end < data + BYTES(ebpf_packetOffsetInBits + 16)) {
>> ...
>> In which I was checking the packet's boundary. BYTE() is a simple macro
>> doing
>> #define BYTES(w) ((w + 7) >> 3)
>
>
> Can you try out the below patch?
>
> evaluate_reg_imm_alu() is invoked on ALU ops where the dst reg is
> CONST_IMM and the src is either a constant from the insn or a reg
> with type CONST_IMM. Currently we only simulate BPF_ADD / BPF_OR
> and if we encounter something else (like in your case shifts), then
> we mark the reg from imm to unknown, and as soon as you try to add
> that to the pkt pointer, then check_packet_ptr_add() will bark due
> to src_reg->imm being 0 from prior mark_reg_unknown_value(). Given
> we don't care about overflows or negative values on tracking pure
> imm ops, we might as well let evaluate_reg_imm_alu() simulate more
> ops than just these two. Does that fix it for you?
>
> Signed-off-by: Daniel Borkmann 
> ---
>  kernel/bpf/verifier.c   | 24 ++--
>  tools/testing/selftests/bpf/test_verifier.c | 24 
>  2 files changed, 46 insertions(+), 2 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index d60e12c..2ac50ae 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -1567,19 +1567,39 @@ static int evaluate_reg_imm_alu(struct
> bpf_verifier_env *env,
> struct bpf_reg_state *src_reg = [insn->src_reg];
> u8 opcode = BPF_OP(insn->code);
>
> -   /* dst_reg->type == CONST_IMM here, simulate execution of 'add'/'or'
> -* insn. Don't care about overflow or negative values, just add them
> +   /* dst_reg->type == CONST_IMM here, simulate execution of
> 'add'/'or'/...
> +* insn. Don't care about overflow or negative values, just add
> them.
>  */
>

Re: [iovisor-dev] BPF verifier: cannot add integer value with 0 upper zero bits to ptr_to_packet

2017-01-17 Thread Daniel Borkmann via iovisor-dev 

Hi William,

On 01/12/2017 07:32 PM, William Tu via iovisor-dev wrote:

Hi,
I encounter the following BPF verifier error:

from 28 to 30: R0=imm1,min_value=1,max_value=1 R1=pkt(id=0,off=0,r=22)
R2=pkt_end R3=imm144,min_value=144,max_value=144
R4=imm0,min_value=0,max_value=0 R5=inv48,min_value=2054,max_value=2054
R10=fp
30: (bf) r5 = r3
31: (07) r5 += 23
32: (77) r5 >>= 3
33: (bf) r6 = r1
34: (0f) r6 += r5
cannot add integer value with 0 upper zero bits to ptr_to_packet
---
Shouldn't the r5 be an imm value? since it comes from r3=144 and just
doing +=23 and shift right 3 bits?
---
the C code is doing data and data_end checking:
ebpf_filter:
; int ebpf_filter(struct xdp_md* skb){
0: r2 = *(u32 *)(r1 + 4)
; void *data = (void *)(long)skb->data;
1: r1 = *(u32 *)(r1 + 0)
; u32 ebpf_zero = 0;
2: r3 = 0
3: *(u32 *)(r10 - 4) = r3
4: r0 = 1
; if (data_end < data + BYTES(ebpf_packetOffsetInBits + 48)) {
5: r3 = r1
6: r3 += 6
7: if r3 > r2 goto 1
8: goto 1
...
LBB0_1:
; if (data_end < data + BYTES(ebpf_packetOffsetInBits + 16)) {
   30: r5 = r3
   31: r5 += 23
   32: r5 >>= 3
   33: r6 = r1
   34: r6 += r5
   35: if r6 > r2 goto 65509
; if (data_end < data + BYTES(ebpf_packetOffsetInBits + 16)) {
...
In which I was checking the packet's boundary. BYTE() is a simple macro doing
#define BYTES(w) ((w + 7) >> 3)


Can you try out the below patch?

evaluate_reg_imm_alu() is invoked on ALU ops where the dst reg is
CONST_IMM and the src is either a constant from the insn or a reg
with type CONST_IMM. Currently we only simulate BPF_ADD / BPF_OR
and if we encounter something else (like in your case shifts), then
we mark the reg from imm to unknown, and as soon as you try to add
that to the pkt pointer, then check_packet_ptr_add() will bark due
to src_reg->imm being 0 from prior mark_reg_unknown_value(). Given
we don't care about overflows or negative values on tracking pure
imm ops, we might as well let evaluate_reg_imm_alu() simulate more
ops than just these two. Does that fix it for you?

Signed-off-by: Daniel Borkmann 
---
 kernel/bpf/verifier.c   | 24 ++--
 tools/testing/selftests/bpf/test_verifier.c | 24 
 2 files changed, 46 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index d60e12c..2ac50ae 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1567,19 +1567,39 @@ static int evaluate_reg_imm_alu(struct bpf_verifier_env 
*env,
struct bpf_reg_state *src_reg = [insn->src_reg];
u8 opcode = BPF_OP(insn->code);

-   /* dst_reg->type == CONST_IMM here, simulate execution of 'add'/'or'
-* insn. Don't care about overflow or negative values, just add them
+   /* dst_reg->type == CONST_IMM here, simulate execution of 'add'/'or'/...
+* insn. Don't care about overflow or negative values, just add them.
 */
if (opcode == BPF_ADD && BPF_SRC(insn->code) == BPF_K)
dst_reg->imm += insn->imm;
else if (opcode == BPF_ADD && BPF_SRC(insn->code) == BPF_X &&
 src_reg->type == CONST_IMM)
dst_reg->imm += src_reg->imm;
+   else if (opcode == BPF_SUB && BPF_SRC(insn->code) == BPF_K)
+   dst_reg->imm -= insn->imm;
+   else if (opcode == BPF_SUB && BPF_SRC(insn->code) == BPF_X &&
+src_reg->type == CONST_IMM)
+   dst_reg->imm -= src_reg->imm;
+   else if (opcode == BPF_MUL && BPF_SRC(insn->code) == BPF_K)
+   dst_reg->imm *= insn->imm;
+   else if (opcode == BPF_MUL && BPF_SRC(insn->code) == BPF_X &&
+src_reg->type == CONST_IMM)
+   dst_reg->imm *= src_reg->imm;
else if (opcode == BPF_OR && BPF_SRC(insn->code) == BPF_K)
dst_reg->imm |= insn->imm;
else if (opcode == BPF_OR && BPF_SRC(insn->code) == BPF_X &&
 src_reg->type == CONST_IMM)
dst_reg->imm |= src_reg->imm;
+   else if (opcode == BPF_RSH && BPF_SRC(insn->code) == BPF_K)
+   dst_reg->imm >>= insn->imm;
+   else if (opcode == BPF_RSH && BPF_SRC(insn->code) == BPF_X &&
+src_reg->type == CONST_IMM)
+   dst_reg->imm >>= src_reg->imm;
+   else if (opcode == BPF_LSH && BPF_SRC(insn->code) == BPF_K)
+   dst_reg->imm <<= insn->imm;
+   else if (opcode == BPF_LSH && BPF_SRC(insn->code) == BPF_X &&
+src_reg->type == CONST_IMM)
+   dst_reg->imm <<= src_reg->imm;
else
mark_reg_unknown_value(regs, insn->dst_reg);
return 0;
diff --git a/tools/testing/selftests/bpf/test_verifier.c 
b/tools/testing/selftests/bpf/test_verifier.c
index 1aa7324..d60bd07 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -2326,6 +2326,30 @@

[iovisor-dev] BPF verifier: cannot add integer value with 0 upper zero bits to ptr_to_packet

2017-01-12 Thread William Tu via iovisor-dev 
Hi,
I encounter the following BPF verifier error:

from 28 to 30: R0=imm1,min_value=1,max_value=1 R1=pkt(id=0,off=0,r=22)
R2=pkt_end R3=imm144,min_value=144,max_value=144
R4=imm0,min_value=0,max_value=0 R5=inv48,min_value=2054,max_value=2054
R10=fp
30: (bf) r5 = r3
31: (07) r5 += 23
32: (77) r5 >>= 3
33: (bf) r6 = r1
34: (0f) r6 += r5
cannot add integer value with 0 upper zero bits to ptr_to_packet
---
Shouldn't the r5 be an imm value? since it comes from r3=144 and just
doing +=23 and shift right 3 bits?
---
the C code is doing data and data_end checking:
ebpf_filter:
; int ebpf_filter(struct xdp_md* skb){
   0: r2 = *(u32 *)(r1 + 4)
; void *data = (void *)(long)skb->data;
   1: r1 = *(u32 *)(r1 + 0)
; u32 ebpf_zero = 0;
   2: r3 = 0
   3: *(u32 *)(r10 - 4) = r3
   4: r0 = 1
; if (data_end < data + BYTES(ebpf_packetOffsetInBits + 48)) {
   5: r3 = r1
   6: r3 += 6
   7: if r3 > r2 goto 1
   8: goto 1
...
LBB0_1:
; if (data_end < data + BYTES(ebpf_packetOffsetInBits + 16)) {
  30: r5 = r3
  31: r5 += 23
  32: r5 >>= 3
  33: r6 = r1
  34: r6 += r5
  35: if r6 > r2 goto 65509
; if (data_end < data + BYTES(ebpf_packetOffsetInBits + 16)) {
...
In which I was checking the packet's boundary. BYTE() is a simple macro doing
#define BYTES(w) ((w + 7) >> 3)

Thanks!
William
___
iovisor-dev mailing list
iovisor-dev@lists.iovisor.org
https://lists.iovisor.org/mailman/listinfo/iovisor-dev