SAFECode Source Code Released

[John_Criswell2]

Dear LLVMers,

We are happy to announce an alpha release of the SAFECode compiler. It is now available for download from the LLVM public Subversion repository. SAFECode uses a set of analysis passes and program transformations to provide strong memory safety guarantees to C/C++ programs. Specifically, the safety guarantees are:

o Array bounds checking (prevents pointers from overflowing from one memory object into another)
o Loads and stores only access valid memory objects
o Type safety for a subset of memory objects
o Dangling pointer errors are harmless (i.e., all safety guarantees hold even when dangling pointers are dereferenced)
o Sound operational semantics in the face of dangling pointer errors
o Optional dangling pointer detection (induces more overhead)

We have currently built a Valgrind-like debugging tool using SAFECode that prints debugging information when a memory safety error is detected at run-time. While the debugging tool doesn't use all of the fancy tricks we developed in our research, transformed programs still run 2.8x faster on average than Valgrind's memcheck tool (on Mac OS X) and 24x faster on average than Valgrind's ptrcheck tool (on Linux).

Currently, the debugging tool does not utilize all of the results from the SAFECode research. Features such as Automatic Pool Allocation and Inter-procedural static array bounds checking are either buggy or disabled. We're working on improving the quality of the code, and we hope to release a "production-speed" version of SAFECode in the near future.

More information on SAFECode can be found here: SAFECode

SAFECode can be checked out from SVN using the following command:

svn co http://llvm.org/svn/llvm-project/safecode/trunk safecode

Once checked out from SVN, you can find the documentation in safecode/docs. See the README file in the distribution for more details on documentation.

-- John T.

[John_Criswell2]

Török Edwin wrote:

[Edward_O_Callaghan]

WOW !

This is a truly fantastic project !

Great work !
I'll be interested to build and port this to AuroraUX.

Keep up the great work,

Cheer,
Edward.

[John_Criswell2]

Török Edwin wrote:

[snip]

I applied the attached patch to make it compile on my box (Debian
x86_64), only to find out that x86_64 is not supported
This architecture is not supported by the pool allocator!
Aborted
  

Thanks for the patch. What options do I give to the patch command to apply it to the source code?

Although there's no documentation about contributions to SAFECode as of yet, I'd like to follow the same policy that LLVM uses (notably that the copyright of contributions is passed to the University of Illinois). Is this acceptable to you?

We haven't regularly tested SAFECode and Automatic Pool Allocation on 64 bit architectures, so while it may work, we can't say for certain that it will.

This particular error is caused by the fact that the run-time does not know which allocator is best for allocating page-aligned sections of memory. If you modify getPages() in runtime/BitmapPoolAllocator/PageManager.cpp to use mmap(), posix_memalign(), or valloc(), then it will fix this error and allow you to continue experimenting with Poolalloc/SAFECode in 64-bit mode.

Eventually, we should set up something in the configure script to find a usable default for this function. This would be a simple autoconf change; it just hasn't been high on the priority list.

I turned off Werror too because I was getting lots of aliasing violation
warnings (with g++ 4.3.4).
There are some "cast pointer to integer of different size" warnings, but
they're all in SVA, and thats the kernel stuff that has nothing to do
with safecode right?
  

Which code are you referring to? I don't believe any of the SVA specific code is compiled by default in the mainline SAFECode tree.

So I've built SAFEcode in a 32-bit chroot (I get the aliasing warnings
on 32-bit too).

A simple test program works, however when trying to compile ClamAV I get
an error right on startup, and it aborts!
The docs say that if I don't use terminate it should go on.
  

The -terminate option used to work but broke during some refactoring of the error reporting code. Getting it to work again is on my TODO list. You can get the behavior you want, for now, by removing the abort() line from runtime/DebugRuntime/Report.cpp.

As far as the ClamAV error, are you sure it's a false positive (i.e., a bug in SAFECode)? I ran SAFECode on the programs in MultiSource/Applications and found that quite a few programs have memory safety errors.

