8 ms·
Weird things I learned while writing an x86 emulator
- schemescape 4y agoI thought this was going to be about a toy emulator/hobby project, but it's apparently about an emulator used in Time Travel Debugging!
- mark_undoio 4y agoHa, I was just reading some of the discussion and thinking it sounded quite similar to the JIT we use in our own (Linuxy) Time Travel Debugger. It's similarly am x86-on-x86 JIT / emulator but (and I'm sure WinDbg's TTD is similar) most of what you want to do there is just code copying for any instructions that don't need special instrumentation. And you want to run entirely in the cache of JITted code so you're close to native speed, rather than exit to C code and make decisions.
- timmisiak 4y agoFunny enough, we tried going down the road of doing a JIT, but for our use cases pure emulation was often fast enough and it wasn't worth the extra complexity to do JIT. Part of that is probably due to the architecture of how TTD works, but part of it is how efficient we were able to get with the emulation mode. Later, a different emulator was created for running x86 code on ARM64, and that one uses an extremely efficient JIT. (I didn't get to work on the x86-on-arm64 emulator though. Would have been fun) Working on the JIT in TTD was a lot of fun though, and it's a shame it didn't make sense to keep it around.
- mark_undoio 4y agoVery impressive you got such good performance out of straight emulation! And WinDbg TTD runs with truly parallel threaded execution within one process, which we do not (yet). I'm surprised a JIT wasn't worth it but, from what I'm aware of, I can see a few reasons why the trade offs are different.
- junon 4y agoFascinating list, and really well presented and written! Lots of stuff I've never read about before.
- amelius 4y agoWhat resources did he use for this research? I would expect at least a reference to an Intel reference manual, but perhaps there are better ways to learn about the ISA.
- a-priori 4y agoThere are reference manuals with a lot of details. Specifically you'd want to read the "Intel® 64 and IA-32 Architectures Software Developer’s Manual", Volumes 2, which includes specifications of each instruction including pseudo-code of how the processor executes them. You can freely access a PDF of the entire manual here: https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html https://www.intel.com/content/www/us/en/developer/articles/t... But there's a lot of details there — that volume alone spans about 4000 printed pages in the manual — so you're bound to mess things up. I've written emulators for simpler instruction sets (RISC-V and the 6502) and found that the best way to ensure they work correctly is to do instruction-by-instruction comparisons against a reference. The good news is that if you've got a PC computer, you've got easy access to a reference machine! So you can do side-by-side comparisons where you set up an initial state on both a real machine and an emulated machine, then execute some code on both, and compare the final states. By using the trap flag you could also single-step through the instructions to extract the intermediate states after each instruction and ensure they match the emulated state. So that's my guess about how he did his too. It's painstaking work, but also kind of fun when you get into it.
- timmisiak 4y agoYes, that's exactly what I did. Most useful thing I did was setting up a unit test framework to test a single instruction, and then generating a huge number of variations of those instructions.
- timmisiak 4y agoI talked a bit about the Intel SDM in the last post I wrote (linked at the top). The SDM is great for getting the specific details, but isn't always approachable for high level overview things.
- troad 4y agoI wish this wasn't written largely using a gray font on a gray background, because it's a pain to read.
- timmisiak 4y agoApologies. I'm just using a Hugo template and haven't spent a lot of time figuring out how to customize it. You're right though, the contrast isn't great.
- Akronymus 4y agoThis reminds me a lot of the defcon 25 talk by xlogicx about assembly being too high level. https://youtu.be/eunYrrcxXfw https://youtu.be/eunYrrcxXfw
- FullyFunctional 4y agoNice article, but nothing really surprising when you follow the progression starting from 8080. One correction though: > EAX is called the “Accumulator register” is not just a convention, it actually makes a difference to the encoding (and potentially the performance, as a result) No. As the decoder doesn't decode byte-by-bytes, but whole strings together and registers are all renamed meaning that %eax isn't really different from %ebx etc. the only difference is that it saves one byte of code space which is an extremely minor density improvement and you'd have to make a very contrived example to be able to measure the difference.
- timmisiak 4y agoMy point is the smaller encoding is what gives you the performance benefit. When done across an entire function/module, you can get a measurable increase in hit rate for the instruction cache. Not that the instruction itself is faster. Apologies if that wasn't clear.
- FullyFunctional 4y agoNo, I got that point and it's vanishingly small. It _only_ affects miss rate (ie. does nothing if you are hitting in the cache) and the effect on miss rate is minuscule.
- trzy 4y agoVery cool! Writing emulators for simple CPUs is challenging enough because it's extremely easy to overlook a quirk or implement a flag calculation incorrectly that is used infrequently and have it silently lurking like a mine waiting for the rare piece of code to trip it. x86 is very complex. Instruction decoding alone looks like a nightmare. I guess the one saving grace here is that since most of us still run on x86, side-by-side validation is a lot easier.
- timmisiak 4y agoYes, that made it 100x easier, because I was able to write unit tests that literally did a single step over the instruction and compare the register context to the emulated register context. The single step approach didn't work for all instructions (and didn't work for undefined flags) but was extremely effective and let me brute force a whole lot of testing.
- convery 4y ago> You can add quite a few until you get to 15 bytes. This length is a hard limit on current x86-compatible CPUs. Any instruction longer than 15 bytes is considered invalid and will generate an exception. There's a few valid 16 byte instructions though.. Sandpile lists a few examples: https://www.sandpile.org/x86/opc_enc.htm https://www.sandpile.org/x86/opc_enc.htm 36 67 8F EA 78 10 84 24 disp32 imm32 = bextr eax,[ss:esp*1+disp32],imm32 64 67 8F EA F8 10 84 18 disp32 imm32 = bextr rax,[fs:eax+ebx+disp32],imm32
- timmisiak 4y agoThat's really interesting. I had no idea there were structurally valid instructions that are longer than 15 bytes.
- dwattttt 4y agoAssuming this limit has even been the cause of a vulnerability before: https://lists.gnu.org/archive/html/qemu-devel/2017-03/msg03858.html https://lists.gnu.org/archive/html/qemu-devel/2017-03/msg038...
- rustybolt 4y agoValid meaning "valid according to spec" or "actually executable by processors in practice"?
- Sniffnoy 4y agoGoing by the linked webpage, the answer appears to be "valid if we ignore the limit, but in fact the limit is enforced and you'll get an exception".
- woodruffw 4y agoThe longest structurally valid x86 instruction is 26 bytes, from some research I did a few years ago[1]. But as others have noted, structurally valid does not mean that any x86 CPU will accept them: they’ll all produce #UD or similar, including these 16 byte ones. [1]: https://yossarian.net/res/pub/mishegos-langsec-2021.pdf https://yossarian.net/res/pub/mishegos-langsec-2021.pdf
- woodruffw 4y agoThis is a good list! Another fun quirk: because x86 is a register-memory architecture and allows all kinds of variants of reg/mem operand encodings, there are a handful of equivalent encodings with exactly the same lengths (and just slightly different ModR/M bytes). You can take advantage of this to do software fingerprinting or, in my case, steganography without changing an executable’s size or semantics[1]. [1]: https://github.com/woodruffw/steg86 https://github.com/woodruffw/steg86
- kuroguro 4y agoUsed the exact same trick when researching dumb ways to break AV signatures at uni :) You can also abuse the displacement math with eiz: ff 34 24 push DWORD PTR [esp] ff 34 e4 push DWORD PTR [esp+eiz*8] Or some useless prefixes may work: 80 c0 53 add al,0x53 36 04 53 ss add al,0x53
- wruza 4y agoThis is the first time I learned about eiz. Cool trick! What’s eiz: https://stackoverflow.com/a/2553556/3125367 https://stackoverflow.com/a/2553556/3125367
- ginnungagap 4y agoIf I remember correctly there are also tricks like lea rax, [eiz+rbx*4] instead of lea rax, [rbx*4] because the latter will produce an heavier binary by being interpreted as lea rax, [00000000h+rbx*4]
- rep_lodsb 4y agoYou won't find "eiz" in any Intel manual, and NASM doesn't recognize it either. x86 has no zero register¹. This appears to be some GNU-specific syntax meaning "encode SIB byte with no index register". The only case where this would be required by the hardware is when using ESP/RSP as a base register, and every assembler should produce the correct encoding for that if you simply write [ESP]. So using "eiz" on GAS lets you control what is put into the (unused) scale field. One might call that a feature, but it is a meaningless encoding detail similar to which variant of "register to register" opcodes is emitted, something that I don't think any assembler gives you control over. ¹ except maybe on the microarchitectural level, but that isn't visible to the programmer
- jamesfinlayson 4y ago> Other instructions leave some of the flags in an undefined state, although in some cases they are conditionally undefined. > I’ve heard that the Atom line of CPUs used a cheaper/slower way of doing bit shifts in the ALU, which results in the undefined flags having different values, although I haven’t tested this myself. That seems... problematic. Do compilers know this and just ignore the flags if/when they use these instructions?
- woodruffw 4y agoYes. In general, compilers only test emit flag testing instructions after instructions that are explicitly defined as having flag-modifying semantics. (This is a common feature of ISAs, and makes sense in terms of component reuse: it allows you to cheaply reuse the ALU, for example, without needing extra wires/control signals telling it not to update the flag state.)
- Someone 4y ago> compilers only emit flag testing instructions after instructions that are explicitly defined as having flag-modifying semantics. I think compiler writers sometimes also have to know that instructions do not modify the flags. Such instructions can be inserted between flag-setting ones and the test of that flag.
- woodruffw 4y agoYes, good point! It would have been more accurate for me to say “the compiler should always have a model of the flags during lowering.”
- userbinator 4y agoAn ADD instruction will update the carry flag but the INC instruction does not! Neither does DEC, and I believe the original reason for this was multiple-precision arithmetic routines --- you need to propagate the carry flag, but also update loop counters and pointers. It seems that the actual behavior of the undefined flags is related to the internal implementation of the shift operation, and is different between different architectures. According to https://www.sandpile.org/x86/flags.htm https://www.sandpile.org/x86/flags.htm which unfortunately hasn't been updated nor is exhaustive, all of the P6 family behave the same, but different from the P5 and the P4, and probably the earlier generations too. "Undefined" values are often used by anti-debugging/anti-emulation/VM detection code to determine if the CPU is real hardware or not, so it's actually quite important to emulate them correctly.
- FartyMcFarter 4y ago> "Undefined" values are often used by anti-debugging/anti-emulation/VM detection code to determine if the CPU is real hardware or not, so it's actually quite important to emulate them correctly. That seems quite brittle, unless all real CPUs implement them the same way. If they do, one has to wonder whether it's really undefined or an undocumented part of the x86 spec instead.
- flohofwoe 4y agoI'd guess it's "undocumented", not "undefined". Don't know how the situation is on x86, but on the Z80 there were indeed some slight differences in undocumented behaviour between CPU vendors, but those are so obscure that it hardly affected any real world code (they affected the undocumented flag bits 3 and 5, and their behaviour was only properly 'decoded' in the 2000's (https://github.com/floooh/emu-info/blob/master/z80/memptr_eng.txt https://github.com/floooh/emu-info/blob/master/z80/memptr_en...). The only CPU I know with actual 'undefined' behaviour is the 6502 for some of the undocumented/illegal opcodes which can yield different results based on things like current CPU temperature (see the ANE/XAA instruction description: https://www.masswerk.at/nowgobang/2021/6502-illegal-opcodes https://www.masswerk.at/nowgobang/2021/6502-illegal-opcodes)
- 4y ago
- menaerus 4y agoHas anyone used TTD, or rr for that purpose in Linux world, to debug a complex multi-threaded application? What is the main use-case of these tools? For example, limitations of rr seem to suggest that it is almost of no use for multi-threaded programs so I have never actually tried it. I don't know about the TTD though. > rr limitations > ... > emulates a single-core machine. So, parallel programs incur the slowdown of running on a single core. This is an inherent feature of the design.
- rcxdude 4y agoIt can still debug multi-threaded programs, but if your bug relies on multi-core interactions it won't appear under rr (you can still catch a lot of race conditions though, and it has a 'chaos mode' which generate irregular scheduling intended to increase the likelyhood of such bugs appearing). It's been used to debug race conditions as well as other bugs in firefox, for example.
- menaerus 4y agoThat's what I thought as well, limited to the single-core race conditions era. Thanks for the evidence.
- pm215 4y agoIt's still much better than the alternative, which is not having any kind of way to reproduce race conditions :-) QEMU's a pretty complex multithreaded program and my experience with chaos mode has been that it's quite good at tripping up the races (and you only need to catch the race once).
- ghusbands 4y agoIt's not limited to any era - it's a general-purpose tool that can perfectly reproduce bugs, even most race conditions. The lack of multi-threading will mostly just slow things down. Being able to perfectly reproduce a bug is immensely valuable.