Page MenuHomePhabricator

Insert random noops to increase security against ROP attacks (llvm)
ClosedPublic

Authored by rinon on Apr 15 2014, 10:57 PM.

Details

Reviewers
yln
ahomescu
jfb
Summary

A pass that adds random noops to X86 binaries to introduce diversity with the goal of increasing security against most return-oriented programming attacks.

Command line options:

-noop-insertion // Enable noop insertion.
-noop-insertion-percentage=X // X% of assembly instructions will have a noop prepended (default: 50%, requires -noop-insertion)
-max-noops-per-instruction=X // Randomly generate X noops per instruction. ie. roll the dice X times with probability set above (default: 1). This doesn't guarantee X noop instructions.

In addition, the following 'quick switch' in clang enables basic diversity using default settings (currently: noop insertion and schedule randomization; it is intended to be extended in the future).

-fdiversify

This is the llvm part of the patch.
clang part: D3393

Diff Detail

Event Timeline

jfb added inline comments.Apr 17 2014, 4:04 PM
include/llvm/CodeGen/CommandFlags.h
209

I'd like to have a better description of what NOP insertion achieves security-wise, and why it's pretty more useful on architectures that have variable instruction size encoding. I'm not sure the description string is the best location, but I'm not sure where else to put it either.

The goal would be to allow users of the option to understand what they're getting out of it.

include/llvm/Target/TargetOptions.h
155

Same as above, I'd explain what NOP insertion is a bit more (though I wouldn't repeat the entire thing here): target developers probably want to know what this is.

