Spectre bounds check mitigation using a subtraction with borrow

Created 25 January 2018.

A range of ‘data flow’ strategies are being explored to mitigate the Spectre bounds check vulnerability. These mask an array access index after a conditional branch bounds check so that no matter if the branch is taken or not the value that the load uses is always within bounds. These assume that the processor does not speculate on the result of these operations, and thus they are safe building blocks.

One interesting pattern discussed on the Linux Kernel mailing list to prevent bounds-check bypass via speculative execution is the code sequence of a comparison instruction followed by a subtraction with borrow instruction to generate the index mask. The comparison instruction sets the carry (borrow) flag when the index is within bounds and clears the carry flag when the index is out of bounds, and then the subtraction with borrow from zero converts this into either a zero or -1 mask as needed.

While the comparison and subtraction can be used alone to mask an index, it can also be combined with a bounds check conditional branch avoiding a redundant comparison. This also ensures that the branch and the load depend on the result of the same comparison instruction which while not necessary might be an added constraint.

It would be interesting to learn if processors optimize a subtraction with borrow in which both arguments are the same register, to at least avoid a dependency on that register, but if not then that is a path they could take.

It will also be interesting to see how this pattern compares with other patterns being explored, but it looks promising being a short sequence using only one temporary register.

Here is an example written in C that can be used with the Spectre Attack C example to demonstrate that this blocks the vulnerability.

#include <stdio.h>
#include <stdint.h>

extern volatile size_t array1_size;
extern uint8_t array1[160];
extern uint8_t array2[256 * 512];

static uint8_t temp = 0;

void victim_function(size_t x)
{
  uint32_t v;

  /* Spectre mitigation using data flow dependency on a masked index. */
  asm volatile ("cmpq %3, %1\n\t"
		"jnb oob%=\n\t"
		"sbbq %%rax, %%rax\n\t"
		"andq %1, %%rax\n\t"
		"movzbl (%2, %%rax, 1), %0\n\t"
		"jmp done%=\n\t"
		"oob%=:\n\t"
		"xor %0, %0\n\t"
		"done%=:\n\t"
		: "=r" (v)
		: "r" (x), "r" (array1), "r" (array1_size)
		: "rax", "cc" );

  temp &= array2[v * 512];
}