[iovisor-dev] [PATCH v2 net-next 2/5] bpf/verifier: when pruning a branch, ignore its write marks

The fact that writes occurred in reaching the continuation state does not screen off its reads from us, because we're not really its parent. So detect 'not really the parent' in do_propagate_liveness, and ignore write marks in that case. Fixes: dc503a8ad984 ("bpf/verifier: track liveness for

[iovisor-dev] [PATCH v2 net-next 4/5] bpf/verifier: remove varlen_map_value_access flag

The optimisation it does is broken when the 'new' register value has a variable offset and the 'old' was constant. I broke it with my pointer types unification (see Fixes tag below), before which the 'new' value would have type PTR_TO_MAP_VALUE_ADJ and would thus not compare equal; other

[iovisor-dev] [PATCH v2 net-next 1/5] selftests/bpf: add a test for a bug in liveness-based pruning

Writes in straight-line code should not prevent reads from propagating along jumps. With current verifier code, the jump from 3 to 5 does not add a read mark on 3:R0 (because 5:R0 has a write mark), meaning that the jump from 1 to 3 gets pruned as safe even though R0 is NOT_INIT. Verifier

[iovisor-dev] [PATCH v2 net-next 3/5] selftests/bpf: add a test for a pruning bug in the verifier

From: Alexei Starovoitov The test makes a read through a map value pointer, then considers pruning a branch where the register holds an adjusted map value pointer. It should not prune, but currently it does. Signed-off-by: Alexei Starovoitov [ec...@solarflare.com:

[iovisor-dev] [PATCH v2 net-next 0/5] bpf: verifier fixes

Fix a couple of bugs introduced in my recent verifier patches. Patch #2 does slightly increase the insn count on bpf_lxc.o, but only by about a hundred insns (i.e. 0.2%). v2: added test for write-marks bug (patch #1); reworded comment on propagate_liveness() for clarity. Alexei Starovoitov

Re: [iovisor-dev] [PATCH net-next 3/4] bpf/verifier: when pruning a branch, ignore its write marks

On 22/08/17 16:50, Edward Cree wrote: > On 22/08/17 16:24, Alexei Starovoitov wrote: >> Do you have a test case for this by any chance? > I think something like > if (cond) > r0=0; > if (cond) > r0=0; > return r0; > might tickle the bug, but I'm not sure. It turns out

Re: [iovisor-dev] [PATCH net-next 4/4] bpf/verifier: document liveness analysis

On 22/08/17 16:42, Alexei Starovoitov wrote: > On 8/22/17 6:27 AM, Edward Cree wrote: >> static bool do_propagate_liveness(const struct bpf_verifier_state *state, >>struct bpf_verifier_state *parent) >> { >> @@ -3457,6 +3463,15 @@ static bool do_propagate_liveness(const

[iovisor-dev] [PATCH net-next 1/4] selftests/bpf: add a test for a pruning bug in the verifier

From: Alexei Starovoitov The test makes a read through a map value pointer, then considers pruning a branch where the register holds an adjusted map value pointer. It should not prune, but currently it does. Signed-off-by: Alexei Starovoitov [ec...@solarflare.com:

Re: [iovisor-dev] [PATCH v3 net-next] bpf/verifier: track liveness for pruning

On 18/08/17 15:16, Edward Cree wrote: > On 18/08/17 04:21, Alexei Starovoitov wrote: >> It seems you're trying to sort-of do per-fake-basic block liveness >> analysis, but our state_list_marks are not correct if we go with >> canonical basic block definition, since we mark the jump insn and >> not

Re: [iovisor-dev] [PATCH v3 net-next] bpf/verifier: track liveness for pruning

On 19/08/17 00:37, Alexei Starovoitov wrote: > that '14: safe' above is not correct. > > Disabling liveness as: > @@ -3282,7 +3288,7 @@ static bool regsafe(struct bpf_reg_state *rold, > struct bpf_reg_state *rcur, > bool varlen_map_access, struct idpair

Re: [iovisor-dev] [PATCH v3 net-next] bpf/verifier: track liveness for pruning

On 18/08/17 04:21, Alexei Starovoitov wrote: > On 8/15/17 12:34 PM, Edward Cree wrote: >> State of a register doesn't matter if it wasn't read in reaching an exit; >> a write screens off all reads downstream of it from all explored_states >> upstream of it. >> This allows us to prune many more

[iovisor-dev] [PATCH v5 net-next 12/12] bpf/verifier: increase complexity limit to 128k

The more detailed value tracking can reduce the effectiveness of pruning for some programs. So, to avoid rejecting previously valid programs, up the limit to 128kinsns. Hopefully we will be able to bring this back down later by improving pruning performance. Signed-off-by: Edward Cree

[iovisor-dev] [PATCH v5 net-next 09/12] selftests/bpf: add tests for subtraction & negative numbers

Signed-off-by: Edward Cree --- tools/testing/selftests/bpf/test_align.c | 104 +++ 1 file changed, 104 insertions(+) diff --git a/tools/testing/selftests/bpf/test_align.c b/tools/testing/selftests/bpf/test_align.c index b081683..8591c89 100644

[iovisor-dev] [PATCH v5 net-next 11/12] Documentation: describe the new eBPF verifier value tracking behaviour

Also bring the eBPF documentation up to date in other ways. Signed-off-by: Edward Cree --- Documentation/networking/filter.txt | 122 ++-- 1 file changed, 104 insertions(+), 18 deletions(-) diff --git a/Documentation/networking/filter.txt

[iovisor-dev] [PATCH v5 net-next 10/12] selftests/bpf: variable offset negative tests

Variable ctx accesses and stack accesses aren't allowed, because we can't determine what type of value will be read. Signed-off-by: Edward Cree --- tools/testing/selftests/bpf/test_verifier.c | 41 + 1 file changed, 41 insertions(+) diff --git

[iovisor-dev] [PATCH v5 net-next 08/12] selftests/bpf: don't try to access past MAX_PACKET_OFF in test_verifier

A number of selftests fell foul of the changed MAX_PACKET_OFF handling. For instance, "direct packet access: test2" was potentially reading four bytes from pkt + 0x, which could take it past the verifier's limit, causing the program to be rejected (checks against pkt_end didn't give us any

[iovisor-dev] [PATCH v5 net-next 04/12] selftests/bpf: change test_verifier expectations

Some of the verifier's error messages have changed, and some constructs that previously couldn't be verified are now accepted. Signed-off-by: Edward Cree --- tools/testing/selftests/bpf/test_verifier.c | 332 +--- 1 file changed, 152 insertions(+),

[iovisor-dev] [PATCH v5 net-next 03/12] bpf/verifier: more concise register state logs for constant var_off

Signed-off-by: Edward Cree --- kernel/bpf/verifier.c | 46 +++--- 1 file changed, 27 insertions(+), 19 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 7557800..08a6fa0 100644 --- a/kernel/bpf/verifier.c

[iovisor-dev] [PATCH v5 net-next 01/12] bpf/verifier: rework value tracking

Unifies adjusted and unadjusted register value types (e.g. FRAME_POINTER is now just a PTR_TO_STACK with zero offset). Tracks value alignment by means of tracking known & unknown bits. This also replaces the 'reg->imm' (leading zero bits) calculations for (what were) UNKNOWN_VALUEs. If pointer

[iovisor-dev] [PATCH v5 net-next 00/12] bpf: rewrite value tracking in verifier

This series simplifies alignment tracking, generalises bounds tracking and fixes some bounds-tracking bugs in the BPF verifier. Pointer arithmetic on packet pointers, stack pointers, map value pointers and context pointers has been unified, and bounds on these pointers are only checked when

Re: [iovisor-dev] [PATCH v4 net-next 01/13] bpf/verifier: rework value tracking

On 07/08/17 00:35, Daniel Borkmann wrote: > On 08/03/2017 06:11 PM, Edward Cree wrote: >> Unifies adjusted and unadjusted register value types (e.g. FRAME_POINTER is >> now just a PTR_TO_STACK with zero offset). >> Tracks value alignment by means of tracking known & unknown bits. This >> also

[iovisor-dev] [PATCH v4 net-next 12/13] Documentation: describe the new eBPF verifier value tracking behaviour

Also bring the eBPF documentation up to date in other ways. Signed-off-by: Edward Cree --- Documentation/networking/filter.txt | 122 ++-- 1 file changed, 104 insertions(+), 18 deletions(-) diff --git a/Documentation/networking/filter.txt

[iovisor-dev] [PATCH v4 net-next 10/13] selftests/bpf: add tests for subtraction & negative numbers

Signed-off-by: Edward Cree --- tools/testing/selftests/bpf/test_align.c | 104 +++ 1 file changed, 104 insertions(+) diff --git a/tools/testing/selftests/bpf/test_align.c b/tools/testing/selftests/bpf/test_align.c index b081683..8591c89 100644

[iovisor-dev] [PATCH v4 net-next 09/13] selftests/bpf: don't try to access past MAX_PACKET_OFF in test_verifier

A number of selftests fell foul of the changed MAX_PACKET_OFF handling. For instance, "direct packet access: test2" was potentially reading four bytes from pkt + 0x, which could take it past the verifier's limit, causing the program to be rejected (checks against pkt_end didn't give us any

[iovisor-dev] [PATCH v4 net-next 08/13] selftests/bpf: add test for bogus operations on pointers

Tests non-add/sub operations (AND, LSH) on pointers decaying them to unknown scalars. Also tests that a pkt_ptr add which could potentially overflow is rejected (find_good_pkt_pointers ignores it and doesn't give us any reg->range). Signed-off-by: Edward Cree ---

[iovisor-dev] [PATCH v4 net-next 06/13] selftests/bpf: rewrite test_align

Expectations have changed, as has the format of the logged state. To make the tests easier to read, add a line-matching framework so that each match need only quote the register it cares about. (Multiple matches may refer to the same line, but matches must be listed in order of increasing

[iovisor-dev] [PATCH v4 net-next 05/13] selftests/bpf: change test_verifier expectations

Some of the verifier's error messages have changed, and some constructs that previously couldn't be verified are now accepted. Signed-off-by: Edward Cree --- tools/testing/selftests/bpf/test_verifier.c | 332 +--- 1 file changed, 152 insertions(+),

[iovisor-dev] [PATCH v4 net-next 03/13] bpf/verifier: track signed and unsigned min/max values

Allows us to, sometimes, combine information from a signed check of one bound and an unsigned check of the other. We now track the full range of possible values, rather than restricting ourselves to [0, 1<<30) and considering anything beyond that as unknown. While this is probably not

[iovisor-dev] [PATCH v4 net-next 04/13] bpf/verifier: more concise register state logs for constant var_off

Signed-off-by: Edward Cree --- kernel/bpf/verifier.c | 46 +++--- 1 file changed, 27 insertions(+), 19 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index ca14f59..2924b01 100644 --- a/kernel/bpf/verifier.c

[iovisor-dev] [PATCH v4 net-next 01/13] bpf/verifier: rework value tracking

Unifies adjusted and unadjusted register value types (e.g. FRAME_POINTER is now just a PTR_TO_STACK with zero offset). Tracks value alignment by means of tracking known & unknown bits. This also replaces the 'reg->imm' (leading zero bits) calculations for (what were) UNKNOWN_VALUEs. If pointer

[iovisor-dev] [PATCH v4 net-next 02/13] nfp: change bpf verifier hooks to match new verifier data structures

Signed-off-by: Edward Cree --- drivers/net/ethernet/netronome/nfp/bpf/verifier.c | 24 +-- kernel/bpf/tnum.c | 1 + 2 files changed, 15 insertions(+), 10 deletions(-) diff --git

[iovisor-dev] [PATCH v4 net-next 00/13] bpf: rewrite value tracking in verifier

This series simplifies alignment tracking, generalises bounds tracking and fixes some bounds-tracking bugs in the BPF verifier. Pointer arithmetic on packet pointers, stack pointers, map value pointers and context pointers has been unified, and bounds on these pointers are only checked when

Re: [iovisor-dev] [PATCH v3 net-next 02/12] bpf/verifier: rework value tracking

On 12/07/17 23:07, Nadav Amit wrote: > Edward Cree wrote: >> In this specific case, there was a bug before: if (say) src and dst were >> both unknown bytes (so range 0 to 255), it would compute the new min and max >> to be 0, so it would think the result is known to be 0.

Re: [iovisor-dev] [PATCH v3 net-next 02/12] bpf/verifier: rework value tracking

On 07/07/17 18:45, Nadav Amit wrote: > For me changes such as: > >> if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE) >> -dst_reg->min_value -= min_val; >> +dst_reg->min_value -= max_val; > > are purely cryptic. What happened here? Was there a

Re: [iovisor-dev] [PATCH v3 net-next 02/12] bpf/verifier: rework value tracking

On 06/07/17 22:21, Nadav Amit wrote: > I find it a bit surprising that such huge changes that can affect security > and robustness are performed in one patch. In the first version of the series, this was two patches, with "feed pointer-to-unknown-scalar casts into scalar ALU path" split out from

Re: [iovisor-dev] [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier

On 07/07/17 10:14, Daniel Borkmann wrote: > But this means the bpf_lxc_* cases increase quite significantly, > arguably one of them is pretty close already, but the other one not > so much, meaning while 142k would shoot over the 128k target quite a > bit, the 95k is quite close to the point that

Re: [iovisor-dev] [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier

On 04/07/17 23:28, Daniel Borkmann wrote: > Have you tried with cilium's BPF code? The kernel selftests are quite small, > so not really pushing processed insns too far. I can send you a BPF obj file > if that's easier for testing. Results from the next (in-progress) version of the patch series,

Re: [iovisor-dev] [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier

On 04/07/17 20:22, Edward Cree wrote: > I don't know why test_l4lb has to process _fewer_ insns with my patches; > if anything I'm worrying that I may be incorrectly pruning branches. > (I've spotted a possible bug in that I'm not looking at 'id' which, > although it doesn't have to match, if

[iovisor-dev] [TEST PATCH] bpf/verifier: roll back ptr handling, and fix signed bounds

I'm far from sure that my adjust_reg_min_max_vals() code remains correct in the face of maybe-signed-maybe-not bounds, even with the checks I've added in. So this probably has security leaks in it; but it should suffice for measuring the effect on pruning. The treat_as_signed part is loosely

Re: [iovisor-dev] [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier

On 28/06/17 22:37, Alexei Starovoitov wrote: > Increasing the limit is must have, since pruning suffered so much. > Going from 53k to 76k is pretty substantial. > What is the % increase for tests in selftests/ ? When I tried to measure the test_verifier tests, they changed hardly at all, only a

[iovisor-dev] [PATCH v3 net-next 10/12] selftests/bpf: don't try to access past MAX_PACKET_OFF in test_verifier

"direct packet access: test2" was potentially reading four bytes from pkt + 0x, which could take it past the verifier's limit, causing the program to be rejected. Increase the shifts by one so that R2 is now mask 0x7fff instead of mask 0x. Signed-off-by: Edward Cree

[iovisor-dev] [PATCH v3 net-next 08/12] selftests/bpf: add a test to test_align

New test adds 14 to the unknown value before adding to the packet pointer, meaning there's no 'fixed offset' field and instead we add into the var_off, yielding a '4n+2' value. Signed-off-by: Edward Cree --- tools/testing/selftests/bpf/test_align.c | 67

[iovisor-dev] [PATCH v3 net-next 07/12] selftests/bpf: rewrite test_align

Expectations have changed, as has the format of the logged state. To make the tests easier to read, add a line-matching framework so that each match need only quote the register it cares about. (Multiple matches may refer to the same line, but matches must be listed in order of increasing

[iovisor-dev] [PATCH v3 net-next 06/12] selftests/bpf: change test_verifier expectations

Some of the verifier's error messages have changed, and some constructs that previously couldn't be verified are now accepted. Signed-off-by: Edward Cree --- tools/testing/selftests/bpf/test_verifier.c | 226 ++-- 1 file changed, 116 insertions(+),

[iovisor-dev] [PATCH v3 net-next 05/12] bpf/verifier: more concise register state logs for constant var_off

Signed-off-by: Edward Cree --- kernel/bpf/verifier.c | 46 +++--- 1 file changed, 27 insertions(+), 19 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index d45c1d1..3e1df75 100644 --- a/kernel/bpf/verifier.c

[iovisor-dev] [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier

This series simplifies alignment tracking, generalises bounds tracking and fixes some bounds-tracking bugs in the BPF verifier. Pointer arithmetic on packet pointers, stack pointers, map value pointers and context pointers has been unified, and bounds on these pointers are only checked when

[iovisor-dev] [RFC PATCH v2 net-next 08/10] selftests/bpf: add a test to test_align

New test adds 14 to the unknown value before adding to the packet pointer, meaning there's no 'fixed offset' field and instead we add into the var_off, yielding a '4n+2' value. Signed-off-by: Edward Cree --- tools/testing/selftests/bpf/test_align.c | 67

[iovisor-dev] [RFC PATCH v2 net-next 01/10] selftests/bpf: add test for mixed signed and unsigned bounds checks

Currently fails due to bug in verifier bounds handling. Signed-off-by: Edward Cree --- tools/testing/selftests/bpf/test_verifier.c | 26 ++ 1 file changed, 26 insertions(+) diff --git a/tools/testing/selftests/bpf/test_verifier.c

Re: [iovisor-dev] More BPF verifier questions

On 05/06/17 08:06, Y Song wrote: > On Fri, Jun 2, 2017 at 7:42 AM, Edward Cree wrote: >> Test "helper access to variable memory: stack, bitwise AND + JMP, correct >> bounds" is listed as expected to pass, but it passes zero in the 'size' >> argument, an ARG_CONST_SIZE, to

Re: [iovisor-dev] More BPF verifier questions

On 05/06/17 19:47, Josef Bacik wrote: > On Mon, Jun 05, 2017 at 11:11:05AM -0700, Alexei Starovoitov wrote: >> Do you have an asm test case that demonstrates that? > From here we want to exploit the fact that false_reg->min_value is not > necessarily correct, but in order to do that we need to get