[LLVMdev] [RFC] Simple control-flow integrity

[Peter Collingbourne]

On Fri, Apr 04, 2014 at 12:17:44PM -0700, Tom Roeder wrote:
> On Thu, Apr 3, 2014 at 7:44 PM, Peter Collingbourne <peter at pcc.me.uk> wrote:
> 
> > On Thu, Apr 03, 2014 at 06:54:55PM -0700, Reid Kleckner wrote:
> > > I think it's a little scary to assume things about LLVM's x86 code
> > > generation.  I haven't really finished the codegen side of the change,
> > but
> > > I'm pretty sure in it's current state it will emit extra loads and
> > stores,
> > > even if they are unnecessary.
> >
> 
> I have an implementation of my proposal that generates the right
> instructions and only those instructions. This is because of the other
> annotations on the jumptable function: optnone, noreturn, naked, and
> unwind. I've just posted my current version of the patch as
> http://llvm-reviews.chandlerc.com/D3292
> 
> 
> >
> > Right, I had similar concerns. Now that I've thought about it a little
> > more,
> > I think that representing the jump table entries as IR functions in any
> > form presents a risk that a change in code generation could endanger the
> > correctness of the CFI mechanism.
> >
> 
> I guess this boils down to the question of whether or not it's possible to
> insist on naked functions with no optimization. My jumptable intrinsic is
> guaranteed by the IR verifier constraints to be the only reachable IR
> instruction in the function at code-generation time.
> 
> Because this instruction is an intrinsic and only undergoes lowering to a
> jump to a symbol, and because the function is annotated with naked,
> optnone, noreturn, and nounwind, I believe that I have complete control
> over the instructions in that function, and that there will be no
> preamble/postamble. Are there mechanisms that can insert other code in
> these circumstances?
> 
> From a perusal of CodeGen, it looks like the attribute optnone translates
> to CodeGenOpt::None, which in turn seems to turn off lots of work that
> would otherwise be performed on the function.
> 
> I can certainly add test cases that make sure that no extra code is added
> now and that will break if anyone ever adds code that does this.

My concern was that some new combination of a signature or attributes might
cause the code generator to emit more instructions.

> > The other alternative we were thinking about was to put the responsibility
> > for
> > generating jump tables in the hands of the code generator using attributes
> > [1].  From a security perspective, I think that might be preferable since
> > the generation of the jump table would be tightly controlled.
> >
> 
> I see the value in terms of the security guarantees, though isn't it the
> case that other code could in principle be added to the function unless the
> jump-table generation was literally the last transform to run?
> 
> My concern about it is more to do with code duplication and maintainability
> for multiple backends. Consider the set of changes that the jump-table
> transformation does:
> 
> 1. find all address-taken functions
> 2. create a jump-table function for each one
> 3. replace all address-taking sites with the appropriate jump-table
> function address
> 3. ensure that the jump-table functions are compiled into a form that
> admits useful runtime checks
> 
> Most of this is not target-specific, and these are all very natural IR
> operations. And I want them to work at least for X86 and ARM (I currently
> support both with my inline asm version), and probably for other backends,
> too. The only target-specific step is the lowering of the jump-table
> intrinsic to its equivalent branch statement, and the only reason that this
> is target-specific is that there's no way to represent an unconditional
> jump to a function in IR. So, I'd really like to confine the
> target-specific code to exactly that lowering.

I discussed this offline with Tom; summarising our discussion for the list:

I mostly agree; I think you should be able to do 1-3 in a target independent
way, probably as a late IR pass. But I think 4 can be done very late,
probably in the asm printer. The streamer already has functionality for
creating labels and align statements; I'm not sure if there is a good target
independent way to emit a branch instruction, but you can probably add one.

> Note that there are CFI transformations that don't depend on the tightness
> of the jump table: e.g., if the check code just compares a given pointer
> against the start and the end functions in the table, then function section
> annotations would suffice, since that would guarantee that all and only
> jumptable functions would be in a given section. I would view the tightness
> of the jump table more as an optimization than as a requirement.

I was imagining that an attacker might be able to exploit an ability to jump
into the middle of an instruction in the jump table.

> It seems to me to be unnecessarily painful to have to fiddle with the
> lowering, e.g., of function symbols to their associated jump-table
> functions in the target backend because we don't want to represent the
> jump-table entries as functions at IR time.

My preliminary idea is that your late IR pass could create declarations
for the jump table functions; those functions would receive definitions
from the asm printer.

Peter

