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

[Edward Cree via iovisor-dev]

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.  But that's wrong,
>> because it could be anything from -255 to +255.  The bug's implications are
>> that it could be used to construct an out-of-range offset to (say) a map
>> pointer which the verifier would think was in-range and thus accept.
> This sounds like a serious bug that may need to be backported to stable
> versions, no? In this case I would assume it should be in a separate patch
> so it could be applied separately.
Having looked deeper into this in attempting to create a test that the existing
 verifier would fail, it turns out that in the existing verifier that BPF_SUB
 handling is dead code.  If (for instance) we subtract an UNKNOWN_VALUE from a
 PTR_TO_MAP_VALUE_ADJ, that code will be run, but afterwards we will
 mark_reg_unknown_value() the register (bottom of check_alu_op()) making our
 previous min/max determination irrelevant.
So there's nothing to backport, and if I did change this in its own patch,
 there'd be no way to test it.  (I have, however, added a test covering this
 codepath in the new verifier.)

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

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

[Nadav Amit via iovisor-dev]

Edward Cree  wrote:

> 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 bug before and if so
>> what are its implications? Why can’t it be in a separate patch?
> 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.  But that's wrong,
> because it could be anything from -255 to +255.  The bug's implications are
> that it could be used to construct an out-of-range offset to (say) a map
> pointer which the verifier would think was in-range and thus accept.

This sounds like a serious bug that may need to be backported to stable
versions, no? In this case I would assume it should be in a separate patch
so it could be applied separately.

> It might be possible to put it in a separate patch, but in general (not
> necessarily the case here) isolated fixes to range handling break some of
> the existing regression tests.  That is why I ended up doing patch #4,
> because I couldn't find a small fix for the patch #1 test without breaking
> others.  Essentially, this patch started out as just the tnum tracking to
> replace imm and align, and then rolled in everything I had to do to get the
> regression tests to pass again.  So some of those things are fixes that
> could go in earlier patches, but because of the order I wrote it in I'd have
> to disentangle them.  I can do that if it's necessary, but I'm not sure it'd
> really make the patch that much more readable so I'd rather avoid that work
> if I can get away with it…

I clearly understand and can relate to it. Still, your patch really stands
out:

git log --stat kernel/bpf/ | grep -G '^ kernel/bpf' | tr -s " " \
>  | sort -g -r  -k 3 | head -n 10

 kernel/bpf/verifier.c | 1075 -
 kernel/bpf/bpf_lru_list.c | 567 ++
 kernel/bpf/core.c | 536 
 kernel/bpf/lpm_trie.c | 503 ++
 kernel/bpf/verifier.c | 441 +-
 kernel/bpf/inode.c | 387 +++
 kernel/bpf/hashtab.c | 362 +++
 kernel/bpf/verifier.c | 329 +++---
 kernel/bpf/hashtab.c | 275 ++-
 kernel/bpf/verifier.c | 266 +++---