lib/LTO/LTOCodeGenerator.cpp
144 ↗(On Diff #8557)

Keep the same order as the bitfield above (so bump up one line).

lib/Target/X86/CMakeLists.txt
16 ↗(On Diff #8557)

You should keep the naming consistency and prefix with X86.

lib/Target/X86/NOPInsertion.cpp
34 ↗(On Diff #8557)

You should probably check that this isn't greater than 100.

40 ↗(On Diff #8557)

It would be nice to add a "code randomization" command-line category (cl::cat), and add all the options to it (so, share the category between all the files).

84 ↗(On Diff #8557)

I think you could instead use X86AsmBackend::writeNopData.

It's actually part of the "generic" MC stuff that all backends should implement, so in theory you could make this pass not x86 specific. I think that would be better :-)

jfb added inline comments.Apr 17 2014, 4:09 PM
lib/Target/X86/NOPInsertion.cpp
99 ↗(On Diff #8557)

This will access thread-local storage each time you try to insert a NOP. Could you instead access the RNG once in the class' construction, so you don't go through TLS?

103 ↗(On Diff #8557)

Same on TLS.

ahomescu added inline comments.Apr 17 2014, 4:18 PM
lib/Target/X86/NOPInsertion.cpp
84 ↗(On Diff #8557)

The NOPs we use are hand-picked to not be usable as ROP gadgets, starting from either the first or second byte of the NOP (or at worst to be harmless). Trying to jump to the middle of a NOP should crash the program. writeNopData uses the canonical Intel NOPs, some of which do contain unsafe sequences (for example, 0x00 could be used by attackers as an ADD).

jfb added inline comments.Apr 17 2014, 4:27 PM
lib/Target/X86/NOPInsertion.cpp
84 ↗(On Diff #8557)

Clever, this reminds me of:

http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20130114/162349.html

You definitely need to explain this.

I would still like this patch to work on other architectures though. Do you think that you could use the writeNopData mechanic and add this cleverness to it, maybe just on the x86 side for now? That way "fast" nops can be inserted everywhere as before, but "secure" nops can also be inserted in backends that support it.

rinon added inline comments.Apr 18 2014, 11:21 AM
lib/Target/X86/NOPInsertion.cpp
99 ↗(On Diff #8557)

Well, we do need an independent random number for each choice. However, we might be able to initialize a new RNG using a single seed in the constructor. I think this would actually introduce more overhead than just the TLS, but I'd have to actually test that I guess.

jfb added inline comments.Apr 18 2014, 11:46 AM
lib/Target/X86/NOPInsertion.cpp
99 ↗(On Diff #8557)

I just mean that RandomNumberGenerator::Get() can be cached to avoid TLS. The call to Random would still be in the loop.

rinon added inline comments.Apr 18 2014, 12:00 PM
lib/Target/X86/NOPInsertion.cpp
99 ↗(On Diff #8557)

Oh of course. I'm completely silly. Definitely, thanks.

jfb added inline comments.Apr 18 2014, 12:29 PM
lib/Target/X86/NOPInsertion.cpp
99 ↗(On Diff #8557)

From our other discussion it sounds like the RNG will be per Module. Each LLVM Module can't be associated with more that one thread right now, so it would probably be better to just move the RNG to Module and avoid all the global static TLS stuff.

yln added inline comments.May 15 2014, 11:15 AM
lib/Target/X86/NOPInsertion.cpp
34 ↗(On Diff #8557)

Just to be sure: Can this be done declaratively? Cannot find it in the docs.
Or do you mean in code?

ahomescu added inline comments.May 15 2014, 1:38 PM
lib/Target/X86/NOPInsertion.cpp
34 ↗(On Diff #8557)

I'm not sure how to sanely handle invalid inputs here. The current approach is to silently ignore all errors (such as >100 or <0 percentage; any percentage larger than 100 winds up being the same as 100 anyway). One alternative is to check at runtime (in the NOP insertion pass) and abort compilation if the value is invalid, but that seems too severe to me. Do we want an invalid parameter to cause compilation to fail?

jfb added inline comments.May 19 2014, 1:28 PM
lib/Target/X86/NOPInsertion.cpp
34 ↗(On Diff #8557)

It does indeed look like you'd need to inherit from Parser<...> and implement a parse method that calls the parent's and the does the range check. Probably not worth it in this patch. If values get auto-clamped to [0,100] then that's good enough.

rinon commandeered this revision.Aug 22 2014, 4:01 PM
rinon edited edge metadata.
rinon edited reviewers, added: yln; removed: rinon.
rinon added a subscriber: Unknown Object (MLST).

Since Julian is on an internship, I'm commandeering this patch to move things along.

rinon updated this revision to Diff 12865.Aug 22 2014, 4:19 PM
rinon edited edge metadata.
  • Update to new RNG API.
  • Make NOP insertion target-independent
rinon updated this revision to Diff 12866.Aug 22 2014, 4:35 PM
  • Fix test cases for use with new RNG.
rinon updated this revision to Diff 12867.Aug 22 2014, 4:37 PM

Setting parent revision to current RNG API.

I hope this works...

rinon added a comment.Aug 22 2014, 4:41 PM

Well, apparently I can't convince arcanist to only show the changes I want... However, the latest revision is based off the latest revision of D4377, and does not include the scheduling randomization patches (not sure how they got into the diffs, sorry...).

jfb added inline comments.Aug 23 2014, 12:15 PM
include/llvm/CodeGen/NOPInsertion.h
26 ↗(On Diff #12867)

You probably want to add the virtual dtor too.

28 ↗(On Diff #12867)

override

lib/CodeGen/NOPInsertion.cpp
71 ↗(On Diff #12867)

Use the new C++11 syntax, here and in other parts of this patch.

83 ↗(On Diff #12867)

Do fix :)

lib/Target/X86/X86InstrInfo.cpp
5546

I'd like to have an explanation of these clever NOPs, it's not obvious from the source.

5548

You should fix this distribution too.

test/CodeGen/X86/nop-insert-percentage.ll
5 ↗(On Diff #12867)

Also add tests for x86-32 (same below).

ahomescu added inline comments.Sep 8 2014, 11:45 PM
lib/CodeGen/NOPInsertion.cpp
89 ↗(On Diff #12867)

This looks inconsistent: LLVM has uses "Noop" but we use "NOP". For consistency's sake, maybe we should change ours to "Noop" everywhere (I picked "NOP" to match the x86 instruction, don't know about other architectures).

rinon updated this revision to Diff 17511.Dec 19 2014, 1:36 PM
  • Rebase with new RNG
  • Address review comments.
rinon added a comment.Dec 19 2014, 1:39 PM

I think the previous revision addresses all existing comments.

  • NOP is now Noop in all places
  • Proper uniform probability distribution is now used
  • C++11 features used where applicable
  • RNG upgraded to be compatible with C++11 uniform distributions
rinon added a reviewer: jfb.Dec 19 2014, 1:51 PM
jfb edited edge metadata.Dec 19 2014, 4:08 PM

Same thing as on the clang side on updating the description to "noop".

Can you explain why the default values that you chose are the right ones? I think that out of the box the -fdiversity flag should provide the "right" defaults, for some "right" that you get to define.

Please run clang-format over the new code.

It would be good to have a new test which exercise x86-32 and architectures which implement insertNoop (Mips, PowerPC, R600), to make sure these work. It would be good to add ARM and Aarch64 to that list, but that can be a different patch.

include/llvm/CodeGen/NoopInsertion.h
31

override

35

The above 2 can be private or protected.

38

nullptr. Can you also make this a std::unique_ptr?

include/llvm/Support/RandomNumberGenerator.h
34

RNG::result_type

47

I think constexpr still isn't usable in LLVM, so this may have to be LLVM_CONSTEXPR from llvm/Support/Compiler.h.

60

typedef std::mt19937_64 RNG and use it here as well as for min, max, and result_type.

include/llvm/Target/TargetInstrInfo.h
875

Remove RNG here, since it isn't used (keep just RandomNumberGenerator*).

lib/CodeGen/NoopInsertion.cpp
65

Remove when using std::unique_ptr.

85

No need to comment range-based for loop.

86
for (MachineBasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) {

Can you also end at FirstTerm, and remove the break below?

105

This may not have inserted a noop, you should return false in that case. You could just track the number of inserted noops in the loop, and update InsertedNoops here, and return whether the local version was non-zero.

lib/Target/X86/X86InstrInfo.cpp
5536

Please explain *why* they're not useful as ROP gadgets. The landmine concept isn't obvious from the code, and the length of each nop presumably also matters.

5550

No need to be static since this class has no data members.

rinon retitled this revision from Insert random NOPs to increase security against ROP attacks (llvm) to Insert random noops to increase security against ROP attacks (llvm).Dec 29 2014, 12:46 PM
rinon updated this object.
rinon edited edge metadata.
rinon updated this revision to Diff 17699.Dec 29 2014, 4:39 PM
  • Use a unique_ptr for the RNG
  • Simplify RNG type reuse
  • Expanded X86 NOP comments
  • Add 32 bit X86 Noop Insertion tests
  • Formatting
  • Noop insertion tests for MIPS and PPC.
rinon updated this revision to Diff 17701.Dec 29 2014, 5:00 PM
  • Update default NOOP insertion rate
rinon added a comment.Dec 29 2014, 5:03 PM

@jfb: I think I've addressed all of your feedback. Thank you so much, was really useful. I tend to forget about the shiny new C++11 things.

I've set the default for NOOP insertion to be 25%. In our research we have empirically found this to result in the largest disruption of gadgets for the least performance impact.

jfb added a comment.Dec 30 2014, 12:03 AM

A few nits, looks good to me otherwise. Please leave this open for a short while, as folks may not have seen this over the holidays.

I'm looking forward to the next patches on diversity :-)

lib/CodeGen/NoopInsertion.cpp
77

I'd drop this comment since it's a common LLVM-ism.

lib/Target/X86/X86InstrInfo.cpp
5545

"privileged"

Interesting side-question (may just require a TODO or a bug filed): some folks are experimenting with using LLVM as a compiler for the Linux kernel, or for bare-metal boards. Are these instructions dangerous in these circumstances?

5555

Missing clang-format.

test/CodeGen/Mips/noop-insert.ll
12

You should use CHECK-NEXT and SEED1-NEXT for all but the first, and also check for ret (otherwise the CHECK case is a subset of the SEED1 case since it stops matching early).

Same comment for the others.

rinon updated this revision to Diff 17815.Jan 5 2015, 2:59 PM
  • Revert loop termination back to include insertion slot before terminators.
  • Fix spelling
  • Update tests to reflect new default insertion percentage.
  • Formatting fixes
rinon added inline comments.Jan 5 2015, 3:20 PM
lib/Target/X86/X86InstrInfo.cpp
5545

The privileged instructions are to read raw input from hardware, which I doubt would be substantially useful in an attack on OS code. Would be far easier to construct a code-reuse attack to call higher-level functions in the kernel to talk to hardware. As long as NOOPs are randomly chosen and placed, reliably exploiting NOOPs should be difficult.

Hi,

I don’t have much background on this topic, but I’m interested to understand how inserting a random number of noops help addressing ROP attacks. Do you have a link that explains this “counter-measure”?

Thanks,

Mehdi

Hi Stephen,

I think my comment was lost in the rather long discussion about the merit of this technique, so I ask again:

Independently of the randomization aspect, I think that the compiler should be able to deterministically get rid of the situation shown Figure 2 in https://www.ics.uci.edu/~ahomescu/multicompiler_cgo13.pdf ; i.e. when a gadget is formed by jumping in the middle of an instruction encoding. The compiler could break it by inserting a nop in these case. Now I’m not sure if it is easy to identify these cases from the assembly code or if it has to be done on the binary code itself?


Mehdi

jfb accepted this revision.Jan 13 2015, 5:10 PM
jfb edited edge metadata.

r225908

This revision is now accepted and ready to land.Jan 13 2015, 5:10 PM
jfb closed this revision.Jan 13 2015, 5:10 PM