Re: bpf pointer alignment validation

[David Miller]

From: Daniel Borkmann 
Date: Wed, 10 May 2017 18:21:50 +0200

> On 05/10/2017 05:57 PM, David Miller wrote:
>> From: Daniel Borkmann 
>> Date: Wed, 10 May 2017 17:51:50 +0200
>>
>>> Would probably be good nevertheless to have this as a flag for
>>> program loads, which gets then passed through to the verifier to
>>> explicitly enable strict alignment checks.
>>>
>>> Might certainly aide developing & testing programs on archs with
>>> efficient unaligned access and later actually running them on archs
>>> that don't have it. (And at minimum, it also helps for checking
>>> the test suite against the verifier.)
>>
>> Ok, I can implement this flag.
>>
>> The only question is where to put it?  An unused bit in the program
>> type? :-)
> 
> See for example 7f677633379b ("bpf: introduce BPF_F_ALLOW_OVERRIDE
> flag"). We can add a flags field to the prog loading part of union
> bpf_attr; we would need to make sure to update
> BPF_PROG_LOAD_LAST_FIELD
> to the new member, and to reject unknown flags, of course. Then the
> syscall will handle compat with older binaries just fine by design,
> the main bpf syscall code and CHECK_ATTR() macros will ensure this
> (backward compat, and to a limited degree also forward compat).

Thanks to both of you for guidance on how to do this properly.

Here is what I have right now, once things look good enough I'll split
it all out into a proper patch series:

1) Add alignment tracking.
2) Add "log_level > 1" per-insn state dumping
3) Add BPF_F_STRICT_ALIGNMENT
4) Add bpf_verify_program() to library
5) Add test_align to selftests


Subject: [PATCH] BPF alignment framework

---
 include/linux/bpf_verifier.h |   3 +
 include/uapi/linux/bpf.h |   8 +
 kernel/bpf/syscall.c |   5 +-
 kernel/bpf/verifier.c| 132 --
 tools/include/uapi/linux/bpf.h   |  11 +-
 tools/lib/bpf/bpf.c  |  22 ++
 tools/lib/bpf/bpf.h  |   4 +
 tools/testing/selftests/bpf/Makefile |   4 +-
 tools/testing/selftests/bpf/test_align.c | 417 +++
 9 files changed, 581 insertions(+), 25 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/test_align.c

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 5efb4db..7c6a519 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -40,6 +40,9 @@ struct bpf_reg_state {
 */
s64 min_value;
u64 max_value;
+   u32 min_align;
+   u32 aux_off;
+   u32 aux_off_align;
 };
 
 enum bpf_stack_slot_type {
diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index 945a1f5..94dfa9d 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -132,6 +132,13 @@ enum bpf_attach_type {
  */
 #define BPF_F_ALLOW_OVERRIDE   (1U << 0)
 
+/* If BPF_F_STRICT_ALIGNMENT is used in BPF_PROG_LOAD command, the
+ * verifier will perform strict alignment checking as if the kernel
+ * has been built with CONFIG_EFFICIENT_UNALIGNED_ACCESS not set,
+ * and NET_IP_ALIGN defined to 2.
+ */
+#define BPF_F_STRICT_ALIGNMENT (1U << 0)
+
 #define BPF_PSEUDO_MAP_FD  1
 
 /* flags for BPF_MAP_UPDATE_ELEM command */
@@ -177,6 +184,7 @@ union bpf_attr {
__u32   log_size;   /* size of user buffer */
__aligned_u64   log_buf;/* user supplied buffer */
__u32   kern_version;   /* checked when 
prog_type=kprobe */
+   __u32   prog_flags;
};
 
struct { /* anonymous struct used by BPF_OBJ_* commands */
diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
index 13642c7..027053a 100644
--- a/kernel/bpf/syscall.c
+++ b/kernel/bpf/syscall.c
@@ -784,7 +784,7 @@ struct bpf_prog *bpf_prog_get_type(u32 ufd, enum 
bpf_prog_type type)
 EXPORT_SYMBOL_GPL(bpf_prog_get_type);
 
 /* last field in 'union bpf_attr' used by this command */
-#defineBPF_PROG_LOAD_LAST_FIELD kern_version
+#defineBPF_PROG_LOAD_LAST_FIELD prog_flags
 
 static int bpf_prog_load(union bpf_attr *attr)
 {
@@ -797,6 +797,9 @@ static int bpf_prog_load(union bpf_attr *attr)
if (CHECK_ATTR(BPF_PROG_LOAD))
return -EINVAL;
 
+   if (attr->prog_flags & ~BPF_F_STRICT_ALIGNMENT)
+   return -EINVAL;
+
/* copy eBPF program license from user space */
if (strncpy_from_user(license, u64_to_user_ptr(attr->license),
  sizeof(license) - 1) < 0)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index c2ff608..87ecb4d 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -241,6 +241,12 @@ static void print_verifier_state(struct bpf_verifier_state 
*state)
if (reg->max_value != BPF_REGISTER_MAX_RANGE)
verbose(",max_value=%llu",
(unsigned long 

Re: bpf pointer alignment validation

[Daniel Borkmann]

On 05/10/2017 05:57 PM, David Miller wrote:

From: Daniel Borkmann 
Date: Wed, 10 May 2017 17:51:50 +0200


Would probably be good nevertheless to have this as a flag for
program loads, which gets then passed through to the verifier to
explicitly enable strict alignment checks.

Might certainly aide developing & testing programs on archs with
efficient unaligned access and later actually running them on archs
that don't have it. (And at minimum, it also helps for checking
the test suite against the verifier.)


Ok, I can implement this flag.

The only question is where to put it?  An unused bit in the program
type? :-)


See for example 7f677633379b ("bpf: introduce BPF_F_ALLOW_OVERRIDE
flag"). We can add a flags field to the prog loading part of union
bpf_attr; we would need to make sure to update BPF_PROG_LOAD_LAST_FIELD
to the new member, and to reject unknown flags, of course. Then the
syscall will handle compat with older binaries just fine by design,
the main bpf syscall code and CHECK_ATTR() macros will ensure this
(backward compat, and to a limited degree also forward compat).

Re: bpf pointer alignment validation

[Alexei Starovoitov]

On 5/10/17 8:57 AM, David Miller wrote:

From: Daniel Borkmann 
Date: Wed, 10 May 2017 17:51:50 +0200


Would probably be good nevertheless to have this as a flag for
program loads, which gets then passed through to the verifier to
explicitly enable strict alignment checks.

Might certainly aide developing & testing programs on archs with
efficient unaligned access and later actually running them on archs
that don't have it. (And at minimum, it also helps for checking
the test suite against the verifier.)


Ok, I can implement this flag.

The only question is where to put it?  An unused bit in the program
type? :-)


just add '__u32 prog_flags' to bpf_attr PROG_LOAD anon union.
There was no need for such flags in the past, hence no flags field
existed. Now it's time.

Re: bpf pointer alignment validation

[David Miller]

From: Daniel Borkmann 
Date: Wed, 10 May 2017 17:51:50 +0200

> Would probably be good nevertheless to have this as a flag for
> program loads, which gets then passed through to the verifier to
> explicitly enable strict alignment checks.
> 
> Might certainly aide developing & testing programs on archs with
> efficient unaligned access and later actually running them on archs
> that don't have it. (And at minimum, it also helps for checking
> the test suite against the verifier.)

Ok, I can implement this flag.

The only question is where to put it?  An unused bit in the program
type? :-)

Re: bpf pointer alignment validation

[Daniel Borkmann]

On 05/10/2017 05:33 PM, David Miller wrote:

From: Alexei Starovoitov 
Date: Tue, 9 May 2017 22:57:37 -0700


On Tue, May 09, 2017 at 02:32:34PM -0400, David Miller wrote:


+static u32 calc_align(u32 imm)
+{
+   u32 align = 1;
+
+   if (!imm)
+   return 1U << 31;
+
+   while (!(imm & 1)) {
+   imm >>= 1;
+   align <<= 1;
+   }
+   return align;
+}


same question as in previous reply.
Why not to use something like:
static u32 calc_align(u32 n)
{
 if (!n)
 return 1U << 31;
 return n - ((n - 1) & n);
}


Ok.

I did a cursory search and we don't have a generic kernel helper for
this kind of calculation.  I was actually quite surprised, as we
have one for everything else :-)


