Svadev mailing list

[John Criswell <criswell AT illinois.edu>]

On 8/18/11 11:35 PM, Thomas Sanchez wrote:
> 2011/8/18 John 
> Criswell<criswell AT illinois.edu>:
> > Dear Thomas,
> >
> > Just an update on this issue.  I successfully got the CompleteChecks pass to
> > work on your test case, so the invalid load is detected and reported.
> Awesome!

I just realized that I forgot to commit a file in the poolalloc project 
that is required to get this working.  Please svn up the poolalloc 
project if you've already gotten the code from SVN and rebuild.

> > The code may still have some issues, but if you want to try it out, you can
> > do the following (assuming you are using Mac OS X):
> >
> > 1) Check out and build SAFECode from the SVN repository.
> > 2) Make a backup copy of /usr/lib/libLTO.dylib.
> > 3) Copy the libLTO.dylib from the SAFECode build directory (usually
> > Debug+Asserts/lib/libLTO.dylib) into /usr/lib.
> > 4) Recompile using the new clang compiler you built.
> I'll do it ASAP, thank you !
>
> > Be sure to read the Install Guide
> > (http://sva.cs.illinois.edu/docs/Install.html) if you attempt to do this.
> By the way, if you don't mind I'm interested by the explanation even
> if I won't understand everything :)

Great!

So, one of the problems with doing memory safety in a compiler is that 
there is code that is not compiled along with the program but is instead 
linked in as native code.  Examples include any of the native code 
libraries in /usr/lib on most Unix systems.  We call such code external 
code.  Worse yet, when compiling one source file at a time, the compiler 
can't tell whether a function is just inside another compilation unit or 
if it is external code.  Only during the final link phase (in libLTO) 
can we do whole program analysis and tell the difference.

The specific problem in SAFECode's case is that external code can 
allocate memory objects and return them to the program.  External code 
can also free objects allocated by the program.

So, when you have a pointer and want to know whether it points into a 
valid memory object, you have a problem: if you can't find the memory 
object, is it because the pointer is invalid, or is it because the 
pointer is pointing into a memory object created by external code that 
the compiler did not analyze and instrument?

To get around this, SAFECode has two types of checks: incomplete and 
complete.  Complete checks fail and report an error if they cannot find 
the memory object.  Incomplete checks will do the best they can to 
ensure safety, but if they can't find a corresponding memory object for 
the pointer, they assume that the pointer points to some unknown memory 
object and conservatively pass.  Note that incomplete array bounds 
checking is still quite useful but that incomplete load/store checks are 
nearly useless.

The instrumentation passes in Clang insert incomplete checks by default 
because code is compiled one source file at a time; it's not possible to 
figure out what is external code and what is not.  However, libLTO, 
during the final link phase, *can* determine which pointers can be 
influenced by external code and which cannot (because it can do whole 
program analysis).  Therefore, we added a pass called CompleteChecks in 
libLTO that converts incomplete checks to complete checks when possible.

When I fixed CompleteChecks and put it into libLTO, it went and make the 
load/store checks that Clang was already putting into your program 
complete, so now they actually catch the error because they know for 
*sure* that any memory object pointed to by the pointer should have been 
registered with the SAFECode run-time.

BTW, I should warn you that CompleteChecks uses DSA to determine which 
pointers are influenced by external code and which are not.  DSA is a 
unification-based points-to analysis, and there has been some concern 
that it may be covered by the Steensgaard patent.  That's one of the 
reasons why DSA is not part of LLVM.

-- John T.