9 ms·
Finding a CPU Design Bug in the Xbox 360
- shaklee3 9y agoGreat read!
- jonny_eh 9y agoAwesome story! I'm curious though why the branch predictor was running the xdcbt instruction if "The symptoms were identical. Except that the game was no longer using the xdcbt instruction". Was the game no longer "using the xdcbt instruction", but the branch predictor caused issues, because they put a jmp instruction in front of it instead of removing the instruction entirely?
- luc157 9y agoAs I understand it, the function that used the xdcbt instruction had an oversight that led to the first set of crashes, so it was rewritten to fix that issue. Even with the fix, the game programmer decided to remove the PREFETCH_EX flag, which is what caused the copy routine to use xdcbt in the first place. So xdcbt ended up in the compiled code, but the flag that caused it to be used wasn't there. The branch predictor ran it anyway, in an unsafe way, leading to the next set of crashes.
- brucedawson 9y agoI think that the developer didn't yet have the fixed version. They thought they would be safe because they weren't passing PREFETCH_EX, but the branch predictor decided otherwise. There were other ways that xdcbt could cause problems (what if the block of memory was freed before being purged from L1) so who knows, and I don't remember for sure.
- xenadu02 9y agoEven if they had the fixed version the branch predictor could still decide to predict the instruction would be hit right? Your ultimate analysis seems correct: the instruction is unsafe to have anywhere.
- syncsynchalt 9y agoIn humans we have a similar problem: https://en.wikipedia.org/wiki/Ironic_process_theory https://en.wikipedia.org/wiki/Ironic_process_theory aka "don't think of a pink elephant"
- Gibbon1 9y agoI'm going to assume that somewhere in the code was something like if(flags | PREFETCH_EX) { xdcbt } else { safe way } And the branch predictor would decide the xdcbt branch was most likely, executes xdcbt and then realizes oops and does it the safe way. Which would be okay except xdcbt is evil, it breaks cache coherency.
- unwind 9y agoNitpick: you meant & for a bitwise AND, of course.
- djhworld 9y agoWow, interesting to see feature flags causing this undesired effect!
- syncsynchalt 9y agoAny if statement could cause this, doesn't have to be feature flags. An untrained branch predictor could still take the "wrong" path even if none of the code that calls that if statement takes the bad path. That's presumably what happened here, the calling program removed all instances of PREFETCH_EX but the CPU would still sometimes execute that branch, such as on the first run through that function. This is a lot like the problem of "don't think of a pink elephant". The mere existence of the "evil opcode" in the library means the CPU might execute it under certain circumstances.
- jonny_eh 9y agoAll clear now, thanks!
- amenghra 9y agoVery well written. Thanks for sharing!
- SamPutnam 9y agoWhere are the L1 caches?
- saagarjha 9y agoI believe each core had its own L1 cache, hence why it’s not possible to see on the diagram.
- brucedawson 9y agoI think the L1 caches are the per-core blue blobs visible in this die shot: https://randomascii.files.wordpress.com/2018/01/xbox360_processor_die-fixed.jpg https://randomascii.files.wordpress.com/2018/01/xbox360_proc... but I'm not sure.
- saagarjha 9y agoIt could be. In any case that image isn’t labeled, so there’s no way to know for sure without another source.
- readittwice 9y agoIs there a way to "recognize" this? For example why the blue blobs and not the green ones?
- MBCook 9y agoCache/RAM always looks like basically solid colors because it’s so densely packed with a repeating structure. How would you know it’s not the green stuff? I don’t know, perhaps by size. I would imagine the green stuff is some other kind of cache or memory (op cache? TLB buffers? patchy SRAM). This is what I know from seeing these shots online for years. I’m no expert by any means.
- brucedawson 9y agoThe green stuff might have been the VMX register files - those things were pretty huge (128 registers per thread, each register 16 bytes, so 212816=4 KiB per core). While the L1 cache was higher capacity (32 KiB) as a general rule of thumb faster memory uses more die area per bit. But I seem to remember being told that the green areas were the VMX pipelines. I don't remember clearly, and the hardware people I asked at the time were uncertain - they were too far removed from that aspect of the hardware. The other reason to assume that the blue is the caches is because it is closer to the cross-bar and the cross-bar is what connects the cores to the L2. Incoming data from the L2 goes first to the L1 caches so they would logically be on that side.
- fps_doug 9y agoScratches PowerPC off the list of trustworthy CPUs Sooo, out you go, G5. Any suggestions what to use for online banking? A 486 can't handle all the jQuery and tracking scripts.
- adrianN 9y agoRun nested CPU simulators on a beowulf cluster of Raspberry Pis?
- KozmoNau7 9y agoAFAIK the 32-bit Atoms (of Netbook fame) are not affected?
- SomeHacker44 9y agoAtom CPUs were in-order execution, at least at first, AFAIK. So, without speculation and an OOE engine, Meltdown and Spectre can't happen.
- phire 9y agoJust because the execution is in-order, doesn't mean there is no speculative execution. The 360 cpu (and the closely related ps3 cpu) is the perfect example of this. Despite the fact that it's 100% in-order, it has a very long instruction pipeline (upto 50 instructions long) and branch prediction. And that's all Spectre needs, a long pipeline + branch prediction. I'm not even 100% sure the intel atom will be safe from Spectre & Meltdown. It's pipeline is much shorter, only 16 stages long, but it still speculatively executes up-to 32 instructions (2 instructions per cycle). It just makes things harder, you have to find a Spectre gadget that's short enough. Though piss-easy for Meltdown, because you can just hand-assemble short code.
- LeoPanthera 9y agoIn the list of possible risks to online banking (and why is it always online banking in these hypothetical world-is-ending scenarios?), CPU bugs are way down the list.
- rwmj 9y agoWould it be fair to say that having any sequence of bytes in memory which looks like the xdcbt instruction (even if those bytes are just data) is unsafe? Given that a stale entry in the branch prediction table might end up pointing at those bytes.
- dingo_bat 9y agoIf that's true, then it may be better to disable that particular opcode itself from the chip.
- rwmj 9y ago84 million XBox 360s in the wild so it may be a bit late for that :-) Consoles have very predictable patterns of execution and only run a limited set of software so it's not so much a problem there. It would be a much more serious problem if this was a chip for a general purpose PC.
- fulafel 9y agoThere may still be JITs and web browsers on consoles.
- kabdib 9y agoThe 360 didn't open up the ability for titles to generate their own code and run it. Some internal features of the 360 did (the back compat stuff, and some other projects I can't talk about), but in general you couldn't JIT without some special permissions bits.
- mst 9y agoAnd presumably once you have those, you're already on the other side of the airtight hatchway and can control the machine directly?
- SolarNet 9y ago
- golergka 9y agoI have seen so many bugs and crashes created exactly because of this kind of thinking: > [insert X here] was no longer guaranteed, but hey, we’re video game programmers, we know what we’re doing, it will be fine.
- pjc50 9y agoThe games industry pretty much valorises doing weird things with the hardware, all the way since the Atari 2600 through the demoscene.
- pjc50 9y agoI'm now wondering if I have enough material to do an interesting writeup for my time as a CPU bug-hunter in verification. The client (a now vanished startup) had a small 8-bit CPU design which they wanted validation for, using the technique of executing random sequences of instructions and comparing the result against an emulator. We wrote the emulator independently from their architecture description. Given that most instructions were a single byte plus arguments and most of those were valid, the test coverage was pretty thorough. All looked fine until I added support for interrupts, at which point we discovered that an interrupt during a branch would not return to the correct point in execution. Verifying security properties of processors is really hard; you can go looking for specific types of failure, but I'm not aware of a general way of proving no information leakage.
- munin 9y ago> but I'm not aware of a general way of proving no information leakage. As I understand it, the current consensus is to use a tagged architecture, then show that there are no observable differences when the tags involve secret data and the value of the tagged data changes. There are a few rubs here. One is that this is pretty hard to do. The other is that no one wants to pay the overhead of using a tagged architecture. Yet another is that deciding what "observable difference" means is challenging (too little, and you probably miss attacks, too much, and you will probably discover information leaks). Further, this kind of rigorous system hasn't been rigorously empirically evaluated by a third party (as far as I know, perhaps in part because it's so hard to create these systems). "Empirically evaluated?" you scoff, "there's a proof, what's the point of testing?" Well... For a glimpse of what this looks like, consider the SAFE architecture: http://www.crash-safe.org/assets/verified-ifc-long-draft-2013-11-10.pdf http://www.crash-safe.org/assets/verified-ifc-long-draft-201... and lowRISC: http://www.lowrisc.org/downloads/lowRISC-memo-2014-001.pdf http://www.lowrisc.org/downloads/lowRISC-memo-2014-001.pdf
- dfox 9y agoOverhead of tagged architecture is to some extent an myth caused by abysmal performance of certain implementations (eg. iAPX whose performance problems are AFAIK caused mainly by funky instruction encoding) and by performance issues with "straightforward" way of running C code on such architectures.
- 6d6b73 9y agoCorrect me if I'm wrong, but won't Meltdown/Spectre bug allow people to jailbreak pretty much any os/device that has CPU that "supports" these bugs? This could potentially open a lot of currently closed devices to people.
- rincebrain 9y agoAIUI (and I am not an expert): - Meltdown, on affected processors (...basically anything from Intel), gets you the ability to read anywhere in memory, whether you could legally map it or not (e.g. you can read from kernel, user, or w/e memory as an unprivileged user, albeit on the order of bytes per second) - Spectre affects approximately anything with a cache and speculative execution, but only buys you reading anywhere that you could legally map, e.g. you can read anything the process you're in could legally read, but you can't, say, read kernel memory with it as an unprivileged user. Either way, you don't get an arbitrary write, but you could maybe use it to make another exploit more reliable with the additional information you get (a big danger of the Spectre family is using it to help you read data outside your sandbox but still in your "process", e.g. stealing password auto-fill data from inside JavaScript, or using it to defeat ASLR on your sandbox, or ...).
- 6d6b73 9y agoTrue, but sometimes just getting private key from the memory will be enough to gain access to the system as it could give researchers ability to build executable that will look like they came from the manufacturer/developer.
- SomeHacker44 9y agoModern design seems to be moving these sorts of keys from CPU addressable memory into "protected enclaves" and co-processors of various sorts.
- Rusky 9y agoSpectre also allows reads from places you can't map, as long as you can mistrain the branch predictor for some other code that can.
- peter_d_sherman 9y agoArticle Excerpt: "So a speculatively-executed xdcbt was identical to a real xdcbt!" I've never thought about it until I saw the above line in the article, and that thought went something like this: "Assembler instructions which might never have the conditions met for their execution during a program's runtime might be speculatively executed nonetheless, and this, depending on the nature of the instruction executed, might have huge ramifications up to and including program incorrectness and even program failure." In other words, your absolutely 100% deterministic Turing machine (or programs that you write on it that you deem to be 100% deterministic) -- may not be quite so deterministic when viewed against these understandings... It adds a whole new dimension to what must be thought about when writing assembler code... Anyway, it's a really great article!
- johannesburgel 9y agoThe machine is still deterministic, it just doesn't conform to the assumption. It's a bug. You can only think about the bug when you write the assembly code if you know about it. There is lots of hardware with strange bugs out there, and in some setups (embedded devices, mission critical systems etc.) it can be easier to work around them instead of trying to fix the hardware. I know of a medical systems manufacturer which still sticks to some incredibly old CPUs, a home-grown operating system and gcc 2.95 because after 15 years they think they at least know about all the problems and how to work around them. Fixing the issues would pretty much require them to re-validate the whole design and repeat all the testing, which would take several years.
- kevingadd 9y agoIn production though the machine will not behave deterministically from your perspective, because you do not have all the inputs to the machine. Some of the inputs are controlled by a third party (the hypervisor, or worse, another VM running on your EC2 host that is actively manipulating branch predictor data to control the speculative execution for your application.) Even if you capture every operation that runs inside your VM, including register states, timing, etc, you won't be able to reproduce the actual behavior that occurred on the host because you don't know what happened outside the VM. One could argue that the introduction of cloud computing (using virtualization) has converted the machines we run on from deterministic to sorta-deterministic. It just happens that until now we haven't been hurt by it much. Now everyone's paying for it, to the tune of a sizable performance hit on syscalls.
- jhallenworld 9y agoThis issue that xdcbt is supposed to solve happens at a completely different level. Performing a full disk to tape backup would slow systems down because the entire disk would be copied through the OS buffer cache, evicting data used by other processes. The UNIX fix for this was to use a raw device or O_DIRECT to bypass the buffer cache. Maybe Intel's new cache partitioning feature offers a similar fix, see: https://lwn.net/Articles/694800/ https://lwn.net/Articles/694800/ Actually in the comments someone mentions using cache partitioning for security. Maybe the threads used by jit code could be placed in their cache partition to avoid some of Spectre.
- rzzzt 9y agoWould gcc's "__builtin_expect" construct help in these cases?
- syncsynchalt 9y agoYes, it might have, assuming it's available in the 360 compilation environment. Another solution would be to split the existing function into safe_function() and unsafe_function(), and remove use of the PREFETCH_EX flag. But then you have to explain to callers that they must not protect calls to unsafe_function() with any kind of conditional statement. The author hinted at possible solutions but it was probably a case of "twice bitten" by that point.
- tmandry 9y agoIn general, no, because branch predictors often ignore or override hints like this. It's hard to say without knowing this architecture specifically, of course. Keep in mind that it's possible for a branch predictor to predict with "high confidence" a branch it's never seen before, because many branches may overlap into the same memory region of the predictor. The article touches on this.
- alexkoeh 9y agoReading about the architecture of that chip (3 core, PowerPC) I am amazed at how smooth GTA V could run on it.