this needs to be tweaked like
if (log_level > 1)
 verbose("%d:", insn_idx);
else
verbose("\nfrom %d to %d:", prev_insn_idx, insn_idx);

otherwise it prints prev_insn_idx which is meaningful
only with processing exit and search pruning.


Agreed.


Nice to see all these comments.
I wonder how we can make them automatic in the verifier.
Like if verifier can somehow hint the user in such human friendly way
about what is happening with the program.
Today that's the #1 problem. Most folks complaining
that verifier error messages are too hard to understand.


We can put whatever text strings we want into that verifier buffer.
It is as flexible as netlink extended acks.


would it make sense to bpf_prog_test_run() it here as well?


We could.


On x86 not much value, but on sparc we can somehow look for traps?
Is there some counter of unaligned traps that we can read and report
as error to user space after prog_test_run ?


Unfortunately, no.


These tests we cannot really run, since they don't do any load/store.
I mean more for some future tests. Or some sort of debug warn
that there were traps while bpf prog was executed, so the user
is alarmed and reports to us, since that would be a bug in verifier
align logic?


One thing I could definitely do is add logic to the unaligned trap
handler to print something special in the logs if we find that we
are executing BPF code.

The basic structure of the log message can be codified in a generic
bpf_xxx() helper, which architectures call with the PC and unaligned
address as arguments.

I was thinking more last night about strict alignment mode for the
verifier, so that bugs can be spotted on all architectures.  But
it stupidly will not work.

The problem is that x86 and powerpc define NET_IP_ALIGN as 0, so all
bets are off.

One thing we could do in "strict alignment" verifier mode is pretend
that NET_IP_ALIGN is 2 in the alignment checks.


Would probably be good nevertheless to have this as a flag for
program loads, which gets then passed through to the verifier to
explicitly enable strict alignment checks.

Might certainly aide developing & testing programs on archs with
efficient unaligned access and later actually running them on archs
that don't have it. (And at minimum, it also helps for checking
the test suite against the verifier.)

Re: bpf pointer alignment validation

[David Miller]

From: Alexei Starovoitov 
Date: Tue, 9 May 2017 22:57:37 -0700

> On Tue, May 09, 2017 at 02:32:34PM -0400, David Miller wrote:
>>  
>> +static u32 calc_align(u32 imm)
>> +{
>> +u32 align = 1;
>> +
>> +if (!imm)
>> +return 1U << 31;
>> +
>> +while (!(imm & 1)) {
>> +imm >>= 1;
>> +align <<= 1;
>> +}
>> +return align;
>> +}
> 
> same question as in previous reply.
> Why not to use something like:
> static u32 calc_align(u32 n)
> {
> if (!n)
> return 1U << 31;
> return n - ((n - 1) & n);
> }

Ok.

I did a cursory search and we don't have a generic kernel helper for
this kind of calculation.  I was actually quite surprised, as we
have one for everything else :-)

> this needs to be tweaked like
> if (log_level > 1)
> verbose("%d:", insn_idx);
> else
>   verbose("\nfrom %d to %d:", prev_insn_idx, insn_idx);
> 
> otherwise it prints prev_insn_idx which is meaningful
> only with processing exit and search pruning.

Agreed.

> Nice to see all these comments.
> I wonder how we can make them automatic in the verifier.
> Like if verifier can somehow hint the user in such human friendly way
> about what is happening with the program.
> Today that's the #1 problem. Most folks complaining
> that verifier error messages are too hard to understand.

