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) + 

[iovisor-dev] Fwd: [CFP/CFD] Tracing Summit 2017 Call for Presentations and Discussions, October 27th, 2017, Prague, Czech Republic

[Geneviève Bastien via iovisor-dev]

Hi,


For your information, as someone mentioned in the meeting earlier, there
is a Tracing Summit in Prague in october. And unlike the previous
edition, it won't be all presentations, but only half a day, and another
half a day of discussions. It would certainly be interesting to discuss
ebpf there as well.


Regards,

Geneviève Bastien



 Forwarded Message 
Subject:[lttng-dev] [CFP/CFD] Tracing Summit 2017 Call for
Presentations and Discussions, October 27th, 2017, Prague, Czech Republic
Date:   Mon, 10 Jul 2017 13:51:00 -0400
From:   Julien Desfossez 
Reply-To:   submiss...@tracingsummit.org
To: lttng-...@lists.lttng.org 



Hi,

This is a call for presentations for the Tracing Summit which will be
held in Prague, Czech Republic, on October 27th, 2017, at the Hilton
Prague. This event is co-located with the Open Source Summit Europe
2017.

The Tracing Summit is organized by the Linux Foundation Diagnostic and
Monitoring Workgroup (http://diamon.org). This event focuses on the
tracing area, gathering people involved in development and end-users
of tracing tools as well as trace analysis tools. The main target of
this Tracing Summit is to provide room for discussion between people
in the various areas that benefit from tracing, namely parallel,
distributed and/or real-time systems, as well as kernel development.

New in the 2017 edition: half the day will be reserved for
presentations and the other half will be reserved for discussions
(more in the style of Linux Plumbers Conference) between users and
developers of the tracing infrastructures. Steven Rostedt will run the
discussion part.

If you are interested to present, please submit a proposal to
submiss...@tracingsummit.org before September 1st, 2017, at 23:59 EST.
Please specify if it is a presentation or a discussion topic, provide
a title, an abstract describing the proposed presentation or
discussion topic (900 characters maximum), a short biography (900
characters maximum), and describe the targeted audience (900
characters maximum).

We are welcoming presentations from both end users and developers, on
topics covering, but not limited to:

 * Investigation workflow of Real-Time, latency, and throughput
   issues,
 * Trace collection and extraction,
 * Trace filtering,
 * Trace aggregation,
 * Trace formats,
 * Tracing multi-core systems,
 * Trace abstraction,
 * Trace modeling,
 * Automated trace analysis (e.g. dependency analysis),
 * Tracing large clusters and distributed systems,
 * Hardware-level tracing (e.g. DSP, GPU, bare-metal),
 * Trace visualisation,
 * Interaction between debugging and tracing,
 * Tracing remote control,
 * Analysis of large trace datasets,
 * Cloud trace collection and analysis,
 * Integration between trace tools,
 * Live tracing & monitoring.

Those can cover recently available technologies, ongoing work, and yet
non-existing technologies (which are compellingly interesting to
end-users).  Please understand that this open forum is not the proper
place to present sales or marketing pitches, nor technologies which
are prevented from being freely used in open source.

There is a single track, containing presentations between 30 and 45
minutes per subject with discussion.

This year, attending the Tracing Summit is free of charge, and
attendees are not required to register to other events. The
registration will soon be available on the Open Source Summit website,
the room is limited to 100 persons, so don't wait too long before
registering.

The Tracing Summit is currently sponsored by EfficiOS. We are
welcoming additional sponsors. Please let us know if your company is
interested in sponsoring this event or next year's Tracing Summit.

See the Tracing Summit 2017 wiki at
http://www.tracingsummit.org/wiki/TracingSummit2017 for details.

Thank you,

On behalf of the Diagnostic and Monitoring Workgroup,
Julien Desfossez & Mathieu Desnoyers
___
lttng-dev mailing list
lttng-...@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

___
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

[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 

[iovisor-dev] Linux Plumber's wiki

[Brendan Gregg via iovisor-dev]

G'Day,

Please add talk/discussion proposals to the wiki, especially in-development
projects you'd like to technically discuss:

http://wiki.linuxplumbersconf.org/2017:tracing

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