[llvm-dev] Contributing a new sanitizer for pointer casts

[Vedant Kumar via llvm-dev]

> On Apr 26, 2017, at 3:58 AM, Stephen Kell <Stephen.Kell at cl.cam.ac.uk> wrote:
> 
> Hi Vedant,
> 
>> I enjoyed reading through your EuroLLVM slides and OOPSLA paper.
>> Detecting the creation of contract-violating pointers is an
>> interesting idea, and your paper demonstrates that the checking can
>> be comprehensive and effective.
> 
> Glad you enjoyed them. :-)
> 
>> However, I have concerns about the quality of diagnostics, the
>> complexity of the driver, and about maintaining an out-of-tree
>> runtime.
>> 
>> First, I'm concerned about libcrunch diagnostics which are morally
>> correct, but which do not point out imminent correctness problems
>> (for convenience I'll refer to these as false positives). You address
>> this in the "Accommodating Sloppy C" section of your paper with the
>> __like_a() runtime check. In my experience, users are reluctant to
>> deploy the type of suppressions described here, and are more likely
>> to abandon the sanitizer instead. What has your experience been with
>> FPs? The results from your SPEC testing look promising, but I'm
>> curious about any FP-related feedback you've gotten from other
>> developers, or about the results of a libcrunch-enabled world build
>> of FreeBSD. 
> 
> Great question. The truth is that I don't yet have enough experience to
> answer this, and part of the point of contributing this to LLVM would
> be to get more people to try it out and contribute improvements.
> However, I would say that I am already pleasantly surprised with how
> on-point the warnings are... although there are false positives, they
> tend to be about genuinely nasty/naughty code.

What it would take to get to a point where there are no crunch "FPs" by design? E.g given the following code:

  A *a = malloc(sizeof(A));
  UnrelatedToA *uta = (UnrelatedToA *)a;
  LikeA *la = (LikeA *)uta;
  deref(la);

Could the diagnostic for the assignment to "uta" be suppressed, since "uta" isn't dereferenced?


> I take your point about the danger that "people would turn it off".
> As an aside -- more below -- one thing I've worked quite hard on is
> to ensure that you don't need to rebuild to turn it off, which at least
> prevents a hard exit.

How does the ability to disable sanitization without rebuilding help prevent hard exits?


> Beyond that, there is quite a long tail of mitigation measures against
> false positives, including some not mentioned in the paper (and, er,
> some not implemented). The big one, and one that isn't in the paper, is
> "trap pointers" -- I outlined this in response to Hal in the TBAA
> sanitizer thread. In short, it delays warnings from the time of cast to
> the time of use.

Oh, neat! Would it handle the example above?


> I only implemented this later, to support bounds
> checking rather than cast checking, but it applies to the latter too. 
> (Sneak preview: I'm working on bounds checker I believe will offer a
> different, possibly better, precision/performance trade-off than ASan,
> but that's still in progress.) 
> 
> Another possible mitigation is to use "__like_a" by default in some
> circumstances, perhaps helped by an up-front static analysis pass to
> find things like structure prefixing. That's pure idea-stuff right now.

I'm not sure what it would take to prototype and evaluate this, but it sounds like a promising mitigation.


> Doing a build-world of FreeBSD or similar, as you suggest, is exactly
> the sort of experience that is required, and inevitably, in doing so
> there will be a lot of handle-turning to fix bugs and the like. I'd
> rather go through this on an implementation that has a chance of
> getting adopted... so I think the LLVM port has to happen first, though
> I understand that the contribution per se may have to wait.
> 
>> I've certainly seen code at Apple which would fail
>> libcrunch's "is-a" checks, but which "works fine" according to the
>> code owners. Would you be open to reducing the number of cases
>> libcrunch is able to diagnose in order to reduce FP rates?
> 
> I'm curious -- can you give me a sketch of what this code is doing?

It's the example I provided above. It might also take some work to teach crunch about type relationships in ObjC, or at least to make crunch ignore ObjC types.


> If it's just a case of "creating wrong-typed pointers that aren't
> deref'd", then I think we're good. In general I'd rather fix the FPs
> precisely, rather than introduce underapproximation, and I've yet to
> see cases where that really can't be done.

Makes sense.


>> Second, do you see any way to simplify the wrappers required to
>> invoke libcrunch? E.g is the runtime preload step necessary? Apart
>> from the runtime shared object, can the other tools required to use
>> libcrunch be consolidated into the clang binary?
> 
> Great question. The plan is to consolidate the tools, yes -- but
> probably mostly into the gold plugin.

Would it be feasible to introduce a clang tool that runs after -cc1 to do some of the heavy lifting? This might be more portable than a linker plugin.


> Only a couple of steps work on the individual compilation units, and they can be deferred until link
> time anyhow. It does mean that each compilation unit's allocation site
> information has to get dumped somewhere, to be picked up at link time.

Sorry for the naive question, but could you explain how the allocation site information is generated? Is this something that could be deferred until link time?


> This is currently in a .i.allocs text file, but that is a bit untidy...
> I've thought about a DWARF extension (DW_TAG_allocation_site or similar)
> instead, which would be cleaner.
> 
> About preloading -- I happen to like this design, modulo the
> clunky invocation, because it means you can easily turn the checking on
> or off. For executables, you could simply link the preload stuff in,
> but that would lose the on/off switch, and doesn't work for shared
> libraries. Another idea I've had is to use a customised loader (ld.so)
> instead of a preload library. So you would do
> 
> $ ./myprogram   # runs normally
> 
> or 
> 
> $ /path/to/crunchld.so ./myprogram    # runs +crunch
> 
> This would more-or-less replicate the usage model of Valgrind tools.
> (In general, my feeling is that extending the ld.so is more sane than
> using LD_PRELOAD, although I realise it will seem a bit off-the-wall.)

I have a preference for building separately when enabling sanitizers. I feel this way because I don't have reasons to disable sanitization once I've enabled it in one build tree, and because the performance of the sanitized binary is impacted. Having this as the supported workflow may be more convenient if it makes it possible to skip the preload step.


>> Third, how do you plan on keeping the libcrunch integration into
>> clang in-sync with the runtime, if the runtime is to live outside of
>> the llvm tree? 
> 
> I think that part is no problem. The interface between instrumented
> code and the runtime is pretty narrow (basically just the __is_a(),
> __like_a() and similar functions) and does not embed any LLVM stuff, so
> it would be stable under LLVM churn. The same would hold for the gold
> plugin... LLVM/clang's involvement is mostly just to do the
> instrumentation, which is a pretty well-isolated task. The allocation
> site metadata I just mentioned is probably the only change-prone thing.
> 
> Of course, there is a problem of breakage/churn in the
> libcrunch/liballocs stuff... in particular, things like new DWARF
> features can break things. I have no good answer to that, except that
> more hands make light(er) work.
> 
>> How will the feature be tested? 
> 
> On that, I have no idea, and I'd have to take your lead on that. To
> make an analogy with another out-of-tree dependency, how do you test
> LTO against GNU binutils? I'm hoping, perhaps naively, that it could
> work similarly.

There are some in-tree tests which use libLTO.dylib and ld64. The tests depend on those tools being available. For end-to-end testing of crunch, you could do something similar. The instrumentation and driver changes could be tested in isolation.

My preference would be to have the sanitizer runtime live in compiler-rt, which is where end-to-end testing of the other sanitizers currently happens.


>> Currently, the
>> sanitizer runtimes ship with official LLVM downloads: what would the
>> deployment story for libcrunch be (how would users get it)?
> 
> Initially they would build the libcrunch tree, which would build for
> them the gold plugin and runtime. Again, I think it would be rather
> like the LTO story (a web page with "follow these instructions"). And
> of course distributors could build binary packages... again, it helps
> that the interface between compiler and plugin/runtime is fairly simple.
> 
> (Full disclosure: currently you have to build both the liballocs tree
> and the libcrunch tree, separately. Eventually the former will be a
> submodule of the latter. I have too many levels of submodule going
> on....)

IMO a model where all of the sanitizer components live in-tree would make testing and deploying the sanitizer easier. It may also make maintenance easier, e.g if it's ever necessary to change the libcrunch <-> clang interface.

I know you mentioned up front that you don't intend to port the runtime to compiler-rt, as this would require a major rewrite. However, I think that would be the right way to go, and I'd be willing to help out with reviews etc.

I'm curious to hear what others think about having an out-of-tree sanitizer runtime. I'm not sure that the situation with LTO and gold is precedent for this, but others may feel differently.

vedant


> 
>> I don't mean any of this as a "do not proceed" message. These are
>> simply some of the issues which I think are worth discussing early on.
> 
> Of course. :-) Thanks for the detailed comments! Hoping my answers make
> sense, and happy to follow up,
> 
> Stephen.