We can put whatever text strings we want into that verifier buffer.
It is as flexible as netlink extended acks.

> would it make sense to bpf_prog_test_run() it here as well?

We could.

> On x86 not much value, but on sparc we can somehow look for traps?
> Is there some counter of unaligned traps that we can read and report
> as error to user space after prog_test_run ?

Unfortunately, no.

> These tests we cannot really run, since they don't do any load/store.
> I mean more for some future tests. Or some sort of debug warn
> that there were traps while bpf prog was executed, so the user
> is alarmed and reports to us, since that would be a bug in verifier
> align logic?

One thing I could definitely do is add logic to the unaligned trap
handler to print something special in the logs if we find that we
are executing BPF code.

The basic structure of the log message can be codified in a generic
bpf_xxx() helper, which architectures call with the PC and unaligned
address as arguments.

I was thinking more last night about strict alignment mode for the
verifier, so that bugs can be spotted on all architectures.  But
it stupidly will not work.

The problem is that x86 and powerpc define NET_IP_ALIGN as 0, so all
bets are off.

One thing we could do in "strict alignment" verifier mode is pretend
that NET_IP_ALIGN is 2 in the alignment checks.

RE: bpf pointer alignment validation

[David Laight]

From: Alexei Starovoitov
> Sent: 10 May 2017 06:58
> > +static u32 calc_align(u32 imm)
> > +{
> > +   u32 align = 1;
> > +
> > +   if (!imm)
> > +   return 1U << 31;
> > +
> > +   while (!(imm & 1)) {
> > +   imm >>= 1;
> > +   align <<= 1;
> > +   }
> > +   return align;
> > +}
> 
> same question as in previous reply.
> Why not to use something like:
> static u32 calc_align(u32 n)
> {
> if (!n)
> return 1U << 31;
> return n - ((n - 1) & n);
> }

That function needs a comment saying what it returns.
Think I'd write it as:
return n & ~(n & (n - 1));
(even though that might be one more instruction)

David

Re: bpf pointer alignment validation

[Alexei Starovoitov]

On Tue, May 09, 2017 at 02:32:34PM -0400, David Miller wrote:
>  
> +static u32 calc_align(u32 imm)
> +{
> + u32 align = 1;
> +
> + if (!imm)
> + return 1U << 31;
> +
> + while (!(imm & 1)) {
> + imm >>= 1;
> + align <<= 1;
> + }
> + return align;
> +}

same question as in previous reply.
Why not to use something like:
static u32 calc_align(u32 n)
{
if (!n)
return 1U << 31;
return n - ((n - 1) & n);
}

