Document potential implementation of CFI in hardware.

[kcc]

Summary

Document potential implementation of CFI in hardware.

[eugenis]

docs/ControlFlowIntegrityDesign.rst

510

We usually refer to it as "cross-DSO scheme".

[pcc]

I think this would benefit from an assembly code listing for a couple of cases (e.g. all-ones, bit vector).

One concern I have is that in the case where we have a bit vector lookup, the code would end up computing the byte offset redundantly with the instruction, which would somewhat diminish the code size benefits here.

[kcc]

Use "cross-DSO scheme"

[kcc]

In D25455#566834, @pcc wrote:

I think this would benefit from an assembly code listing for a couple of cases (e.g. all-ones, bit vector).

One concern I have is that in the case where we have a bit vector lookup, the code would end up computing the byte offset redundantly with the instruction, which would somewhat diminish the code size benefits here.

Right now I don't see a good way to have the bit vector lookup in the HW scheme. (written: "The bit vector lookup is probably too complex for a hardware implementation.")
Even w/o the bit vector the check will nearly precise (and fully precise in > 50% cases).

[pcc]

My point was that this would make it more verbose to implement the bit vector check in software. But I think on balance this is fine because as you point out bit vector tests are relatively rare, I don't think we've removed as many as we can and even in the case where we want to be 100% we can always fall back to our existing code.

docs/ControlFlowIntegrityDesign.rst

507

An estimate of the # of bytes would be useful here.

509

aligned

523–526

Please put these in the same order as the "arguments" below.

[kcc]

address pcc's comments

[kcc]

addressed comments

[pcc]

An estimate of less than 10 bytes doesn't seem realistic if the operands take up 10 bytes by themselves.

[kcc]

Changed the instruction size estimate to 12.
We may still be able to make the constants smaller.
May also have two instructions: 1 for monolythic case, one for cross-DSO.
The first one will be smaller.

[pcc]

LGTM

docs/ControlFlowIntegrityDesign.rst

 
 Position-independent executable requirement
 -------------------------------------------
 
 Cross-DSO CFI mode requires that the main executable is built as PIE.
 In non-PIE executables the address of an external function (taken from
 the main executable) is the address of that function’s PLT record in
 the main executable. This would break the CFI checks.
+
+
+Hardware support
+================
+
+We believe that the above design can be efficiently implemented in hardware.
+A single new instruction added to an ISA would allow to perform the CFI check
+with fewer bytes per check (smaller code size overhead) and potentially more
+efficiently. The current software-only instrumentation requires at least
+32-bytes per check (on x86_64).
+A hardware instruction may probably be less than ~ 12 bytes.
+Such instruction would check that the argument pointer is in-bounds,
+and is properly aligned, and if the checks fail it will either trap (in monolithic scheme)
+or call the slow path function (cross-DSO scheme).
+The bit vector lookup is probably too complex for a hardware implementation.
+
+.. code-block:: none
+
+  //  This instruction checks that 'Ptr'
+  //   * is aligned by (1 << kAlignment) and
+  //   * is inside [kRangeBeg, kRangeBeg+(kRangeSize<<kAlignment))
+  //  and if the check fails it jumps to the given target (slow path).
+  //
+  // 'Ptr' is a register, pointing to the virtual function table
+  //    or to the function which we need to check. We may require an explicit
+  //    fixed register to be used.
+  // 'kAlignment' is a 4-bit constant.
+  // 'kRangeSize' is a ~20-bit constant.
+  // 'kRangeBeg' is a PC-relative constant (~28 bits)
+  //    pointing to the beginning of the allowed range for 'Ptr'.
+  // 'kFailedCheckTarget': is a PC-relative constant (~28 bits)
+  //    representing the target to branch to when the check fails.
+  //    If kFailedCheckTarget==0, the process will trap
+  //    (monolithic binary scheme).
+  //    Otherwise it will jump to a handler that implements `CFI_SlowPath`
+  //    (cross-DSO scheme).
+  CFI_Check(Ptr, kAlignment, kRangeSize, kRangeBeg, kFailedCheckTarget) {
+     if (Ptr < kRangeBeg ||
+         Ptr >= kRangeBeg + (kRangeSize << kAlignment) ||
+         Ptr & ((1 << kAlignment) - 1))
+           Jump(kFailedCheckBranchTarget);
+  }
+
+Note that such hardware extension would be complementary to checks
+at the callee side, such as e.g. **Intel ENDBRANCH**.
+Moreover, CFI would have two benefits over ENDBRANCH: a) precision and b)
+ability to protect against invalid casts between polymorphic types.