Subzero: Randomize immediates by constant blinding or pooling.

src/IceTargetLoweringX8632.cpp

Index: src/IceTargetLoweringX8632.cpp
diff --git a/src/IceTargetLoweringX8632.cpp b/src/IceTargetLoweringX8632.cpp
index ebc0bae319fc44d9d509e67999f088e905586076..3d533d21eae9a90c8458e26596e59d964136dcd9 100644
--- a/src/IceTargetLoweringX8632.cpp
+++ b/src/IceTargetLoweringX8632.cpp
@@ -128,6 +128,8 @@ const uint32_t X86_CHAR_BIT = 8;
 const uint32_t X86_STACK_ALIGNMENT_BYTES = 16;
 // Size of the return address on the stack
 const uint32_t X86_RET_IP_SIZE_BYTES = 4;
+// Randomize integer immediates at least 2 bytes in size.
+const uint64_t X86_INT_IMMEDIATE_RANDOMIZATION_THRESHOLD = 65536;

[JF, 2014/08/12 05:37:47]

I find 0xFFFF more readable.

[wala, 2014/08/16 00:07:13]

Done.

 
 // Value is a size in bytes.  Return Value adjusted to the next highest
 // multiple of the stack alignment.
@@ -137,6 +139,31 @@ uint32_t applyStackAlignment(uint32_t Value) {
   return (Value + X86_STACK_ALIGNMENT_BYTES - 1) & -X86_STACK_ALIGNMENT_BYTES;
 }
 
+bool immediateShouldBeRandomized(Operand *Immediate) {
+  if (!Immediate) {
+    return false;
+  } else if (llvm::isa<ConstantRelocatable>(Immediate)) {

[Jim Stichnoth, 2014/08/13 23:30:25]

Remove "else" after "return".

[wala, 2014/08/16 00:07:12]

Done.

+    return true;
+  } else if (ConstantInteger *ConstInt =
+                 llvm::dyn_cast<ConstantInteger>(Immediate)) {
+    return ConstInt->getType() != IceType_i64 &&

[JF, 2014/08/12 05:37:47]

Why not i64?

[Jim Stichnoth, 2014/08/13 23:30:25]

i64 constants are split into i32 operations at this point, so they shouldn't
occur.  Maybe assert this?

[wala, 2014/08/16 00:07:13]

Done.

[wala, 2014/08/16 00:16:15]

Hmm, it looks like some i64 "immediates" are reaching this function when I run
the crosstests with constant blinding enabled.

I don't know the exact issue that is causing this, but I know that the call is
made in line 4234 of patchset #3 (the second usage of
immediateShouldBeRandomized() in legalize()).

+           ConstInt->getValue() >= X86_INT_IMMEDIATE_RANDOMIZATION_THRESHOLD;

[Jim Stichnoth, 2014/08/13 23:30:25]

As we discussed offline, you probably want to add
X86_INT_IMMEDIATE_RANDOMIZATION_THRESHOLD/2 before comparing to deal with
negative immediates.

+  } else {
+    return false;

[JF, 2014/08/12 05:37:47]

What about FP and vectors?

[Jim Stichnoth, 2014/08/13 23:30:26]

FP and vector constants are always pooled, due to lack of immediate addressing
mode in x86 for these types.

+  }
+}
+
+// This gives a name to the immediate so it can be identified as a
+// constant pool entry.
+IceString nameImmediate(Constant *Immediate) {
+  bool IsRelocatable = llvm::isa<ConstantRelocatable>(Immediate);
+  IceString Name;
+  llvm::raw_string_ostream NameBuf(Name);
+  NameBuf << (IsRelocatable ? "L$__reloc" : "L$") << Immediate->getType()
+          << "$" << Immediate->getPoolEntryID();
+  return NameBuf.str();
+}
+
 // Instruction set options
 namespace cl = ::llvm::cl;
 cl::opt<TargetX8632::X86InstructionSet> CLInstructionSet(
@@ -148,6 +175,23 @@ cl::opt<TargetX8632::X86InstructionSet> CLInstructionSet(
         clEnumValN(TargetX8632::SSE4_1, "sse4.1",
                    "Enable SSE 4.1 instructions"), clEnumValEnd));
 
+enum RandomizeImmediates {
+  Randomize_None,
+  Randomize_ConstantBlinding,
+  Randomize_ConstantPooling
+};
+
+cl::opt<RandomizeImmediates> CLRandomizeImmediates(
+    "randomize-immediates",
+    cl::desc("Randomize the representation of immediates"),
+    cl::init(Randomize_None),
+    cl::values(clEnumValN(Randomize_None, "none", "Don't randomize (default)"),
+               clEnumValN(Randomize_ConstantBlinding, "constant-blinding",
+                          "Use constant blinding"),
+               clEnumValN(Randomize_ConstantPooling, "constant-pooling",
+                          "Use constant pooling"),
+               clEnumValEnd));

