[LLVMdev] [RFC] Simple control-flow integrity

[Tom Roeder]

Following up: Peter and I just discussed this at slightly higher bandwidth.
We agreed that I'd look into doing the emission directly in the AsmPrinter:
given that the jump tables really work best with a particular structure, it
makes sense to emit them as a single unit and not trust to the vagaries of
the underlying target mechanisms. This should still lead to most of the
work being done in IR; I'll modify the targets to support emitting an
unconditional branch during the assembly-generation process and add some
code to the AsmPrinter to use that to emit the tables properly.

Tom


On Fri, Apr 4, 2014 at 12:17 PM, Tom Roeder <tmroeder at google.com> 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.
>
>
>
>>
>> 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.
>
> 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.
>
> 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.
>
>
>>
>> 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
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140404/095109a5/attachment.html>