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

27

You probably want to add the virtual dtor too.

29

override

lib/CodeGen/NOPInsertion.cpp

72

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

84

Do fix :)

lib/Target/X86/X86InstrInfo.cpp

5321

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

5323

You should fix this distribution too.

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

5

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

[ahomescu]

lib/CodeGen/NOPInsertion.cpp

90

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

30 ↗

(On Diff #17511)

override

34 ↗

(On Diff #17511)

The above 2 can be private or protected.

37 ↗

(On Diff #17511)

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

include/llvm/Support/RandomNumberGenerator.h

34

RNG::result_type

44

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

48

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

include/llvm/Target/TargetInstrInfo.h

685

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

lib/CodeGen/NoopInsertion.cpp

64 ↗

(On Diff #17511)

Remove when using std::unique_ptr.

84 ↗

(On Diff #17511)

No need to comment range-based for loop.

85 ↗

(On Diff #17511)

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

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

104 ↗

(On Diff #17511)

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

5311

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.

5325

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

76 ↗

(On Diff #17701)

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

lib/Target/X86/X86InstrInfo.cpp

5320

"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?

5330

Missing clang-format.

test/CodeGen/Mips/noop-insert.ll

11 ↗

(On Diff #17701)

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

5320

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

EnablePIE("enable-pie",
           cl::desc("Assume the creation of a position independent executable."),
           cl::init(false));
 
 cl::opt<bool>
 UseInitArray("use-init-array",
              cl::desc("Use .init_array instead of .ctors."),
              cl::init(false));
 
+cl::opt<bool>
+NOPInsertion("nop-insertion",
+             cl::desc("Randomly add noop instructions to create fine-grained diversity."),
+             cl::init(false));
+
 cl::opt<std::string> StopAfter("stop-after",
                             cl::desc("Stop compilation after a specific pass"),
                             cl::value_desc("pass-name"),
                                       cl::init(""));
 cl::opt<std::string> StartAfter("start-after",
                           cl::desc("Resume compilation after a specific pass"),
                           cl::value_desc("pass-name"),
                           cl::init(""));
 
 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<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() {
   if (FloatABIForCalls != FloatABI::Default)
     Options.FloatABIType = FloatABIForCalls;
   Options.NoZerosInBSS = DontPlaceZerosInBSS;
   Options.GuaranteedTailCallOpt = EnableGuaranteedTailCallOpt;
   Options.DisableTailCalls = DisableTailCalls;
   Options.StackAlignmentOverride = OverrideStackAlignment;
   Options.TrapFuncName = TrapFuncName;
   Options.PositionIndependentExecutable = EnablePIE;
+  Options.NOPInsertion = NOPInsertion;
   Options.UseInitArray = UseInitArray;
   Options.DataSections = DataSections;
   Options.FunctionSections = FunctionSections;
 
   Options.MCOptions = InitMCTargetOptionsFromFlags();
   Options.JTType = JTableType;
 
   return Options;
 }
 
 #endif

include/llvm/CodeGen/NOPInsertion.h

+//===-- NOPInsertion.h - NOP 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) NOP instructions.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_NOPINSERTION_H
+#define LLVM_CODEGEN_NOPINSERTION_H
+
+#include "llvm/CodeGen/MachineFunctionPass.h"
+
+namespace llvm {
+
+class NOPInsertion : public MachineFunctionPass {
+public:
+  static char ID;
+
+  NOPInsertion();
+
+  bool runOnMachineFunction(MachineFunction &MF);
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+};
+
+}
+
+#endif // LLVM_CODEGEN_NOPINSERTION_H

include/llvm/CodeGen/Passes.h

namespace llvm {
   /// 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;
 
+  /// NOPInsertion - This pass adds fine-grained diversity by displacing code
+  /// using randomly placed (optionally target supplied) NOP instructions.
+  extern char &NOPInsertionID;
+
   /// createJumpInstrTables - This pass creates jump-instruction tables.
   ModulePass *createJumpInstrTablesPass();
 } // End llvm namespace
 
 /// This initializer registers TargetMachine constructor, so the pass being
 /// initialized can use target dependent interfaces. Please do not move this
 /// macro to be together with INITIALIZE_PASS, which is a complete target
 /// independent initializer, and we don't want to make libScalarOpts depend

include/llvm/IR/Module.h

private:
   std::string GlobalScopeAsm;     ///< Inline Asm at global scope.
   ValueSymbolTable *ValSymTab;    ///< Symbol table for values
   ComdatSymTabType ComdatSymTab;  ///< Symbol table for COMDATs
   std::unique_ptr<GVMaterializer>
   Materializer;                   ///< Used to materialize GlobalValues
   std::string ModuleID;           ///< Human readable identifier for the module
   std::string TargetTriple;       ///< Platform target triple Module compiled on
   void *NamedMDSymTab;            ///< NamedMDNode names.
-  // Allow lazy initialization in const method.
-  mutable RandomNumberGenerator *RNG; ///< The random number generator for this module.
 
   // We need to keep the string because the C API expects us to own the string
   // representation.
   // Since we have it, we also use an empty string to represent a module without
   // a DataLayout. If it has a DataLayout, these variables are in sync and the
   // string is just a cache of getDataLayout()->getStringRepresentation().
   std::string DataLayoutStr;
   DataLayout DL;
/// @{
   /// Get the global data context.
   /// @returns LLVMContext - a container for LLVM's global information
   LLVMContext &getContext() const { return Context; }
 
   /// Get any module-scope inline assembly blocks.
   /// @returns a string containing the module-scope inline assembly blocks.
   const std::string &getModuleInlineAsm() const { return GlobalScopeAsm; }
 
-  /// Get the RandomNumberGenerator for this module. The RNG can be
-  /// seeded via -rng-seed=<uint64> and is salted with the ModuleID.
-  /// The returned RNG should not be shared across threads.
-  RandomNumberGenerator &getRNG() const;
+  /// Get a RandomNumberGenerator salted for use with this module. The
+  /// RNG can be seeded via -rng-seed=<uint64> and is salted with the
+  /// ModuleID and the provided pass salt. The returned RNG should not
+  /// be shared across threads or passes.
+  ///
+  /// A unique RNG per pass ensures a reproducible random stream even
+  /// when other randomness consuming passes are added or removed. In
+  /// addition, the random stream will be reproducible across LLVM
+  /// versions when the pass does not change.
+  RandomNumberGenerator *createRNG(const Pass* P) const;
 
 /// @}
 /// @name Module Level Mutators
 /// @{
 
   /// Set the module identifier.
   void setModuleIdentifier(StringRef ID) { ModuleID = ID; }
 

include/llvm/InitializePasses.h

 void initializeMachineVerifierPassPass(PassRegistry&);
 void initializeMemCpyOptPass(PassRegistry&);
 void initializeMemDepPrinterPass(PassRegistry&);
 void initializeMemoryDependenceAnalysisPass(PassRegistry&);
 void initializeMetaRenamerPass(PassRegistry&);
 void initializeMergeFunctionsPass(PassRegistry&);
 void initializeModuleDebugInfoPrinterPass(PassRegistry&);
 void initializeNoAAPass(PassRegistry&);
+void initializeNOPInsertionPass(PassRegistry&);
 void initializeObjCARCAliasAnalysisPass(PassRegistry&);
 void initializeObjCARCAPElimPass(PassRegistry&);
 void initializeObjCARCExpandPass(PassRegistry&);
 void initializeObjCARCContractPass(PassRegistry&);
 void initializeObjCARCOptPass(PassRegistry&);
 void initializeOptimizePHIsPass(PassRegistry&);
 void initializePartiallyInlineLibCallsPass(PassRegistry&);
 void initializePEIPass(PassRegistry&);

include/llvm/Support/RandomNumberGenerator.h

 //==- llvm/Support/RandomNumberGenerator.h - RNG for diversity ---*- C++ -*-==//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
-// This file defines an abstraction for random number generation (RNG).
-// Note that the current implementation is not cryptographically secure
-// as it uses the C++11 <random> facilities.
+// This file defines an abstraction for deterministic random number
+// generation (RNG).  Note that the current implementation is not
+// cryptographically secure as it uses the C++11 <random> facilities.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_RANDOMNUMBERGENERATOR_H_
 #define LLVM_SUPPORT_RANDOMNUMBERGENERATOR_H_
 
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/DataTypes.h" // Needed for uint64_t on Windows.
 #include <random>
 
 namespace llvm {
 
 /// A random number generator.
-/// Instances of this class should not be shared across threads.
+///
+/// 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:
-  /// Seeds and salts the underlying RNG engine. The salt of type StringRef
-  /// is passed into the constructor. The seed can be set on the command
-  /// line via -rng-seed=<uint64>.
-  /// The reason for the salt is to ensure different random streams even if
-  /// the same seed is used for multiple invocations of the compiler.
-  /// A good salt value should add additional entropy and be constant across
-  /// different machines (i.e., no paths) to allow for reproducible builds.
-  /// An instance of this class can be retrieved from the current Module.
-  /// \see Module::getRNG
-  RandomNumberGenerator(StringRef Salt);
-
   /// Returns a random number in the range [0, Max).
-  uint64_t next(uint64_t Max);
+  uint_fast64_t operator()();
 
 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;
 
   // 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;
 class 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 *RNG) const {
+    insertNoop(MBB, MI);
+  }
+
 
   /// getNoopForMachoTarget - Return the noop instruction to use for a noop.
   virtual void getNoopForMachoTarget(MCInst &NopInst) const {
     // Default to just using 'nop' string.
   }
 
 
   /// isPredicated - Returns true if the instruction is already predicated.

include/llvm/Target/TargetOptions.h

TargetOptions()
         : PrintMachineCode(false), NoFramePointerElim(false),
           LessPreciseFPMADOption(false), UnsafeFPMath(false),
           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),
+          NOPInsertion(false), UseInitArray(false), DisableIntegratedAS(false),
           CompressDebugSections(false), FunctionSections(false),
           DataSections(false), TrapUnreachable(false), TrapFuncName(""),
           FloatABIType(FloatABI::Default),
           AllowFPOpFusion(FPOpFusion::Standard), JTType(JumpTable::Single) {}
 
     /// 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.
public:
     /// as their parent function, etc.), using an alternate ABI if necessary.
     unsigned GuaranteedTailCallOpt : 1;
 
     /// DisableTailCalls - This flag controls whether we will use tail calls.
     /// Disabling them may be useful to maintain a correct call stack.
     unsigned DisableTailCalls : 1;
 
     /// StackAlignmentOverride - Override default stack alignment for target.
     unsigned StackAlignmentOverride;
 
     /// EnableFastISel - This flag enables fast-path instruction selection
     /// which trades away generated code quality in favor of reducing
     /// compile time.
     unsigned EnableFastISel : 1;
 
     /// PositionIndependentExecutable - This flag indicates whether the code
     /// will eventually be linked into a single executable, despite the PIC
     /// relocation model being in use. It's value is undefined (and irrelevant)
     /// if the relocation model is anything other than PIC.
     unsigned PositionIndependentExecutable : 1;
 
+    /// Randomly insert noop instructions to create fine-grained diversity
+    unsigned NOPInsertion : 1;
+
     /// UseInitArray - Use .init_array instead of .ctors for static
     /// constructors.
     unsigned UseInitArray : 1;
 
     /// Disable the integrated assembler.
     unsigned DisableIntegratedAS : 1;
 
     /// Compress DWARF debug sections.

lib/CodeGen/CMakeLists.txt

add_llvm_library(LLVMCodeGen
   MachinePassRegistry.cpp
   MachinePostDominators.cpp
   MachineRegisterInfo.cpp
   MachineSSAUpdater.cpp
   MachineScheduler.cpp
   MachineSink.cpp
   MachineTraceMetrics.cpp
   MachineVerifier.cpp
+  NOPInsertion.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) {
   initializeUnpackMachineBundlesPass(Registry);
   initializeUnreachableBlockElimPass(Registry);
   initializeUnreachableMachineBlockElimPass(Registry);
   initializeVirtRegMapPass(Registry);
   initializeVirtRegRewriterPass(Registry);
   initializeLowerIntrinsicsPass(Registry);
   initializeMachineFunctionPrinterPassPass(Registry);
   initializeStackMapLivenessPass(Registry);
+  initializeNOPInsertionPass(Registry);
 }
 
 void LLVMInitializeCodeGen(LLVMPassRegistryRef R) {
   initializeCodeGen(*unwrap(R));
 }

lib/CodeGen/NOPInsertion.cpp

+//===- NOPInsertion.cpp - NOP 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) NOP instructions.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/NOPInsertion.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 "nop-insertion"
+
+static cl::opt<unsigned>
+NOPInsertionPercentage(
+  "nop-insertion-percentage",
+  cl::desc("Percentage of instructions that have NOPs prepended"),
+  cl::init(50));
+
+static cl::opt<unsigned>
+MaxNOPsPerInstruction(
+  "max-nops-per-instruction",
+  llvm::cl::desc("Maximum number of NOPs per instruction"),
+  llvm::cl::init(1));
+
+
+STATISTIC(InsertedNOPs,
+          "Total number of noop type instructions inserted for diversity");
+
+char NOPInsertion::ID = 0;
+char &llvm::NOPInsertionID = NOPInsertion::ID;
+INITIALIZE_PASS(NOPInsertion, "nop-insertion",
+                "NOP Insertion for fine-grained code randomization", false,
+                false)
+
+NOPInsertion::NOPInsertion() : MachineFunctionPass(ID) {
+  initializeNOPInsertionPass(*PassRegistry::getPassRegistry());
+
+  // clamp percentage to 100
+  if (NOPInsertionPercentage > 100)
+    NOPInsertionPercentage = 100;
+}
+
+void NOPInsertion::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesCFG();
+  MachineFunctionPass::getAnalysisUsage(AU);
+}
+
+bool NOPInsertion::runOnMachineFunction(MachineFunction &Fn) {
+  const TargetInstrInfo *TII = Fn.getTarget().getInstrInfo();
+
+  RandomNumberGenerator *RNG = Fn.getFunction()->getParent()->createRNG(this);
+  for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
+    MachineBasicBlock::iterator FirstTerm = BB->getFirstTerminator();
+    // Insert NOPs before instruction.
+    for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
+      MachineBasicBlock::iterator NextI = std::next(I);
+      if (I->isPseudo()) {
+        I = NextI;
+        continue;
+      }
+
+      // Insert random number of NOP-like instructions.
+      for (unsigned i = 0; i < MaxNOPsPerInstruction; i++) {
+        unsigned Roll = (*RNG)() % 100; // FIXME: not uniform
+        if (Roll >= NOPInsertionPercentage)
+          continue;
+
+        TII->insertNoop(*BB, I, RNG);
+
+        ++InsertedNOPs;
+      }
+
+      // Do not insert NOPs between terminators.
+      if (I == FirstTerm)
+        break;
+
+      I = NextI;
+    }
+  }
+  return true;
+}
+

lib/CodeGen/Passes.cpp

void TargetPassConfig::addMachinePasses() {
   }
 
   // GC
   if (addGCPasses()) {
     if (PrintGCInfo)
       addPass(createGCInfoPrinter(dbgs()));
   }
 
+  if (TM->Options.NOPInsertion)
+    addPass(&NOPInsertionID);
+
   // Basic block placement.
   if (getOptLevel() != CodeGenOpt::None)
     addBlockPlacement();
 
   if (addPreEmitPass())
     printAndVerify("After PreEmit passes");
 
   addPass(&StackMapLivenessID);

lib/IR/Module.cpp

 template class llvm::SymbolTableListTraits<GlobalVariable, Module>;
 template class llvm::SymbolTableListTraits<GlobalAlias, Module>;
 
 //===----------------------------------------------------------------------===//
 // Primitive Module methods.
 //
 
 Module::Module(StringRef MID, LLVMContext &C)
-    : Context(C), Materializer(), ModuleID(MID), RNG(nullptr), DL("") {
+    : Context(C), Materializer(), ModuleID(MID), DL("") {
   ValSymTab = new ValueSymbolTable();
   NamedMDSymTab = new StringMap<NamedMDNode *>();
   Context.addModule(this);
 }
 
 Module::~Module() {
   Context.removeModule(this);
   dropAllReferences();
   GlobalList.clear();
   FunctionList.clear();
   AliasList.clear();
   NamedMDList.clear();
   delete ValSymTab;
   delete static_cast<StringMap<NamedMDNode *> *>(NamedMDSymTab);
-  delete RNG;
 }
 
+RandomNumberGenerator *Module::createRNG(const Pass* P) const {
+  SmallString<32> Salt(P->getPassName());
+
+  // This RNG is guaranteed to produce the same random stream only
+  // when the Module ID and thus the input filename is the same. This
+  // might be problematic if the input filename extension changes
+  // (e.g. from .c to .bc or .ll).
+  //
+  // We could store this salt in NamedMetadata, but this would make
+  // the parameter non-const. This would unfortunately make this
+  // interface unusable by any Machine passes, since they only have a
+  // const reference to their IR Module. Alternatively we can always
+  // store salt metadata from the Module constructor.
+  Salt += sys::path::filename(getModuleIdentifier());
+
+  return new RandomNumberGenerator(Salt);
+}
+
+
 /// getNamedValue - Return the first global value in the module with
 /// the specified name, of arbitrary type.  This method returns null
 /// if a global with the specified name is not found.
 GlobalValue *Module::getNamedValue(StringRef Name) const {
   return cast_or_null<GlobalValue>(getValueSymbolTable().lookup(Name));
 }
 
 /// getMDKindID - Return a unique non-zero ID for the specified metadata kind.

 }
 
 const DataLayout *Module::getDataLayout() const {
   if (DataLayoutStr.empty())
     return nullptr;
   return &DL;
 }
 
-// We want reproducible builds, but ModuleID may be a full path so we just use
-// the filename to salt the RNG (although it is not guaranteed to be unique).
-RandomNumberGenerator &Module::getRNG() const {
-  if (RNG == nullptr) {
-    StringRef Salt = sys::path::filename(ModuleID);
-    RNG = new RandomNumberGenerator(Salt);
-  }
-  return *RNG;
-}
-
 //===----------------------------------------------------------------------===//
 // Methods to control the materialization of GlobalValues in the Module.
 //
 void Module::setMaterializer(GVMaterializer *GVM) {
   assert(!Materializer &&
          "Module already has a GVMaterializer.  Call MaterializeAllPermanently"
          " to clear it out before setting another one.");
   Materializer.reset(GVM);

lib/Support/RandomNumberGenerator.cpp

 //===-- RandomNumberGenerator.cpp - Implement RNG class -------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
-// This file implements random number generation (RNG).
+// This file implements deterministic random number generation (RNG).
 // The current implementation is NOT cryptographically secure as it uses
 // the C++11 <random> facilities.
 //
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "rng"
-#include "llvm/Support/RandomNumberGenerator.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Support/RandomNumberGenerator.h"
 
 using namespace llvm;
 
 // Tracking BUG: 19665
 // http://llvm.org/bugs/show_bug.cgi?id=19665
 //
 // Do not change to cl::opt<uint64_t> since this silently breaks argument parsing.
 static cl::opt<unsigned long long>
 Seed("rng-seed", cl::value_desc("seed"),
      cl::desc("Seed for the random number generator"), cl::init(0));
 
 RandomNumberGenerator::RandomNumberGenerator(StringRef Salt) {
   DEBUG(
     if (Seed == 0)
-      errs() << "Warning! Using unseeded random number generator.\n"
+      dbgs() << "Warning! Using unseeded random number generator.\n"
   );
 
-  // Combine seed and salt using std::seed_seq.
-  // Entropy: Seed-low, Seed-high, Salt...
+  // Combine seed and salts using std::seed_seq.
+  // Data: Seed-low, Seed-high, Salt
+  // Note: std::seed_seq can only store 32-bit values, even though we
+  // are using a 64-bit RNG. This isn't a problem since the Mersenne
+  // twister constructor copies these correctly into its initial state.
   std::vector<uint32_t> Data;
-  Data.reserve(2 + Salt.size()/4 + 1);
+  Data.reserve(2 + Salt.size());
   Data.push_back(Seed);
   Data.push_back(Seed >> 32);
 
-  uint32_t Pack = 0;
-  for (size_t I = 0; I < Salt.size(); ++I) {
-    Pack <<= 8;
-    Pack += Salt[I];
-
-    if (I%4 == 3)
-      Data.push_back(Pack);
-  }
-  Data.push_back(Pack);
+  std::copy(Salt.begin(), Salt.end(), Data.end());
 
   std::seed_seq SeedSeq(Data.begin(), Data.end());
   Generator.seed(SeedSeq);
 }
 
-uint64_t RandomNumberGenerator::next(uint64_t Max) {
-  std::uniform_int_distribution<uint64_t> distribution(0, Max - 1);
-  return distribution(Generator);
+uint_fast64_t RandomNumberGenerator::operator()() {
+  return Generator();
 }

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/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/raw_ostream.h"
+#include "llvm/Support/RandomNumberGenerator.h"
 #include "llvm/Target/TargetOptions.h"
 #include <limits>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "x86-instr-info"
 
 #define GET_INSTRINFO_CTOR_DTOR
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 {
+  enum { NOP,
+         MOV_BP, MOV_SP,
+         LEA_SI, LEA_DI,
+         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 },
+  };
+
+  unsigned Type = (*RNG)() % MAX_NOPS;
+
+  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);
 }
 
 void X86InstrInfo::getUnconditionalBranch(
     MCInst &Branch, const MCSymbolRefExpr *BranchTarget) const {
   Branch.setOpcode(X86::JMP_4);

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

+; RUN: llc < %s -mtriple=x86_64-linux -rng-seed=5 -nop-insertion -nop-insertion-percentage=10 \
+; RUN:     | FileCheck %s --check-prefix=PERCENT10
+; RUN: llc < %s -mtriple=x86_64-linux -rng-seed=5 -nop-insertion -nop-insertion-percentage=50 \
+; RUN:     | FileCheck %s --check-prefix=PERCENT50
+; RUN: llc < %s -mtriple=x86_64-linux -rng-seed=5 -nop-insertion -nop-insertion-percentage=100 \
+; RUN:     | FileCheck %s --check-prefix=PERCENT100
+
+; This test case tests NOP 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: leaq   (%rsi), %rsi
+
+; PERCENT50: movq   %rbp, %rbp
+; PERCENT50: nop
+; PERCENT50: leaq   (%rsi), %rsi
+; PERCENT50: leaq   (%rdi), %rdi
+; PERCENT50: movq   %rbp, %rbp
+; PERCENT50: movq   %rsp, %rsp
+
+; PERCENT100: leaq  (%rdi), %rdi
+; PERCENT100: leaq  (%rdi), %rdi
+; PERCENT100: movq  %rsp, %rsp
+; PERCENT100: movq  %rsp, %rsp
+; PERCENT100: leaq  (%rdi), %rdi
+; PERCENT100: leaq  (%rsi), %rsi
+; PERCENT100: leaq  (%rdi), %rdi
+; PERCENT100: movq  %rbp, %rbp
+; PERCENT100: movq  %rsp, %rsp
+; PERCENT100: leaq  (%rsi), %rsi
+; PERCENT100: nop
+; PERCENT100: leaq  (%rsi), %rsi
+

test/CodeGen/X86/nop-insert.ll

+; RUN: llc < %s -mtriple=x86_64-linux -nop-insertion | FileCheck %s
+; RUN: llc < %s -mtriple=x86_64-linux -nop-insertion -rng-seed=1 | FileCheck %s --check-prefix=SEED1
+; RUN: llc < %s -mtriple=x86_64-linux -nop-insertion -rng-seed=25 | FileCheck %s --check-prefix=SEED2
+; RUN: llc < %s -mtriple=x86_64-linux -nop-insertion -rng-seed=1534 | FileCheck %s --check-prefix=SEED3
+
+; This test case checks that NOPs are inserted, and that the RNG seed
+; affects both the placement (position of imull) and choice of these NOPs.
+
+; CHECK: imull
+; CHECK: leaq (%rsi), %rsi
+; CHECK: retq
+; CHECK-NOT: nop
+
+; SEED1: imull
+; SEED1: movq %rbp, %rbp
+; SEED1: retq
+; SEED1-NOT: nop
+
+; SEED2: movq %rsp, %rsp
+; SEED2: imull
+; SEED2: leaq (%rsi), %rsi
+; SEED2: nop
+; SEED2: retq
+
+; SEED3: movq %rsp, %rsp
+; SEED3: imull
+; SEED3: nop
+; SEED3: retq
+
+define i32 @test1(i32 %x, i32 %y, i32 %z) {
+entry:
+    %tmp = mul i32 %x, %y
+    %tmp2 = add i32 %tmp, %z
+    ret i32 %tmp2
+}