[LLVMdev] [RFC] Simple control-flow integrity

[Joerg Sonnenberger]

On Tue, Feb 11, 2014 at 09:12:03AM -0800, Reid Kleckner wrote:
> > On Mon, Feb 10, 2014 at 03:33:32PM -0800, Tom Roeder wrote:
> > >     3. adds a fast check for pointer safety at each indirect call site:
> >
> > Why not using a bloom filter for valid target addresses instead?
> >
> 
> Can a bloom filter be as fast as a simple bounds check?  I'm thinking lea
> base, sub, cmp, jl, and cold call.

Depends. The potential issue with the "jump table" approach is code
size -- as written, at least 64bit for every potential target. If you
want to include virtual functions in that list it will grow very large.
A decently working bloom filter would need in the order of 1 or 2 bits
per potential target, making the chance of fitting into cache quite a
bit larger. A basic hash function as candidate would be "and size" for
the first filter and "mul with constant; and size" for the second,
followed by a bit test for each. On modern CPUs the mul is quite cheap,
so the trade off is more or less one memory access vs two.

Joerg