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

[rinon]

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

[jfb]

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]

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]

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]

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]

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]

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]

lib/Target/X86/NOPInsertion.cpp

99 ↗

(On Diff #8557)

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

[jfb]

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]

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]

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]

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]

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

[rinon]

• Update to new RNG API.
• Make NOP insertion target-independent

[rinon]

• Fix test cases for use with new RNG.

[rinon]

Setting parent revision to current RNG API.

I hope this works...

[rinon]

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]

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]

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]

• Rebase with new RNG
• Address review comments.

[rinon]

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

[jfb]

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]

• 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]

• Update default NOOP insertion rate

[rinon]

@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]

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]

• Revert loop termination back to include insertion slot before terminators.
• Fix spelling
• Update tests to reflect new default insertion percentage.
• Formatting fixes

[rinon]

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.

[mehdi_amini]

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

[mehdi_amini]

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]

r225908

include/llvm/CodeGen/CommandFlags.h

 cl::opt<bool> DataSections("data-sections",
                            cl::desc("Emit data into separate sections"),
                            cl::init(false));
 
 cl::opt<bool>
 FunctionSections("function-sections",
                  cl::desc("Emit functions into separate sections"),
                  cl::init(false));
 
+cl::opt<bool>
+NoopInsertion("noop-insertion",
+             cl::desc("Randomly add Noop instructions to create fine-grained "
+                      "code layout diversity."),
+             cl::init(false));
+
 cl::opt<llvm::JumpTable::JumpTableType>
 JTableType("jump-table-type",
           cl::desc("Choose the type of Jump-Instruction Table for jumptable."),
           cl::init(JumpTable::Single),
           cl::values(
               clEnumValN(JumpTable::Single, "single",
                          "Create a single table for all jumptable functions"),
               clEnumValN(JumpTable::Arity, "arity",
static inline TargetOptions InitTargetOptionsFromCodeGenFlags() {
   Options.GuaranteedTailCallOpt = EnableGuaranteedTailCallOpt;
   Options.DisableTailCalls = DisableTailCalls;
   Options.StackAlignmentOverride = OverrideStackAlignment;
   Options.TrapFuncName = TrapFuncName;
   Options.PositionIndependentExecutable = EnablePIE;
   Options.UseInitArray = !UseCtors;
   Options.DataSections = DataSections;
   Options.FunctionSections = FunctionSections;
+  Options.NoopInsertion = NoopInsertion;
 
   Options.MCOptions = InitMCTargetOptionsFromFlags();
   Options.JTType = JTableType;
   Options.FCFI = FCFI;
   Options.CFIType = CFIType;
   Options.CFIEnforcing = CFIEnforcing;
   Options.CFIFuncName = CFIFuncName;
 
   Options.ThreadModel = TMModel;
 
   return Options;
 }
 
 #endif

include/llvm/CodeGen/NoopInsertion.h

+//===-- NoopInsertion.h - Noop Insertion ------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass adds fine-grained diversity by displacing code using randomly
+// placed (optionally target supplied) Noop instructions.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_NOOPINSERTION_H
+#define LLVM_CODEGEN_NOOPINSERTION_H
+
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include <random>
+
+namespace llvm {
+
+class RandomNumberGenerator;
+
+class NoopInsertion : public MachineFunctionPass {
+public:
+  static char ID;
+
+  NoopInsertion();
+
+private:
+  bool runOnMachineFunction(MachineFunction &MF) override;
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+
+  std::unique_ptr<RandomNumberGenerator> RNG;
+
+  // Uniform real distribution from 0 to 100
+  std::uniform_real_distribution<double> Distribution =
+      std::uniform_real_distribution<double>(0, 100);
+};
+}
+
+#endif // LLVM_CODEGEN_NOOPINSERTION_H

include/llvm/CodeGen/Passes.h

/// MachineDominanaceFrontier - This pass is a machine dominators analysis pass.
   /// bundles (created earlier, e.g. during pre-RA scheduling).
   extern char &FinalizeMachineBundlesID;
 
   /// StackMapLiveness - This pass analyses the register live-out set of
   /// stackmap/patchpoint intrinsics and attaches the calculated information to
   /// the intrinsic for later emission to the StackMap.
   extern char &StackMapLivenessID;
 
+  /// NoopInsertion - This pass adds fine-grained diversity by displacing code
+  /// using randomly placed (optionally target supplied) Noop instructions.
+  extern char &NoopInsertionID;
+
   /// createJumpInstrTables - This pass creates jump-instruction tables.
   ModulePass *createJumpInstrTablesPass();
 
   /// createForwardControlFlowIntegrityPass - This pass adds control-flow
   /// integrity.
   ModulePass *createForwardControlFlowIntegrityPass();
 } // End llvm namespace
 

include/llvm/InitializePasses.h

 void initializeMemCpyOptPass(PassRegistry&);
 void initializeMemDepPrinterPass(PassRegistry&);
 void initializeMemoryDependenceAnalysisPass(PassRegistry&);
 void initializeMergedLoadStoreMotionPass(PassRegistry &);
 void initializeMetaRenamerPass(PassRegistry&);
 void initializeMergeFunctionsPass(PassRegistry&);
 void initializeModuleDebugInfoPrinterPass(PassRegistry&);
 void initializeNoAAPass(PassRegistry&);
+void initializeNoopInsertionPass(PassRegistry&);
 void initializeObjCARCAliasAnalysisPass(PassRegistry&);
 void initializeObjCARCAPElimPass(PassRegistry&);
 void initializeObjCARCExpandPass(PassRegistry&);
 void initializeObjCARCContractPass(PassRegistry&);
 void initializeObjCARCOptPass(PassRegistry&);
 void initializePAEvalPass(PassRegistry &);
 void initializeOptimizePHIsPass(PassRegistry&);
 void initializePartiallyInlineLibCallsPass(PassRegistry&);

include/llvm/Support/RandomNumberGenerator.h

 /// A random number generator.
 ///
 /// Instances of this class should not be shared across threads. The
 /// seed should be set by passing the -rng-seed=<uint64> option. Use
 /// Module::createRNG to create a new RNG instance for use with that
 /// module.
 class RandomNumberGenerator {
 public:
+  typedef std::mt19937_64 RNG;
+  typedef RNG::result_type result_type;
+
   /// Returns a random number in the range [0, Max).
-  uint_fast64_t operator()();
+  result_type operator()();
+
+  // Must define min and max to be compatible with URNG as used by
+  // std::uniform_*_distribution
+  static LLVM_CONSTEXPR result_type min() {
+    return RNG::min();
+  }
+  static LLVM_CONSTEXPR result_type max() {
+    return RNG::max();
+  }
 
 private:
   /// Seeds and salts the underlying RNG engine.
   ///
   /// This constructor should not be used directly. Instead use
   /// Module::createRNG to create a new RNG salted with the Module ID.
   RandomNumberGenerator(StringRef Salt);
 
   // 64-bit Mersenne Twister by Matsumoto and Nishimura, 2000
   // http://en.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine
   // This RNG is deterministically portable across C++11
   // implementations.
-  std::mt19937_64 Generator;
+  RNG Generator;
 
   // Noncopyable.
   RandomNumberGenerator(const RandomNumberGenerator &other)
       LLVM_DELETED_FUNCTION;
   RandomNumberGenerator &
   operator=(const RandomNumberGenerator &other) LLVM_DELETED_FUNCTION;
 
   friend class Module;
 };
 }
 
 #endif

include/llvm/Target/TargetInstrInfo.h

 class LiveVariables;
 class MCAsmInfo;
 class MachineMemOperand;
 class MachineRegisterInfo;
 class MDNode;
 class MCInst;
 struct MCSchedModel;
 class MCSymbolRefExpr;
+class RandomNumberGenerator;
 class SDNode;
 class ScheduleHazardRecognizer;
 class SelectionDAG;
 class ScheduleDAG;
 class TargetRegisterClass;
 class TargetRegisterInfo;
 class BranchProbability;
 class TargetSubtargetInfo;
bool ReverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const {
     return true;
   }
 
   /// insertNoop - Insert a noop into the instruction stream at the specified
   /// point.
   virtual void insertNoop(MachineBasicBlock &MBB,
                           MachineBasicBlock::iterator MI) const;
 
+  /// insertNoop - Insert a type of noop into the instruction stream at the
+  /// specified point to introduce fine-grained diversity. A target may randomly
+  /// choose from a pool of valid noops using the provided RNG.
+  virtual void insertNoop(MachineBasicBlock &MBB,
+                          MachineBasicBlock::iterator MI,
+                          RandomNumberGenerator&) const {
+    insertNoop(MBB, MI);
+  }
 
   /// Return the noop instruction to use for a noop.
   virtual void getNoopForMachoTarget(MCInst &NopInst) const;
 
 
   /// isPredicated - Returns true if the instruction is already predicated.
   ///
   virtual bool isPredicated(const MachineInstr *MI) const {

include/llvm/Target/TargetOptions.h

TargetOptions()
           NoInfsFPMath(false), NoNaNsFPMath(false),
           HonorSignDependentRoundingFPMathOption(false), UseSoftFloat(false),
           NoZerosInBSS(false), JITEmitDebugInfo(false),
           JITEmitDebugInfoToDisk(false), GuaranteedTailCallOpt(false),
           DisableTailCalls(false), StackAlignmentOverride(0),
           EnableFastISel(false), PositionIndependentExecutable(false),
           UseInitArray(false), DisableIntegratedAS(false),
           CompressDebugSections(false), FunctionSections(false),
-          DataSections(false), TrapUnreachable(false), TrapFuncName(),
-          FloatABIType(FloatABI::Default),
-          AllowFPOpFusion(FPOpFusion::Standard), JTType(JumpTable::Single),
-          FCFI(false), ThreadModel(ThreadModel::POSIX),
-          CFIType(CFIntegrity::Sub), CFIEnforcing(false), CFIFuncName() {}
+          DataSections(false), NoopInsertion(false),
+          TrapUnreachable(false), TrapFuncName(),
+          FloatABIType(FloatABI::Default), AllowFPOpFusion(FPOpFusion::Standard),
+          JTType(JumpTable::Single), FCFI(false),
+          ThreadModel(ThreadModel::POSIX), CFIType(CFIntegrity::Sub),
+          CFIEnforcing(false), CFIFuncName() {}
 
     /// PrintMachineCode - This flag is enabled when the -print-machineinstrs
     /// option is specified on the command line, and should enable debugging
     /// output from the code generator.
     unsigned PrintMachineCode : 1;
 
     /// NoFramePointerElim - This flag is enabled when the -disable-fp-elim is
     /// specified on the command line.  If the target supports the frame pointer
public:
     /// .bss section. This flag disables such behaviour (necessary, e.g. for
     /// crt*.o compiling).
     unsigned NoZerosInBSS : 1;
 
     /// JITEmitDebugInfo - This flag indicates that the JIT should try to emit
     /// debug information and notify a debugger about it.
     unsigned JITEmitDebugInfo : 1;
 
     /// JITEmitDebugInfoToDisk - This flag indicates that the JIT should write
     /// the object files generated by the JITEmitDebugInfo flag to disk.  This
     /// flag is hidden and is only for debugging the debug info.
     unsigned JITEmitDebugInfoToDisk : 1;
 
     /// GuaranteedTailCallOpt - This flag is enabled when -tailcallopt is
     /// specified on the commandline. When the flag is on, participating targets
     /// will perform tail call optimization on all calls which use the fastcc
     /// calling convention and which satisfy certain target-independent
public:
     unsigned CompressDebugSections : 1;
 
     /// Emit functions into separate sections.
     unsigned FunctionSections : 1;
 
     /// Emit data into separate sections.
     unsigned DataSections : 1;
 
+    /// Randomly insert noop instructions to create fine-grained code
+    /// layout diversity.
+    unsigned NoopInsertion : 1;
+
     /// Emit target-specific trap instruction for 'unreachable' IR instructions.
     unsigned TrapUnreachable : 1;
 
     /// getTrapFunctionName - If this returns a non-empty string, this means
     /// isel should lower Intrinsic::trap to a call to the specified function
     /// name instead of an ISD::TRAP node.
     std::string TrapFuncName;
     StringRef getTrapFunctionName() const;

lib/CodeGen/CMakeLists.txt

add_llvm_library(LLVMCodeGen
   MachinePostDominators.cpp
   MachineRegisterInfo.cpp
   MachineRegionInfo.cpp
   MachineSSAUpdater.cpp
   MachineScheduler.cpp
   MachineSink.cpp
   MachineTraceMetrics.cpp
   MachineVerifier.cpp
+  NoopInsertion.cpp
   OcamlGC.cpp
   OptimizePHIs.cpp
   PHIElimination.cpp
   PHIEliminationUtils.cpp
   Passes.cpp
   PeepholeOptimizer.cpp
   PostRASchedulerList.cpp
   ProcessImplicitDefs.cpp

lib/CodeGen/CodeGen.cpp

void llvm::initializeCodeGen(PassRegistry &Registry) {
   initializeMachineDominatorTreePass(Registry);
   initializeMachinePostDominatorTreePass(Registry);
   initializeMachineLICMPass(Registry);
   initializeMachineLoopInfoPass(Registry);
   initializeMachineModuleInfoPass(Registry);
   initializeMachineSchedulerPass(Registry);
   initializeMachineSinkingPass(Registry);
   initializeMachineVerifierPassPass(Registry);
+  initializeNoopInsertionPass(Registry);
   initializeOptimizePHIsPass(Registry);
   initializePHIEliminationPass(Registry);
   initializePeepholeOptimizerPass(Registry);
   initializePostMachineSchedulerPass(Registry);
   initializePostRASchedulerPass(Registry);
   initializeProcessImplicitDefsPass(Registry);
   initializePEIPass(Registry);
   initializeRegisterCoalescerPass(Registry);

lib/CodeGen/NoopInsertion.cpp

+//===- NoopInsertion.cpp - Noop Insertion ---------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass adds fine-grained diversity by displacing code using randomly
+// placed (optionally target supplied) Noop instructions.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/NoopInsertion.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/RandomNumberGenerator.h"
+#include "llvm/Target/TargetInstrInfo.h"
+using namespace llvm;
+
+#define DEBUG_TYPE "noop-insertion"
+
+static cl::opt<unsigned> NoopInsertionPercentage(
+    "noop-insertion-percentage",
+    cl::desc("Percentage of instructions that have Noops prepended"),
+    cl::init(25)); // Default is a good balance between entropy and
+                   // performance impact
+
+static cl::opt<unsigned> MaxNoopsPerInstruction(
+    "max-noops-per-instruction",
+    llvm::cl::desc("Maximum number of Noops per instruction"),
+    llvm::cl::init(1));
+
+STATISTIC(InsertedNoops,
+          "Total number of noop type instructions inserted for diversity");
+
+char NoopInsertion::ID = 0;
+char &llvm::NoopInsertionID = NoopInsertion::ID;
+INITIALIZE_PASS(NoopInsertion, "noop-insertion",
+                "Noop Insertion for fine-grained code randomization", false,
+                false)
+
+NoopInsertion::NoopInsertion() : MachineFunctionPass(ID) {
+  initializeNoopInsertionPass(*PassRegistry::getPassRegistry());
+
+  // clamp percentage to 100
+  if (NoopInsertionPercentage > 100)
+    NoopInsertionPercentage = 100;
+}
+
+void NoopInsertion::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesCFG();
+  MachineFunctionPass::getAnalysisUsage(AU);
+}
+
+bool NoopInsertion::runOnMachineFunction(MachineFunction &Fn) {
+  // The RNG must be initialized on first use so we have a Module to
+  // construct it from
+  if (!RNG)
+    RNG.reset(Fn.getFunction()->getParent()->createRNG(this));
+
+  const TargetInstrInfo *TII = Fn.getSubtarget().getInstrInfo();
+
+  unsigned FnInsertedNoopCount = 0;
+
+  for (auto &BB : Fn) {
+    MachineBasicBlock::iterator FirstTerm = BB.getFirstTerminator();
+
+    for (MachineBasicBlock::iterator I = BB.begin(), E = BB.end(); I != E;
+         ++I) {
+      if (I->isPseudo())
+        continue;
+
+      // Insert random number of Noop-like instructions.
+      for (unsigned i = 0; i < MaxNoopsPerInstruction; i++) {
+        if (Distribution(*RNG) >= NoopInsertionPercentage)
+          continue;
+
+        TII->insertNoop(BB, I, *RNG);
+
+        ++FnInsertedNoopCount;
+      }
+
+      if (I == FirstTerm)
+        break;
+    }
+  }
+
+  InsertedNoops += FnInsertedNoopCount;
+
+  return FnInsertedNoopCount > 0;
+}

lib/CodeGen/Passes.cpp

void TargetPassConfig::addMachinePasses() {
   }
 
   // GC
   if (addGCPasses()) {
     if (PrintGCInfo)
       addPass(createGCInfoPrinter(dbgs()), false, false);
   }
 
+  if (TM->Options.NoopInsertion)
+    addPass(&NoopInsertionID);
+
   // Basic block placement.
   if (getOptLevel() != CodeGenOpt::None)
     addBlockPlacement();
 
   addPreEmitPass();
 
   addPass(&StackMapLivenessID, false);
 

lib/Target/X86/X86InstrInfo.h

public:
   /// have already been scheduled after Load1.
   bool shouldScheduleLoadsNear(SDNode *Load1, SDNode *Load2,
                                int64_t Offset1, int64_t Offset2,
                                unsigned NumLoads) const override;
 
   bool shouldScheduleAdjacent(MachineInstr* First,
                               MachineInstr *Second) const override;
 
+  void insertNoop(MachineBasicBlock &MBB,
+                  MachineBasicBlock::iterator MI) const override;
+
+  void insertNoop(MachineBasicBlock &MBB,
+                  MachineBasicBlock::iterator MI,
+                  RandomNumberGenerator &RNG) const override;
+
   void getNoopForMachoTarget(MCInst &NopInst) const override;
 
   bool
   ReverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const override;
 
   /// isSafeToMoveRegClassDefs - Return true if it's safe to move a machine
   /// instruction that defines the specified register class.
   bool isSafeToMoveRegClassDefs(const TargetRegisterClass *RC) const override;

lib/Target/X86/X86InstrInfo.cpp

 #include "llvm/IR/Function.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/MC/MCExpr.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/RandomNumberGenerator.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetOptions.h"
 #include <limits>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "x86-instr-info"
 
if (!table) { // try the other table
     assert((Subtarget.hasAVX2() || Domain < 3) &&
            "256-bit vector operations only available in AVX2");
     table = lookupAVX2(MI->getOpcode(), dom);
   }
   assert(table && "Cannot change domain");
   MI->setDesc(get(table[Domain-1]));
 }
 
+/// insertNoop - Insert a noop into the instruction stream at the specified
+/// point.
+void X86InstrInfo::insertNoop(MachineBasicBlock &MBB,
+                              MachineBasicBlock::iterator MI) const {
+  DebugLoc DL;
+  BuildMI(MBB, MI, DL, get(X86::NOOP));
+}
+
+/// insertNoop - Insert a randomly chosen type of noop into the instruction
+/// stream at the specified point to introduce fine-grained diversity.
+void X86InstrInfo::insertNoop(MachineBasicBlock &MBB,
+                              MachineBasicBlock::iterator MI,
+                              RandomNumberGenerator &RNG) const {
+  // This set of Noop instructions was carefully chosen so that
+  // misaligned parses of these instructions do not introduce new,
+  // useful ROP gadgets. The ASM instructions noted are for misaligned
+  // parses of the noop in 32 and 64 bits.
+  enum {
+    NOP,    // 90
+    MOV_BP, // 89 ed, 48 89 ed -- IN EAX, IN AL (privileged)
+    MOV_SP, // 89 e4, 48 89 e4 -- IN AL, IN EAX (privileged)
+    LEA_SI, // 8d 36, 48 8d 36 -- SS segment override, NULL
+            // prefix (does not add new gadget)
+    LEA_DI, // 8d 3f, 48 8d 3f -- AAS (bcd->hex), invalid
+    MAX_NOPS
+  };
+
+  static const unsigned NopRegs[MAX_NOPS][2] = {
+      {0, 0},
+      {X86::EBP, X86::RBP},
+      {X86::ESP, X86::RSP},
+      {X86::ESI, X86::RSI},
+      {X86::EDI, X86::RDI},
+  };
+
+  std::uniform_int_distribution<unsigned> Distribution(0, MAX_NOPS - 1);
+
+  unsigned Type = Distribution(RNG);
+
+  DebugLoc DL;
+  bool is64Bit = Subtarget.is64Bit();
+  unsigned Reg = NopRegs[Type][is64Bit];
+
+  switch (Type) {
+  case NOP:
+    BuildMI(MBB, MI, DL, get(X86::NOOP));
+    break;
+  case MOV_BP:
+  case MOV_SP:
+    copyPhysReg(MBB, MI, DL, Reg, Reg, false);
+    break;
+  case LEA_SI:
+  case LEA_DI: {
+    unsigned opc = is64Bit ? X86::LEA64r : X86::LEA32r;
+    addRegOffset(BuildMI(MBB, MI, DL, get(opc), Reg), Reg, false, 0);
+    break;
+  }
+  }
+}
+
 /// getNoopForMachoTarget - Return the noop instruction to use for a noop.
 void X86InstrInfo::getNoopForMachoTarget(MCInst &NopInst) const {
   NopInst.setOpcode(X86::NOOP);
 }
 
 // This code must remain in sync with getJumpInstrTableEntryBound in this class!
 // In particular, getJumpInstrTableEntryBound must always return an upper bound
 // on the encoding lengths of the instructions generated by

test/CodeGen/Mips/noop-insert.ll

+; RUN: llc < %s -march=mips -noop-insertion | FileCheck %s
+; RUN: llc < %s -march=mips -noop-insertion -rng-seed=1 | FileCheck %s --check-prefix=SEED1
+; RUN: llc < %s -march=mips -noop-insertion -noop-insertion-percentage=100 | FileCheck %s --check-prefix=100PERCENT
+
+; This test case checks that NOOPs are inserted correctly for MIPS.
+
+; It just happens that with a default percentage of 25% and seed=0,
+; no NOOPs are inserted.
+; CHECK: mul
+; CHECK-NEXT: jr
+
+; SEED1: nop
+; SEED1-NEXT: mul
+; SEED1-NEXT: jr
+
+; 100PERCENT: nop
+; 100PERCENT-NEXT: mul
+; 100PERCENT-NEXT: nop
+; 100PERCENT-NEXT: jr
+
+define i32 @test1(i32 %x, i32 %y, i32 %z) {
+entry:
+    %tmp = mul i32 %x, %y
+    %tmp2 = add i32 %tmp, %z
+    ret i32 %tmp2
+}

test/CodeGen/PowerPC/noop-insert.ll

+; RUN: llc < %s -march=ppc32 -noop-insertion | FileCheck %s
+; RUN: llc < %s -march=ppc32 -noop-insertion -rng-seed=1 | FileCheck %s --check-prefix=SEED1
+; RUN: llc < %s -march=ppc32 -noop-insertion -noop-insertion-percentage=100 | FileCheck %s --check-prefix=100PERCENT
+
+; This test case checks that NOOPs are inserted correctly for PowerPC.
+
+; It just happens that with a default percentage of 25% and seed=0,
+; no NOOPs are inserted.
+; CHECK: mullw
+; CHECK-NEXT: add
+; CHECK-NEXT: blr
+
+; SEED1: nop
+; SEED1-NEXT: mullw
+; SEED1-NEXT: add
+; SEED1-NEXT: nop
+; SEED1-NEXT: blr
+
+; 100PERCENT: nop
+; 100PERCENT-NEXT: mullw
+; 100PERCENT-NEXT: nop
+; 100PERCENT-NEXT: add
+; 100PERCENT-NEXT: nop
+; 100PERCENT-NEXT: blr
+
+define i32 @test1(i32 %x, i32 %y, i32 %z) {
+entry:
+    %tmp = mul i32 %x, %y
+    %tmp2 = add i32 %tmp, %z
+    ret i32 %tmp2
+}

test/CodeGen/X86/noop-insert-percentage.ll

+; RUN: llc < %s -mtriple=x86_64-linux -rng-seed=5 -noop-insertion -noop-insertion-percentage=10 \
+; RUN:     | FileCheck %s --check-prefix=PERCENT10
+; RUN: llc < %s -mtriple=x86_64-linux -rng-seed=5 -noop-insertion -noop-insertion-percentage=50 \
+; RUN:     | FileCheck %s --check-prefix=PERCENT50
+; RUN: llc < %s -mtriple=x86_64-linux -rng-seed=5 -noop-insertion -noop-insertion-percentage=100 \
+; RUN:     | FileCheck %s --check-prefix=PERCENT100
+
+; RUN: llc < %s -march=x86 -rng-seed=5 -noop-insertion -noop-insertion-percentage=100 \
+; RUN:     | FileCheck %s --check-prefix=X86-PERCENT100
+
+; This test case tests NOOP insertion at varying percentage levels.
+
+define i32 @test(i32 %x, i32 %y, i32 %z) {
+entry:
+    %t1 = add i32 %x, %y
+    %t2 = mul i32 %t1, %z
+    %t3 = add i32 %t2, %x
+    %t4 = mul i32 %t3, %z
+    %t5 = add i32 %t4, %x
+    %t6 = mul i32 %t5, %z
+    %t7 = add i32 %t6, %x
+    %t8 = mul i32 %t7, %z
+    %t9 = add i32 %t8, %x
+    %t10 = mul i32 %t9, %z
+    %t11 = add i32 %t10, %x
+    ret i32 %t11
+}
+
+; PERCENT10: movq   %rbp, %rbp
+; PERCENT10: retq
+
+; PERCENT50: leaq   (%rdi), %rdi
+; PERCENT50: nop
+; PERCENT50: movq   %rbp, %rbp
+; PERCENT50: movq   %rsp, %rsp
+; PERCENT50: leaq   (%rsi), %rsi
+; PERCENT50: nop
+; PERCENT50: retq
+
+; PERCENT100: leaq  (%rdi), %rdi
+; PERCENT100: leaq  (%rdi), %rdi
+; PERCENT100: nop
+; PERCENT100: movq  %rbp, %rbp
+; PERCENT100: movq  %rsp, %rsp
+; PERCENT100: nop
+; PERCENT100: nop
+; PERCENT100: leaq  (%rsi), %rsi
+; PERCENT100: nop
+; PERCENT100: leaq  (%rdi), %rdi
+; PERCENT100: leaq  (%rdi), %rdi
+; PERCENT100: leaq  (%rsi), %rsi
+; PERCENT100: retq
+
+
+; X86-PERCENT100: leal  (%edi), %edi
+; X86-PERCENT100: leal  (%edi), %edi
+; X86-PERCENT100: nop
+; X86-PERCENT100: movl  %ebp, %ebp
+; X86-PERCENT100: movl  %esp, %esp
+; X86-PERCENT100: nop
+; X86-PERCENT100: nop
+; X86-PERCENT100: leal  (%esi), %esi
+; X86-PERCENT100: nop
+; X86-PERCENT100: leal  (%edi), %edi
+; X86-PERCENT100: leal  (%edi), %edi
+; X86-PERCENT100: leal  (%esi), %esi

test/CodeGen/X86/noop-insert.ll

+; RUN: llc < %s -mtriple=x86_64-linux -noop-insertion | FileCheck %s
+; RUN: llc < %s -mtriple=x86_64-linux -noop-insertion -rng-seed=1 | FileCheck %s --check-prefix=SEED1
+; RUN: llc < %s -mtriple=x86_64-linux -noop-insertion -rng-seed=20 | FileCheck %s --check-prefix=SEED2
+; RUN: llc < %s -mtriple=x86_64-linux -noop-insertion -rng-seed=500 | FileCheck %s --check-prefix=SEED3
+
+; RUN: llc < %s -march=x86 -noop-insertion | FileCheck %s --check-prefix=x86_32
+
+; This test case checks that NOOPs are inserted, and that the RNG seed
+; affects both the placement (position of imull) and choice of these NOOPs.
+
+; It just happens that with a default percentage of 25% and seed=0,
+; no NOOPs are inserted.
+; CHECK: imull
+; CHECK-NEXT: leal
+; CHECK-NEXT: retq
+; CHECK-NOT: nop
+
+; SEED1: leaq (%rsi), %rsi
+; SEED1-NEXT: imull
+; SEED1-NEXT: leal
+; SEED1-NEXT: retq
+
+; SEED2: imull
+; SEED2-NEXT: movq %rsp, %rsp
+; SEED2-NEXT: leal
+; SEED2-NEXT: retq
+
+; SEED3: imull
+; SEED3-NEXT: movq %rsp, %rsp
+; SEED3-NEXT: leal
+; SEED3-NEXT: leaq (%rdi), %rdi
+; SEED3-NEXT: retq
+
+; The operand of the following is used to distinguish from a movl NOOP
+; x86_32: movl 4(%esp),
+; x86_32-NEXT: imull
+; x86_32-NEXT: addl
+; x86_32-NEXT: movl %esp, %esp
+; x86_32-NEXT: retl
+
+define i32 @test1(i32 %x, i32 %y, i32 %z) {
+entry:
+    %tmp = mul i32 %x, %y
+    %tmp2 = add i32 %tmp, %z
+    ret i32 %tmp2
+}