Hacker News Reader

Comment by ashleyn | Hacker News Reader

It's not everyday that a security issue is borne out of a side-effect of underlying theory; in this case, how out-of-order execution works. It's almost as bad as if someone proved P = NP, rendering all cryptography useless on the spot.

The game is changed forever, and CPU designers across the industry will likely have to can some or all of OoOE, setting performance back considerably. It can take years to reachieve performance we're used to today at the security level required.

View on HN

It can mostly be fixed by making sure aborted speculative execution has no side effects.

I think this is doable by adding a buffer to store cache entries evicted by speculative execution, so they can be put back, and a log of new cache entries, so they can be removed

Also, the abort process itself needs to take a constant amount of time out of the critical path to avoid leaking info via timing (the timing then only depends on how fast the CPU determines it speculated wrong, but that doesn't depend on the speculated code).

EDIT: Hyperthreading also needs to be handled somehow, which other than disabling it might require adding a per-thread "L0" cache and using that exclusively for speculatively executed code.

There is still the problem of theoretical plain timing attacks on normally executed code though, but that's unrelated.

Making sure that the indirect branch predictor only makes predictions when the source address fully matches would be nice as well (although theoretically not required if there are no side effects).

I don't think undoing all cache changes is enough, since it went to memory it generated memory bus traffic, which could be observed by another core (as extra latency). And speaking of another core, the cacheline might have come from another core, which could observe the effect on its own cache, even if it's later put back.

Yes. I doubt this will be what actually happens, but perhaps the safest fix is to remove speculative execution in its entirety, increasing clock frequency and/or core count to mitigate the resulting performance loss by as much as possible.

> It can mostly be fixed by making sure aborted speculative execution has no side effects.

Not an expert, but if speculative execution has no side effects, not even on timing, then you might as well disable it.

Speculative execution is meant to speed up computations.

The approach Mill Computing [0] is taking is to have the compiler toolchain handle all instruction scheduling for their new design. All instructions have a fixed, known latency (in terms of clocks). And the processor doesn't have much in the way of global state (like condition code registers and such). All metadata is stored with the data on the 'belt' (replacement for registers) itself, which is saved / restored upon context switch.

They are also years away from silicon it seems.

[0] https://millcomputing.com/docs/

I’m a bit puzzled how this helps prevent handcrafted binaries from exploiting CPU designs.

Well, if nothing else, the design of the Mill has a much smaller "attack surface". There's not nearly as much in the way of interesting activities going on behind the scenes as compared to a modern OoOE CPU. That logic is pushed out of the hardware and into the software development toolchain.

The Mill has many other aspects that improve the security story. All protection is based on memory address, for example. And pointers are not integers. There are reserved portions of the address space that programs are completely not allowed to touch.

Maybe it's a sign that the current CPU architectures are too complex for their own good. Branch prediction is a really, really weird concept. It could be avoided if we switched from Von Neumann architecture.

> It's almost as bad as if someone proved P = NP, rendering all cryptography useless on the spot.

No, P=NP does not immediately break crypto, because that relation makes no statement w.r.t. if those algorithms in P solving problems we thought were NP are easy to find. Or efficient. Just because the problem your adversary has to break is part of P doesn't make it easy.

Technically, if P=NP then we already have a working algorithm to solve NP problems in polynomial time.

It involves iterating through and running all possible programs ordered by length, giving them an increasing amount of time to run and checking (in polynomial time) if they produce the correct answer.

If there exists a program that finds the answer in polynomial time, this algorithm will eventually find it after wasting (at most polynomial) time iterating through other programs and tentative bounds.

If P != NP, it's still at least asymptotically optimal.

Hmm, but running 'all possible programs' is an exponential time operation (in the lengths of the programs)...

Yes, but as you note, "in the size of the program" and the size of {the program that solves 3-SAT in polynomial time if there is one} is a constant, so it's all constant.

Of course, that constant is astronomically unpractical.

I like the term "Galactic Algorithm" for these algorithms with unpractical constants.

https://rjlipton.wordpress.com/2010/10/23/galactic-algorithm...

Polynomial time is unbounded. Indeed constant Time is unbounded.

Bare metal servers that run trusted code like a build not are not effected. Maybe this will be a bios setting or a kernel flag to set .

Kernel flag at compile time? - Yes

Kernel flag at boot time? - No (the fix is a to compile instructions differently).

Bare metal servers that only run trusted code are only unaffected so long as they explicitly opt out of the new security model, and I'm not sure how easy that'll be...

IIUC it's not possible to opt out at this time (short of reverting the patches). Linus expressed some concern about it: https://lkml.org/lkml/2018/1/3/797

What a tl;dr!

  Please talk to management. Because I really see exactly two possibibilities:
 
  - Intel never intends to fix anything

  OR

  - these workarounds should have a way to disable them.

  Which of the two is it?

I feel like user-facing server-side scripting languages should be investigated whether they incur the same risk as running JavaScript in a browser (which is big and complicated). I'm thinking about stuff like Sievescript and IFTTT-like applications.

In case of Meltdown and Linux you simply set the boot parameter pti=off and reboot the machine.

Ah, sorry. My comment was specifically directed at Spectre (though I didn't say it), the more serious of the two.

Side-effects strike again! Not only does the hardware have observable side-effects that are not cleaned-up, but our browser languages allow pervasive side-effects which are used for exploits (e.g. precision timing).

Note one of the mitigations for this is that Mozilla (and I'm guessing other browsers) is reducing the resolution of performance.now()

From the Spectre paper: Chrome reduced resolution of performance.now(), so they set up a webworker with a tight loop that increments a shared variable.

This is why Mozilla also removed support for shared variables (i.e. SharedArrayBuffer).

Yes and creating one or more "web workers" (threads) is a significant side-effect. Javascript to me, looks more like a systems-programming language (imperative with threads and sockets) than something trusted for interactive web sites. The web is a huge mess and today we learn that hardware is too.

How many years should we think back?

I have some old laptops at home and they work quite well with a proper Linux setup.

Should we think in terms of slowing everything down by some factor, or just slowing tasks that need an un-throttled CPU?

The patches you're seeing go out amount to little more than hacks that try to stop the CPU from doing branch predictions in some cases. It depends on the CPU, really. For example, and this is just a guess, netburst-era Intel CPUs may have even more of a hit as they relied on deep pipelines to get higher clockspeed, and any step in that pipeline may do a branch prediction.

Qualifier: I'm working off articles and a few computer-architecture courses from college, so don't trust me too much here.

Taht said... Branch prediction and TLBs have been ubiquitous since about 1975. We're seeing vulnerabilities in ARM processors with unit costs of a tenth of a cent. We don't have to go that far back; if nothing else our toolchains and manufacturing techniques are far better. But if we're forced to discard speculative execution as a concept, which I think may be necessary to entirely prevent side channels, we'll be going way, way far back. Further back than the Pentium 4.

Fundamentally speaking, the power of out-of-order execution is not one of engineering. It's not like object-oriented programming or version control in that it simply makes it easier to engineer fast processors. It is more powerful on a fundamental level. And there's been so much theoretical and practical work put into it over the decades that it may take more decades to bring a different mathematical formalism up to the same level of development.

Let's just say that I really hope we don't have to throw out out-of-order execution. It'd suck. Hard.

It's not so much out of order as it is the speculative execution. Predicting a branch and then trying to run the code after the jump while you wait on the branch itself to finish calculating. At least that's my understanding from the papers. This means that otherwise normal out of order techniques like memory load/store reordering and such aren't subject to these particular attacks. I hope that attacks on them aren't found either because those are some of the biggest gains because it can allow better cache coherence and avoid misses, or make the impact of one almost non-existent since it can do other instructions while waiting on a load from system memory.

My understanding is: Speculative executive is flawed, out of order makes it hard to tell when the errors are going to be really bad.

> if we're forced to discard speculative execution as a concept

Do you have any reason to believe this will be the case?

> Further back than the Pentium 4

This is a bad example.

The Pentium 4's pitfall was a high clock speed with little concurrency, and thusly a big heat problem that limited peak computation power.

Yes, we lose some concurrency without branch prediction, but post-P4 multi-core processors would have to take some very major hits to be comparable to the P4 in a modern multi-threaded computing environment.

The P4 is just not a good reference point for old processors because of its architectural differences.

I'm far from an expert in this field, but I just read the Wikipedia article on it and it says Spectre affects pretty much every processor since 1995.

Rather than changing OoOE, wouldn't it be much simpler to prevent unprivileged processes from seeing the real time? For maximum compatibility with existing software, a CPU could provide fake time, that on average passes at the same rate as the real time, but is completely determined by the instructions executed. If the length of process time slices are determined by fake time instead of real time, the process will never be affected small variations in real execution time, no matter how much time passes.

Unless you never get the real time doesn’t this just push out the problem to statistical analysis of differences between real and fake time?

The fake time can be synced to real time at the beginning of the time slice of a process. So the process never sees the real time, but the fake time is fairly close to it.

Processes can run a long time and pass data around. This isn’t realistic.

I'm not seeing the issue with a long running process. If the fake time is regularly synced to real time, it should not matter how long the process runs.

If passing data involves frequent switches between processes, then, yes, I see there would be a problem with syncing on every process switch. I think syncing at longer intervals would solve that problem. All processes could share the same fake time, but see the fake time skip a small fixed amount at fixed regular intervals. That fixed amount of fake time would take a variable amount of real time, which absorbs the small variations in real execution time.

[cough] Oh dear, Moore’s Law

/edit

Lots of simple cores would be inherently better.

But much harder to program and not effective for speeding up quite a lot of software.

Isn't that exactly what made PS3 hard to develop for?

Yep. It bad to develop for, and left lots on the table compared to its contemporary Xbox 360, despite "theoretically" better specs. 1

The Cell processor was never used in any other consoles, and the IBM Roadrunner supercomputer using them ended up being replaced by Cray+AMD hardware.

1 https://kotaku.com/5885358/why-skyrim-didnt-play-nice-with-t...

https://en.m.wikipedia.org/wiki/IBM_Roadrunner

That's the Xeon Phi concept... which is apparently being taken out back and shot.

Our current programming paradigms don't adapt well to massive parallelism, except for some small classes of "embarassingly parallel" problems (e.g., make -jN).

Most of what we do is pretty parallel: web hosting, servicing requests, databases, hosting tons of VMs and containers, etc. I don't buy it.

My guess on Phi is that it wasn't a big win over fewer deeper cores and so there was not much market. This might change things a bit.

There are also GreenArrays chips, like the GA144.[1] 144 cores on a chip.

The downside (or upside) is that they're desgined for running Forth, and are not x86 compatible.

http://www.greenarraychips.com/home/documents/greg/PB001-100...

Reply on news.ycombinator.com