> - if (log_level && do_print_state) {
> + if (log_level > 1 || (log_level && do_print_state)) {
>   verbose("\nfrom %d to %d:", prev_insn_idx, insn_idx);
>   print_verifier_state(>cur_state);
>   do_print_state = false;

this needs to be tweaked like
if (log_level > 1)
verbose("%d:", insn_idx);
else
verbose("\nfrom %d to %d:", prev_insn_idx, insn_idx);

otherwise it prints prev_insn_idx which is meaningful
only with processing exit and search pruning.
That's why below ...

> + .descr = "unknown shift",
> + .insns = {
> + LOAD_UNKNOWN(BPF_REG_3),
> + BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
> + BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
> + BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
> + BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
> + LOAD_UNKNOWN(BPF_REG_4),
> + BPF_ALU64_IMM(BPF_LSH, BPF_REG_4, 5),
> + BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
> + BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
> + BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
> + BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
> + BPF_MOV64_IMM(BPF_REG_0, 0),
> + BPF_EXIT_INSN(),
> + },
> + .prog_type = BPF_PROG_TYPE_SCHED_CLS,
> + .matches = {
> + "from 4 to 7: R0=pkt(id=0,off=8,r=8) R1=ctx 
> R2=pkt(id=0,off=0,r=8) R3=inv56 R10=fp",
> + "from 4 to 8: R0=pkt(id=0,off=8,r=8) R1=ctx 
> R2=pkt(id=0,off=0,r=8) R3=inv55,min_align=2 R10=fp",
> + "from 4 to 9: R0=pkt(id=0,off=8,r=8) R1=ctx 
> R2=pkt(id=0,off=0,r=8) R3=inv54,min_align=4 R10=fp",
> + "from 4 to 10: R0=pkt(id=0,off=8,r=8) R1=ctx 
> R2=pkt(id=0,off=0,r=8) R3=inv53,min_align=8 R10=fp",
> + "from 4 to 11: R0=pkt(id=0,off=8,r=8) R1=ctx 
> R2=pkt(id=0,off=0,r=8) R3=inv52,min_align=16 R10=fp",
> + "from 15 to 18: R0=pkt(id=0,off=8,r=8) R1=ctx 
> R2=pkt(id=0,off=0,r=8) R3=pkt_end R4=inv56 R10=fp",
> + "from 15 to 19: R0=pkt(id=0,off=8,r=8) R1=ctx 
> R2=pkt(id=0,off=0,r=8) R3=pkt_end R4=inv51,min_align=32 R10=fp",
> + "from 15 to 20: R0=pkt(id=0,off=8,r=8) R1=ctx 
> R2=pkt(id=0,off=0,r=8) R3=pkt_end R4=inv52,min_align=16 R10=fp",

... looks crazy here, since program is linear and 'from 4' and 'from 15' are
completely non-obvious and will change in the future for sure.
Since it just happened that search pruning heuristic kicked in at those points.
Hence doing verbose("%d:", insn_idx); is necessary to avoid noise.

> + .prog_type = BPF_PROG_TYPE_SCHED_CLS,
> + .matches = {
> + /* Calculated offset in R4 has unknown value, but known
> +  * alignment of 4.
> +  */
> + "from 4 to 8: R0=pkt(id=0,off=8,r=8) R1=ctx 
> R2=pkt(id=0,off=0,r=8) R3=pkt_end R6=inv54,min_align=4 R10=fp",
> +
> + /* Offset is added to packet pointer, resulting in known
> +  * auxiliary alignment and offset.
> +  */
> + "from 4 to 11: R0=pkt(id=0,off=8,r=8) R1=ctx 
> R2=pkt(id=0,off=0,r=8) R3=pkt_end 
> R5=pkt(id=1,off=0,r=0),aux_off=14,aux_off_align=4 R6=inv54,min_align=4 
> R10=fp",
> +
> + /* At the time the word size load is performed from R5,
> +  * it's total offset is NET_IP_ALIGN + reg->off (0) +
> +  * reg->aux_off (14) which is 16.  Then the variable
> +  * offset is considered using reg->aux_off_align which
> +  * is 4 and meets the load's requirements.
> +  */
> + "from 13 to 15: R0=pkt(id=0,off=8,r=8) R1=ctx 
> R2=pkt(id=0,off=0,r=8) R3=pkt_end 
> R4=pkt(id=1,off=4,r=4),aux_off=14,aux_off_align=4 
> R5=pkt(id=1,off=0,r=4),aux_off=14,aux_off_align=4 R6=inv54,min_align=4 
> R10=fp",
> +
> +
> + /* Variable offset is added to R5 packet pointer,
> +  * resulting in auxiliary alignment of 4.
> +  */
> + "from 13 to 18: R0=pkt(id=0,off=8,r=8) R1=ctx 
> R2=pkt(id=0,off=0,r=8) R3=pkt_end 

Re: bpf pointer alignment validation

[David Miller]

From: Daniel Borkmann 
Date: Mon, 08 May 2017 12:49:25 +0200

> Could you also add test cases specifically to this for test_verifier
> in bpf selftests? I'm thinking of the cases when we have no pkt id
> and offset originated from reg->off (accumulated through const imm
> ops on reg) and insn->off, where we had i) no pkt id and ii) a
> specific pkt id (so we can probe for aux_off_align rejection as well).
> I believe we do have coverage to some extend in some of the tests
> (more on the map_value_adj though), but it would be good to keep
> tracking this specifically as well.

So I created a new test, that uses the verifier, but in a new way.

The thing I wanted to do is match on verifier dump strings so that I
can test what the verifier thinks about the known alignment et al. of
various registers after the execution of certain instructions.

I accomplish this by doing two things:

1) If the log level of 2 or greater is given to the verifier, I dump
   the internal state to the log after every instruction.

2) A new BPF library helper called bpf_verify_program() is added which
   always passes the log to the BPF system call and uses a log level
   of 2.

