More Turing-completeness in surprising places

My twitter feed was full of “printf is Turing-complete” tweets after the 32c3 talk "New memory corruption attacks: why can't we have nice things?" (see printbf for the paper and the implementation discussed in the video), and that inspired me to read some more articles about Turing-complete¹ mechanisms hiding in surprising places...

C++ exception stack unwinding is Turing-complete

The DWARF debugging information format is complex, which is needed in order to describe optimized code. For example, an expression such as i+1 may be placed in a register reg, and i is not available anywhere in the registers or memory in the optimized program. But the debugger should be able to display the value of i, so the debug information must be able to express that i has the value reg-1. And optimized code can be transformed in much more complex ways than this, so DWARF does (surprisingly) define a stack machine that can do arbitrary computation in order to be able to represent the information.

Exception handling need to unwind the stack and restore registers, which is functionality that can be represented by the debug information, so DWARF was adopted (with some minor modifications) for the exception handling. The stack unwinding code can thus execute programs "hidden" in the DWARF information while unwinding the stack.

The Turing-completeness of this is not strange in the same way as the others I have written about previously; DWARF is designed to be general! But it is probably surprising to most developers that this functionality exists... The paper "Exploiting the hard-working DWARF: Trojan and Exploit Techniques With No Native Executable Code" looks at what can be done with this. The stack machine is rather easy to work with — here is an example from the paper that calculates the length of a string that is located just below the stack frame:

  # Value at −0x8(%rbp) on stack
  DW_OP_breg6 −8
  DW_OP_lit0  # initial strlen
  DW_OP_swap
  DW_OP_dup
LOOP:
  DW_OP_deref_size 1
  # Branch if top of stack nonzero
  DW_OP_bra NOT_DONE
  DW_OP_skip FINISH
NOT_DONE:
  # Increment the counted length
  DW_OP_swap
  DW_OP_lit1
  DW_OP_plus
  DW_OP_swap
  # Add length to char pointer
  DW_OP_plus
  DW_OP_skip LOOP
FINISH:
  # Finally put the character count on the top of the stack
  # as return value
  DW_OP_swap

ELF metadata is Turing-complete

The Runtime Linker/Loader (RTLD) is responsible for loading shared libraries into a process' address space and updating the symbol references in the object code using the relocation and symbol tables. The RTLD can be viewed as a machine that is executing the relocation tables, and the paper "“Weird Machines” in ELF: A Spotlight on the Underappreciated Metadata" shows that this machine is Turing-complete by constructing an assembly-like  language  composed  of  three  instructions

• mov — move
• add — addition
• jnz — jump if not zero

where each instruction is built from a sequence of relocations.

There are two kinds of structures involved in the relocation:

• The symbol tables contain information about the symbols, where each symbol is described by the ELF64_Sym structure

  typedef struct
  {
    Elf64_Word    st_name;      /* Symbol name (string table index) */
    unsigned char st_info;      /* Symbol type and binding */
    unsigned char st_other;     /* Unused */
    Elf64_Section st_shndx;     /* Section index */
    Elf64_Addr    st_value;     /* Symbol value */
    Elf64_Xword   st_size;      /* Symbol size */
  } Elf64_Sym;
  

• The relocation tables specify how to modify the binary, where each relocation is described by the Elf64_Rela structure
  

  typedef struct
  {
    Elf64_Addr    r_offset;     /* Address to patch */
    Elf64_Xword   r_info;       /* Relocation type and symbol index */
    Elf64_Sxword  r_addend;     /* Addend */
  } Elf64_Rela;
  

The construct of the machine is using three kinds of relocations, R_X86_64_COPY, R_X86_64_64, and R_X86_64_RELATIVE, which have the functionality

R_X86_64_COPY         memcpy(base + r.r_offset, s.st_value, s.st_size)
R_X86_64_64           *(base + r.r_offset) = s.st_value + r.addend + base
R_X86_64_RELATIVE     *(base + r.r_offset) = r.r_addend + base

