Randomize instruction scheduling to increase security against ROP attacks (llvm)

[yln]

Summary

Modifies the selection DAG scheduler to randomize instruction selection to introduce diversity with the goal of increasing security against most return-oriented programming attacks.

Command line options:

-sched-randomize // Enable the schedule randomizer.
-sched-randomize-percentage=X // X% of instructions are scheduled randomly (default: 50%, requires -sched-randomize).

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

[jfb]

lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

115

Same as other review: cl::cat, and check that this isn't over 100%.

Actually why would you ever set scheduler randomization to less than 100%? IMO you should either randomize all-out, or not at all. Could you just drop the percentage from this change?

1773

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?

1804

Same on TLS.

test/CodeGen/X86/sched-rnd-test.ll

3

I think you need to specify a target? This test won't work if x86 isn't the default.

18

Do you think that it would be possible to test that dependencies between instructions are respected? Say with a function that has a long dependency chain so that statistically if there were a bug you'd see at least one invalid swap?

[rinon]

lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

115

We intended this to be a knob to adjust a performance vs security tradeoff. In order to make sure that we don't affect performance too much, we wanted to set a lower default, and allow users to up this if they wish.

[jfb]

lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

115

I see. Once this change is further along could you quantify the performance difference, and add those numbers to the commit message? I.e. run SPEC2k or something with a few randomization percentages, and figure out what's in the noise. This could also help choose an acceptable default for the option, where the default gives a schedule randomization that's statistically equivalent to general benchmarking noise.

lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

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

   "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

 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,

   SUnit *pop() override {
     if (Queue.empty()) return nullptr;
 
-    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;
   }

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, %esi
+; SEED1-NEXT: addl  %edx, %edi
+; SEED1-NEXT: imull %edi, %eax
+; SEED1-NEXT: imull %esi, %eax
+
+; SEED2: leal (%rdi,%rsi), %eax
+; SEED2-NEXT: addl  %edx, %edi
+; SEED2-NEXT: imull %edi, %eax
+; SEED2-NEXT: addl  %edx, %esi
+; SEED2-NEXT: imull %esi, %eax
+
+; PERCENTAGE: leal  (%rdi,%rsi), %eax
+; PERCENTAGE: addl  %edx, %esi
+; PERCENTAGE: addl  %edx, %edi
+; PERCENTAGE: imull %edi, %eax
+; PERCENTAGE: imull %esi, %eax