> 
> >
> > Peter
> >
> > [1] http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-March/071340.html
> >
> > >
> > >
> > > On Thu, Apr 3, 2014 at 6:28 PM, Peter Collingbourne <peter at pcc.me.uk>
> > wrote:
> > >
> > > > On Wed, Apr 02, 2014 at 05:28:04PM -0700, Tom Roeder wrote:
> > > > > On Fri, Mar 21, 2014 at 1:46 PM, Peter Collingbourne <
> > peter at pcc.me.uk
> > > > >wrote:
> > > > >
> > > > > > On Fri, Mar 21, 2014 at 12:54:07PM -0700, Tom Roeder wrote:
> > > > > > > On Fri, Mar 21, 2014 at 12:15 PM, Peter Collingbourne <
> > > > peter at pcc.me.uk>
> > > > > > wrote:
> > > > > > > >> The way I've implemented it (see the patch I sent to
> > llvm-commits
> > > > > > > >> yesterday), it's not just metadata: the intrinsic lowers to
> > the
> > > > > > > >> jumptable entry code given above. The CFI pass then generates
> > a
> > > > > > > >> function for each jump table; the function consists solely of
> > > > these
> > > > > > > >> intrinsic calls.
> > > > > > > >
> > > > > > > > Well, the intrinsic you proposed has no effect on the caller
> > and
> > > > has
> > > > > > > > non-local effects on other specified functions. I'm not aware
> > of
> > > > any
> > > > > > other
> > > > > > > > intrinsic with similar behavior.
> > > > > > >
> > > > > > > I agree that it's not very similar to other intrinsics. But I
> > don't
> > > > > > > exactly follow these statements. There are definitely intrinsics
> > that
> > > > > > > have no effect on the caller, like llvm.var.annotation.
> > > > > >
> > > > > > Yes but the purpose of such intrinsics is to communicate
> > information
> > > > about
> > > > > > a specific value that may have an effect on analysis, optimization
> > or
> > > > code
> > > > > > generation for that caller. On the other hand, the intrinsic you
> > are
> > > > > > proposing
> > > > > > has nothing to do with the caller.
> > > > > >
> > > > > > > And AFAIK,
> > > > > > > there is no non-local behavior: all the intrinsic does is lower
> > to
> > > > the
> > > > > > > labeled jump instruction; the changes to address-taken functions
> > are
> > > > > > > done separately by the CFI pass. Note that in the patch I sent,
> > the
> > > > > > > intrinsic only takes one argument: the function to jump to. Are
> > there
> > > > > > > other effects in this case?
> > > > > >
> > > > > > The non-local effect is that the intrinsic describes the
> > definition of
> > > > a
> > > > > > function in the global scope. Normally such definitions come from
> > > > top-level
> > > > > > entities.
> > > > > >
> > > > > > > So, maybe it would be better to call it something like
> > > > > > > @llvm.unconditional.jump(i8*)? I could then make it only lower
> > to the
> > > > > > > jump and add an intrinsic that lowered to a function label as
> > well.
> > > > > >
> > > > > > I'd imagine that might present more problems. For example, if you
> > used
> > > > > > either intrinsic in the middle of a regular function the behavior
> > > > would not
> > > > > > necessarily be well defined. It would be necessary to carefully
> > > > document
> > > > > > where and how these intrinsics may be used.
> > > > > >
> > > > >
> > > > > Taking these considerations into account, I propose this:
> > > > >
> > > > > Jump functions created for the jump table are actual functions,
> > marked
> > > > with
> > > > > a new jumptable attribute, as well as naked and noreturn and optnone.
> > > > Each
> > > > > table is put in a special section using the section attribute, and
> > > > > alignment of these functions is done using the align attribute. The
> > > > > combination of these attributes means that the function has no
> > preamble
> > > > or
> > > > > postamble, so it consists of exactly a global function label and its
> > > > > instructions.
> > > > >
> > > > > Then I think it would make sense to create an intrinsic like
> > > > > llvm.jumptable.instr(i8*) that would be a placeholder for an
> > > > unconditional
> > > > > jump. I can add code to the verifier that insists on two conditions:
> > > > >
> > > > > 1. functions marked as jumptable must have exactly two instructions:
> > an
> > > > > llvm.jumptable.instr followed by a unreachable.
> > > > > 2. llvm.jumptable.instr can only occur in a jumptable function.
> > > > >
> > > > > I think this handles the problem of using llvm.jumptable.instr in
> > normal
> > > > > functions: that isn't allowed. And I think it deals with the
> > problems of
> > > > > non-local behavior by making functions out of the things that really
> > are
> > > > > functions. Each entry in the jump table really is a function, albeit
> > a
> > > > > rather strange one, so it should look like a function at the IR
> > level.
> > > > >
> > > > > In other words, this change would add a new attribute that marks a
> > very
> > > > > specialized kind of function and an intrinsic that can only occur in
> > this
> > > > > kind of function.
> > > > >
> > > > > What do you think?
> > > >
> > > > I think you might be close.
> > > >
> > > > The llvm.jumptable.instr intrinsic you have proposed is similar to the
> > > > 'musttail' call marker that Reid (cc'd) is working on in [1]. That
> > marker
> > > > will
> > > > also have verifier support. I think it might be reasonable to require
> > the
> > > > code generator to emit the body of a function containing only a
> > 'musttail'
> > > > function call as a single branch instruction. Then you could emit such
> > > > functions in the jump table section.
> > > >
> > > > Reid, what do you think?
> > > >
> > > > Thanks,
> > > > --
> > > > Peter
> > > >
> > > > [1] http://llvm-reviews.chandlerc.com/D3240
> > > >
> >
> > --
> > Peter
> >

-- 
Peter