In the case of ClamAV, a false positive might occur if 1) the memory object is allocated by a library linked in as native code, or 2) the memory object is allocated via some C library function that SAFECode doesn't recognize as an allocator (e.g., getenv() or getpwent()). Handling the latter requires some simple changes to the DSA analysis and SAFECode so that it treats these functions as allocators.

SAFECode:Violation Type 0x2 when accessing 0x832d228 at IP=0x812b531

=======+++++++ SAFECODE RUNTIME ALERT +++++++=======
= Error type : Invalid Free Error
= Program counter : 0x812b531
= Faulting pointer : 0x832d228

Program received signal SIGABRT, Aborted.
0xf7fdf430 in __kernel_vsyscall ()
(gdb) bt
#0 0xf7fdf430 in __kernel_vsyscall ()
#1 0xf7d713d0 in raise () from /lib/i686/cmov/libc.so.6
#2 0xf7d74a85 in abort () from /lib/i686/cmov/libc.so.6
#3 0x08214227 in
safecode::ReportMemoryViolation(safecode::ViolationInfo const*) ()
#4 0xf7fccea0 in ?? () from /usr/lib/libstdc++.so.6
Backtrace stopped: previous frame inner to this frame (corrupt stack?)

I did compile ClamAV with -g, I even used -disable-opt for llvm-ld, but
I still don't see line number error there (according to the docs I should).
  
Hrm. Yes. This seems to be a missing feature. I think I can add it relatively easily.

$ ~/llvm2.6/obj32/projects/safecode/Release/bin/sc -rewrite-oob
clamscan.bc -o clamscan_sc3.bc
$ ~/llvm2.6/obj32/Release/bin/llc clamscan_sc3.bc -f
$ gcc -o clamscan_sc3 clamscan_sc3.s
~/llvm2.6/obj32/projects/safecode/Release/lib/libsc_dbg_rt.a
~/llvm2.6/obj32/projects/safecode/Release/lib/libpoolalloc_bitmap.a
-lstdc++ -lbz2 -pthread -lz ../libltdl/.libs/libltdlcS.o

And I've built ClamAV like this:
$ ./configure CC=llvm-gcc --disable-shared
$ make CPPFLAGS="-O2 -g -emit-llvm" CFLAGS=
CCLD="/home/edwin/llvm2.6/obj32/Release/bin/llvm-ld -disable-opt" -j8

If I use addr2line on the IP printed by SAFEcode, I get this, but I
don't see anything wrong there:
foreach_dirinpath
/home/edwin/clam/git/builds/sc/libltdl/../../../clamav-devel/libltdl/ltdl.c:717

If I use the system's libltdl I get an invalid freee error here:
optfree
/home/edwin/clam/git/builds/sc/clamscan/../../../clamav-devel/shared/optparser.c:612

Is there a way to disable these invalid free errors? They look like
false positives to me (valgrind doesn't report them).
  

Not currently. SAFECode should not have false positives. There is either a real error in ClamAV or a bug in SAFECode.

I can send you clamscan.bc (it is 2.3M gzipped) if you want to.
  

Let me first enhance the invalid free error reporting. That may help you narrow down what SAFECode thinks the problem is and may help rule out the possibility of a real memory error in ClamAV. After that, if SAFECode is still reporting an error, and you can't figure out why, I can add looking at the problem to my TODO list.

P.S.: should I send "bugs" like this to you directly, or report them on
LLVM bugzilla?
  

I think it's actually best to file bug reports for each individual issue. That way, we can track their progress, and they won't get lost in my email INBOX.

Thanks again for giving SAFECode a test drive. I'll try to get the invalid free error reporting improved within the next day or two. If you can let me know how to apply your patch (patch < patchfile isn't working for me), that'd be great too.

Thanks again!

-- John T.

[David_A_Greene]

