Clamping the array index - is this a good idea for the Javascript Spectre mitigation?

Question

From the Spectre document I learned that the attack can be successful because the compiler generates a memory read instruction that refers to the invalid array index. And even though the instruction is normally only executed after checking the array index, accessing out-of-bounds elements produces undesirable side effects through the speculative execution in some CPUs.

javascript:

  x=array[index];

assembler pseudocode:

  MOV reg,index
  CMP reg,array[length]
  JNC fail
  MOV x,array[reg]
  ...access probe array based on x

What if the compiler was changed to never ever generate invalid addresses?

assembler pseudocode:

  MOV reg,index
  CMP reg,array[length]
  JNC fail
  AND reg,array[bit_mask] <---| bit mask of all 1's lower than
  MOV x,array[reg]            |  2*length (might be an object member)
  ...access probe array based on x

This way, for the price of an extra AND, the address used in the speculative read is limited to less then 2*length. Next, for all array buffers, let's always allocate 2^N bytes (N >= log₂(length)) and the attacker will be only able to probe its own unused memory (alternatively, arrange the memory allocations so that the only memory available for probing is their own other buffers).

Is this a good idea?

Answer 1

A similar approach was taken by WebKit developers, among other means, to mitigate possible effects of Spectre.

See: "What Spectre and Meltdown Mean For WebKit", paragraph "Index Masking".

Note that index masking is different from your proposal in that it doesn't require to allocate 2^N bytes for each array (in worst case, almost twice as much as required), thus still exposing a (somewhat limited) portion of information to an attacker, but reducing the amount of data allowed for an attacker to read overall and saving some memory for the sake of effectiveness. For large arrays, they might put some faith in ASLR which makes it less likely there would be an allocation within index mask reachability.

Nevertheless, what exactly could be exposed to an attacker this way in WebKit depends on their architecture and code base; yours may be different.

Regarding the effectiveness of allocating almost twice the requested memory in worst case, it is worth mentioning that the ideal array growth rate is close to 1.6 and the growth factor of 2 is widely used but much less effective.

However, assuming Linux, there's probably a trick that could be used to reduce the amount of memory being lost while still being safe from speculative out-of-bounds reads. You can try writing a custom allocator that, for arrays at least larger than 2*page size (the latter is 4K under most circumstances, but more strictly, sysconf(SC_PAGE_SIZE)), will firstly parse /proc/self/maps to find an unmapped memory region of a size at least 2^N bytes, N >= log₂(array_length), and then map only the required size via mmap(MAP_FIXED).

Some subsequent work would be needed to ensure that no memory would be mapped within 2*length of any array allocated before, but this is still not a rocket science.

The memory pages allocated and returned to you will be consecutive in virtual memory, but are not required to be consecutive in physical memory, thus this approach wouldn't cause the physical memory fragmentation. The subsequent virtual memory fragmentation wouldn't probably be an issue on a 64-bit system any time soon, as 16 Exabytes of total addressable memory ought to be enough for anybody.

Other operating systems probably have tools similar to Linux's.

Regarding WebKit, as it also features other mitigations, which are, as of now, meant to be enough for the effects of Spectre themselves, index masking is rather excessive mitigation for them, and their approach is fine for their remaining threat model.

Your threat model, however, could be different. That's all we know.