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

From: Nadav Amit
Date: Fri Jul 07 2017 - 20:55:25 EST

Nadav Amit <nadav.amit@xxxxxxxxx> wrote:

> Edward Cree <ecree@xxxxxxxxxxxxxx> 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 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
> 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 */
>> + u32 range;
> I would (personally) prefer range (and offsets) to be u64. I could
> understand if you left the range as u16 (since packet size is limited to
> 64k). But why would it be u32?
> Or:
>> - if (off < 0 || size <= 0 || off + size > reg->range) {
>> + if (off < 0 || size <= 0 || off > MAX_PACKET_OFF ||
>> + off + size > reg->range) {
> Why donât you check (off + size > max(MAX_PACKET_OFF, reg->range))? Is there
> a reason you ignore size when comparing to MAX_PACKET_OFF ?

(should be min, not max)