Adding diversity for security (llvm)

[yln]

Summary

This patch was split into multiple, smaller patches (see dependencies).
clang parts: D3391, D3393, D3395

Old (outdated) summary:
Adds the capability to randomly insert NOPs, permuting the code layout, as well as the option to randomize scheduling decisions. Includes an OpenSSL-linked RNG to provide secure random number generation.

[rinon]

• Removed LLVM_ENABLE_RNG setting.
• Fixing debug outputs
• Various formatting to comply with coding style

[alexr]

I'm not a crypto geek but... I think the choices of seeds need to be explained in the comments.

For example, the result of malloced memory is likely to be just zeros on some platforms and the addresses of command line argument pointers is likely to be constant between runs.

Alex

On Oct 1, 2013, at 3:13 PM, Stephen Crane <[e-mail]> wrote:

Adds the capability to randomly insert NOPs, permuting the code layout, as well as the option to randomize scheduling decisions. Includes an OpenSSL-linked RNG to provide secure random number generation.

http://llvm-reviews.chandlerc.com/D1802

Files:
CMakeLists.txt
Makefile.config.in
autoconf/configure.ac
cmake/config-ix.cmake
cmake/modules/LLVM-Config.cmake
configure
include/llvm/CodeGen/CommandFlags.h
include/llvm/CodeGen/MachineInstr.h
include/llvm/Config/config.h.cmake
include/llvm/Config/config.h.in
include/llvm/MC/MCRegisterInfo.h
include/llvm/Support/RandomNumberGenerator.h
include/llvm/Target/TargetOptions.h
lib/CodeGen/LLVMBuild.txt
lib/CodeGen/MachineBasicBlock.cpp
lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
lib/LTO/LTOCodeGenerator.cpp
lib/LTO/LTOModule.cpp
lib/Support/CMakeLists.txt
lib/Support/RandomNumberGenerator.cpp
lib/Target/X86/CMakeLists.txt
lib/Target/X86/NOPInsertion.cpp
lib/Target/X86/X86.h
lib/Target/X86/X86TargetMachine.cpp
test/CodeGen/X86/nop-insert-percentage.ll
test/CodeGen/X86/nop-insert.ll
test/CodeGen/X86/sched-rnd-test.ll
test/Makefile
test/lit.cfg
test/lit.site.cfg.in
tools/llc/llc.cpp
tools/opt/opt.cpp
<D1802.1.patch>

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[rinon]

Discussion of the existing OpenSSL RNG and thread safety brings up another important point: The RNG needs to store state in some thread-local way. Should RNG state be stored in the LLVMContext? I didn't want to mess with LLVMContext without advice from someone who knows the multi-threading roadmap better. It doesn't seem to be the right place, but we need some way to guarantee that only one RNG will be initialized per-thread, rather than using the current static singleton.

[rinon]

Thread safe and commented

• Cleaned up coding style.
• Removed unnecessary copy constructors for RNG
• Made OpenSSL thread-safe
• Reorganized RNGs.
• Added virtual destructor.
• Added comments to describe RNG construction.

[tmroeder]

I'm glad you were able to set up the OpenSSL locking. I have a few comments on the code; see below. My high-level comment about the algorithm is that it looks like this is not an exact implementation of of SP 800-90A; see my comments for some (not all) of the differences.

Also, someone familiar with the details of the X86 Target and other backend code should look at this, too, since I don't know much about the backend details.

include/llvm/Support/RandomNumberGenerator.h

18

This should follow the style LLVM_SUPPORT_RANDOMNUMBERGENERATOR_H (see other files in include/llvm)

70

Looks like the style here should be a semi-colon alone on a line. See, e.g., lib/CodeGen/MachineBasicBlock.cpp around the changes in this diff.

include/llvm/Target/TargetOptions.h

51–55

It looks like this diff is missing at least one place that uses TargetOptions: in tools/lto/lto.cpp, there is a function lto_set_target_options that sets values in TargetOptions based on the command-line flags. Please change that too.

lib/Support/RandomNumberGenerator.cpp

78–81

You should probably note, then, that the entropy here depends almost entirely on the entropy in the seed, since the command-line arguments aren't going to have much, I assume. Do you have a sense of how many bits of entropy are needed here to make this construction secure in a given context?

From Table 3 in SP 800-90A, it looks like the minimum entropy required for the construction that uses a key derivation function is the required security strength.

92–93

