Subzero: Randomize immediates by constant blinding or pooling.

src/IceTargetLoweringX8632.cpp

 //===- subzero/src/IceTargetLoweringX8632.cpp - x86-32 lowering -----------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the TargetLoweringX8632 class, which
@@ skipping 110 matching lines @@
 }
 
 // The maximum number of arguments to pass in XMM registers
 const uint32_t X86_MAX_XMM_ARGS = 4;
 // The number of bits in a byte
 const uint32_t X86_CHAR_BIT = 8;
 // Stack alignment
 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.
 uint32_t applyStackAlignment(uint32_t Value) {
   // power of 2
   assert((X86_STACK_ALIGNMENT_BYTES & (X86_STACK_ALIGNMENT_BYTES - 1)) == 0);
   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(
     "mattr", cl::desc("X86 target attributes"),
     cl::init(TargetX8632::SSE2),
     cl::values(
         clEnumValN(TargetX8632::SSE2, "sse2",
                    "Enable SSE2 instructions (default)"),
         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) {
   IceString Str;
   llvm::raw_string_ostream BaseOS(Str);
   if (isVectorType(Ty)) {
     BaseOS << "v" << typeNumElements(Ty) << typeElementType(Ty);
   } else {
     BaseOS << Ty;
   }
@@ skipping 691 matching lines @@
         snprintf(buf, llvm::array_lengthof(buf), T::PrintfString, RawValue);
     assert(CharsPrinted >= 0 &&
            (size_t)CharsPrinted < llvm::array_lengthof(buf));
     (void)CharsPrinted; // avoid warnings if asserts are disabled
     Str << "L$" << Ty << "$" << Const->getPoolEntryID() << ":\n";
     Str << "\t" << T::AsmTag << "\t" << buf << "\t# " << T::TypeName << " "
         << Value << "\n";
   }
 }
 
+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.
 }
 
 void TargetX8632::split64(Variable *Var) {
   switch (Var->getType()) {
   default:
     return;
   case IceType_i64:
@@ skipping 2839 matching lines @@
     _br(InstX8632Br::Br_ne, Label);
     Context.insert(InstFakeUse::create(Func, DestLo));
     Context.insert(InstFakeUse::create(Func, DestHi));
     Operand *SrcFLo = loOperand(SrcF);
     Operand *SrcFHi = hiOperand(SrcF);
     SrcLoRI = legalize(SrcFLo, Legal_Reg | Legal_Imm, true);
     SrcHiRI = legalize(SrcFHi, Legal_Reg | Legal_Imm, true);
     _mov(DestLo, SrcLoRI);
     _mov(DestHi, SrcHiRI);
   } else {
+    // Call legalize() before _cmp, since legalize() may modify flags.
+    SrcT = legalize(SrcT, Legal_Reg | Legal_Imm, true);
     _cmp(ConditionRMI, Zero);
-    SrcT = legalize(SrcT, Legal_Reg | Legal_Imm, true);
     _mov(Dest, SrcT);
     _br(InstX8632Br::Br_ne, Label);
     Context.insert(InstFakeUse::create(Func, Dest));
     SrcF = legalize(SrcF, Legal_Reg | Legal_Imm, true);
     _mov(Dest, SrcF);
   }
 
   Context.insert(Label);
 }
 
@@ skipping 197 matching lines @@
   Type Ty = Src->getType();
   Variable *Reg = makeReg(Ty, RegNum);
   if (isVectorType(Ty)) {
     _movp(Reg, Src);
   } else {
     _mov(Reg, Src);
   }
   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
   // to legalize() allow a physical register.  If a physical register
   // needs to be explicitly disallowed, then new code will need to be
   // written to force a spill.
   assert(Allowed & Legal_Reg);
   // If we're asking for a specific physical register, make sure we're
   // not allowing any other operand kinds.  (This could be future
   // work, e.g. allow the shl shift amount to be either an immediate
   // or in ecx.)
   assert(RegNum == Variable::NoRegister || Allowed == Legal_Reg);
   if (OperandX8632Mem *Mem = llvm::dyn_cast<OperandX8632Mem>(From)) {
     // Before doing anything with a Mem operand, we need to ensure
     // 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) {
       RegBase = legalizeToVar(Base, true);
     }
     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)) {
       From = copyToReg(From, RegNum);
     }
     return From;
   }
   if (llvm::isa<Constant>(From)) {
     if (llvm::isa<ConstantUndef>(From)) {
       // Lower undefs to zero.  Another option is to lower undefs to an
       // uninitialized register; however, using an uninitialized register
       // results in less predictable code.
       //
       // If in the future the implementation is changed to lower undef
       // values to uninitialized registers, a FakeDef will be needed:
       //     Context.insert(InstFakeDef::create(Func, Reg));
       // This is in order to ensure that the live range of Reg is not
       // overestimated.  If the constant being lowered is a 64 bit value,
       // then the result should be split and the lo and hi components will
       // need to go in uninitialized registers.
       if (isVectorType(From->getType()))
         return makeVectorOfZeros(From->getType());
       From = Ctx->getConstantZero(From->getType());
     }
     // 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
       NeedsReg = true;
     // TODO(stichnot): LEAHACK: remove Legal_Reloc once a proper
     // emitter is used.
     if (!(Allowed & Legal_Reloc) && llvm::isa<ConstantRelocatable>(From))
       // Relocatable specifically not allowed
       NeedsReg = true;
     if (!(Allowed & Legal_Mem) &&
@@ skipping 241 matching lines @@
     for (SizeT i = 0; i < Size; ++i) {
       Str << "\t.byte\t" << (((unsigned)Data[i]) & 0xff) << "\n";
     }
     Str << "\t.size\t" << MangledName << ", " << Size << "\n";
   }
   Str << "\t" << (IsInternal ? ".local" : ".global") << "\t" << MangledName
       << "\n";
 }
 
 } // end of namespace Ice