[DTrace-devel] [PATCH v3 13/19] alloca: support null pointers

[Kris Van Hees]

On Mon, Mar 28, 2022 at 06:44:00PM +0100, Nick Alcock wrote:
> On 28 Mar 2022, Kris Van Hees stated:
> > On Thu, Mar 24, 2022 at 06:24:39PM +0000, Nick Alcock via DTrace-devel wrote:
> >> Variables used to store pointers obtained from alloca() cannot be reused
> >> for any other purpose -- but there is one purpose people are almost
> >> certain to want, which is assigning NULL to them.  You don't want that
> >> to elicit an error message!
> >> 
> >> Making this work is quite tricky.  We can't just stuff a 0 into
> >> variables and load it, because that would lead to us subtracting
> >> scratchbot from it and then adding scratchbot back afterwards, giving
> >> null pointers a huge random value in the variables.  So we detect
> >> the specific case of var = NULL at codegen time by literal matching the
> >> parse tree and turn it into a store of a sentinel value,
> >> DT_CG_ALLOCA_NULLPTR (~(1<<30)).  We can then detect that at load time
> >> and turn it back into a NULL.
> >
> > I do not follow this...  If you store 0 in a variable, and then load it and
> > end up subtracting scratchbot from it and then adding scratchbot back, you
> > better end up with 0 again.  Which you can define to be an invalid scratchmem
> > offset by decree (i.e. enforce that allocation starts at offset 1).  So why
> > is that not sufficient?
> 
> That's possible in theory, but has the horrible consequence (to me,
> anyway) that ((struct foo *)NULL)->bar) is not trapped (because that is
> not at offset zero). This would fail on any normal system, so I consider
> it a QoI matter that we fail here. Storing 0 (in the register) as a
> unique value that cannot appear as a valid scratchmem offset does that
> with only a couple of instructions of overhead. (It used to be much
> worse, but since the null pointer space nightmare mentioned in relic
> comments below turned out to be unnecessary, it's actually quite easy.)

But we know exactly how ((struct foo *)NULL)->bar) is generated in code, and
thus we can definitely check whether (ptr + offset) has ptr == NULL.  In that
case, you can check whether offset is > scratchbot, and if not, flag this as a
BADADDR fault.  If it is, you could be fancy and replace the content of the reg
with (val - (uint64_t)scratchbot) + (char *)scratchbot.  Or in other words,
reduce the value to an offset from scratchbt, and then add that to the
scratchbot address (thereby resulting in a map_value).  Obviously this needs
bounds checking to ensure the offset in the map is valid.

Needing this would be very rare though - I doubt sensible code would use an
alloca address as an integer and then apply it as an index to NULL.  Or any
other combination of (a + b) being used as a pointer.  Same logic applies - if
the pointer is expected to be an alloca point, the above should be sufficient
to validate it where needed and convert it into a real map_value pointer if the
bounds checking deemds it valid.