Then in my "test_align" I have BPF programs as well as strings to
match against in the verifier dump.

The whole thing is below, and writing the test cases certainly helped
me refine the implementation quite a bit.

I'll keep adding some more tests and hacking on this.  It just
occurred to me that it would be extremely variable to be able to turn
on strict alignment requirements even on architectures that do not
need it.

That way anyone adding regressions to the alignment code, or hitting
new cases the code can't currently handle, would notice immediately
regardles of the type of system the run the test case on.

To be quite honest, strict alignment might not be a bad default either
to give helpful feedback to people writing eBPF programs.

---
 include/linux/bpf_verifier.h |   3 +
 kernel/bpf/verifier.c| 104 -
 tools/lib/bpf/bpf.c  |  20 ++
 tools/lib/bpf/bpf.h  |   4 +
 tools/testing/selftests/bpf/Makefile |   4 +-
 tools/testing/selftests/bpf/test_align.c | 378 +++
 6 files changed, 500 insertions(+), 13 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/test_align.c

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 5efb4db..7c6a519 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -40,6 +40,9 @@ struct bpf_reg_state {
 */
s64 min_value;
u64 max_value;
+   u32 min_align;
+   u32 aux_off;
+   u32 aux_off_align;
 };
 
 enum bpf_stack_slot_type {
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index c2ff608..2b1b06e 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -241,6 +241,12 @@ static void print_verifier_state(struct bpf_verifier_state 
*state)
if (reg->max_value != BPF_REGISTER_MAX_RANGE)
verbose(",max_value=%llu",
(unsigned long long)reg->max_value);
+   if (reg->min_align)
+   verbose(",min_align=%u", reg->min_align);
+   if (reg->aux_off)
+   verbose(",aux_off=%u", reg->aux_off);
+   if (reg->aux_off_align)
+   verbose(",aux_off_align=%u", reg->aux_off_align);
}
for (i = 0; i < MAX_BPF_STACK; i += BPF_REG_SIZE) {
if (state->stack_slot_type[i] == STACK_SPILL)
@@ -455,6 +461,9 @@ static void init_reg_state(struct bpf_reg_state *regs)
regs[i].imm = 0;
regs[i].min_value = BPF_REGISTER_MIN_RANGE;
regs[i].max_value = BPF_REGISTER_MAX_RANGE;
+   regs[i].min_align = 0;
+   regs[i].aux_off = 0;
+   regs[i].aux_off_align = 0;
}
 
/* frame pointer */
@@ -483,11 +492,17 @@ static void reset_reg_range_values(struct bpf_reg_state 
*regs, u32 regno)
regs[regno].max_value = BPF_REGISTER_MAX_RANGE;
 }
 