Did I miss a message? I am getting tons of compiler errors building poolalloc
and safecode and am wondering if this patch would fix things.

                                  -Dave

[To_ro_k_Edwin]

Török Edwin wrote:

[snip]

I applied the attached patch to make it compile on my box (Debian
x86_64), only to find out that x86_64 is not supported
This architecture is not supported by the pool allocator!
Aborted
  

Thanks for the patch. What options do I give to the patch command to
apply it to the source code?

It was generated by svn diff, so patch -p0 should apply it. I only fixed
the obvious compiler warnings about pointer size, I don't know if there
are any more assumptions
that sizeof(void*) == 4 in the code.

Although there's no documentation about contributions to SAFECode as
of yet, I'd like to follow the same policy that LLVM uses (notably
that the copyright of contributions is passed to the University of
Illinois). Is this acceptable to you?

I don't think that a few lines of changes are copyrightable, but sure
its acceptable.

We haven't regularly tested SAFECode and Automatic Pool Allocation on
64 bit architectures, so while it may work, we can't say for certain
that it will.

This particular error is caused by the fact that the run-time does not
know which allocator is best for allocating page-aligned sections of
memory. If you modify getPages() in
runtime/BitmapPoolAllocator/PageManager.cpp to use mmap(),
posix_memalign(), or valloc(), then it will fix this error and allow
you to continue experimenting with Poolalloc/SAFECode in 64-bit mode.

Why is that dependent on the architecture, and not the OS? mmap always
allocates page-aligned memory AFAIK, and its widely available (except
for win32).

Eventually, we should set up something in the configure script to find
a usable default for this function. This would be a simple autoconf
change; it just hasn't been high on the priority list.

I turned off Werror too because I was getting lots of aliasing violation
warnings (with g++ 4.3.4).
There are some "cast pointer to integer of different size" warnings, but
they're all in SVA, and thats the kernel stuff that has nothing to do
with safecode right?
  

Which code are you referring to? I don't believe any of the SVA
specific code is compiled by default in the mainline SAFECode tree.

The SVA runtime, see the buildlog I sent you:
/home/edwin/llvm2.6/llvm-2.6/projects/safecode/runtime/SVA/PoolCheck.c:66:
warning: cast from pointer to integer of different size

So I've built SAFEcode in a 32-bit chroot (I get the aliasing warnings
on 32-bit too).

A simple test program works, however when trying to compile ClamAV I get
an error right on startup, and it aborts!
The docs say that if I don't use terminate it should go on.
  

The -terminate option used to work but broke during some refactoring
of the error reporting code. Getting it to work again is on my TODO
list. You can get the behavior you want, for now, by removing the
abort() line from runtime/DebugRuntime/Report.cpp.

As far as the ClamAV error, are you sure it's a false positive (i.e.,
a bug in SAFECode)? I ran SAFECode on the programs in
MultiSource/Applications and found that quite a few programs have
memory safety errors.

One of the errors is in libltdl, the other one inside optparser in ClamAV.
Neither of these errors show up in valgrind, and mudflap.
That doesn't mean there is no error there, its just very unlikely.

Do you accept NULL as a parameter to free? If not that might the problem
here.

In the case of ClamAV, a false positive might occur if 1) the memory
object is allocated by a library linked in as native code, or 2) the
memory object is allocated via some C library function that SAFECode
doesn't recognize as an allocator (e.g., getenv() or getpwent()).
Handling the latter requires some simple changes to the DSA analysis
and SAFECode so that it treats these functions as allocators.

The allocation is:
opts->filename = (char **) calloc(argc - optind + 1, sizeof(char *));
opts->filename[i - optind] = strdup(argv[i]);

The free is this one (according to addr2line, assuming you are reporting
the address of the call):
free(opts->filename);

And it is this line (assuming you are reporting the return address, and
thus addr2line is one-off):
free(opts->filename[i]);

