为何完成旅行? [英] Why is mov turing complete?

问题描述

我最近发现了这个问题: https://github.com/xoreaxeaxeax/movfuscator
这似乎取决于 mov 是图灵完整的事实.是真的，为什么?

I found this recently: https://github.com/xoreaxeaxeax/movfuscator
It seems to be contingent on the fact that mov is turing-complete. Is that true, and why?

推荐答案

是的，x86的 mov 已完成图灵化.我将该标签添加到您的问题中，因为对于其他ISA，使用 mov 指令可能不是真的，并且movfuscator编译器仅针对x86.

Yes, x86's mov is Turing complete. I added that tag to your question because it may not be true for other ISAs with an instruction called mov, and the movfuscator compiler only targets x86.

本身不是在进行计算的移动"，而是可以进行加法(和移位)的x86寻址模式.我没有详细介绍它的工作原理，但是它在很大程度上依赖于查找表，并且 mov eax，[base + eax * 4] 之类的东西取决于EAX为0或1的两个可能值中的一个.

It's not "mov" itself doing computation, it's x86 addressing modes which can do addition (and bit-shift). I haven't looked in detail at how it works, but it relies a lot on lookup tables, and stuff like mov eax, [base + eax*4] loading one of two possible values depending on EAX being 0 or 1.

还请记住， x86 mov 具有几种形式:在存储器和寄存器之间(加载，存储或reg-reg)，或直接在存储器或寄存器之间.并且具有包括绝对和寄存器间接寻址的寻址模式.

Also remember that x86 mov has several forms: between memory and register (load, store, or reg<-reg), or immediate to memory or register. And with addressing modes including absolute and register indirect.

我不认为它依赖于自我修改的代码，但是如果我错了，请纠正我.(如果这样的话，我认为/希望movfuscator至少不会创建除 mov 以外的指令.那会是作弊.)

I don't think it relies on self-modifying code, but correct me if I'm wrong. (And if it does, I think/hope movfuscator at least won't create instructions other than mov. That would be cheating.)

此外，这只是一种事实；您需要某种方法来循环主程序，假设原始源不是直线无循环的-Movfuscator github自述文件对此进行了讨论:

Also, it's only sort of true; you need some way to loop the main program, assuming the original source isn't straight-line with no loops - the Movfuscator github readme talks about this:

尽管Dolan的论文需要使用jmp指令，但M/o/Vfuscator却不需要-它使用有故障的mov指令来实现无限执行循环.如果您担心这仍在跳跃"中，则可以通过将页面别名为相同的地址，在内存的上限范围内环绕执行，ring 0异常处理或简单地无限期重复mov循环来实现相同的效果.目前，使用jmp来调度外部函数-如果这是一个问题，请避免使用外部函数，或者也可以使用M/o/Vfuscator编译库.

While Dolan's paper required a jmp instruction, the M/o/Vfuscator does not - it uses a faulting mov instruction to achieve the infinite execution loop. If you're worried that this is still "jumping", the same effect could be achieved through pages aliased to the same address, wrapping execution around the upper range of memory, ring 0 exception handling, or simply repeating the mov loop indefinitely. A jmp is currently used to dispatch external functions - if this is a problem, avoid using external functions, or compile libraries with the M/o/Vfuscator as well.

为仅运行mov的代码创建用户空间环境时，我假设它创建了一个SIGSEGV处理程序(在POSIX OS上)，该处理程序从顶部重新开始执行.因此，任何有故障的负载都可以重新启动主循环.

When creating a user-space environment for mov-only code to run, I assume it creates a SIGSEGV handler (on POSIX OSes) that restarts execution from the top. So any faulting load can restart the main loop.

还提到了保留执行环绕的可能性:

Letting execution wrap around is also mentioned as a possibility:

IP的环绕可在16位模式(IP为16位，但CS:IP形成20位线性地址(实模式)或在16位保护模式下在线性地址空间中的64k窗口)中很好地工作.也就是说，您只能在地址空间的 part 中有一个64k的指令块，剩下的空间用于存储数据.DS细分受众群可以使用其他基准.(可以使用16位模式下的32位寻址模式，因此您仍具有任何寄存器和缩放索引寻址模式的全部功能.)请注意，用于读取和写入段寄存器的助记符也是 mov .

Wraparound of IP can work well in 16-bit mode where IP is 16-bit but CS:IP form a 20-bit linear address (real mode) or in 16-bit protected mode a 64k window somewhere in linear address space. i.e. you can have a 64k block of instructions in only part of your address space, with other space left for data. The DS segment can use a different base. (32-bit addressing modes in 16-bit mode are possible so you still have the full power of any register and scaled-index addressing mode.) Note that the mnemonic for reading and writing segment registers is also mov.

但是在EIP为32位的32位模式下更困难，因此在seg + off计算之后的线性地址也是如此.除非有其他技巧，否则绕回只能在整个地址空间中进行，而不管您使用分段如何.这不会为数据留出任何非代码空间.设置较低的段限制可能会导致代码提取错误，但这不会引起环绕(除非您设置了信号处理程序，或者在裸机上设置了中断处理程序地址).

But harder in 32-bit mode where EIP is 32-bit and so are linear addresses after seg+off calculation. Unless there's some other trick, wraparound can only happen across the entire address space, regardless of what you do with segmentation. This leaves no non-code space for data. Setting a lower segment limit could make code-fetch fault, but that doesn't cause wraparound (unless you set a signal handler, or on bare metal set an interrupt handler address).

无论哪种方式，甚至x86-64都只有64位指针(理论上是48或57位指针)，所以空间是有限的，这与带有无限磁带的真正图灵机不同.

And either way, even x86-64 only has 64-bit pointers (in theory; 48 or 57-bit in practice), so space is finite, unlike a real Turing machine with infinite tape.

这篇关于为何完成旅行?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！