+static void reset_reg_align(struct bpf_reg_state *regs, u32 regno)
+{
+   regs[regno].min_align = 0;
+}
+
 static void mark_reg_unknown_value_and_range(struct bpf_reg_state *regs,
 u32 regno)
 {
mark_reg_unknown_value(regs, regno);
reset_reg_range_values(regs, regno);
+   reset_reg_align(regs, regno);
 }
 
 enum reg_arg_type {
@@ -770,13 +785,24 @@ static bool is_pointer_value(struct bpf_verifier_env 
*env, int regno)
 static int check_pkt_ptr_alignment(const struct bpf_reg_state *reg,
   int off, int size)
 {
-   if (reg->id && size != 1) {
-   verbose("Unknown alignment. Only byte-sized access allowed in 
packet access.\n");
-   return -EACCES;
+   int reg_off;
+
+

Re: bpf pointer alignment validation

[Alexei Starovoitov]

On Fri, May 05, 2017 at 10:47:09PM -0400, David Miller wrote:
> From: David Miller 
> Date: Fri, 05 May 2017 16:20:44 -0400 (EDT)
> 
> > Anyways, I'll play with this design and see what happens...
> > Feedback is of course welcome.
> 
> Here is a prototype that works for me with test_pkt_access.c,
> which otherwise won't load on sparc.

the approach looks good.

> +static u32 calc_align(u32 imm)
> +{
> + u32 align = 1;
> +
> + if (!imm)
> + return 1U << 31;
> +
> + while (!(imm & 1)) {
> + imm >>= 1;
> + align <<= 1;
> + }
> + return align;
> +}

who about
static u32 calc_align(u32 n)
{
if (!n)
return 1U << 31;
return n - ((n - 1) & n);
}
instead?

Re: bpf pointer alignment validation

[David Miller]

From: Daniel Borkmann 
Date: Mon, 08 May 2017 12:49:25 +0200

> On 05/06/2017 04:47 AM, David Miller wrote:
>> From: David Miller 
>> Date: Fri, 05 May 2017 16:20:44 -0400 (EDT)
>>
>>> Anyways, I'll play with this design and see what happens...
>>> Feedback is of course welcome.
>>
>> Here is a prototype that works for me with test_pkt_access.c,
>> which otherwise won't load on sparc.
> 
> Code looks good to me as far as I can tell, thanks for working
> on this.
> 
> Could you also add test cases specifically to this for test_verifier
> in bpf selftests? I'm thinking of the cases when we have no pkt id
> and offset originated from reg->off (accumulated through const imm
> ops on reg) and insn->off, where we had i) no pkt id and ii) a
> specific pkt id (so we can probe for aux_off_align rejection as well).
> I believe we do have coverage to some extend in some of the tests
> (more on the map_value_adj though), but it would be good to keep
> tracking this specifically as well.

Yes, I am working on also on special tests that parse the verifier
trace to make sure the alignment values were calculated properly.

Re: bpf pointer alignment validation

[Daniel Borkmann]

On 05/06/2017 04:47 AM, David Miller wrote:

From: David Miller 
Date: Fri, 05 May 2017 16:20:44 -0400 (EDT)


Anyways, I'll play with this design and see what happens...
Feedback is of course welcome.


Here is a prototype that works for me with test_pkt_access.c,
which otherwise won't load on sparc.


Code looks good to me as far as I can tell, thanks for working
on this.

Could you also add test cases specifically to this for test_verifier
in bpf selftests? I'm thinking of the cases when we have no pkt id
and offset originated from reg->off (accumulated through const imm
ops on reg) and insn->off, where we had i) no pkt id and ii) a
specific pkt id (so we can probe for aux_off_align rejection as well).
I believe we do have coverage to some extend in some of the tests
(more on the map_value_adj though), but it would be good to keep
tracking this specifically as well.

Thanks a lot,
Daniel

Re: bpf pointer alignment validation

[David Miller]

From: David Miller 
Date: Fri, 05 May 2017 16:20:44 -0400 (EDT)

> Anyways, I'll play with this design and see what happens...
> Feedback is of course welcome.