where r is the relocation, s is the symbol referenced by the relocation, and base is the ELF object’s base address (that is typically 0 for an executable). These relocations directly correspond to move and addition instructions of the form

mov *0xbeef0000, $0x02        # *(uint64_t*)0xbeef0000 = 2;
mov *0xbeef0000, [%foo]       # *(uint64_t*)0xbeef0000 = *(uint64_t*)foo;
add *0xbeef0000, %foo, $0x02  # *(uint64_t*)0xbeef0000 = foo + 2;

For example, an addition instruction

add *0xbeef0000, %foo, $0x02

is encoded as a relocation entry with r_offset=0xbeef0000, r_addend=2, and r_info specifying relocation type R_X86_64_64 and the symbol foo.

Branch instructions are implemented by modifying the data RTLD is using while processing the relocations. The RTLD is maintaining a doubly linked list of link_map structures containing information for each ELF object, and it iterates over this list in reverse order when relocating the binary

while (lm != NULL) {
  r = lm->dyn[DT_RELA];
  end = r + lm->dyn[DT_RELASZ];
  for (r ; r < end; r++)
    relocate(lm, r, &dyn[DT_SYM]);
  lm = lm->prev;
}

A branch instruction can be implemented by relocations modifying lm->prev, lm->dyn[DT_RELASZ], or lm->dyn[DT_RELA] so that an lm structure is skipped, handled partially, or handled multiple times. There are some complications such as finding the address to modify, and to save/restore the original value to be able to exit the program. I refer to the paper for the details.

The only thing remaining is a conditional branch instruction. The paper constructs the jnz instruction by noting that symbols of the type STT_GNU_IFUNC are treated differently depending on if the section index is 0 or not, and the symbol can be initialized so that an add instruction of the form

add *0xbeef0000, %foo, $0x00

has the effect

*(uint64_t*)0xbeef0000 = (s.st_shindx != 0) ? CONSTANT : 0;

where s is the Elf64_Sym structure describing foo. This can now be used when rewriting the end marker lm->dyn[DT_RELASZ] so that RTLD does not enter the for-loop for the link map when the condition is 0 (and the machine is thus not jumping to the part of the program defined by those relocations), by relocations first writing the condition to test to s.st_shindx of a temporary symbol s, and then writing the symbol (by adding 0 to it) to lm->dyn[DT_RELASZ].

---

1. I'm playing fast and loose with the concept “Turing-complete”, as does most papers I have read. I had expected computer scientists to be more careful, and use terms like "linear bounded automaton" or similar...

Instruction-less computation – technical details

This blog post continues the previous post by describing the technical details.

Configuring x86 hardware

The IA-32 hardware is configured by a combination of architectural registers and descriptors in memory. The construction of the movdbz machine uses four different kinds of descriptors:

• memory translation tables
  The memory translation is done through a two-level page table, where the first level is called a "page directory". The CR3 register contains the physical address of the page directory to use.

• TSS – Task-State Segment
  The TSS is a structure where the processor state (registers, status flags, etc.) is stored when the task is not running.

• GDT – Global Descriptor Table
  The GDT is an array of "segment descriptors" containing a pointer to a segment (such as a TSS) and some flags. The task switching mechanism access the TSS by indexing the GDT. For example,

  ljmp $24, $0

  switches to a new task whose TSS is described at offset 24 in the GDT.

• IDT – Interrupt Descriptor Table
  The IDT defines how each interrupt is handled by providing an interrupt descriptor for each interrupt type. We configure it to switch to a new task for #PF and #DF exceptions, and each descriptor contains an offset into the GDT corresponding to the target TSS.

Interrupts, task switching, and memory translation tables

The branch targets in the instructions are specified by the IDT, so it needs to be changed when stepping into a new instruction (i.e. when switching to a new task). The task switch cannot change it directly, but the IDT is placed in virtual memory, and the TSS contains CR3 that points to the page directory, so the new task may map a new page for the IDT, and thus modify the branch targets for the new instruction.

