: arm and x86 are turing-complete without data fetches // domas, @xoreaxeaxeax
Tiresias is a brief proof of concept that ARM and x86 (and most other Von Neumann architectures) are Turing-complete without actually reading data.
The project began as a thought experiment on circumventions to an arbitrary 'execute-only' memory protection. Looking at x86 for succinctness, the (somewhat uninspiring) observation is that a data fetch:
data: 0xdeadc0de
mov eax, [data]
can be simulated by an instruction fetch instead:
mov eax, 0xdeadc0de
A data write, then, simply modifies the immediate used in the instruction. Memory can then be modeled as an array of 'fetch cells':
cell_0:
mov eax, 0xdeadc0de
jmp esi
cell_1:
mov eax, 0xfeedface
jmp esi
cell_2:
mov eax, 0xcafed00d
jmp esi
To read a memory cell, without a data fetch, we then:
mov esi, mret
jmp cell_2 ; load cell 2
mret:
And writing a data cell is simply modifying the immediate used:
mov [cell_1+1], 0xc0ffee ; set cell 1
Of course, for a proof of concept, we should actually compute something, without reading data. As is typical in this situation, the BrainF#$! language is an ideal candidate for implementation - our fetch cells can be easily adapted to fit the BF memory model. Reads from the BF memory space are performed through a jmp to the BF data cell, which loads an immediate, and jmps back; writes to the BF memory space are executed as self modifying code, overwriting the immediate value loaded by the data cell. To satisfy our 'no data fetch' requirement, we implement a BrainF#$! interpreter without a stack. The I/O BF instructions (. and ,), which use an int 0x80, will, at some point, use data reads of course, but this is merely a result of the Linux implementation of I/O.
The result is functioning Turing-machines on ARM and x86 capable of execution without ever touching the data read pipeline. Practical applications are nonexistent.
# build:
$ make
# verify there are no ARM data fetches:
$ objdump -d tiresias | grep -e ldr -e ldm
# or for x86:
$ objdump -d tiresias | grep '),'
$ objdump -d tiresias | grep -v mov | grep ',('
# execute a program without reading data:
$ cat hello_world.by | ./tiresias
Hello World!
This work is inspired by the blog post 'x86 is Turing-complete with no registers'. http://mainisusuallyafunction.blogspot.com/2014/02/x86-is-turing-complete-with-no-registers.html
Tiresias is a proof-of-concept from Christopher Domas (@xoreaxeaxeax).