>> I also think that changes such as:
>>> -   s64 min_value;
>>> -   u64 max_value;
>> [snip]
>>> +   s64 min_value; /* minimum possible (s64)value */
>>> +   u64 max_value; /* maximum possible (u64)value */
>> Should have been avoided. Personally, I find this comment redundant (to say
>> the least). It does not help to reduce the diff size.
> The comment is meaningful, though perhaps badly phrased.  It's an attempt to
> define the semantics of these fields (which previously was unclear); e.g. the
> first one means "minimum value when interpreted as signed", i.e. the (s64) in
> the comment is a cast.
> Apparently those weren't the semantics the original author intended, but I'm
> not sure the original semantics were well-defined and I certainly don't
> understand them well enough to define them, hence why I defined my own here
> (and then redefined them in patch #4).

Makes more sense now.

>> In this regard, I think that refactoring should have been done first and not
>> together with the logic changes. As another example, changing UNKNOWN_VALUE
>> to SCALAR_VALUE should have been a separate, easy to understand patch.
> But SCALAR_VALUE is the union UNKNOWN_VALUE *or* CONST_IMM, and merging those
> together means all of the ripping-out of evaluate_reg_alu() and friends and
> thus depends on much of the rest of the patch.
>>> The latter is also needed for correctness in computing reg->range;
>>> if 'pkt_ptr + offset' could conceivably overflow, then the result
>>> could be < pkt_end without being a valid pointer into the packet.
>>> We thus rely on the assumption that the packet pointer will never be
>>> within MAX_PACKET_OFF of the top of the address space.  (This
>>> assumption is, again, carried over from the existing verifier.)
>> I understand the limitations (I think). I agree that CONST being spillable
>> is not directly related. As for the possible packet offsets/range:
>> intentionally or not you do make some changes that push the 64k packet size
>> limit even deeper into the code. While the packet size should be limited to
>> avoid overflow, IIUC the requirement is that:
>> 
>>  64 > log(n_insn) + 

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

[Edward Cree via iovisor-dev]

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 bug before and if so
> what are its implications? Why can’t it be in a separate patch?
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.  But that's wrong,
 because it could be anything from -255 to +255.  The bug's implications are
 that it could be used to construct an out-of-range offset to (say) a map
 pointer which the verifier would think was in-range and thus accept.
It might be possible to put it in a separate patch, but in general (not
 necessarily the case here) isolated fixes to range handling break some of
 the existing regression tests.  That is why I ended up doing patch #4,
 because I couldn't find a small fix for the patch #1 test without breaking
 others.  Essentially, this patch started out as just the tnum tracking to
 replace imm and align, and then rolled in everything I had to do to get the
 regression tests to pass again.  So some of those things are fixes that
 could go in earlier patches, but because of the order I wrote it in I'd have
 to disentangle them.  I can do that if it's necessary, but I'm not sure it'd
 really make the patch that much more readable so I'd rather avoid that work
 if I can get away with it...
> I also think that changes such as:
>> -s64 min_value;
>> -u64 max_value;
> [snip]
>> +s64 min_value; /* minimum possible (s64)value */
>> +u64 max_value; /* maximum possible (u64)value */
> Should have been avoided. Personally, I find this comment redundant (to say
> the least). It does not help to reduce the diff size.
The comment is meaningful, though perhaps badly phrased.  It's an attempt to
 define the semantics of these fields (which previously was unclear); e.g. the
 first one means "minimum value when interpreted as signed", i.e. the (s64) in
 the comment is a cast.
Apparently those weren't the semantics the original author intended, but I'm
 not sure the original semantics were well-defined and I certainly don't
 understand them well enough to define them, hence why I defined my own here
 (and then redefined them in patch #4).
> In this regard, I think that refactoring should have been done first and not
> together with the logic changes. As another example, changing UNKNOWN_VALUE
> to SCALAR_VALUE should have been a separate, easy to understand patch.
But SCALAR_VALUE is the union UNKNOWN_VALUE *or* CONST_IMM, and merging those
 together means all of the ripping-out of evaluate_reg_alu() and friends and
 thus depends on much of the rest of the patch.
>> The latter is also needed for correctness in computing reg->range;
>> if 'pkt_ptr + offset' could conceivably overflow, then the result
>> could be < pkt_end without being a valid pointer into the packet.
>> We thus rely on the assumption that the packet pointer will never be
>> within MAX_PACKET_OFF of the top of the address space.  (This
>> assumption is, again, carried over from the existing verifier.)
> I understand the limitations (I think). I agree that CONST being spillable
> is not directly related. As for the possible packet offsets/range:
> intentionally or not you do make some changes that push the 64k packet size
> limit even deeper into the code. While the packet size should be limited to
> avoid overflow, IIUC the requirement is that:
>
>   64 > log(n_insn) + log(MAX_PACKET_OFF) + 1
I don't think that's right, unless you also make each addition to a packet-
 pointer require a max_value <= MAX_PACKET_OFF.  It's also a very loose bound
 because it assumes every instruction is such an add.
I think it makes far more sense to do it the way I have done, where the bounds
 are tracked all the way through the arithmetic and then only checked against
 MAX_PACKET_OFF when doing the access (and when doing a test against a
 PTR_TO_PACKET_END, i.e. find_good_pkt_pointers(), though for some reason I
 only added that check in patch #4).
That way we can allow things like (for the sake of example) adding $BIG_NUMBER
 to a packet pointer and then subtracting it again.
> Such an assertion may be staticly checked (using BUILD_BUG_ON), but I don’t
> think should propagate into the entire code, especially in a non consistent
> way. For example:
>
>> struct bpf_reg_state {
>>  enum bpf_reg_type type;
>>  union {
>> -/* valid when type == CONST_IMM | PTR_TO_STACK | UNKNOWN_VALUE 
>> */
>> -s64 imm;
>> -
>> -/* valid when type == PTR_TO_PACKET* */
>> -struct {
>> -u16 off;
>> -u16 range;
>> -};
>> +/* valid when type == PTR_TO_PACKET 

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

[Nadav Amit via iovisor-dev]

Nadav Amit  wrote:

> Edward Cree  wrote:
> 
>> 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 the 
>> rest;
>> but that just caused a lot of code movement and confusing diffs, hence why I
>> folded it into the same patch.
>> As for the rest of it, I'm not sure it can be split up: I'm changing the
>> definition and semantics of a core data structure (struct bpf_reg_state)
>> and I don't see any reasonable intermediate steps that would even compile.
>> For instance, replacing reg->imm (with its two meanings of 'known value' or
>> 'number of leading zero bits') with reg->var_off necessitates replacing all
>> the arithmetic-handling code (e.g. evaluate_reg_imm_alu()).  But then
>> var_off also replaces reg->aux_align[_off], so all the alignment-checking
>> code has to change as well.  And changing what register state we track
>> means that the pruning code (states_equal()) has to change too.
>> As it is, this patch leaves some selftests failing and it takes _another_
>> big patch (4/12 "track signed and unsigned min/max values") to get them
>> all to pass again.
> 
> Thanks for your polite response to my rantings. I do understand the
> complexity, and I did not like the two meanings of reg->imm either (it took
> me some time to understand them). Yet, I really doubt anyone is capable of
> really reviewing such a big patch. Most likely people will not even start or
> pick to small details they know or care about.
> 
>>> Personally, I cannot comprehend
>>> all of these changes. In addition, I think that it is valuable to describe
>>> in detail the bugs that the patch solves and when they were introduced.
>> Mostly this patch series isn't about fixing bugs (except those which were
>> exposed when the changes caused some selftests to fail).  Instead, it's a
>> combination of refactoring and unifying so that (for instance) the rules
>> for pointer arithmetic and alignment checking are as similar as possible
>> for all pointer types rather than having special-case rules for each type.
>> This allows many (correct) programs which the verifier will currently
>> reject, and makes the overall description of the verifier's rules much
>> shorter and simpler.  I have written a documentation patch explaining
>> these rules, which the next version of the patch series will include.
> 
> Ok. But I doubt it is as useful as commenting in the code or writing in the
> commit message what exactly is addressed by the patch. And documentation
> does not really help others to rebase their patches on top of yours.
> 
>> The diff _is_ hard to read, I accept that; I think `diff` was too eager to
>> interpolate and match single lines like '{' from completely unrelated
>> functions.  It might be easier to just try applying the patch to a tree
>> and then reading the result, rather than trying to interpret the diff.
> 
> I don’t know to review patches this way. Hopefully others do, but I doubt it.
> 
> 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 bug before and if so
> what are its implications? Why can’t it be in a separate patch?
> 
> I also think that changes such as:
>> -s64 min_value;
>> -u64 max_value;
> [snip]
>> +s64 min_value; /* minimum possible (s64)value */
>> +u64 max_value; /* maximum possible (u64)value */
> 
> Should have been avoided. Personally, I find this comment redundant (to say
> the least). It does not help to reduce the diff size.
> 
> In this regard, I think that refactoring should have been done first and not
> together with the logic changes. As another example, changing UNKNOWN_VALUE
> to SCALAR_VALUE should have been a separate, easy to understand patch.
> 
>>> I can bring up some concerns regarding inconsistencies in offset checks and
>>> size, not spilling SCALAR and my wish not to limit packet size. However,
>>> when the patch is that big, I think it is useless.
>> Please, do describe these concerns; what inconsistencies do you see?
>> The not spilling scalars, and the limit to packet size, are retained
>> from the existing code (is_spillable_regtype() and MAX_PACKET_OFF).
>> The latter is also needed for correctness in computing reg->range;
>> if 'pkt_ptr + offset' could conceivably overflow, then the result
>> could be < pkt_end without being a valid pointer into the packet.
>> We thus rely on the assumption that the packet pointer will never be
>> within MAX_PACKET_OFF of the top of the address space.  (This
>> assumption is, again, carried over from the existing verifier.)
> 
> I 

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

[Nadav Amit via iovisor-dev]

Edward Cree  wrote:

> 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 the rest;
> but that just caused a lot of code movement and confusing diffs, hence why I
> folded it into the same patch.
> As for the rest of it, I'm not sure it can be split up: I'm changing the
> definition and semantics of a core data structure (struct bpf_reg_state)
> and I don't see any reasonable intermediate steps that would even compile.
> For instance, replacing reg->imm (with its two meanings of 'known value' or
> 'number of leading zero bits') with reg->var_off necessitates replacing all
> the arithmetic-handling code (e.g. evaluate_reg_imm_alu()).  But then
> var_off also replaces reg->aux_align[_off], so all the alignment-checking
> code has to change as well.  And changing what register state we track
> means that the pruning code (states_equal()) has to change too.
> As it is, this patch leaves some selftests failing and it takes _another_
> big patch (4/12 "track signed and unsigned min/max values") to get them
> all to pass again.

Thanks for your polite response to my rantings. I do understand the
complexity, and I did not like the two meanings of reg->imm either (it took
me some time to understand them). Yet, I really doubt anyone is capable of
really reviewing such a big patch. Most likely people will not even start or
pick to small details they know or care about.

>> Personally, I cannot comprehend
>> all of these changes. In addition, I think that it is valuable to describe
>> in detail the bugs that the patch solves and when they were introduced.
> Mostly this patch series isn't about fixing bugs (except those which were
> exposed when the changes caused some selftests to fail).  Instead, it's a
> combination of refactoring and unifying so that (for instance) the rules
> for pointer arithmetic and alignment checking are as similar as possible
> for all pointer types rather than having special-case rules for each type.
> This allows many (correct) programs which the verifier will currently
> reject, and makes the overall description of the verifier's rules much
> shorter and simpler.  I have written a documentation patch explaining
> these rules, which the next version of the patch series will include.

Ok. But I doubt it is as useful as commenting in the code or writing in the
commit message what exactly is addressed by the patch. And documentation
does not really help others to rebase their patches on top of yours.

> The diff _is_ hard to read, I accept that; I think `diff` was too eager to
> interpolate and match single lines like '{' from completely unrelated
> functions.  It might be easier to just try applying the patch to a tree
> and then reading the result, rather than trying to interpret the diff.

I don’t know to review patches this way. Hopefully others do, but I doubt it.

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 bug before and if so
what are its implications? Why can’t it be in a separate patch?

I also think that changes such as:
> - s64 min_value;
> - u64 max_value;
[snip]
> + s64 min_value; /* minimum possible (s64)value */
> + u64 max_value; /* maximum possible (u64)value */

Should have been avoided. Personally, I find this comment redundant (to say
the least). It does not help to reduce the diff size.

In this regard, I think that refactoring should have been done first and not
together with the logic changes. As another example, changing UNKNOWN_VALUE
to SCALAR_VALUE should have been a separate, easy to understand patch.

>> I can bring up some concerns regarding inconsistencies in offset checks and
>> size, not spilling SCALAR and my wish not to limit packet size. However,
>> when the patch is that big, I think it is useless.
> Please, do describe these concerns; what inconsistencies do you see?
> The not spilling scalars, and the limit to packet size, are retained
> from the existing code (is_spillable_regtype() and MAX_PACKET_OFF).
> The latter is also needed for correctness in computing reg->range;
> if 'pkt_ptr + offset' could conceivably overflow, then the result
> could be < pkt_end without being a valid pointer into the packet.
> We thus rely on the assumption that the packet pointer will never be
> within MAX_PACKET_OFF of the top of the address space.  (This
> assumption is, again, carried over from the existing verifier.)

I understand the limitations (I think). I agree that CONST being spillable
is not directly related. As for the possible packet offsets/range:
intentionally or not 

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

[Edward Cree via iovisor-dev]

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 the rest;
 but that just caused a lot of code movement and confusing diffs, hence why I
 folded it into the same patch.
As for the rest of it, I'm not sure it can be split up: I'm changing the
 definition and semantics of a core data structure (struct bpf_reg_state)
 and I don't see any reasonable intermediate steps that would even compile.
For instance, replacing reg->imm (with its two meanings of 'known value' or
 'number of leading zero bits') with reg->var_off necessitates replacing all
 the arithmetic-handling code (e.g. evaluate_reg_imm_alu()).  But then
 var_off also replaces reg->aux_align[_off], so all the alignment-checking
 code has to change as well.  And changing what register state we track
 means that the pruning code (states_equal()) has to change too.
As it is, this patch leaves some selftests failing and it takes _another_
 big patch (4/12 "track signed and unsigned min/max values") to get them
 all to pass again.
> Personally, I cannot comprehend
> all of these changes. In addition, I think that it is valuable to describe
> in detail the bugs that the patch solves and when they were introduced.
Mostly this patch series isn't about fixing bugs (except those which were
 exposed when the changes caused some selftests to fail).  Instead, it's a
 combination of refactoring and unifying so that (for instance) the rules
 for pointer arithmetic and alignment checking are as similar as possible
 for all pointer types rather than having special-case rules for each type.
This allows many (correct) programs which the verifier will currently
 reject, and makes the overall description of the verifier's rules much
 shorter and simpler.  I have written a documentation patch explaining
 these rules, which the next version of the patch series will include.

The diff _is_ hard to read, I accept that; I think `diff` was too eager to
 interpolate and match single lines like '{' from completely unrelated
 functions.  It might be easier to just try applying the patch to a tree
 and then reading the result, rather than trying to interpret the diff.
> I can bring up some concerns regarding inconsistencies in offset checks and
> size, not spilling SCALAR and my wish not to limit packet size. However,
> when the patch is that big, I think it is useless.
Please, do describe these concerns; what inconsistencies do you see?
The not spilling scalars, and the limit to packet size, are retained
 from the existing code (is_spillable_regtype() and MAX_PACKET_OFF).
The latter is also needed for correctness in computing reg->range;
 if 'pkt_ptr + offset' could conceivably overflow, then the result
 could be < pkt_end without being a valid pointer into the packet.
We thus rely on the assumption that the packet pointer will never be
 within MAX_PACKET_OFF of the top of the address space.  (This
 assumption is, again, carried over from the existing verifier.)

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

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

[Nadav Amit via iovisor-dev]

Edward Cree via iovisor-dev  wrote:

> Tracks value alignment by means of tracking known & unknown bits.
> Tightens some min/max value checks and fixes a couple of bugs therein.
> If pointer leaks are allowed, and adjust_ptr_min_max_vals returns -EACCES,
> treat the pointer as an unknown scalar and try again, because we might be
> able to conclude something about the result (e.g. pointer & 0x40 is either
> 0 or 0x40).
> 
> Signed-off-by: Edward Cree 
> ---
> include/linux/bpf.h  |   34 +-
> include/linux/bpf_verifier.h |   40 +-
> include/linux/tnum.h |   79 ++
> kernel/bpf/Makefile  |2 +-
> kernel/bpf/tnum.c|  163 
> kernel/bpf/verifier.c| 1692 --
> 6 files changed, 1235 insertions(+), 775 deletions(-)

(RESEND)

I find it a bit surprising that such huge changes that can affect security
and robustness are performed in one patch. Personally, I cannot comprehend
all of these changes. In addition, I think that it is valuable to describe
in detail the bugs that the patch solves and when they were introduced.

I can bring up some concerns regarding inconsistencies in offset checks and
size, not spilling SCALAR and my wish not to limit packet size. However,
when the patch is that big, I think it is useless.

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

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

[Nadav Amit via iovisor-dev]

Edward Cree via iovisor-dev  wrote:

> Tracks value alignment by means of tracking known & unknown bits.
> Tightens some min/max value checks and fixes a couple of bugs therein.
> If pointer leaks are allowed, and adjust_ptr_min_max_vals returns -EACCES,
> treat the pointer as an unknown scalar and try again, because we might be
> able to conclude something about the result (e.g. pointer & 0x40 is either
> 0 or 0x40).
> 
> Signed-off-by: Edward Cree 
> ---
> include/linux/bpf.h  |   34 +-
> include/linux/bpf_verifier.h |   40 +-
> include/linux/tnum.h |   79 ++
> kernel/bpf/Makefile  |2 +-
> kernel/bpf/tnum.c|  163 
> kernel/bpf/verifier.c| 1692 --
> 6 files changed, 1235 insertions(+), 775 deletions(-)

I find it a bit surprising that such huge changes that can affect security
and robustness are performed in one patch. Personally, I cannot comprehend
all of these changes. In addition, I think that it is valuable to describe
in detail the bugs that the patch solves and when they were introduced.

I can bring up some concerns regarding inconsistencies in offset checks and
size, not spilling SCALAR and my wish not to limit packet size. However,
when the patch is that big, I think it is useless.

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

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

[kbuild test robot via iovisor-dev]

Hi Edward,

[auto build test ERROR on net-next/master]

url:
https://github.com/0day-ci/linux/commits/Edward-Cree/bpf-rewrite-value-tracking-in-verifier/20170629-012559
config: ia64-allmodconfig (attached as .config)
compiler: ia64-linux-gcc (GCC) 6.2.0
reproduce:
wget 
https://raw.githubusercontent.com/01org/lkp-tests/master/sbin/make.cross -O 
~/bin/make.cross
chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
make.cross ARCH=ia64 

Note: the 
linux-review/Edward-Cree/bpf-rewrite-value-tracking-in-verifier/20170629-012559 
HEAD 7a882286a655cc99ca765008aa3f830f6ad6b3eb builds fine.
  It only hurts bisectibility.

All errors (new ones prefixed by >>):

   drivers/net//ethernet/netronome/nfp/bpf/verifier.c: In function 
'nfp_bpf_check_exit':
>> drivers/net//ethernet/netronome/nfp/bpf/verifier.c:86:20: error: 'CONST_IMM' 
>> undeclared (first use in this function)
 if (reg0->type != CONST_IMM) {
   ^
   drivers/net//ethernet/netronome/nfp/bpf/verifier.c:86:20: note: each 
undeclared identifier is reported only once for each function it appears in
   In file included from include/linux/kernel.h:13:0,
from include/linux/list.h:8,
from include/linux/timer.h:4,
from include/linux/workqueue.h:8,
from include/linux/bpf.h:12,
from drivers/net//ethernet/netronome/nfp/bpf/verifier.c:36:
>> drivers/net//ethernet/netronome/nfp/bpf/verifier.c:88:20: error: 'const 
>> struct bpf_reg_state' has no member named 'imm'
   reg0->type, reg0->imm);
   ^
   include/linux/printk.h:308:34: note: in definition of macro 'pr_info'
 printk(KERN_INFO pr_fmt(fmt), ##__VA_ARGS__)
 ^~~
   drivers/net//ethernet/netronome/nfp/bpf/verifier.c:93:10: error: 'const 
struct bpf_reg_state' has no member named 'imm'
 reg0->imm != 0 && (reg0->imm & ~0U) != ~0U) {
 ^~
   drivers/net//ethernet/netronome/nfp/bpf/verifier.c:93:29: error: 'const 
struct bpf_reg_state' has no member named 'imm'
 reg0->imm != 0 && (reg0->imm & ~0U) != ~0U) {
^~
   In file included from include/linux/kernel.h:13:0,
from include/linux/list.h:8,
from include/linux/timer.h:4,
from include/linux/workqueue.h:8,
from include/linux/bpf.h:12,
from drivers/net//ethernet/netronome/nfp/bpf/verifier.c:36:
   drivers/net//ethernet/netronome/nfp/bpf/verifier.c:95:20: error: 'const 
struct bpf_reg_state' has no member named 'imm'
   reg0->type, reg0->imm);
   ^
   include/linux/printk.h:308:34: note: in definition of macro 'pr_info'
 printk(KERN_INFO pr_fmt(fmt), ##__VA_ARGS__)
 ^~~
   drivers/net//ethernet/netronome/nfp/bpf/verifier.c:99:44: error: 'const 
struct bpf_reg_state' has no member named 'imm'
 if (nfp_prog->act == NN_ACT_DIRECT && reg0->imm <= TC_ACT_REDIRECT &&
   ^~
   drivers/net//ethernet/netronome/nfp/bpf/verifier.c:100:10: error: 'const 
struct bpf_reg_state' has no member named 'imm'
 reg0->imm != TC_ACT_SHOT && reg0->imm != TC_ACT_STOLEN &&
 ^~
   drivers/net//ethernet/netronome/nfp/bpf/verifier.c:100:38: error: 'const 
struct bpf_reg_state' has no member named 'imm'
 reg0->imm != TC_ACT_SHOT && reg0->imm != TC_ACT_STOLEN &&
 ^~
   drivers/net//ethernet/netronome/nfp/bpf/verifier.c:101:10: error: 'const 
struct bpf_reg_state' has no member named 'imm'
 reg0->imm != TC_ACT_QUEUED) {
 ^~
   In file included from include/linux/kernel.h:13:0,
from include/linux/list.h:8,
from include/linux/timer.h:4,
from include/linux/workqueue.h:8,
from include/linux/bpf.h:12,
from drivers/net//ethernet/netronome/nfp/bpf/verifier.c:36:
   drivers/net//ethernet/netronome/nfp/bpf/verifier.c:103:20: error: 'const 
struct bpf_reg_state' has no member named 'imm'
   reg0->type, reg0->imm);
   ^
   include/linux/printk.h:308:34: note: in definition of macro 'pr_info'
 printk(KERN_INFO pr_fmt(fmt), ##__VA_ARGS__)
 ^~~

vim +/CONST_IMM +86 drivers/net//ethernet/netronome/nfp/bpf/verifier.c

cd7df56e drivers/net/ethernet/netronome/nfp/nfp_bpf_verifier.c Jakub Kicinski 
2016-09-21  80  {
cd7df56e drivers/net/ethernet/netronome/nfp/nfp_bpf_verifier.c Jakub Kicinski 
2016-09-21  81const struct bpf_reg_state *reg0 = >cur_state.regs[0];
cd7df56e drivers/net/ethernet/netronome/nfp/nfp_bpf_verifier.c Jakub Kicinski 
2016-09-21  82  
6d677075 drivers/net/ethernet/netronome/nfp/nfp_bpf_verifier.c Jakub 

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

[Daniel Borkmann via iovisor-dev]

On 06/28/2017 06:07 PM, Edward Cree wrote:

On 28/06/17 16:15, Daniel Borkmann wrote:

On 06/27/2017 02:56 PM, Edward Cree wrote:

Tracks value alignment by means of tracking known & unknown bits.
Tightens some min/max value checks and fixes a couple of bugs therein.


You mean the one in relation to patch 1/12? Would be good to elaborate
here since otherwise this gets forgotten few weeks later.

That wasn't the only one; there were also some in the new min/max value
  calculation for ALU ops.  For instance, in subtraction we were taking
  the new bounds as [min-min, max-max] instead of [min-max, max-min].
I can't remember what else there was and there might also have been some
  that I missed but that got incidentally fixed by the rewrite.  But I
  guess I should change "checks" to "checks and updates" in the above?


Ok. Would be good though to have them all covered in the selftests
part of your series if possible, so we can make sure to keep track
of these cases.


Could you also document all the changes that verifier will then start
allowing for after the patch?

Maybe not the changes, because the old verifier had a lot of special
  cases, but I could, and probably should, document the new behaviour
  (maybe in Documentation/networking/filter.txt, that already has a bit
  of description of the verifier).


Yeah, that would definitely help; filter.txt should be fine.


[...]

   /* check whether memory at (regno + off) is accessible for t = (read | write)
@@ -899,52 +965,79 @@ static int check_mem_access(struct bpf_verifier_env *env, 
int insn_idx, u32 regn
   struct bpf_reg_state *reg = >regs[regno];
   int size, err = 0;

-if (reg->type == PTR_TO_STACK)
-off += reg->imm;
-
   size = bpf_size_to_bytes(bpf_size);
   if (size < 0)
   return size;


[...]

-if (reg->type == PTR_TO_MAP_VALUE ||
-reg->type == PTR_TO_MAP_VALUE_ADJ) {
+/* for access checks, reg->off is just part of off */
+off += reg->off;


Could you elaborate on why removing the reg->type == PTR_TO_STACK?

Previously bpf_reg_state had a member 'imm' which, for PTR_TO_STACK, was
  a fixed offset, so we had to add it in to the offset.  Now we instead
  have reg->off and it's generic to all pointerish types, so we don't need
  special handling of PTR_TO_STACK here.

Also in context of below PTR_TO_CTX.

[...]

   } else if (reg->type == PTR_TO_CTX) {
-enum bpf_reg_type reg_type = UNKNOWN_VALUE;
+enum bpf_reg_type reg_type = SCALAR_VALUE;

   if (t == BPF_WRITE && value_regno >= 0 &&
   is_pointer_value(env, value_regno)) {
   verbose("R%d leaks addr into ctx\n", value_regno);
   return -EACCES;
   }
+/* ctx accesses must be at a fixed offset, so that we can
+ * determine what type of data were returned.
+ */
+if (!tnum_is_const(reg->var_off)) {
+char tn_buf[48];
+
+tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
+verbose("variable ctx access var_off=%s off=%d size=%d",
+tn_buf, off, size);
+return -EACCES;
+}
+off += reg->var_off.value;


... f.e. in PTR_TO_CTX case the only access that is currently
allowed is LDX/STX with fixed offset from insn->off, which is
passed as off param to check_mem_access(). Can you elaborate on
off += reg->var_off.value? Meaning we make this more dynamic
as long as access is known const?

So, I can't actually figure out how to construct a pointer with a known
  variable offset, but future changes to the verifier (like learning from
  comparing two pointers with the same base) could make it possible.  The
  situation we're handling here is where our register holds ctx + x,
  where x is also known to be some constant value k, and currently I don't
  know if that's possible except for the trivial case of k==0, and the edge
  case where k is too big to fit in the s32 reg->off (in which case the
  check_ctx_access will presumably reject it).
Stepping back a bit, each register holding a pointer type has two offsets,
  reg->off and reg->var_off, and the latter is a tnum representing
  knowledge about a value that's not necessarily exactly known.  But
  tnum_is_const checks that it _is_ exactly known.


Right, I was reviewing this with the thought in mind where we could
run into a pruning situation where in the first path we either add
a scalar or offset to the ctx ptr that is then spilled to stack, later
filled to a reg again with eventual successful exit. And the second path
would prune on the spilled reg, but even if scalar, we require that it's
a _known_ const whereas reading back from stack marks it unknown, so that
is not possible. So all is fine; including your below example since it
all has to be a _known_ scalar.


There is another case that we allow now through the reg->off handling:
  adding a constant to a pointer and then dereferencing it.
So, with r1=ctx, instead of r2 = 

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

[Daniel Borkmann via iovisor-dev]

On 06/27/2017 02:56 PM, Edward Cree wrote:

Tracks value alignment by means of tracking known & unknown bits.
Tightens some min/max value checks and fixes a couple of bugs therein.


You mean the one in relation to patch 1/12? Would be good to elaborate
here since otherwise this gets forgotten few weeks later.

Could you also document all the changes that verifier will then start
allowing for after the patch?


If pointer leaks are allowed, and adjust_ptr_min_max_vals returns -EACCES,
  treat the pointer as an unknown scalar and try again, because we might be
  able to conclude something about the result (e.g. pointer & 0x40 is either
  0 or 0x40).

Signed-off-by: Edward Cree 

[...]

  /* check whether memory at (regno + off) is accessible for t = (read | write)
@@ -899,52 +965,79 @@ static int check_mem_access(struct bpf_verifier_env *env, 
int insn_idx, u32 regn
struct bpf_reg_state *reg = >regs[regno];
int size, err = 0;

-   if (reg->type == PTR_TO_STACK)
-   off += reg->imm;
-
size = bpf_size_to_bytes(bpf_size);
if (size < 0)
return size;


[...]

-   if (reg->type == PTR_TO_MAP_VALUE ||
-   reg->type == PTR_TO_MAP_VALUE_ADJ) {
+   /* for access checks, reg->off is just part of off */
+   off += reg->off;


Could you elaborate on why removing the reg->type == PTR_TO_STACK?
Also in context of below PTR_TO_CTX.

[...]

} else if (reg->type == PTR_TO_CTX) {
-   enum bpf_reg_type reg_type = UNKNOWN_VALUE;
+   enum bpf_reg_type reg_type = SCALAR_VALUE;

if (t == BPF_WRITE && value_regno >= 0 &&
is_pointer_value(env, value_regno)) {
verbose("R%d leaks addr into ctx\n", value_regno);
return -EACCES;
}
+   /* ctx accesses must be at a fixed offset, so that we can
+* determine what type of data were returned.
+*/
+   if (!tnum_is_const(reg->var_off)) {
+   char tn_buf[48];
+
+   tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
+   verbose("variable ctx access var_off=%s off=%d size=%d",
+   tn_buf, off, size);
+   return -EACCES;
+   }
+   off += reg->var_off.value;


... f.e. in PTR_TO_CTX case the only access that is currently
allowed is LDX/STX with fixed offset from insn->off, which is
passed as off param to check_mem_access(). Can you elaborate on
off += reg->var_off.value? Meaning we make this more dynamic
as long as access is known const?


err = check_ctx_access(env, insn_idx, off, size, t, _type);
if (!err && t == BPF_READ && value_regno >= 0) {
-   mark_reg_unknown_value_and_range(state->regs,
-value_regno);
-   /* note that reg.[id|off|range] == 0 */
+   /* ctx access returns either a scalar, or a
+* PTR_TO_PACKET[_END].  In the latter case, we know
+* the offset is zero.
+*/
+   if (reg_type == SCALAR_VALUE)
+   mark_reg_unknown(state->regs, value_regno);
+   else
+   mark_reg_known_zero(state->regs, value_regno);
+   state->regs[value_regno].id = 0;
+   state->regs[value_regno].off = 0;
+   state->regs[value_regno].range = 0;
state->regs[value_regno].type = reg_type;
-   state->regs[value_regno].aux_off = 0;
-   state->regs[value_regno].aux_off_align = 0;
}

-   } else if (reg->type == FRAME_PTR || reg->type == PTR_TO_STACK) {
+   } else if (reg->type == PTR_TO_STACK) {

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