This does, however, give us new problems... The TSS contains the stack pointer which is used to encode the register value, so the TSS is now used to represent both a register and an instruction, and we need to separate them.

The TSS is defined as:

We can place this structure in memory so that it crosses a page boundary, where the stack pointer (ESP) is in one page, and CR3 in the other. That is, the TSS is mapped as a combination of a "register page" and an "instruction page".

The implementation places the TSS so that the page boundary is between ECX and EDX (ESP is thus placed 8 bytes from the top of the page).

Handling source and destination registers

The execution of one instruction in the movdbz machine is done in three steps:

1. Read the TSS for the new instruction.
2. Generate exception (as the program counter is invalid). If the stack pointer is not zero, write status and update the stack pointer.
3. Store the TSS.

The registers are represented by the stack pointer stored in the TSS, but the instructions use two registers (source and destination), so the read and write of the stack pointer should be to different TSS structures.

The TSS is stored in virtual memory, and we may play some tricks with the memory translation. The "read TSS" step reads the state (including the CR3) from the TSS, which updates the memory translation. We may use this to map a new register page for the TSS as a side effect of reading the TSS, and the "store TSS" will now write to this new register page (i.e. the destination register). So we will in some sense have two TSS structures; one "source TSS" and one "destination TSS".

Task switching to itself

There is a hardware restriction that task switching must be done to a new task – it is not possible to switch to the currently running task. This means that instructions of the form

loop:    movdbz r0, r0, loop, done

are invalid. But this is not much of a problem as it is easily fixed by inserting a NOP instruction

loop:    movdbz r0, r0, nop, done
nop:     movdbz discard, 0, loop, loop

TSS segment descriptor busy flag

The IA-32 tries to prevent recursive task switching; it has a "busy flag" that is set in the TSS segment descriptor when a task is entered from an interrupt, and the flag must be cleared before the task can be run a second time.

We need to clear this flag, and we do this by mapping the GDT page containing the instruction's segment descriptor as the instruction page in the destination TSS. Writing the TSS will now overwrite the six last segment descriptors in that GDT page. The descriptor at offset 0x0ff8 is overwritten by the value of EAX and EDX, so the instruction page initializes those registers with the original descriptor value, which clears the flag when they are written to the TSS.

This means that we can only have one TSS segment descriptor per page, and the GDT has a maximum size of 16 pages, so we can only have 16 segment descriptors (and thus only 16 TSS). But each instruction sets up the page tables, so we may remap these to correspond to different instructions over time. There are restrictions; each instruction needs to have its own and its destinations' TSS mapped, so their TSS segment descriptors must be different. The trapcc implementation handles this by graph coloring, but there are simpler ways (see "Generating assembler instructions" below).

Encoding of the instructions

We now have everything we need in order to describe the implementation.

The instless_comp uses three TSS segment descriptors for the instructions, at GDT offset 0x1ff8, 0x2ff8, and 0x3ff8, and have the corresponding TSS mapped at address 0x40ffd0, 0x41ffd0, and 0x42ffd0 in the virtual address space.

The instructions are encoded in four pages:

• Page Directory
  The page directory sets up five virtual address ranges:
  
  • STACK – the stack for the movdbz machine
  • INST – mappings for the movdbz instruction (where TSS  and IDT are placed)
  • GDT – the GDT
  • X86 – the code and data for the CPU (only needed to access the TSS when exiting the movdbz machine)
  • PROG – the movdbz program
  It is only the INST address range that is specific for the instruction – the other ranges have identical mappings in all instructions.

• Page Table
  This maps the IDT page, the destination TSS (destination register page and GDT page) for the current instruction, and the source TSS (source register page and instruction page) for the successor instructions, into the address space.

• Instruction page
  The instruction page of the TSS is set up so that
  
  • CR3 points to the page directory.
  • The program counter (EIP) is set to an invalid address.
  • EAX and EDX have the value of the corresponding TSS segment descriptor.
  • EFLAGS, that contains miscellaneous flags for the system state, is set to the value used when running the CPU.

