[llvm-dev] Runtime interception: design problem

[John Criswell via llvm-dev]

On 5/26/16 3:57 AM, Pierre Gagelin wrote:
> Hi John,
>
> On 25 May 2016 at 16:11, John Criswell <jtcriswel at gmail.com 
> <mailto:jtcriswel at gmail.com>> wrote:
>
>     Dear Pierre,
>
>     Stepping up a level, what is your goal in replacing calls to
>     malloc() and free()?  Is it any different than what SAFECode,
>     SoftBound, or ASan do?
>
>
> That's a good question. I didn't knew about SoftBound until now, so 
> thank you for the name =). Anyway here is what I know:
>   - ASan is a shadow-based memory protection, which allows accesses to 
> an addressable field
>   - I don't know every aspects of SAFECode. What I looked at was 
> BaggyBoundsCheck which is an object based memory protection. In this 
> way it still allows wild accesses inside an allocation

I wouldn't all them "wild," but yes, object-referent approaches 
(Jones-Kelley, Ruwase-Lam, SAFECode, WIT) will allow bound overflows in 
arrays embedded within structures so long as they don't leave the memory 
object.  That said, the original SAFECode (with automatic pool 
allocation) had provably sound operational semantics (see Dinakar 
Dhurjati's PLDI 2006 paper).


>   - I quickly looked at SoftBound and it does protect the memory at a 
> precise level. However metadata is separately stored which involve 
> higher overhead

One of the things that makes memory safety in C so expensive is that a) 
pointers can point into the middle of objects and b) the original C 
design doesn't make it easy to take a pointer and determine into which 
object it points.  This leads to the two primary memory safety designs: 
referent objects (which tracks metadata separately from pointers) and 
FAT pointers (which expand the pointer representation so that each 
pointer contains both base and bounds information to its referent object 
(or sub-object)).  Each one has advantages or disadvantages.


>
> My point is BoundsChecking has been designed (by Nuno Lopes) to be a 
> very low overhead checking tool. For the moment no runtime have been 
> implemented and I wanted to do a lightweight one on it (I am just a 
> student so even for the personal experience I'm interested). The 
> runtime would be necessary to solve the actual problem of 
> inter-procedural checks.

Nuno's BoundsChecking trades completeness for speed; it only does a 
bounds check when the bounds information can be easily found though 
local analysis (e.g., the malloc() and pointer arithmetic operation 
occur within the same function).

Once you go inter-procedural, things get messy as you may not have the 
bounds information for a pointer readily available in the function doing 
the memory access.  That's when you start either having to look up 
metadata about a pointer's referent object (SAFECode) or transforming 
the program to pass bounds information on pointers (SoftBound).  Either 
way, you hit the performance problems and have to deal with them.

My overall impression is that high speed memory safety (sans new 
hardware support) won't be *really* fast without strong analysis. The 
original SAFECode got its speed using points-to analysis, 
type-inference, and the automatic pool allocation transformation and 
could elide load/store checks.  The challenge, IMHO, is making these 
analyses simple enough to be maintainable or useful enough for 
optimization that the maintenance burden can be spread among a larger 
group of interested people.


>
> As said I haven't strong basis on the topic so any suggestion is 
> welcome. However I know there are several criteria a program can't all 
> match together like effectiveness, memory use, compatibility...

The memory safety menagerie (http://sva.cs.illinois.edu/menagerie/) 
contains a list of papers on memory safety attacks and defenses.  As I 
left Illinois about two years ago, I've let its maintenance slide, so 
there are some papers (notably the "Eternal War in Memory" paper) that 
aren't listed.  If I get time this summer, I'll try to get that web site 
updated.

Regards,

John Criswell

-- 
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
http://www.cs.rochester.edu/u/criswell

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160526/1ffa1fba/attachment.html>