> >> But that's not enough.  We might say "it's up to the user to not
> >> dereference it", but the verifier forces us to ensure that this can't
> >> happen.  We can't leave a 0 in there either because it's not a pointer
> >> value and the verifier's tracking of what happens if a 0 is dereferenced
> >> hits map_value-versus-literal problems: since every *other* value we
> >> can hold in an alloca parse tree node is a pointer, we should arrange
> >> for this to be one too.
> >
> > Where exactly is this causing issues with the verifier in terms of map_value
> > vs plain integer value?
> > 
> >> certainly can't be a pointer to NULL -- that's not a map_value!  So we
> >> introduce a new "null pointer space", in the shape of a BPF array twice
> >> the size of scratch space, and set null pointers to point halfway
> >> through that at load time.  Then it's just a matter of having the
> >> bounds-checkers check for both 0 and the null pointer space value and
> >> raise suitable out-of-bounds errors in both cases.  (As usual,
> >> in-scratch and out-of-scratch bounds checkers diverge: *both* consider
> >> null pointers out of bounds, but the in-scratch checker only checks for
> >> the null-pointer-space version so it can raise a suitable error, since
> >> null pointers that are still 0 raise the right error anyway.  This means
> >> null pointer detection adds relatively little code except to bcopy.)
> >
> > This really seems overly complicated.  So why can't we just use 0 (which is in
> > fact scratchbot, which is a valid pointer i.e. map_value)?  Any adjustment to
> > that value (add or subtract) due to e.g. indexing would then simply need to be
> > bounds checked against the bounds of the scratch space, i.e. offset greater
> > than 0 and less than the scratch space size - 1.
> 
> Sorry, this stuff is residual commit message junk I should have cleaned
> up. The null pointer space has been gone for some time :) null pointers
> are encoded as DT_CG_ALLOCA_NULLPTR in variables, and represented when
> not in variables as 0 (with +/- scratchlen also considered a null
> pointer).
> 
> > I really do not see where we need a 'null pointer space' rather than 0 being
> > the null pointer, and not-0 nit being the null pointer.
> 
> You are quite right!
> 
> > Given that the scratch space may need to be pretty big, doubling it just to be
> > able to handle a NULL pointer seems rather extreme as well.
> 
> Well, we have to double the scratch space in *any* case -- with the
> latter half unused -- but that's for an entirely different reason: that
> you might choose to do a 1-long bcopy() from the last byte in scratch
> space, but that size is a value in a register, and the verifier cannot
> use values in registers to determine bounds. So we must use a worst-case
> static bound, which is that for a bcopy() into the first valid scratch
> address, running up to the last: thus we need twice the space we would
> otherwise need. (Well, twice less one byte, but honestly it makes
> reasoning about this easier to just double it.)

Good point.  Which reminds me I really should propose a kernel patch to handle
reg vs reg comparison-based bounds updating for the verifier.  I don't think
it can be done for every single case, but we should be able to do handle most
common cases if not all.

> >> -	emit(dlp,  BPF_BRANCH_IMM(BPF_JNE, reg, 0, lbl_notnull));
> >> -	dt_cg_probe_error(yypcb, DT_LBL_NONE, DTRACEFLT_BADADDR, 0);
> >> +	uint_t	lbl_null = dt_irlist_label(dlp);
> >> +
> >> +	emit(dlp,  BPF_BRANCH_IMM(BPF_JEQ, reg, 0, lbl_null));
> >> +	emit(dlp,  BPF_BRANCH_IMM(BPF_JSGT, reg, opt_scratchsize,
> >> +				  lbl_notnull));
> >> +	emit(dlp,  BPF_BRANCH_IMM(BPF_JSLT, reg, -opt_scratchsize,
> >> +				  lbl_notnull));
> >> +	dt_cg_probe_error(yypcb, lbl_null, DTRACEFLT_BADADDR, 0);
> >
> > This is a problem because we're doing this for every not-NULL check, even
> > if alloca is not involved.
> 
> As noted above, I consider this a QoI matter, since every other null
> pointer check in every implementation out there will correct diagnose
> (by crashing) pointers *near* null, as well as pointers *at* null. The
> verifer is happy because we have a null check too.

We already have validation of memory access for other cases because those
require the use of bpf_probe_read() which employs the address validation that
the kernel provides already.  No need to do it ourselves.  We can just ensure
that we report BADADDR for failed bpf_probe_read( calls.

> > E.g. a simple dtrace -n 'BEGIN { s = probename; trace(s); exit(0); }' 
> >
> > now gets these extra conditionals added that are not necessary.
> 
> Yes, but conversely,
> 
> trace((struct foo *)NULL)->bar);
> 
> is now correctly diagnosed as a null pointer dereference. (This really
> happens, and quite a lot too. Even the kernel itself has done it
> internally, and indeed this has been the source of security holes in the
> past...)
> 
> We should certainly do it at least for alloca pointers, given that they
> are often likely to be pointers to structures or arrays -- but it's only
> two insns, dammit: are we so short of insns that this is actually
> causing a problem?

Well, for one, it is two conditionals which means the verifier will end up
walking a *lot* more instructions as it performs its static analysis on the
different branches of the execution tree.

Secondly, the use of [-maxstreize .. maxstrsize] as the range for the NULL
pointer value is extremely arbitrary.  Why is it maxstrsize based?  What if
struct foo is larger than maxstrsize and you encounter (struct foo *)NULL)->bar?