• IDT page
  The IDT page contains an IDT that handles #PF and #DF exceptions by switching to a task corresponding to the destination instruction.

The movdbz machine is started by switching to the task corresponding to the first instruction, and it is possible to exit from the machine by letting it switch to the task identified by GDT index 0x18, which is the task for the original program running on the CPU.

Generating assembler instructions

The restrictions on the instructions make it hard to write assembly code, and are annoying when doing code generation. The assembler in instless_comp solves this by generating each assembler instruction as three "real" instructions, so that an instruction of the form

label:    movdbz rdest, rsrc, label_nonzero, label_zero

is generated as

label:    movdbz discard, 1, label+2, label+2
label+1:  movdbz discard, 1, label+2, label+2
label+2:  movdbz rdest, rsrc, label_nonzero, label_zero+1

The first instruction is always encoded with the TSS descriptor at offset 0x1ff8, the second at offset  0x2ff8, and the third at offset 0x3ff8, so this always satisfies the constraints without needing graph coloring. And it also handles the assembler instruction branching to itself, as that will branch from the last instruction to one of the two preceding NOP instructions.

We also know that the target in an assembly instruction always is a NOP, so its input register is always the constant 1, and we do not need to propagate the input registers to its predecessors.

Instruction-less computation

The paper "The Page-Fault Weird Machine: Lessons in Instruction-less Computation" show that you can run programs on the X86 fault handling mechanism, i.e. without executing any instructions on the CPU!

The construction of this weird machine is using two properties of the IA-32 architecture:

• Task switching
  The IA-32 has hardware support for task switching — storing the CPU state (registers and status flags), and resuming execution with a new memory map and previously stored CPU state. The interrupt controller may be configured so that a task switch happens when an exception is raised.