Here is a prototype that works for me with test_pkt_access.c,
which otherwise won't load on sparc.

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 5efb4db..5733308 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -40,6 +40,8 @@ struct bpf_reg_state {
 */
s64 min_value;
u64 max_value;
+   u32 min_align;
+   u32 aux_off_align;
 };
 
 enum bpf_stack_slot_type {
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index c2ff608..95f70d0 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -241,6 +241,10 @@ static void print_verifier_state(struct bpf_verifier_state 
*state)
if (reg->max_value != BPF_REGISTER_MAX_RANGE)
verbose(",max_value=%llu",
(unsigned long long)reg->max_value);
+   if (reg->min_align)
+   verbose(",min_align=%u", reg->min_align);
+   if (reg->aux_off_align)
+   verbose(",aux_off_align=%u", reg->aux_off_align);
}
for (i = 0; i < MAX_BPF_STACK; i += BPF_REG_SIZE) {
if (state->stack_slot_type[i] == STACK_SPILL)
@@ -455,6 +459,8 @@ static void init_reg_state(struct bpf_reg_state *regs)
regs[i].imm = 0;
regs[i].min_value = BPF_REGISTER_MIN_RANGE;
regs[i].max_value = BPF_REGISTER_MAX_RANGE;
+   regs[i].min_align = 0;
+   regs[i].aux_off_align = 0;
}
 
/* frame pointer */
@@ -483,11 +489,17 @@ static void reset_reg_range_values(struct bpf_reg_state 
*regs, u32 regno)
regs[regno].max_value = BPF_REGISTER_MAX_RANGE;
 }
 
+static void reset_reg_align(struct bpf_reg_state *regs, u32 regno)
+{
+   regs[regno].min_align = 0;
+}
+
 static void mark_reg_unknown_value_and_range(struct bpf_reg_state *regs,
 u32 regno)
 {
mark_reg_unknown_value(regs, regno);
reset_reg_range_values(regs, regno);
+   reset_reg_align(regs, regno);
 }
 
 enum reg_arg_type {
@@ -770,9 +782,16 @@ static bool is_pointer_value(struct bpf_verifier_env *env, 
int regno)
 static int check_pkt_ptr_alignment(const struct bpf_reg_state *reg,
   int off, int size)
 {
-   if (reg->id && size != 1) {
-   verbose("Unknown alignment. Only byte-sized access allowed in 
packet access.\n");
-   return -EACCES;
+   /* Byte size accesses are always allowed. */
+   if (size == 1)
+   return 0;
+
+   if (reg->id) {
+   if (reg->aux_off_align % size) {
+   verbose("Packet access is only %u byte aligned, %d byte 
access not allowed\n",
+   reg->aux_off_align, size);
+   return -EACCES;
+   }
}
 
/* skb->data is NET_IP_ALIGN-ed */
@@ -872,6 +891,7 @@ static int check_mem_access(struct bpf_verifier_env *env, 
u32 regno, int off,
 value_regno);
/* note that reg.[id|off|range] == 0 */
state->regs[value_regno].type = reg_type;
+   state->regs[value_regno].aux_off_align = 0;
}
 
} else if (reg->type == FRAME_PTR || reg->type == PTR_TO_STACK) {
@@ -1444,6 +1464,8 @@ static int check_packet_ptr_add(struct bpf_verifier_env 
*env,
 */
dst_reg->off += imm;
} else {
+   bool had_id;
+
if (src_reg->type == PTR_TO_PACKET) {
/* R6=pkt(id=0,off=0,r=62) R7=imm22; r7 += r6 */
tmp_reg = *dst_reg;  /* save r7 state */
@@ -1477,14 +1499,22 @@ static int check_packet_ptr_add(struct bpf_verifier_env 
*env,
src_reg->imm);
return -EACCES;
}
+
+   had_id = (dst_reg->id != 0);
+
/* dst_reg stays as pkt_ptr type and since some positive
 * integer value was added to the pointer, increment its 'id'
 */
dst_reg->id = ++env->id_gen;
 
-   /* something was added to pkt_ptr, set range and off to zero */
+   /* something was added to pkt_ptr, set range to zero */
dst_reg->off = 0;
dst_reg->range = 0;
+   if (had_id)
+   dst_reg->aux_off_align = min(dst_reg->aux_off_align,
+src_reg->min_align);
+   else
+   dst_reg->aux_off_align = src_reg->min_align;
}
return 0;
 }
@@ -1658,6 +1688,20 @@