Nothing fancy here, standard libc allocations, my guess would be strdup.
Where is the list of allocator functions handled by DSA/SAFEcode?

However if I remove the abort as you suggest below, I get this:
SAFECode:Violation Type 0x2 when accessing 0xa1567e0 at IP=0x812892d

=======+++++++ SAFECODE RUNTIME ALERT +++++++=======
= Error type : Invalid Free Error
= Program counter : 0x812892d
= Faulting pointer : 0xa1567e0
clamscan_sc3:
/home/edwin/llvm2.6/llvm-2.6/projects/safecode/runtime/BitmapPoolAllocator/PoolAllocatorBitMask.cpp:378:
void __pa_bitmap_poolfree(safecode::BitmapPoolTy*, void*): Assertion `PS
&& "poolfree: No poolslab found for object!\n"' failed.
Aborted

SAFECode:Violation Type 0x2 when accessing 0x832d228 at IP=0x812b531

=======+++++++ SAFECODE RUNTIME ALERT +++++++=======
= Error type : Invalid Free Error
= Program counter : 0x812b531
= Faulting pointer : 0x832d228

Program received signal SIGABRT, Aborted.
0xf7fdf430 in __kernel_vsyscall ()
(gdb) bt
#0 0xf7fdf430 in __kernel_vsyscall ()
#1 0xf7d713d0 in raise () from /lib/i686/cmov/libc.so.6
#2 0xf7d74a85 in abort () from /lib/i686/cmov/libc.so.6
#3 0x08214227 in
safecode::ReportMemoryViolation(safecode::ViolationInfo const*) ()
#4 0xf7fccea0 in ?? () from /usr/lib/libstdc++.so.6
Backtrace stopped: previous frame inner to this frame (corrupt stack?)

I did compile ClamAV with -g, I even used -disable-opt for llvm-ld, but
I still don't see line number error there (according to the docs I
should).
  
Hrm. Yes. This seems to be a missing feature. I think I can add it
relatively easily.

Thanks.

$ ~/llvm2.6/obj32/projects/safecode/Release/bin/sc -rewrite-oob
clamscan.bc -o clamscan_sc3.bc
$ ~/llvm2.6/obj32/Release/bin/llc clamscan_sc3.bc -f
$ gcc -o clamscan_sc3 clamscan_sc3.s
~/llvm2.6/obj32/projects/safecode/Release/lib/libsc_dbg_rt.a
~/llvm2.6/obj32/projects/safecode/Release/lib/libpoolalloc_bitmap.a
-lstdc++ -lbz2 -pthread -lz ../libltdl/.libs/libltdlcS.o

And I've built ClamAV like this:
$ ./configure CC=llvm-gcc --disable-shared
$ make CPPFLAGS="-O2 -g -emit-llvm" CFLAGS=
CCLD="/home/edwin/llvm2.6/obj32/Release/bin/llvm-ld -disable-opt" -j8

If I use addr2line on the IP printed by SAFEcode, I get this, but I
don't see anything wrong there:
foreach_dirinpath
/home/edwin/clam/git/builds/sc/libltdl/../../../clamav-devel/libltdl/ltdl.c:717

If I use the system's libltdl I get an invalid freee error here:
optfree
/home/edwin/clam/git/builds/sc/clamscan/../../../clamav-devel/shared/optparser.c:612

Is there a way to disable these invalid free errors? They look like
false positives to me (valgrind doesn't report them).
  

Not currently. SAFECode should not have false positives. There is
either a real error in ClamAV or a bug in SAFECode.

Ok, in that case a flag to warn about unknown pointers would help: i.e.
warnings calls to native functions that DSA/SAFEcode doesn't know about
that can return a pointer (or create one in another way,
by filling a struct field for example). This could be a runtime warning
too, whenever you use something that could have been modified by native
code, if you stumble across a pointer
to an unknown memory zone: warn about it.

I can send you clamscan.bc (it is 2.3M gzipped) if you want to.
  

Let me first enhance the invalid free error reporting. That may help
you narrow down what SAFECode thinks the problem is and may help rule
out the possibility of a real memory error in ClamAV. After that, if
SAFECode is still reporting an error, and you can't figure out why, I
can add looking at the problem to my TODO list.

Thanks, linenumber for the error, and a stacktrace would help a lot.
Also saying why it is an invalid free would help:
- is it trying to free something that was already freed (in that case
were was the previous free)?
- is it trying to free something that was never allocated?
- is it trying to free a stack allocated object? (doesn't appear to be
the case here)

P.S.: should I send "bugs" like this to you directly, or report them on
LLVM bugzilla?
  

I think it's actually best to file bug reports for each individual
issue. That way, we can track their progress, and they won't get lost
in my email INBOX.

Thanks again for giving SAFECode a test drive. I'll try to get the
invalid free error reporting improved within the next day or two. If
you can let me know how to apply your patch (patch < patchfile isn't
working for me), that'd be great too.

Thanks again!

Thanks for making SAFEcode available.

Best regards,
--Edwin

[To_ro_k_Edwin]

My initial message (containing the patch) was a private reply to John.

Attached the patch again, it applies with 'patch -p0'.

Also try to build on x86-32, x86-64 is not quite ready yet.

Best regards,
--Edwin

patch (5.99 KB)

[John_Criswell2]

David Greene wrote:

  

[snip]

I applied the attached patch to make it compile on my box (Debian
x86_64), only to find out that x86_64 is not supported
This architecture is not supported by the pool allocator!
Aborted
      

Thanks for the patch. What options do I give to the patch command to
apply it to the source code?
    
Did I miss a message? I am getting tons of compiler errors building poolalloc
and safecode and am wondering if this patch would fix things.
  

What platform are you building on? What types of errors are you seeing? Edwin's patch will fix warnings for SAFECode on 64-bit platforms.

-- John T.

[John_Criswell2]

Török Edwin wrote:

  

[snip]

I applied the attached patch to make it compile on my box (Debian
x86_64), only to find out that x86_64 is not supported
This architecture is not supported by the pool allocator!
Aborted
      

Thanks for the patch. What options do I give to the patch command to
apply it to the source code?
    

Did I miss a message? I am getting tons of compiler errors building poolalloc
and safecode and am wondering if this patch would fix things.
  
My initial message (containing the patch) was a private reply to John.

Attached the patch again, it applies with 'patch -p0'.

Also try to build on x86-32, x86-64 is not quite ready yet.
  

Patch applied. Thanks!

-- John T.

[John_Criswell2]

[snip]

My initial message (containing the patch) was a private reply to John.

Attached the patch again, it applies with 'patch -p0'.

Also try to build on x86-32, x86-64 is not quite ready yet.
  

Actually, I made one small change to the patch. I kept -Werror in Makefile.common.in. It's better if we fix these warnings; -Werror provides incentive for that.

I'll consider removing it if there's a problem that's not trivially fixable.

-- John T.

[To_ro_k_Edwin]

That leaves us with the aliasing violations. I looked at the first, and
I couldn't tell why gcc (4.3.4) thinks it is wrong:
safecode/runtime/BitmapPoolAllocator/PoolAllocatorBitMask.cpp:185:
warning: dereferencing type-punned pointer will break strict-aliasing rules
Line 185 is: PS->addToList((PoolSlab**)&Pool->Ptr2);

and Ptr2 is a field of type void*. Isn't void* compatible with anything?

Best regards,
--Edwin

log (5.51 KB)

[John_McCall1]

Török Edwin wrote:

[snip]
    

My initial message (containing the patch) was a private reply to John.

Attached the patch again, it applies with 'patch -p0'.

Also try to build on x86-32, x86-64 is not quite ready yet.
  
      

Actually, I made one small change to the patch.  I kept -Werror in
Makefile.common.in.  It's better if we fix these warnings; -Werror
provides incentive for that.

I'll consider removing it if there's a problem that's not trivially
fixable.
    

That leaves us with the aliasing violations. I looked at the first, and
I couldn't tell why gcc (4.3.4) thinks it is wrong:
safecode/runtime/BitmapPoolAllocator/PoolAllocatorBitMask.cpp:185:
warning: dereferencing type-punned pointer will break strict-aliasing rules
Line 185 is: PS->addToList((PoolSlab**)&Pool->Ptr2);

and Ptr2 is a field of type void*. Isn't void* compatible with anything?
  

No. void* is convertible to an arbitrary pointer type (6.3.2.3p1):

A pointer to void may be converted to or from a pointer to any incomplete or object type. A pointer to any incomplete or object type may be converted to a pointer to void and back again; the result shall compare equal to the original pointer.

But the compatibility rules for pointers don’t mention void* (6.7.5.1p2):

For two pointer types to be compatible, both shall be identically qualified and both shall be pointers to compatible types.

Nor is there an exception carved out in 6.5p1.

Among other things, this permits null pointers to have different representations based on the element type, &c &c.

John.

[David_A_Greene]

I'm on a 64-bit Linux machine, SLES 10.1.

Here's what I see:

[x86_64-mod-dbg]: In file included
from /ptmp/dag/llvm-project.modified/llvm/trunk/projects/poolalloc/include/dsa/DSGraph.h:18,
[x86_64-mod-dbg]:
from /ptmp/dag/llvm-project.modified/llvm/trunk/projects/poolalloc/lib/DSA/Basic.cpp:16:
[x86_64-mod-dbg]: /ptmp/dag/llvm-project.modified/llvm/trunk/projects/poolalloc/include/dsa/DSNode.h:18:34:
error: llvm/Support/Streams.h: No such file or directory

Looks like if this gets fixed I will be in good shape.

I configured with:

cd /ptmp/dag/build.llvm.trunk.modified.debug/x86_64-unknown-linux-gnu

/ptmp/dag/llvm-project.modified/llvm/trunk/configure
--prefix=/tools/llvm-tools/llvm/install.trunk.modified.debug/x86_64-unknown-linux-gnu
--target=x86_64-unknown-linux-gnu --enable-assertions
--with-llvmgccdir=/tools/llvm-tools/llvm/install.trunk.modified.debug/x86_64-unknown-linux-gnu
--disable-jit --disable-threads
--with-llvmsrc=/ptmp/dag/llvm-project.modified/llvm/trunk
--with-llvmobj=/ptmp/dag/build.llvm.trunk.modified.debug/x86_64-unknown-linux-gnu

                                    -Dave

[John_Criswell2]

David Greene wrote:

[To_ro_k_Edwin]

Ok, then converting from void** to PoolSlab** can be done by going
through void* as an intermediary type?

The attached patch fixes the warnings.

BTW how do I run make check for SAFEcode? It says 'make[1]: Nothing to
be done for `check-local'' if I run make check.

Best regards,
--Edwin

patch (4.81 KB)

[John_McCall1]

Török Edwin wrote:

Ok, then converting from void** to PoolSlab** can be done by going
through void* as an intermediary type?
  
The violation is not in how you're converting the void** to a PoolSlab**. That array is forever and always an array of void*s, and no amount of conversion will make it not a strict-aliasing violation to load PoolSlab*s from it. All your patch is doing is introducing enough indirection to disable the warning.

The only ways to avoid the aliasing violation are to (1) have the array be a PoolSlab** in the first place or (2) actually read and write void*s from the array, casting to and from PoolSlab* as appropriate.

John.

[To_ro_k_Edwin]

In this case changing the field type from void* to PoolSlab* worked (I
don't know why it had to be a void* in the first place).
Now SAFEcode (excluding the SVA runtime which I disabled in my patch)
builds.

Best regards,
--Edwin

patch (1.99 KB)