Re: [PATCH 2/3] bpf: Track alignment of MAP pointers in verifier.

[Daniel Borkmann <daniel@iogearbox.net>]

On 05/15/2017 05:34 PM, David Miller wrote:
> From: Daniel Borkmann <daniel@iogearbox.net>
> Date: Mon, 15 May 2017 15:10:02 +0200
>
>>>> What are the semantics of using id here? In ptr_to_pkt, we have it,
>>>> so that eventually, in find_good_pkt_pointers() we can match on id
>>>> and update the range for all such regs with the same id. I'm just
>>>> wondering as the side effect of this is that this makes state
>>>> pruning worse.
>
> Daniel, I looked at the state pruning for maps.  The situation is
> quite interesting.
>
> Once we have env->varlen_map_value_access (and load or store via a
> PTR_TO_MAP_VALUE_ADJ pointer), the state pruning gets more strict, the
> relevant tests are:
>
> 		if (memcmp(rold, rcur, sizeof(*rold)) == 0)
> 			continue;
>
> 		/* If the ranges were not the same, but everything else was and
> 		 * we didn't do a variable access into a map then we are a-ok.
> 		 */
> 		if (!varlen_map_access &&
> 		    memcmp(rold, rcur, offsetofend(struct bpf_reg_state, id)) == 0)
> 			continue;
>
> The first memcmp() is not going to match any time we adjust any
> component of a MAP pointer reg.  The offset, the alignment, anything.
> That means any side effect whatsoever performed by check_pointer_add()
> even if we changed the code to not modify reg->id
>
> The second check elides:
>
> 	s64 min_value;
> 	u64 max_value;
> 	u32 min_align;
> 	u32 aux_off;
> 	u32 aux_off_align;
>
> from the comparison but only if we haven't done a variable length
> MAP access.

I'm actually wondering about the min_align/aux_off/aux_off_align and
given this is not really related to varlen_map_access and we currently
just skip this.

We should make sure that when env->strict_alignment is false that we
ignore any difference in min_align/aux_off/aux_off_align, afaik, the
min_align would also be set on regs other than ptr_to_pkt.

What about compare_ptrs_to_packet() for when env->strict_alignment is
true in ptr_to_pkt case? Could we have a situation that prunes the search
with matching the third test? Say, in the old case, we did go all the
way and ...

   R3(off=0, r=0)
   R4 = R3 + 20   // AAA
   // now R4(off=20,r=0)
   if (R4 > data_end)
       got out;
   // BBB: now R4(off=20,r=20), R3(off=0,r=20) and R3 used to access

... verify the code under 'BBB' and found that it's safe to run,
including alignment, etc. Next time we come to this branch through
R4 = R3 + 33 (under AAA), so we have R4(off=33,r=0). What happens
if we then do R4-=4, and access 4 bytes of the packet?

The old R4(off=20,r=20) becomes R4(off=16,r=20), which was found
safe and the new R4(off=33,r=0) becomes R4(off=29,r=33) which
would end up being unaligned? Looks like we shouldn't prune in
such case? Maybe test_verifier test case helps to visualize.

> The only conclusion I can come to is that changing reg->id for
> PTR_TO_MAP_VALUE_ADJ has no side effect for state pruning, unless we
> perform PTR_TO_MAP_VALUE_ADJ register adjustments without ever
> accessing the map via that pointer in the entire program.

Why entire program, just between two state pruning points, no?
(They are marked as STATE_LIST_MARK.)

> I could add some new state to avoid the reg->id change, but given
> the above I don't think that it is really necessary.