[JF, 2014/08/12 05:37:47]

Those should probably be composable.

[Jim Stichnoth, 2014/08/13 23:30:26]

I didn't think it would add any more security to blind *and* pool a constant, so
I suggested using the enum instead of composition.  Composing also increases the
complexity and testing requirements.  (Also, constant folding is another option
that isn't yet included here.)

Unless you mean composable in the sense that some constants could be blinded and
others pooled?  Maybe with the per-instance decision made randomly?

+
 // Return a string representation of the type that is suitable for use
 // in an identifier.
 IceString typeIdentString(const Type Ty) {
@@ -859,9 +903,41 @@ template <typename T> void TargetX8632::emitConstantPool() const {
   }
 }
 
+void TargetX8632::emitPooledImmediates() const {

[JF, 2014/08/12 05:37:47]

Are redundant pooled immediates pooled at the same location (and shared between
functions)? Is their ordering predictable? Is there any effort to reduce the
number of "far" immediates from a function?

[wala, 2014/08/16 00:07:12]

Right now, the implementation uses the Subzero constant pooling infrastructure
which builds global constant pools that are emitted after all the functions have
been emitted.

The ordering of the immediates in the constant pool is predictable for
reproducibility purposes.

There's currently no code that emits per-function constant pools or tries to
locate pooled constants near the functions that use them.

+  Ostream &Str = Ctx->getStrEmit();
+  SizeT Align = typeWidthInBytesOnStack(IceType_i32);
+  // TODO: Determine the right directives to place here.
+  Str << "\t.section\t.rodata.cst" << Align << ",\"aM\",@progbits," << Align
+      << "\n";
+  Str << "\t.align\t" << Align << "\n";
+  ConstantList PooledImmediates = Ctx->getImmediatePool();
+  for (ConstantList::const_iterator I = PooledImmediates.begin(),
+           E = PooledImmediates.end(); I != E; ++I) {
+    Constant *Value = *I;
+    IceString Name = nameImmediate(Value);
+    Str << Name << ":\n";
+    if (ConstantInteger *Int = llvm::dyn_cast<ConstantInteger>(Value)) {
+      assert(Int->getType() == IceType_i32);
+      char buf[30];
+      int CharsPrinted =
+          snprintf(buf, llvm::array_lengthof(buf), "0x%x",
+                   (uint32_t) Int->getValue());
+      assert(CharsPrinted >= 0 &&
+           (size_t)CharsPrinted < llvm::array_lengthof(buf));
+      Str << "\t.long\t" << buf << "\n";
+    } else if (ConstantRelocatable *Reloc =
+                   llvm::dyn_cast<ConstantRelocatable>(Value)) {
+      Str << "\t.long\t";
+      Reloc->emit(Ctx);
+      Str << "\n";
+    }
+  }
+}
+
 void TargetX8632::emitConstants() const {
   emitConstantPool<PoolTypeConverter<float> >();
   emitConstantPool<PoolTypeConverter<double> >();
+  emitPooledImmediates();
 
   // No need to emit constants from the int pool since (for x86) they
   // are embedded as immediates in the instructions.
@@ -3721,8 +3797,9 @@ void TargetX8632::lowerSelect(const InstSelect *Inst) {
     _mov(DestLo, SrcLoRI);
     _mov(DestHi, SrcHiRI);
   } else {
-    _cmp(ConditionRMI, Zero);
+    // Call legalize() before _cmp, since legalize() may modify flags.
     SrcT = legalize(SrcT, Legal_Reg | Legal_Imm, true);
+    _cmp(ConditionRMI, Zero);
     _mov(Dest, SrcT);
     _br(InstX8632Br::Br_ne, Label);
     Context.insert(InstFakeUse::create(Func, Dest));
@@ -3940,6 +4017,45 @@ Variable *TargetX8632::copyToReg(Operand *Src, int32_t RegNum) {
   return Reg;
 }
 
+// Insert code to randomize the representation of the immediate.  Return
+// a register that holds the (derandomized) value of the immediate.
+// WARNING: Constant blinding overwrites the flags register.

[JF, 2014/08/12 05:37:47]

Is that one random cookie per immediate, or one per function or basic block?

[wala, 2014/08/16 00:07:13]

One per immediate.

+Variable *TargetX8632::randomizeImmediate(Constant *Immediate) {
+  assert(llvm::isa<ConstantInteger>(Immediate) ||
+         llvm::isa<ConstantRelocatable>(Immediate));
+
+  if (CLRandomizeImmediates == Randomize_None)
+    return legalizeToVar(Immediate);
+
+  Variable *Dest = makeReg(Immediate->getType());
+
+  if (CLRandomizeImmediates == Randomize_ConstantPooling ||
+      llvm::isa<ConstantRelocatable>(Immediate)) {
+    const Type Ty = Immediate->getType();
+    const int64_t Offset = 0;
+    const IceString Name = nameImmediate(Immediate);
+    const bool SuppressMangling = true;
+    Ctx->addConstantPooledImmediate(Name, Immediate);
+    Constant *Sym = Ctx->getConstantSym(Ty, Offset, Name, SuppressMangling);
+    // LEAHACK: Once a proper assembler is used, change this to be
+    // mov Dest, [Sym].
+    _mov(Dest, OperandX8632Mem::create(Func, Ty, NULL, Sym));
+  } else {
+    assert(CLRandomizeImmediates == Randomize_ConstantBlinding);
+    // Mask integer immediates with a random XOR key.
+    ConstantInteger *IntegerImmediate = llvm::cast<ConstantInteger>(Immediate);
+    assert(IntegerImmediate->getType() != IceType_i64);
+    uint64_t Value = IntegerImmediate->getValue();
+    RandomNumberGenerator &RNG = Ctx->getRNG();

[Jim Stichnoth, 2014/08/13 23:30:25]

I think it should be one random cookie per function, or the same across all
functions.

[wala, 2014/08/16 00:07:12]

Done, no CSE yet.

+    uint32_t Mask1 = RNG.next((uint64_t)UINT32_MAX + 1);

[JF, 2014/08/12 05:37:47]

Use std::numeric_limits.

[wala, 2014/08/16 00:07:12]

Done.

+    uint32_t Mask2 = Mask1 ^ Value;
+    _mov(Dest, Ctx->getConstantInt(IceType_i32, Mask1));
+    _xor(Dest, Ctx->getConstantInt(IceType_i32, Mask2));
+  }
+
+  return Dest;
+}
+
 Operand *TargetX8632::legalize(Operand *From, LegalMask Allowed,
                                bool AllowOverlap, int32_t RegNum) {
   // Assert that a physical register is allowed.  To date, all calls
@@ -3957,6 +4073,7 @@ Operand *TargetX8632::legalize(Operand *From, LegalMask Allowed,
     // that the Base and Index components are in physical registers.
     Variable *Base = Mem->getBase();
     Variable *Index = Mem->getIndex();
+    Constant *Offset = Mem->getOffset();
     Variable *RegBase = NULL;
     Variable *RegIndex = NULL;
     if (Base) {
@@ -3965,10 +4082,22 @@ Operand *TargetX8632::legalize(Operand *From, LegalMask Allowed,
     if (Index) {
       RegIndex = legalizeToVar(Index, true);
     }
+
+    if (CLRandomizeImmediates && immediateShouldBeRandomized(Offset)) {

[Jim Stichnoth, 2014/08/13 23:30:25]

Can you just add the CLRandomizeImmediates test into
immediateShouldBeRandomized()?

[wala, 2014/08/16 00:07:12]

Done.

+      // lea new_base [base + randomize(offset)]
+      Variable *RegOffset = randomizeImmediate(Offset);
+      OperandX8632Mem *NewBaseAddr = OperandX8632Mem::create(
+          Func, Mem->getType(), RegBase, NULL, RegOffset, 0);
+      Variable *NewBase = makeReg(IceType_i32);
+      _lea(NewBase, NewBaseAddr);
+      RegBase = NewBase;
+      Offset = NULL;
+    }
+
     if (Base != RegBase || Index != RegIndex) {
-      From = OperandX8632Mem::create(
-          Func, Mem->getType(), RegBase, Mem->getOffset(), RegIndex,
-          Mem->getShift(), Mem->getSegmentRegister());
+      From = OperandX8632Mem::create(Func, Mem->getType(), RegBase, Offset,
+                                     RegIndex, Mem->getShift(),
+                                     Mem->getSegmentRegister());
     }
 
     if (!(Allowed & Legal_Mem)) {
@@ -3995,6 +4124,11 @@ Operand *TargetX8632::legalize(Operand *From, LegalMask Allowed,
     }
     // There should be no constants of vector type (other than undef).
     assert(!isVectorType(From->getType()));
+
+    if (CLRandomizeImmediates && immediateShouldBeRandomized(From)) {
+      return randomizeImmediate(llvm::cast<Constant>(From));
+    }
+
     bool NeedsReg = false;
     if (!(Allowed & Legal_Imm))
       // Immediate specifically not allowed