trapcc VS movfuscator

A variation of this has been done using Intel MMU fault handling. Behold: https://github.com/jbangert/trapcc

This is a proof by construction that the Intel MMU's fault handling mechanism is Turing complete. We have constructed an assembler that translates 'Move, Branch if Zero, Decrement' instructions to C source that sets up various processor control tables. After this code has executed, the CPU computes by attempting to fault without ever executing a single instruction. Optionally, the assembler can also generate X86 instructions that will display variables in the VGA frame buffer and will cause control to be transferred between the native (display) instructions and 'weird machine' trap instructions.

This thread is about hacking something up and not building a product.

For example imagine somebody shares the "one instruction set computer" (https://en.wikipedia.org/wiki/One-instruction_set_computer) project or x86 MMU being turing complete (https://github.com/jbangert/trapcc). Both are clearly just interesting hacks (which may have some interesting implications about security and what does it mean to be "code" etc) and certainly are not intended to be practical products

fwiw, linked to from the article:

> As others have shown, we can compute using alphanumeric machine code[1] or English sentences[2], using only the mov instruction[3], or using the MMU[4] as it handles a never-ending double-fault. Here is my contribution to this genre of Turing tarpit: x86 is Turing-complete with no registers.

[1] http://www.phrack.org/issues.html?issue=57&id=15#article

[2] http://www.cs.jhu.edu/~sam/ccs243-mason.pdf

[3] http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf

[4] https://github.com/jbangert/trapcc

I think trapcc is what you're thinking about maybe?

MMU gang.

page fault handling is Turing complete

Everything can be reduced to assignments. https://github.com/xoreaxeaxeax/movfuscator

However, the movfuscator as implemented does still require a sigaction(2) syscall to set up a signal handler, under the justifications that "it is not actually part of the program" and that "if we were in ring 0, we wouldn't need help from the kernel" [0]. However, the latter part seems a little dubious to me: without the help of the kernel running non-MOV instructions, you'd never be able to escape from 16-bit real mode into 32-bit protected mode, since you wouldn't be able to load a valid GDT with the LGDT instruction (as far as I am aware).

[0] https://github.com/xoreaxeaxeax/movfuscator/blob/90a49f31219...

I _think_ the idea is thinking of an "interface" as "something that you use as a way to interact with something from outside an abstraction". I'd summarize their argument as reasoning that if the goal of an abstraction is to avoid having to care about the internal details of something, an interface is a way to expose a subset of ways to interact with it, and the more you expand it, the more it exposes the internals of the thing being abstracted. I don't think they necessarily mean this only in terms of programming, but you could apply this argument to a programming language interface; if you use an interface for interacting with something instead of its direct functionality, each additional method you add to the interface exposes more details of the inner value, which makes it less of an abstraction.

Assuming my interpretation is correct, I'm not sure I totally buy this argument because there doesn't seem to be an obvious way to define the "size" of an interface where it holds true. The naive way to define the size would be number of methods, but I'd argue that methods can vary so much in terms of the amount of cognitive overhead they "expose" to the user that it's not very meaningful. Consider the Movfuscator compiler[0], which compiles code into binaries only using MOV x86 instructions because it happens to be Turing complete; as complex as it might be to learn x86 assembly as a whole and start writing programs directly in it, I'm dubious that trying to do so only with MOV would somehow be easier. Put another way, an x86 instruction set that only contains the MOV instruction is not a "stronger" abstraction than the actual one because it _introduces_ complexity that doesn't exist in the original. Does adding an ADD instruction alongside MOV increase the strength of the abstraction, or weaken it? I don't think there's an answer that we'd immediately all agree on for this sort of thing.

Ultimately, I think trying to measure interfaces through the number of methods they expose is similar to trying to measure code by the number of lines in it; while there are some extreme cases where we'd likely all agree (e.g. for a fizzbuzz implementation, having 10 lines of code is probably better than thousands of lines of code[1]), we can't really come up with a good objective metric because the "target" number is based on the complexity of what you're trying to define, and we don't have a way of quantifying that complexity. I think the ideas here are still super interesting though, not because they have definitive right or wrong answers, but because thinking about stuff like this overall improves one's ability to write good software for usage by other programmers.

[0]: https://github.com/xoreaxeaxeax/movfuscator

The mov instruction in x86-64 is Turing complete. Someone even made a C compiler using only mov.

Are you sure they didn't use the MOVFUSCATOR?

Yep. In fact you can reduce everything to just one simple assembly instruction.