[llvm-dev] llvm-dev Digest, Vol 136, Issue 22

[Ed Robbins via llvm-dev]

Hi John, Vikram and all,
I've been working on this a while now and thought I'd send a mail to
report some status. I've also got various patches I'd like to submit for
review, but I'm still getting my commits in order so I will follow up
with those later.

The context is that I'm working on getting the contiki embedded
(Internet of Things) OS working with some notion of type and memory
safety, on the Texas Instruments CC2538. This is a 32MHz Cortex M3 with
32K RAM, 512K flash, a zigbee/802.15.4 wireless interface, and an MPU.

I've revived poolalloc, which was not actually too much work. Currently
I'm using it to create pools for heap allocations only (not to create
pool handles for safecode). There were just a couple of
incompatibilities between it and LLVM 3.7. I also had to make a couple
of changes to support ARM, and also make changes in the runtime (FL2
allocator) where I replaced the mutex implementation and disabled
pointer compression. The pointer compression routines want an MMU, and
the cc2538 only has an MPU.

Safecode has been more work. There were some bugs and a bunch more
changes due to incompatibilities with LLVM 3.7 (in fact the code built
fine, but was crashing or not working when you tried to run the passes).
I've also changed it to build shared objects so that I can run
everything through opt, and that all works fine. I'm using the relevant
passes to insert checks, and the optimisations that remove them, and it
looks at the moment as though ~60% of checks are removed by static
passes, which is not bad. 

I'm not using any of the baggy bounds checking, dangling pointer checks,
or softbound, as they either need an MMU or wont fit into memory. I
tried using the control flow integrity checking but it causes the object
files to really blow up in size and they wont fit into flash anymore
afterwards (they use too much RAM as well).

I basically rewrote most of the runtime, creating an optional new
runtime called "EmbeddedRuntime". This was required because although
safecode exports all its runtime functionality to C, it uses a lot of
C++ STL bits such as set,map etc, which would require linking against
libstdc++, and we can't get this into memory. So the EmbeddedRuntime
uses a very simple binary tree (based on tsearch) to store allocated
ranges, and other parts of the runtime have been rewritten to remove STL
stuff.

Building the poolalloc and safecode runtimes is a bit messy. I've had to
create my own makefiles and build outside of the main build system
because I need to target arm (with different flags) and my main build
targets x86. If anyone has ideas about a cleaner solution I'd love to
hear from them.

A note about memory safety; since poolalloc is not yet creating pool
handles, many of the checks are not completely memory safe. Those
objects will be registered into and checked against the global tree
instead, so often although we can guarantee they remain in an allocated
range, we can't be sure they remain in the correct range. However, I
hope to rectify this at some point so that we can get complete memory
safety. I'd also like to be sure we can trust libc, but am just trusting
the wrappers for now.

Best,
Ed


-- 
  Ed Robbins
  ed at dismantleengineering.co.uk

On Mon, Oct 12, 2015, at 03:51 PM, Ed Robbins wrote:
> On Fri, Oct 9, 2015, at 05:45 PM, Adve, Vikram Sadanand wrote:
> > > Maybe I should have been a bit clearer; we're really interested in full
> > > memory and type safety. We want to harden the system against memory
> > > corruption vulnerabilities. Process isolation isn't an issue, as we are
> > > in an embedded context where we don't have processes.
> > 
> > 
> > Do you also care about use-after-free and free-after-free errors? 
> > Handling free-after-free is not too hard, but general use-after-free can
> > be expensive, unless you’re willing to spend a fair amount of extra
> > memory.  If dynamic allocation isn’t an issue for your (embedded)
> > applications, that makes this whole problem go away, of course.
> 
> Yes, we do care about these issues. We are happy with the trick used in
> the TECS paper - that use after frees are type safe in that they will
> either point to the original object or an object of the same type.
> 
> > 
> > This brings me to the new question: exactly what unsafe features do you
> > need to be concerned about?  Our first paper in the SAFECode project
> > focused on identifying a subset of C for which type and memory safety
> > could be enforced without *any* run-time checks or GC.  We found that
> > array bounds checks were the biggest problem; ignoring these, we can
> > ensure the safety of pointer and dynamic memory usage in all the embedded
> > benchmarks we tried without any run-time checks.  The paper appeared at
> > LCTES:
> > 	http://llvm.org/pubs/2003-05-05-LCTES03-CodeSafety.html
> > Like the later work, this did not eliminate use-after-free but used APA
> > to ensure that any use-after-free errors are “harmless” in that they did
> > not violate all the other type- and memory-safety guarantees.
> > 
> > Let me know if you have any questions about this.
> > 
> 
> We're not sure what features to be concerned about until we actually try
> to run it on some of the intended code base. So probably, everything.
> But we are happy to spend some effort in refactoring programs if it
> means we can get type/memory safety without run time checks. Most of the
> C semantics that need to be dropped appear to be things that are quite
> bad practice anyway (except perhaps complex array indexing).
> 
> I've been reading through this and a few other publications in order to
> try and get a better handle on the code. Having not done anything with
> llvm before and not knowing DSA/APA/SafeCode intimately I am a bit out
> of my depth so the background reading is great. Also, your code is
> really well commented :)
> 
> The main question I have at the moment is what is really broken with APA
> in its current state? Or is it just that it's suspected to be broken?
> I've managed to build and run it using opt, and it appears to work just
> as well as it did for llvm-3.2. I was expecting to have to modify
> something to work around the untyped GEPs that John mentioned, but in
> fact I haven't had any such issues. I run using:
> 
> path/to/opt -S -load path/to/LLVMDataStructure.so -load
> path/to/poolalloc.so -paheur-AllHeapNodes -poolalloc myprog.bc >
> myprog.pa.ll
> 
> and get the same (modulo bytecode syntax changes) as with llvm 3.2. I
> have also tried some of the other heuristics and have not found any
> differences. But I don't think I tried with any programs that need more
> than one pool yet (so haven't really exercised it), and I haven't tried
> running sc over the output yet either.
> 
> It would be useful if I could get a pointer to some test programs that
> really exercise PA. This is next on my todo list (going to check those
> referenced in your publications first).
> 
> Thanks for your help Vikram. Best,
> Ed