[LLVMdev] [RFC] Simple control-flow integrity

Mon Feb 10 16:22:43 PST 2014

Hi Tom,

The PNaCl team is very interested in your work. We see 3 applications
for our purpose:
 - Augment the safety of our trusted code base, which includes OS
shims as well as NaCl validators.
 - Apply extra CFI to the PNaCl translator. The PNaCl translator
already runs inside a NaCl SFI sandbox (which include CFI), but this
sandboxing just ensure that the code doesn't escape the sandbox, it
doesn't guarantee that the translator is doing the right thing. Adding
your CFI on top is nice because it captures some semantic information
from the original LLVM source, and makes it that much harder to
exploit a bug in LLVM to generate malicious code (which still needs to
pass NaCl validation, so it's an extra defense-in-depth layer).
 - Optionally apply your CFI to user applications which opt-in.

Some of the concerns you express won't affect our platform since we
link everything statically and avoid passing raw pointer when
possible.

A few questions:
 - Have you tried running your CFI on LLVM itself? Did you need to add
any annotations?
 - What is the performance and size hit on different applications?

JF

On Mon, Feb 10, 2014 at 3:33 PM, Tom Roeder <tmroeder at google.com> wrote:
> Hi everyone,
>
> I've been working on control-flow integrity (CFI) techniques over
> LLVM, and I'd like to get feedback on these techniques and their
> potential usefulness as a part of LLVM. I'd like to submit some
> patches for this; I've implemented a version of it, and I've applied
> it to large, real-world programs like Chromium to see how well it
> holds up in practice.
>
>
> TL;DR: my CFI pass builds jump tables and adds a fast check to
> indirect calls; values that fail the check are passed to a function
> defined at compile time. I have added special analysis and
> source-level annotations to help deal with the problems of external
> function pointers.
>
>
>
> Details:
>
> My current implementation works as a pass over a single module
> consisting of all the code that the compiler has at LTO time. At the
> IR level, this pass:
>
>     1. creates a power-of-two sized InlineAsm jump table (or multiple
> jump tables) filled with jump instructions to each address-taken
> function.
>
>     2. replaces each such address-taken function with a pointer to the
> corresponding location in the appropriate table. Note that these will
> be valid function pointers for the purposes of external code.
>
>     3. adds a fast check for pointer safety at each indirect call site:
>
>          a. It forces the pointer into the appropriate table (based on
> type information), and checks to see if the pointer changed. Pointers
> that were already in the right table will not change, and all other
> pointers will. We rewrite the pointer either by masking and adding to
> a base pointer, if we can guarantee sufficient table alignment,
> otherwise by subtracting from a base, then masking, then adding back
> to the base.
>
>          b. If the pointer fails the check, it's passed to a CFI
> failure function defined at compile time to handle it. By default, we
> define a function written in IR; this function prints out the name of
> the function in which the CFI violation happens.
>
>
>
>
> The biggest challenge for such an implementation is functions that are
> neither declared nor defined at LTO time. These functions are false
> positives for the CFI check. They can occur in at least 3 ways:
>
>     - JIT code, like in the v8 javascript engine, can allocate and
> call functions that were not defined at compile time. These functions
> are not even external: they just didn’t exist at LTO time.
>
>     - External functions can return pointers to external functions
> that were not exposed at LTO time. The canonical example in this class
> is dlsym, which is used extensively by many projects. Other commonly
> used cases are signal/sigaction (returns the old signal handler),
> XSetErrorHandler from X, and std::set_new_handler from the Standard
> C++ library. But this happens with any dynamically-linked library that
> has a method that returns function pointers.
>
>     - Internal code that takes function pointer arguments can be
> passed to external code and have external function pointers passed to
> it as arguments. This pattern is used extensively by graphics
> libraries, e.g., gtk.
>
>
>
>
> I have some techniques that help handle these false positives:
>
>     - Since CFI violations are passed to an arbitrary function, the
> policy for these violations can be set at compile time. For example,
> you could run the rewritten code for a while to build up a set of
> known false positives, then switch to a CFI failure function that
> stopped when it saw something not allowed by the policy. This is
> similar to the approach taken by, e.g., AppArmor.
>
>     - my current CFI pass looks for special annotations added to the
> source code: these are of the form
> __attribute__((annotate("cfi-maybe-external"))) and
> __attribute__((annotate("cfi-no-rewrite")))
>
>          - cfi-maybe-external can be applied to pointers and variables
> (llvm.ptr.annotation and llvm.var.annotation) and means that this
> value sometimes stores external function pointers.
>
>          - cfi-no-rewrite is applied to functions and means that there
> are indirect calls in this function that can happen with external
> function pointers. The current implementation skips rewriting for
> these functions, but it could instead be used to prepopulate a list of
> known potential false positives.
>
>     - I have a separate analysis pass called ExternalFunctionAnalysis
> that does a fairly naive interprocedural dataflow analysis starting
> from cfi-maybe-external annotations and from all places where it can
> find external function pointers coming in to the module:
>
>           - if an external function pointer flows into a store that
> doesn't flow from an annotated location, then the pass prints a
> warning
>
>           - all indirect call sites that flow from annotated
> pointers/variables are not rewritten (but this could be used instead
> to prepopulate a whitelist of known false positives instead).
>
>
>
> As I mentioned, I've used my current implementation to build a version
> of Chromium protected with this form of CFI; in the process, I added
> sufficient annotations to the Chromium code base to catch all false
> positives (or at least: I haven't seen any in my testing so far). I've
> also tried it out with other, less immense, projects, like the SPEC
> CPU2006 benchmark suite.
>
> Please let me know what you think.
>
> Thanks,
>
> Tom
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev