Index: include/llvm/CodeGen/CommandFlags.h =================================================================== --- include/llvm/CodeGen/CommandFlags.h +++ include/llvm/CodeGen/CommandFlags.h @@ -207,6 +207,12 @@ cl::desc("Emit functions into separate sections"), cl::init(false)); +cl::opt +NoopInsertion("noop-insertion", + cl::desc("Randomly add Noop instructions to create fine-grained " + "code layout diversity."), + cl::init(false)); + cl::opt JTableType("jump-table-type", cl::desc("Choose the type of Jump-Instruction Table for jumptable."), @@ -284,6 +290,7 @@ Options.UseInitArray = !UseCtors; Options.DataSections = DataSections; Options.FunctionSections = FunctionSections; + Options.NoopInsertion = NoopInsertion; Options.MCOptions = InitMCTargetOptionsFromFlags(); Options.JTType = JTableType; Index: include/llvm/CodeGen/NoopInsertion.h =================================================================== --- /dev/null +++ include/llvm/CodeGen/NoopInsertion.h @@ -0,0 +1,40 @@ +//===-- 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 + +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 RNG; +}; +} + +#endif // LLVM_CODEGEN_NOOPINSERTION_H Index: include/llvm/CodeGen/Passes.h =================================================================== --- include/llvm/CodeGen/Passes.h +++ include/llvm/CodeGen/Passes.h @@ -603,6 +603,10 @@ /// 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(); Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -205,6 +205,7 @@ void initializeMergeFunctionsPass(PassRegistry&); void initializeModuleDebugInfoPrinterPass(PassRegistry&); void initializeNoAAPass(PassRegistry&); +void initializeNoopInsertionPass(PassRegistry&); void initializeObjCARCAliasAnalysisPass(PassRegistry&); void initializeObjCARCAPElimPass(PassRegistry&); void initializeObjCARCExpandPass(PassRegistry&); Index: include/llvm/Support/RandomNumberGenerator.h =================================================================== --- include/llvm/Support/RandomNumberGenerator.h +++ include/llvm/Support/RandomNumberGenerator.h @@ -31,8 +31,24 @@ /// module. class RandomNumberGenerator { public: - /// Returns a random number in the range [0, Max). - uint_fast64_t operator()(); + typedef std::mt19937_64 RNG; + typedef RNG::result_type result_type; + + /// Returns a random number in the range [0, RNG::max()). + result_type operator()(); + + /// Returns an unbiased random number in the range [0, Max). Max + /// must be <= RNG::max(). + result_type operator()(result_type Max); + + // 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. @@ -45,7 +61,7 @@ // 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) Index: include/llvm/Target/TargetInstrInfo.h =================================================================== --- include/llvm/Target/TargetInstrInfo.h +++ include/llvm/Target/TargetInstrInfo.h @@ -32,6 +32,7 @@ class MCInst; struct MCSchedModel; class MCSymbolRefExpr; +class RandomNumberGenerator; class SDNode; class ScheduleHazardRecognizer; class SelectionDAG; @@ -866,6 +867,14 @@ 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; Index: include/llvm/Target/TargetOptions.h =================================================================== --- include/llvm/Target/TargetOptions.h +++ include/llvm/Target/TargetOptions.h @@ -78,11 +78,12 @@ 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 @@ -198,6 +199,10 @@ /// 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; Index: lib/CodeGen/CMakeLists.txt =================================================================== --- lib/CodeGen/CMakeLists.txt +++ lib/CodeGen/CMakeLists.txt @@ -71,6 +71,7 @@ MachineSink.cpp MachineTraceMetrics.cpp MachineVerifier.cpp + NoopInsertion.cpp OcamlGC.cpp OptimizePHIs.cpp PHIElimination.cpp Index: lib/CodeGen/CodeGen.cpp =================================================================== --- lib/CodeGen/CodeGen.cpp +++ lib/CodeGen/CodeGen.cpp @@ -51,6 +51,7 @@ initializeMachineSchedulerPass(Registry); initializeMachineSinkingPass(Registry); initializeMachineVerifierPassPass(Registry); + initializeNoopInsertionPass(Registry); initializeOptimizePHIsPass(Registry); initializePHIEliminationPass(Registry); initializePeepholeOptimizerPass(Registry); Index: lib/CodeGen/NoopInsertion.cpp =================================================================== --- /dev/null +++ lib/CodeGen/NoopInsertion.cpp @@ -0,0 +1,101 @@ +//===- 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 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 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 ((*RNG)(100) >= NoopInsertionPercentage) + continue; + + TII->insertNoop(BB, I, *RNG); + + ++FnInsertedNoopCount; + } + + if (I == FirstTerm) + break; + } + } + + InsertedNoops += FnInsertedNoopCount; + + return FnInsertedNoopCount > 0; +} Index: lib/CodeGen/Passes.cpp =================================================================== --- lib/CodeGen/Passes.cpp +++ lib/CodeGen/Passes.cpp @@ -582,6 +582,9 @@ addPass(createGCInfoPrinter(dbgs()), false, false); } + if (TM->Options.NoopInsertion) + addPass(&NoopInsertionID); + // Basic block placement. if (getOptLevel() != CodeGenOpt::None) addBlockPlacement(); Index: lib/Support/RandomNumberGenerator.cpp =================================================================== --- lib/Support/RandomNumberGenerator.cpp +++ lib/Support/RandomNumberGenerator.cpp @@ -53,3 +53,17 @@ uint_fast64_t RandomNumberGenerator::operator()() { return Generator(); } + +uint_fast64_t RandomNumberGenerator::operator()(result_type Max) { + // To produce unbiased results, the maximum random value must be a + // multiple of Max so the resulting remainder is uniformly + // distributed. MaxMultiple is the largest multiple of Max < + // RNG::max(), the maximum supported result from the underlying RNG. + result_type MaxMultiple = Max * (max()/Max); + + result_type RandomNumber = Generator(); + while (RandomNumber >= MaxMultiple) + RandomNumber = Generator(); + + return RandomNumber % Max; +} Index: lib/Target/X86/X86InstrInfo.h =================================================================== --- lib/Target/X86/X86InstrInfo.h +++ lib/Target/X86/X86InstrInfo.h @@ -360,6 +360,13 @@ 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 Index: lib/Target/X86/X86InstrInfo.cpp =================================================================== --- lib/Target/X86/X86InstrInfo.cpp +++ lib/Target/X86/X86InstrInfo.cpp @@ -34,6 +34,7 @@ #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 @@ -5518,6 +5519,64 @@ 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}, + }; + + 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); Index: test/CodeGen/Mips/noop-insert.ll =================================================================== --- /dev/null +++ test/CodeGen/Mips/noop-insert.ll @@ -0,0 +1,24 @@ +; RUN: llc < %s -march=mips -noop-insertion | FileCheck %s +; RUN: llc < %s -march=mips -noop-insertion -rng-seed=10 | 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. + +; CHECK: mul +; CHECK-NEXT: nop +; CHECK-NEXT: jr + +; SEED1: 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 +} Index: test/CodeGen/PowerPC/noop-insert.ll =================================================================== --- /dev/null +++ test/CodeGen/PowerPC/noop-insert.ll @@ -0,0 +1,28 @@ +; RUN: llc < %s -march=ppc32 -noop-insertion | FileCheck %s +; RUN: llc < %s -march=ppc32 -noop-insertion -rng-seed=10 | 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. + +; CHECK: mullw +; CHECK-NEXT: nop +; CHECK-NEXT: add +; CHECK-NEXT: blr + +; SEED1: mullw +; SEED1-NEXT: add +; 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 +} Index: test/CodeGen/X86/noop-insert-percentage.ll =================================================================== --- /dev/null +++ test/CodeGen/X86/noop-insert-percentage.ll @@ -0,0 +1,70 @@ +; 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: leaq (%rsi), %rsi +; PERCENT10: retq + +; PERCENT50: movq %rbp, %rbp +; PERCENT50: nop +; PERCENT50: leaq (%rsi), %rsi +; PERCENT50: leaq (%rdi), %rdi +; PERCENT50: movq %rbp, %rbp +; PERCENT50: movq %rsp, %rsp +; PERCENT50: retq + +; 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 +; PERCENT100: retq + + +; X86-PERCENT100: leal (%edi), %edi +; X86-PERCENT100: leal (%edi), %edi +; X86-PERCENT100: movl %esp, %esp +; X86-PERCENT100: movl %esp, %esp +; X86-PERCENT100: leal (%edi), %edi +; X86-PERCENT100: leal (%esi), %esi +; X86-PERCENT100: leal (%edi), %edi +; X86-PERCENT100: movl %ebp, %ebp +; X86-PERCENT100: movl %esp, %esp +; X86-PERCENT100: leal (%esi), %esi +; X86-PERCENT100: nop +; X86-PERCENT100: leal (%esi), %esi +; X86-PERCENT100: leal (%esi), %esi +; X86-PERCENT100: movl %ebp, %ebp +; X86-PERCENT100: movl %esp, %esp +; X86-PERCENT100: retl Index: test/CodeGen/X86/noop-insert.ll =================================================================== --- /dev/null +++ test/CodeGen/X86/noop-insert.ll @@ -0,0 +1,44 @@ +; 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. + +; CHECK: imull +; CHECK-NEXT: leaq (%rsi), %rsi +; CHECK-NEXT: leal +; CHECK-NEXT: retq + +; SEED1: imull +; SEED1-NEXT: movq %rbp, %rbp +; SEED1-NEXT: leal +; SEED1-NEXT: retq + +; SEED2: imull +; SEED2-NEXT: movq %rsp, %rsp +; SEED2-NEXT: leal +; SEED2-NEXT: retq + +; SEED3: imull +; SEED3-NEXT: leal +; SEED3-NEXT: movq %rsp, %rsp +; SEED3-NEXT: retq + +; The operand of the following is used to distinguish from a movl NOOP +; x86_32: movl 4(%esp), +; x86_32-NEXT: leal (%esi), %esi +; x86_32-NEXT: imull +; x86_32-NEXT: addl +; x86_32-NEXT: leal (%edi), %edi +; 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 +}