On 15 Aug 2023, at 00:34, Demi Marie Obenour wrote:

...

This makes me wonder if it’d make sense to design a new CPU and/or instruction set with the goal of eliminating timing and other side channels. Like, we had the Lisp machines with hardware support for Lisp, and now most CPUs are optimized for C and similar languages, and in turn those languages are optimized for those CPUs (x86, Arm, etc.).

Fully-associative caches with random eviction help a lot.

I’d claim they don’t help at all. They might if “random” was truly random, which in hardware is rarely the case. “Random” cache replacement is more properly described as “unspecified”. In reality it’s usually using some existing state (eg some counter) and as such is actually fully deterministic, you only have to reverse-engineer the mechanism. Besides that, fully-associative caches (unless very small) are inherently slow (long critical path) and energy-hungry many gates to traverse).

Speculative taint tracking helps close some of the remaining holes.

I’m highly sceptical too. Taint-tracking has to be highly pessimistic to be feasible, and adds a lot of complexity to the hardware (which gets back to my earlier argument: make it more complex and you’re making it more likely that something goes wrong). Gernot

With e.g. HBM, there might be an opportunity to state save the entire cache on a context switch and restore it on resume. I guess some of the overhead of flushing is due to random accesses. State save could just do a single contiguous write. There’s likely to be some complexity around cache coherency and shared memory but maybe not insurmountable. In the worst case, shared memory could have a separate cache which would be flushed rather than state saved. On Mon, 14 Aug 2023 at 17:31, Gernot Heiser wrote:

On 15 Aug 2023, at 01:59, Gernot Heiser wrote:

...

...

Speculative taint tracking helps close some of the remaining holes.

I’m highly sceptical too. Taint-tracking has to be highly pessimistic to

be feasible, and adds a lot of complexity to the hardware (which gets back to my earlier argument: make it more complex and you’re making it more likely that something goes wrong).

Forgot to add:

...

It’s not perfect, but it is the best one can do without cache partitioning or heavyweight flushing, and I suspect both of those are often impractical from a performance perspective.

Cache partitioning (which really is static, software-controlled vs dynamic partitioning by hardware) produces, in average, at best a mild performance degradation. There are plenty of cases where it actually improves performance (loads with a cache working set that exceeds the cache size) and it is used for performance isolation and sometimes for improving average-case performance.

Similar, cache-flushing (of the L1) has little performance impact, except where context-switching rates are very high. Otherwise, the L1 is too small to hold much hot data after a full round of context switches, so the cache is effectively flushed implicitly.

On OoO processors explicit flushes have a cost, as the cost of the implicit replacement can be at least partially hidden by OoO execution. But I doubt there are many use realistic cases where the impact is significant. (Yes, we did evaluate this, although it’s been studied in more detail by others.)

Gernot _______________________________________________ Devel mailing list -- devel@sel4.systems To unsubscribe send an email to devel-leave@sel4.systems

On 8/14/23 11:59, Gernot Heiser wrote:

On 15 Aug 2023, at 00:34, Demi Marie Obenour wrote:

...

...

This makes me wonder if it’d make sense to design a new CPU and/or instruction set with the goal of eliminating timing and other side channels. Like, we had the Lisp machines with hardware support for Lisp, and now most CPUs are optimized for C and similar languages, and in turn those languages are optimized for those CPUs (x86, Arm, etc.).

Fully-associative caches with random eviction help a lot.

I’d claim they don’t help at all. They might if “random” was truly random, which in hardware is rarely the case. “Random” cache replacement is more properly described as “unspecified”. In reality it’s usually using some existing state (eg some counter) and as such is actually fully deterministic, you only have to reverse-engineer the mechanism.

Besides that, fully-associative caches (unless very small) are inherently slow (long critical path) and energy-hungry many gates to traverse).

What about Chameleon Cache (https://arxiv.org/pdf/2209.14673.pdf)?

...

Speculative taint tracking helps close some of the remaining holes.

I’m highly sceptical too. Taint-tracking has to be highly pessimistic to be feasible, and adds a lot of complexity to the hardware (which gets back to my earlier argument: make it more complex and you’re making it more likely that something goes wrong).

You’re not wrong. I just don’t know if a better solution for fully dynamic workloads exists. -- Sincerely, Demi Marie Obenour (she/her/hers)

On 8/26/23 09:20, Gernot Heiser via Devel wrote:

On 16 Aug 2023, at 00:22, Demi Marie Obenour wrote:

...

...

I’d claim they don’t help at all. They might if “random” was truly random, which in hardware is rarely the case. “Random” cache replacement is more properly described as “unspecified”. In reality it’s usually using some existing state (eg some counter) and as such is actually fully deterministic, you only have to reverse-engineer the mechanism.

Besides that, fully-associative caches (unless very small) are inherently slow (long critical path) and energy-hungry many gates to traverse).

What about Chameleon Cache (https://arxiv.org/pdf/2209.14673.pdf)?

I had a look, and the paper pretty much confirms what I’ve said. (Besides being only a proposal…)

For one, they don’t actually do an FA cache, nor true randomness, they approximate both in some fashion so that the effect is basically the same (so they claim, I didn’t read it carefully enough to confirm that, note that the paper is published in a third-tier venue I hadn’t even heard of before – IEEE International Symposium on Secure and Private Execution Environment Design).

It does all this by making the hardware more complicated (and thus more likely to be buggy/attackable). Specifically, they take the IMHO wrong approach of trying to solve the whole problem in hardware, discarding alternative approaches as “involve[ing] software to manage the partitions”. As I keep saying, security is inherently a HW-SW-codesign problem, you won’t get good solutions by trying to do it all in HW or in SW. The right approach is policy-mechanism separation: HW provides minimal (and ideally orthogonal) mechanisms, and SW uses them according to its security policy.

The HW-only approach means that the HW must take a pessimistic approach and prevent information flow across anything that looks like it might be a security boundary, whether or not it actually is (which only the OS can know). This has a (generally measurable) cost.

Here this cost is that the cache will likely be slower (in terms of access), likely more energy-hungry and have reduced hit rates compared to, say, a 4-way LRU cache. This will be a constant overhead, whether it’s needed or not. In contrast, flushing the L1 is a cost that is only needed when an actual security-domain switch happens. It is small (fraction of a µs), negligible unless domain-switch rates are unusually high.

For an L1 cache, flushing on each domain switch might be the best choice, but what about L2 and L3? Flushing L2 and L3 is going to be very slow, since it requires going all the way out to main memory. Do you have an alternative suggestion that can scale to hundreds of security domains? That’s not unrealistic for e.g. a web browser, where each origin is a separate security domain. The impression I got from the academic work I have seen so far is that it works well when there are a small number of security domains and crossings between them are infrequent. Real-world systems, though, have lots of security domains and tend to cross them quite frequently, most notably at every single system call. Yes, part of the problem is that existing APIs were designed around low syscall costs and that existing kernels keep too many pages mapped at once, but still. -- Sincerely, Demi Marie Obenour (she/her/hers)