• Interrupts writes an error code to the stack
  The Page-Fault Exception (#PF) writes a 32-bit error code to the stack and decrements the stack pointer before handling the exception, which lets us modify the stack pointer without executing any CPU instructions. The stack pointer cannot wrap, so a Double Fault Exception (#DF) is raised instead of #PF if the stack pointer is less than four.

This can be used to  create a machine with registers r0, r1, ..., and a move-branch-if-zero-or-decrement instruction

movdbz rdest, rsrc, label_nonzero, label_zero

that is doing the work corresponding to

if (rsrc == 0) {
    rdest = rsrc;
    goto label_zero;
} else {
    rdest = rsrc - 1;
    goto label_nonzero;
}

The movdbz instruction is Turing-complete (see e.g. Wikipedia "One instruction set computer"¹, or this blog post that describes a BF compiler that only generates movdbz instructions). The paper comes with an implementation in trapcc, and I have made a somewhat simpler and more user-friendly implementation in instless_comp.²

A simplified description of the construction is that each register is represented by a task where the stack pointer contains the register's value multiplied by four. Each instruction is represented by an interrupt vector that switches to new tasks (including a new interrupt vector), where #DF switches to the task corresponding to label_zero and #PF switches to label_nonzero. All tasks have invalid program counters, so the new task will raise a new #PF exception (or #DF if the stack pointer is zero), and the machine steps into the next instruction. The implementation is however much more involved, and I describe the construction in detail in a separate blog post.

The stack pointer needs to point to valid memory (or we will get other interrupts), so the registers can only have values that are represented as valid stack addresses, and we cannot represent 32-bit values even if we map all memory for the stack (the decrement is done by subtracting four from the stack pointer, so we lose the two least significant bits...). It is natural to just map page 0 for the stack to give us registers that are 10 bits wide.

It is possible to make the registers wider by adding more pages to the stack, but it does not help much; the machine can only do subtraction, so e.g. addition

a = b + c;

need to be done by subtracting from a maximum value

a = MAX_VAL - (MAX_VAL - b - c);

And the machine can only decrement by one, so the subtractions need to be done by looping

tmp = MAX_VAL;
while (b--)
    tmp--;
while (c--)
    tmp--;
a = MAX_VAL;
while (tmp--)
    a--;

That is, the running time of addition is exponential in the bit width of the registers, so wide registers are not that useful.

The blog post is continued in part 2 that describes the technical details.

---

1. movdbz reduces trivially to the subtract-and-branch-if-nonzero instruction.

2. The trapcc need to do global analysis (graph coloring etc.) when generating the instructions in order to satisfy some annoying hardware constraints. My implementation uses a less efficient instruction encoding that makes it possible to handle each instruction independently (and makes it easier to write assembly manually).

mov-only code generation

I stumbled on the M/o/Vfuscator compiler that only use mov instructions in the generated code¹ using ideas from the "mov is Turing-complete" paper.

It proves to be surprisingly easy to generate such code. This blog post shows how it is done using a somewhat idealized version of the CPU, but it should be easy to map it on the real X86 ISA. The examples use registers r0, r1, …, and a mov instruction that can be in one of the three forms

mov rdest, rsrc
mov rdest, [rsrc + roffset]      ; Load indexed
mov [rdest + roffset], rsrc      ; Store indexed

It is possible to use an immediate constant instead of rsrc, or for the rdest and roffset in the addresses. The width of the move can be 8 bits (movb) or 32 bits (movl). We'll only use 8-bit values for the computations — wider widths can be handled by working on one byte at a time. Pointers are assumed to be 32 bits wide.

if-statements

We'll begin with if-statements. Comparing two registers r1 == r2 and placing the result in r0 can be done as

movb [&scratch + r1], 0
movb [&scratch + r2], 1
movb r0, [&scratch + r1]

where scratch is an array

uint8_t scratch[256];

We cannot have any flow control when only using mov instructions, so the idea is to handle if-statements by executing both the true and false parts, and ignoring the result from the false part. E.g. code of the form

if (r1 == r2)
    r0 = r3;
else
    r0 = r4;

is compiled as if written

r0 = (r1 == r2) ? r3 : r4;

which can be done as

movb [&scratch + r1], 0
movb [&scratch + r2], 1
movb r0, [&scratch + r1]
movb [&scratch + 1], r3
movb [&scratch + 0], r4
movb r0, [&scratch + r0]

This works fine as long as everything is in registers, or both the true and false parts write to the same memory. The case where they write different memory need to be handled by writing to a dummy location for the cases where no value should be stored. For example,

if (r1 == r2)
    a = r3;

is compiled to

movb [&scratch + r1], 0
movb [&scratch + r2], 4
movb r0, [&scratch + r1]
movl [&tmp + 4], &a
movl [&tmp + 0], &dummy
movl r0, [&tmp + r0]
movb [r0 + 0], r3

where tmp and dummy are defined as

uint32_t tmp[2];
uint8_t dummy;

Addition

Addition by a constant can be implemented by leveraging the addition done within the addressing mode by indexing in a constant array

const uint8_t constants[512] = {
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
       ...
    0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
       ...
    0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff
};

so e.g. adding 23 to r0 is done as

movb r0, [&(constants+23) + r0]

Loops etc.

We now have nearly everything needed to implement a Turing machine where the tape is implemented as an array that is indexed by the current position. The only problem is that we only can do straight line code... So we cheat by adding a jmp instruction at the end of our program, jumping back to the first instruction. This works fine for implementing a Turing machine, as it is typically written as

while (1) {
    if (current_state == 0) {
        /* Do the work for this state */
        current_state = /* State transition */
    } else if (current_state == 1) {
        /* Do the work for this state */
        current_state = /* State transition */
    } else if ...
}

But the same approach works for normal languages too, by treating each basic block as a state, and to do a state transition for each branch.

Program termination

Finally, we need a way to terminate the program. This is done by writing to address 0

movb [0 + 0], 0

which terminates the process with a segmentation fault. Conditional termination is done with the same dummy-variable trick as for the conditional store above.

---

1. This is not completely true – it need exactly one jmp instruction in addition to the mov instructions.