80-char limit (here and in a couple other places). Maybe reformat with clang-format --style=LLVM ?

113

AFAICT from SP 800-90A, the initial key is supposed to be 0, and subsequent reseeding operations are supposed to use the existing key to generate a new one.

154–155

See the description of the CTR_DRBG algorithm on page 58-59 of NIST SP 800-90A: the randomness generation process also needs to call an update function to change the secret state, including the key, each time. This is step 6 of CTR_DRBG Generate Process.

Also, it looks like there is supposed to be a reseed count that forces reseeding after a certain interval. Table 3 in SP 800-90A gives the recommended number of iterations for a given security strength.

lib/Target/X86/NOPInsertion.cpp

104

!! on bool is unnecessary

tools/opt/opt.cpp

600–609 ↗

(On Diff #4727)

I think something similar to this will have to be added to llvm-lto to support nop code generation there, too. Maybe instead of repeating the same snippet everywhere, you could make this a function in RandomNumberGenerator. Something like AddSeedData?

[ahomescu]

lib/Target/X86/NOPInsertion.cpp

104

This is supposed to be a bool->int cast (false->0, true->1). I think I might have been getting compilation errors without it, have to check...

[rinon]

Rewrote the RNG somewhat to comply with CTR_DRBG. Generation now complies with the spec, although without reseeding. Since we need predictability and only have a single entropy source (command line flag), we cannot reseed with additional entropy.
Also added TargetOption updates in a few places where it got forgotton and fixed a bool cast.

[rinon]

lib/Support/RandomNumberGenerator.cpp

154–155

The existing RNG we were using was based on CTR_DRBG, but missing a few pieces which you very correctly point out. Thanks! I've tried to make it as complying as possible, without reseeding now.

tools/opt/opt.cpp

600–609 ↗

(On Diff #4727)

I've added a function, but also removed this setting everywhere but clang. This "EntropyData" (now called more correctly SaltData) is only needed during a larger build so that every compilation can use the same seed, but still result in a different random stream. Clang now sets this SaltData based on input filenames, to make each invocation unique.

[tmroeder]

LGTM now, other than a minor comment fix. The crypto RNG implementation now looks to be a special case of CTR_DRBG. However, I'm new to LLVM, so someone other than me should still look at the code and approve it.

CC'ing Nadav as the owner of the X86 backend: Nadav, can you please look at this?

Thanks,

Tom

lib/Support/RandomNumberGenerator.cpp

141

This code depends on the fact that AES_BLOCK_SIZE divides SEEDLEN exactly. This is probably OK to assume, but it should be documented in a comment on the definition of SEEDLEN.

[rinon]

• Added a comment to note block size assumptions.

[rinon]

Trying to convince arcanist to upload the correct diffs...

[nadav]

Hi Stephen,

Thanks for submitting the patch. I have a few questions. It is not clear to me why you need cryptographically strong randomization at *compile* time. You absolutely do need this kind of randomization when distributing the binary, not when compiling it. To the best of my understanding in order to predict a safe jump location you need to read the binary data anyway, so using a strong crypto is not better than any pseudo random number generator.

Thanks,
Nadav

[rinon]

• Replaced OpenSSL AES RNG with an MD5 HMAC_DRBG RNG
• Updating test cases for new RNG
• Formatting and comments for the RNG

[nadav]

Hi Stephen,

Why did you need to add a new NOP flag and the isInsertedNOP function ?

Thanks,
Nadav

[yln]

Hello everyone!
A lot of time has passed since someone was actively pursuing this issue.
I will try to push this forward and incorporate any remarks you might have.

[yln]

Nadav mentioned that we do not want to slow down users by adding a flag 'isInsertedNOP' to the MachineInst class and checking against it in the MachineBasicBlock::getFirstTerminator methods.

This update addresses this concern by simply not inserting NOPs between terminators (less secure, but simplest solution for now).

[yln]

Move patch forward to ToT.

[silvas]

Was there ever consensus that we want to maintain this in LLVM? I just
looked back at the original thread on llvmdev, and it looked like basically:

• A number of security folks having an inconclusive, wandering,

back-and-forth discussion about various security things that should have
been done on a security mailing list.

• Lots of "this seems maybe interesting, but ..." with the "but ..." not

clearly addressed in any way. Often times the "but ..." was an alternative
approach that would be more maintainable, effective, and/or fit in better
with existing deployment processes.

• No concrete use cases. Who is going to be deploying this? If nobody is

deploying, then how do we know it will be maintained? It seems like the
initial patch submitter has already jumped ship on this patch; doesn't
exactly inspire confidence.

It seems like basically nobody who participated in the original discussion
on llvmdev is participating in this patch review either. Especially the
people who had doubts don't seem to be participating; those doubts need to
be addressed.

Also, at the very least, adding the RNG should be split out into a separate
patch.

• Sean Silva

[jfb]

I discussed this change with the UCI folks offline: the PNaCl team is interested in their approach (binary diversity) And we'd like to help with the reviews to get this upstream into LLVM.

The current main point of contention seems to be the RNG. Now that LLVM is slowly moving to C++11 would it be acceptable to use one of <random>'s pseudo-random number generators, and use std::random_device when a random seed is needed? Chandler was asking folks to hold off on using C++11 features for the near future (to make sure the switchover is clean), and I'm not sure <random> is whitelisted, but I'd like to get the discussion going.

Once we settle the RNG issue we could commit the RNG's state as its own change, and handle NOP insertion in a different change?

[jfb]

C++11 now seems to be OK with LLVM (see http://llvm-reviews.chandlerc.com/D2905). Could we start the discussion about using it for this patch instead of having a separate RNG?

Bikeshed *which* RNG to use, and how to use random_device and such to seed things, as well as being able to feed randomness for an external file (which Geremy suggested offline).

[perl]

Thanks for getting back to us on that. Agree wholeheartedly that we should
use the C++11 RNG for now in the interest of landing the initial patch.
Stay tuned for an updated patch.

Best,
Per

[atrick]

I'm completely ignoring RNG, which should be a separate patch.

I don't think we should add a dependence from CodeGen to Instrumentation. Is that necessary?

RandomizeSchedule can be a separate patch from random nops. Doing this in the SelectionDAG scheduler may not be very effective because the MachineScheduler and PostRA scheduler can undo it. I think the right way to handle this is for the target to schedule a PostRA scheduling pass that just does the randomization.

There is currently an option, -misched-postra, that enables the MachineScheduler as a postRA pass. Alternatively, a target could schedule the pass itself using one of the TargetPassConfig hooks and calling:

addPass(&PostMachineSchedulerID);

Then the target can override TargetPassConfig::createPostMachineScheduler and instantiate a scheduler something like this:

return new ScheduleDAGMI(C, new PostRandomScheduler(C), /*IsPostRA=*/true);

Where PostRandomScheduler would be a MachineSchedStrategy implemented very similar to InstructionShuffler.

Alternatively, this can be done for all targets by adding an option that forces
PostMachineScheduler::createPostMachineScheduler to use the PostRandomScheduler.

I don't understand the nop insertion percentage math. Each instruction gets MaxNOPsPerInstruction rolls. If I allow 8 nops per instruction, then the chance an instruction does NOT have a nop is 1/256. I don't think you should retry after a failed roll--then the percentage would make sense.

Juergen Ributzka recently added MI level support for inserting variable sized x86 nops. You might want to look at that.

[yln]

The updated replaces the custom RNG implementation with C++11 facilities.
Andrew Trick made good suggestions on how to improve the patch.
I will try to incorporate those (starting with splitting RNG - NOP insertion - schedule randomization int separate patches).

[alexr]

Is this deterministic for multi-threaded builds?

Alex

[yln]

You are referring to the fact that the RNG instance id is part of the seed, right?

Seeds[2] = InstanceID;

The initial patch had this so I left it in, but indeed this looks strange from the angle of reproducible builds.
I will remove it.

[alexr]

I was referring to the call to AtomicIncrement as a way to get a seed for each thread. The threads aren't guaranteed to enter that code in the same order, so there is no guarantee of determinism for a given seed.

Alex

[yln]

Does anyone have an authoritative answer whether or not the C++11 <random> facilities are thread save?
The docs (http://en.cppreference.com/w/cpp/numeric/random) do not mention thread safety, so I assume they are not.

[yln]

Do not include RNG instance ID in the seed value.

This enables reproducible builds in a multi-threaded environment.
It might also reduce security, but this is not our topmost concern
as we are not using a cryptographically secure RNG to start with.

[yln]

Adapt tests after changing RNG seed.

[yln]

This patch is now split into smaller, more manageable chunks.
Please subscribe if you are interested in participating, thanks.

include/llvm/CodeGen/CommandFlags.h

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>
+NOPInsertion("nop-insertion",
+             cl::desc("Randomly add NOPs."),
+             cl::init(false));
+
+
 // Common utility function tightly tied to the options listed here. Initializes
 // a TargetOptions object with CodeGen flags and returns it.
 static inline TargetOptions InitTargetOptionsFromCodeGenFlags() {
   TargetOptions Options;
   Options.LessPreciseFPMADOption = EnableFPMAD;
   Options.NoFramePointerElim = DisableFPElim;
   Options.AllowFPOpFusion = FuseFPOps;
   Options.UnsafeFPMath = EnableUnsafeFPMath;
   Options.NoInfsFPMath = EnableNoInfsFPMath;
   Options.NoNaNsFPMath = EnableNoNaNsFPMath;
   Options.HonorSignDependentRoundingFPMathOption =
       EnableHonorSignDependentRoundingFPMath;
   Options.UseSoftFloat = GenerateSoftFloatCalls;
   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.EnableSegmentedStacks = SegmentedStacks;
   Options.UseInitArray = UseInitArray;
+  Options.NOPInsertion = NOPInsertion;
   return Options;
 }
 
 #endif

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.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_RANDOMNUMBERGENERATOR_H_
+#define LLVM_SUPPORT_RANDOMNUMBERGENERATOR_H_
+
+#include "llvm/ADT/StringRef.h"
+#include <string>
+#include <random>
+
+namespace llvm {
+
+class RandomNumberGenerator {
+public:
+  /// \brief Add additional personalization data to the RNG seed.
+  ///
+  /// This function should be used to add deterministic command line
+  /// argument data to the RNG initialization, resulting in a
+  /// different stream of random numbers for each invocation during a
+  /// build. The input to this function should be unique per
+  /// compilation unit.
+  static void SetSalt(const StringRef &Salt);
+
+  static RandomNumberGenerator *Get();
+
+  /// \brief Returns a random number in the range [0, Max).
+  uint64_t Random(uint64_t Max);
+
+private:
+  std::default_random_engine generator;
+
+  void Seed(StringRef Salt, uint64_t Seed);
+
+  RandomNumberGenerator();
+  // Noncopyable.
+  RandomNumberGenerator(const RandomNumberGenerator &other) = delete;
+  RandomNumberGenerator &
+  operator=(const RandomNumberGenerator &other) = delete;
+};
+}
+
+#endif

include/llvm/Target/TargetOptions.h

public:
     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),
-          EnableSegmentedStacks(false), UseInitArray(false),
+          EnableSegmentedStacks(false), NOPInsertion(false), UseInitArray(false),
           DisableIntegratedAS(false), CompressDebugSections(false),
           TrapFuncName(""), FloatABIType(FloatABI::Default),
           AllowFPOpFusion(FPOpFusion::Standard) {}
 
     /// 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:
     /// 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;
 
     unsigned EnableSegmentedStacks : 1;
 
+    /// Attempt to insert NOPs
+    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/SelectionDAG/ScheduleDAGRRList.cpp

 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/ScheduleHazardRecognizer.h"
 #include "llvm/CodeGen/SelectionDAGISel.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/InlineAsm.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/TargetInstrInfo.h"
 #include "llvm/Target/TargetLowering.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include <climits>
 using namespace llvm;
 
static cl::opt<int> MaxReorderWindow(
   "max-sched-reorder", cl::Hidden, cl::init(6),
   cl::desc("Number of instructions to allow ahead of the critical path "
            "in sched=list-ilp"));
 
 static cl::opt<unsigned> AvgIPC(
   "sched-avg-ipc", cl::Hidden, cl::init(1),
   cl::desc("Average inst/cycle whan no target itinerary exists."));
 
+static cl::opt<bool> RandomizeSchedule(
+  "sched-randomize",
+  cl::desc("Enable randomization of scheduling"),
+  cl::init(false));
+
+static cl::opt<unsigned> SchedRandPercentage(
+  "sched-randomize-percentage",
+  cl::desc("Percentage of instructions where schedule is randomized"),
+  cl::init(50));
+
+
 namespace {
 //===----------------------------------------------------------------------===//
 /// ScheduleDAGRRList - The actual register reduction list scheduler
 /// implementation.  This supports both top-down and bottom-up scheduling.
 ///
 class ScheduleDAGRRList : public ScheduleDAGSDNodes {
 private:
   /// NeedLatency - True if the scheduler will make use of latency information.
#endif
   (void)DAG;
   return popFromQueueImpl(Q, Picker);
 }
 
 template<class SF>
 class RegReductionPriorityQueue : public RegReductionPQBase {
   SF Picker;
 
+  static SUnit *popRandom(std::vector<SUnit*> &Q) {
+    RandomNumberGenerator *randGen = RandomNumberGenerator::Get();
+    size_t randIndex = randGen->Random(Q.size());
+    SUnit *V = Q[randIndex];
+    if (randIndex < Q.size() - 1)
+      std::swap(Q[randIndex], Q.back());
+    Q.pop_back();
+    return V;
+  }
+
 public:
   RegReductionPriorityQueue(MachineFunction &mf,
                             bool tracksrp,
                             bool srcorder,
                             const TargetInstrInfo *tii,
                             const TargetRegisterInfo *tri,
                             const TargetLowering *tli)
     : RegReductionPQBase(mf, SF::HasReadyFilter, tracksrp, srcorder,
                          tii, tri, tli),
       Picker(this) {}
 
   bool isBottomUp() const override { return SF::IsBottomUp; }
 
   bool isReady(SUnit *U) const override {
     return Picker.HasReadyFilter && Picker.isReady(U, getCurCycle());
   }
 
   SUnit *pop() override {
     if (Queue.empty()) return NULL;
 
-    SUnit *V = popFromQueue(Queue, Picker, scheduleDAG);
+    SUnit *V;
+    if (RandomizeSchedule) {
+      RandomNumberGenerator *randGen = RandomNumberGenerator::Get();
+      unsigned int Roll = randGen->Random(100);
+      if (Roll < SchedRandPercentage) {
+        V = popRandom(Queue);
+      } else {
+        V = popFromQueue(Queue, Picker, scheduleDAG);
+      }
+    } else {
+      V = popFromQueue(Queue, Picker, scheduleDAG);
+    }
     V->NodeQueueId = 0;
     return V;
   }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   void dump(ScheduleDAG *DAG) const {
     // Emulate pop() without clobbering NodeQueueIds.
     std::vector<SUnit*> DumpQueue = Queue;

lib/LTO/LTOCodeGenerator.cpp

void LTOCodeGenerator::setTargetOptions(TargetOptions options) {
   Options.NoZerosInBSS = options.NoZerosInBSS;
   Options.GuaranteedTailCallOpt = options.GuaranteedTailCallOpt;
   Options.DisableTailCalls = options.DisableTailCalls;
   Options.StackAlignmentOverride = options.StackAlignmentOverride;
   Options.TrapFuncName = options.TrapFuncName;
   Options.PositionIndependentExecutable = options.PositionIndependentExecutable;
   Options.EnableSegmentedStacks = options.EnableSegmentedStacks;
   Options.UseInitArray = options.UseInitArray;
+  Options.NOPInsertion = options.NOPInsertion;
 }
 
 void LTOCodeGenerator::setDebugInfo(lto_debug_model debug) {
   switch (debug) {
   case LTO_DEBUG_MODEL_NONE:
     EmitDwarfDebugInfo = false;
     return;
 

lib/Support/CMakeLists.txt

add_llvm_library(LLVMSupport
   Locale.cpp
   LockFileManager.cpp
   ManagedStatic.cpp
   MemoryBuffer.cpp
   MemoryObject.cpp
   MD5.cpp
   PluginLoader.cpp
   PrettyStackTrace.cpp
+  RandomNumberGenerator.cpp
   Regex.cpp
   SmallPtrSet.cpp
   SmallVector.cpp
   SourceMgr.cpp
   Statistic.cpp
   StreamableMemoryObject.cpp
   StringExtras.cpp
   StringMap.cpp

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).
+// 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/ManagedStatic.h"
+#include "llvm/Support/ThreadLocal.h"
+
+using namespace llvm;
+
+// Initialized once, then only read by threads, so no locking required.
+static std::string SaltData;
+
+// Do not change to cl::opt<uint64_t> since this silently breaks argument parsing.
+static cl::opt<unsigned long long>
+RandomSeed("rng-seed", cl::value_desc("seed"),
+           cl::desc("Seed for the random number generator"), cl::init(0));
+
+static cl::opt<std::string, true>
+SaltDataOpt("entropy-data",
+            cl::desc("Entropy data for the RNG (testing only, should be set "
+                     "by command line options"),
+            cl::Hidden, cl::location(SaltData));
+
+static ManagedStatic<sys::ThreadLocal<const RandomNumberGenerator> > Instance;
+
+void RandomNumberGenerator::SetSalt(const StringRef &Salt) {
+  SaltData = Salt;
+}
+
+RandomNumberGenerator *RandomNumberGenerator::Get() {
+  RandomNumberGenerator *RNG =
+      const_cast<RandomNumberGenerator *>(Instance->get());
+
+  if (RNG == 0) {
+    RNG = new RandomNumberGenerator;
+    Instance->set(RNG);
+  }
+
+  return RNG;
+}
+
+// Note that every new RNG will produce the same stream of
+// pseudo-random numbers, unless SetSalt is called again.
+RandomNumberGenerator::RandomNumberGenerator() {
+  if (RandomSeed == 0 && SaltData.empty())
+    DEBUG(errs()
+          << "Warning! Using unseeded and unsalted random number generator\n");
+
+  Seed(SaltData, RandomSeed);
+}
+
+uint64_t RandomNumberGenerator::Random(uint64_t Max) {
+  std::uniform_int_distribution<uint64_t> distribution(0, Max - 1);
+  return distribution(generator);
+}
+
+void RandomNumberGenerator::Seed(StringRef Salt, uint64_t Seed) {
+  DEBUG(dbgs() << "Re-Seeding RNG from salt and seed\n");
+  DEBUG(dbgs() << "Salt: " << Salt << "\n");
+  DEBUG(dbgs() << "Seed: " << Seed << "\n");
+
+  // Sequence: Seed-low, Seed-high, Salt...
+  unsigned SeedSize = Salt.size() + 2;
+  unsigned Seeds[SeedSize];
+  Seeds[0] = Seed;
+  Seeds[1] = Seed >> 32;
+  for (unsigned i = 0; i < Salt.size(); ++i)
+    Seeds[2 + i] = Salt[i];
+
+  std::seed_seq SeedSeq(Seeds, Seeds + SeedSize);
+  generator.seed(SeedSeq);
+}

lib/Target/X86/CMakeLists.txt

 set(LLVM_TARGET_DEFINITIONS X86.td)
 
 tablegen(LLVM X86GenRegisterInfo.inc -gen-register-info)
 tablegen(LLVM X86GenDisassemblerTables.inc -gen-disassembler)
 tablegen(LLVM X86GenInstrInfo.inc -gen-instr-info)
 tablegen(LLVM X86GenAsmWriter.inc -gen-asm-writer)
 tablegen(LLVM X86GenAsmWriter1.inc -gen-asm-writer -asmwriternum=1)
 tablegen(LLVM X86GenAsmMatcher.inc -gen-asm-matcher)
 tablegen(LLVM X86GenDAGISel.inc -gen-dag-isel)
 tablegen(LLVM X86GenFastISel.inc -gen-fast-isel)
 tablegen(LLVM X86GenCallingConv.inc -gen-callingconv)
 tablegen(LLVM X86GenSubtargetInfo.inc -gen-subtarget)
 add_public_tablegen_target(X86CommonTableGen)
 
 set(sources
+  NOPInsertion.cpp
   X86AsmPrinter.cpp
   X86COFFMachineModuleInfo.cpp
   X86CodeEmitter.cpp
   X86FastISel.cpp
   X86FloatingPoint.cpp
   X86FrameLowering.cpp
   X86ISelDAGToDAG.cpp
   X86ISelLowering.cpp

lib/Target/X86/NOPInsertion.cpp

+//===- NOPInsertion.cpp - Insert NOPs between instructions ----------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains the NOPInsertion pass.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "nop-insertion"
+#include "X86InstrBuilder.h"
+#include "X86InstrInfo.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/RandomNumberGenerator.h"
+#include "llvm/Target/TargetInstrInfo.h"
+
+using namespace llvm;
+
+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");
+
+namespace {
+class NOPInsertionPass : public MachineFunctionPass {
+
+  static char ID;
+
+  bool is64Bit;
+
+public:
+  NOPInsertionPass(bool is64Bit_) :
+      MachineFunctionPass(ID), is64Bit(is64Bit_) {
+  }
+
+  virtual bool runOnMachineFunction(MachineFunction &MF);
+
+  virtual const char *getPassName() const {
+    return "NOP insertion pass";
+  }
+
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.setPreservesCFG();
+    MachineFunctionPass::getAnalysisUsage(AU);
+  }
+};
+}
+
+char NOPInsertionPass::ID = 0;
+
+enum { NOP,
+       MOV_EBP, MOV_ESP,
+       LEA_ESI, LEA_EDI,
+       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 },
+};
+
+bool NOPInsertionPass::runOnMachineFunction(MachineFunction &Fn) {
+  const TargetInstrInfo *TII = Fn.getTarget().getInstrInfo();
+  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 = RandomNumberGenerator::Get()->Random(100);
+        if (Roll >= NOPInsertionPercentage)
+          continue;
+
+        unsigned NOPCode = RandomNumberGenerator::Get()->Random(MAX_NOPS);
+
+        MachineInstr *NewMI = NULL;
+        unsigned reg = nopRegs[NOPCode][is64Bit];
+        switch (NOPCode) {
+        case NOP:
+          NewMI = BuildMI(*BB, I, I->getDebugLoc(), TII->get(X86::NOOP));
+          break;
+        case MOV_EBP:
+        case MOV_ESP: {
+          unsigned opc = is64Bit ? X86::MOV64rr : X86::MOV32rr;
+          NewMI = BuildMI(*BB, I, I->getDebugLoc(), TII->get(opc), reg)
+            .addReg(reg);
+          break;
+        }
+
+        case LEA_ESI:
+        case LEA_EDI: {
+          unsigned opc = is64Bit ? X86::LEA64r : X86::LEA32r;
+          NewMI = addRegOffset(BuildMI(*BB, I, I->getDebugLoc(),
+                                       TII->get(opc), reg),
+                               reg, false, 0);
+          break;
+        }
+        }
+
+        if (NewMI != NULL)
+          ++InsertedNOPs;
+      }
+      // Do not insert NOPs between terminators.
+      if (I == FirstTerm)
+        break;
+
+      I = NextI;
+    }
+  }
+  return true;
+}
+
+namespace llvm {
+  FunctionPass *createNOPInsertionPass(bool is64Bit) {
+    return new NOPInsertionPass(is64Bit);
+  }
+}

lib/Target/X86/X86.h

 ///
 FunctionPass *createX86FloatingPointStackifierPass();
 
 /// createX86IssueVZeroUpperPass - This pass inserts AVX vzeroupper instructions
 /// before each call to avoid transition penalty between functions encoded with
 /// AVX and SSE.
 FunctionPass *createX86IssueVZeroUpperPass();
 
+/// createNOPInsertionPass - This pass adds NOPs at random between
+/// instructions.
+FunctionPass *createNOPInsertionPass(bool is64Bit);
+
 /// createX86CodeEmitterPass - Return a pass that emits the collected X86 code
 /// to the specified MCE object.
 FunctionPass *createX86JITCodeEmitterPass(X86TargetMachine &TM,
                                           JITCodeEmitter &JCE);
 
 /// createX86EmitCodeToMemory - Returns a pass that converts a register
 /// allocated function into raw machine code in a dynamically
 /// allocated chunk of memory.

lib/Target/X86/X86TargetMachine.cpp

if (getOptLevel() != CodeGenOpt::None &&
     ShouldPrint = true;
   }
   if (getOptLevel() != CodeGenOpt::None &&
       getX86Subtarget().LEAusesAG()){
     addPass(createX86FixupLEAs());
     ShouldPrint = true;
   }
 
+  if (TM->Options.NOPInsertion) {
+    addPass(createNOPInsertionPass(getX86Subtarget().is64Bit()));
+    ShouldPrint = true;
+  }
+
   return ShouldPrint;
 }
 
 bool X86TargetMachine::addCodeEmitter(PassManagerBase &PM,
                                       JITCodeEmitter &JCE) {
   PM.add(createX86JITCodeEmitterPass(*this, JCE));
 
   return false;
 }

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

+; RUN: llc < %s -rng-seed=1 -nop-insertion -nop-insertion-percentage=10 \
+; RUN:     | FileCheck %s --check-prefix=PERCENT10
+; RUN: llc < %s -rng-seed=1 -nop-insertion -nop-insertion-percentage=50 \
+; RUN:     | FileCheck %s --check-prefix=PERCENT50
+; RUN: llc < %s -rng-seed=1 -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: movq   %rbp, %rbp
+
+; PERCENT50: movq   %rbp, %rbp
+; PERCENT50: nop
+; PERCENT50: leaq   (%rdi), %rdi
+; PERCENT50: leaq   (%rsi), %rsi
+; PERCENT50: leaq   (%rsi), %rsi
+; PERCENT50: leaq   (%rsi), %rsi
+; PERCENT50: leaq   (%rdi), %rdi
+; PERCENT50: nop
+; PERCENT50: leaq   (%rsi), %rsi
+
+; PERCENT100: movq  %rbp, %rbp
+; PERCENT100: nop
+; PERCENT100: leaq  (%rdi), %rdi
+; PERCENT100: leaq  (%rsi), %rsi
+; PERCENT100: leaq  (%rsi), %rsi
+; PERCENT100: movq  %rsp, %rsp
+; PERCENT100: leaq  (%rdi), %rdi
+; PERCENT100: leaq  (%rdi), %rdi
+; PERCENT100: movq  %rsp, %rsp
+; PERCENT100: movq  %rbp, %rbp
+; PERCENT100: movq  %rsp, %rsp
+; PERCENT100: leaq  (%rsi), %rsi

test/CodeGen/X86/nop-insert.ll

+; RUN: llc < %s -nop-insertion | FileCheck %s
+; RUN: llc < %s -nop-insertion -entropy-data="test" -rng-seed=1 | FileCheck %s --check-prefix=SEED1
+; RUN: llc < %s -nop-insertion -entropy-data="test" -rng-seed=25 | FileCheck %s --check-prefix=SEED2
+; RUN: llc < %s -nop-insertion -entropy-data="test" -rng-seed=1534 | FileCheck %s --check-prefix=SEED3
+; RUN: llc < %s -nop-insertion -entropy-data="different entropy" -rng-seed=1 | FileCheck %s --check-prefix=ENTROPY
+
+; This test case checks that NOPs are inserted, and that the RNG seed
+; affects both the placement and choice of these NOPs.
+
+; CHECK: leaq (%rdi), %rdi
+; CHECK: movq %rsp, %rsp
+
+; SEED1: leaq (%rsi), %rsi
+; SEED1-NOT: movq
+; SEED1-NOT: nop
+
+; SEED2: nop
+; SEED2-NOT: movq
+; SEED2-NOT: leaq
+
+; SEED3-NOT: movq
+; SEED3-NOT: nop
+; SEED3-NOT: leaq
+
+; ENTROPY: movq %rsp, %rsp
+; ENTROPY-NOT: nop
+; ENTROPY-NOT: leaq
+
+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/sched-rnd-test.ll

+; RUN: llc < %s -rng-seed=1 -sched-randomize -sched-randomize-percentage=100 | FileCheck %s --check-prefix=SEED1
+; RUN: llc < %s -rng-seed=5 -sched-randomize -sched-randomize-percentage=100 | FileCheck %s --check-prefix=SEED2
+; RUN: llc < %s -rng-seed=5 -sched-randomize -sched-randomize-percentage=50 | FileCheck %s --check-prefix=PERCENTAGE
+
+; This test case checks that the schedule randomization is changing
+; scheduling decisions, that different seeds result in different
+; schedules, and that the percentage alters the amount of
+; randomization
+
+define i32 @test(i32 %x, i32 %y, i32 %z) {
+entry:
+    %a = add i32 %x, %y
+    %b = add i32 %x, %z
+    %c = add i32 %y, %z
+    %d = mul i32 %a, %b
+    %e = mul i32 %d, %c
+    ret i32 %e
+}
+
+; SEED1: leal (%rdi,%rsi), %eax
+; SEED1-NEXT: addl  %edx, %edi
+; SEED1-NEXT: imull %edi, %eax
+; SEED1-NEXT: addl  %edx, %esi
+; SEED1-NEXT: imull %esi, %eax
+
+; SEED2: leal (%rdi,%rdx), %ecx
+; SEED2-NEXT: leal  (%rdi,%rsi), %eax
+; SEED2-NEXT: imull %ecx, %eax
+; SEED2-NEXT: addl  %edx, %esi
+; SEED2-NEXT: imull %esi, %eax
+
+; PERCENTAGE: leal  (%rdi,%rsi), %eax
+; PERCENTAGE: addl  %edx, %edi
+; PERCENTAGE: addl  %edx, %esi
+; PERCENTAGE: imull %edi, %eax
+; PERCENTAGE: imull %esi, %eax