Implementing Turing machine using iptables...

Ok, today I decided that I'm going to try to implement Turing machine using iptables. From the start it was obvious to me that I'll use stream of IP packets as a tape. So, after reading a bit and thinking, I decided to implement this Turing machine. The reason I selected that particular one is because tape always moves to the right, and that simplifies things a lot. More precisely, I decided to implement example given in the linked Wikipedia article.

Now, next problem, after deciding which Turing machine to implement, was where to keep internal state of a Turing machine. For that part I found that I can have mark value (32bit number, i.e. state) per connection. In other words, this means that testing current state is performed with the following test:

-m conntrack --mark <desiredstate>

and to set new state I have to use:

-j CONNTRACK --set-mark <newstate>

It also means that packets that belong to a tape should belong to a single connection, i.e. TCP connection.

Also, I had to decide where to keep content of a cell. There are different possibilities, but for now the simplest one is to use MARK target. So, to test a value of the cell I use:

--mark <cellvalue>

and to set it, I use

-j MARK --set-mark <cellvalue>

The last bit is initialization, i.e. to set initial state, and halting. To set initial state I used state tracking feature of connections in iptables, i.e. the following test:

-m state --state NEW -j CONNTRACK  --set-mark <initialstate>

finally, to halt machine, I set connection tracking state to special state in which no iptable rule will be triggered again.

So, let me show initial version of a shell script that makes this a bit "higher level". First, some initializations, i.e. tape and states definitions:

# Tape is a stream of IP packets belonging to a single TCP connection

TAPE="-s 192.168.0.1 -d 192.168.0.2 -p tcp --dport 80 --sport 10000"

# States, assigned arbitrarily integer values

STATE_A=1

STATE_B=2

STATE_C=3

# Halt state

HALT=4          # Halt state, no instruction will be executed in this state

# Tests when Turing machine is in a particular state

IN_STATE_A="-m connmark --mark $STATE_A"

IN_STATE_B="-m connmark --mark $STATE_B"

IN_STATE_C="-m connmark --mark $STATE_C"

# Actions to change a state of a Turing machine

SET_STATE_A="-j CONNAMRK --set-mark $STATE_A"

SET_STATE_B="-j CONNAMRK --set-mark $STATE_B"

SET_STATE_C="-j CONNAMRK --set-mark $STATE_C"

Next, few pseudo instruction:

INITIALIZE_STATE_A="-m state --state NEW --mark $STATE_A"

# Reading a symbol from a tape, i.e. packet

READ_SYMBOL_0="--mark 0"

READ_SYMBOL_1="--mark 1"

# Writing a symbol to a tape, i.e. packet

WRITE_SYMBOL_0="-j MARK --set-mark 0"

WRITE_SYMBOL_1="-j MARK --set-mark 1"

# Short-hand "pseudo-instruction" to add instruction to a Turing machine

ADD_TURING_INSTRUCTION="iptables -A INPUT $TAPE"

Finally, all the instructions:

# If in state A and symbol 0 was read write symbol 1 and go to state B

$ADD_TURING_INSTRUCTION $IN_STATE_A $READ_SYMBOL0 $WRITE_SYMBOL1

$ADD_TURING_INSTRUCTION $IN_STATE_A $READ_SYMBOL0 $SET_STATE_B

# If in state A and symbol 0 was read write symbol 1 and go to state C

$ADD_TURING_INSTRUCTION $IN_STATE_A $READ_SYMBOL1 $WRITE_SYMBOL1

$ADD_TURING_INSTRUCTION $IN_STATE_A $READ_SYMBOL1 $SET_STATE_C

# If in state B and symbol 0 was read write symbol 0 and go to state A

$ADD_TURING_INSTRUCTION $IN_STATE_B $READ_SYMBOL0 $WRITE_SYMBOL1

$ADD_TURING_INSTRUCTION $IN_STATE_B $READ_SYMBOL0 $SET_STATE_A

# If in state B and symbol 1 was read write symbol 1 and go to state B

$ADD_TURING_INSTRUCTION $IN_STATE_B $READ_SYMBOL1 $WRITE_SYMBOL1

$ADD_TURING_INSTRUCTION $IN_STATE_B $READ_SYMBOL1 $SET_STATE_B

# If in state C and symbol 0 was read write symbol 1 and go to state B

$ADD_TURING_INSTRUCTION $IN_STATE_C $READ_SYMBOL0 $WRITE_SYMBOL1

$ADD_TURING_INSTRUCTION $IN_STATE_C $READ_SYMBOL0 $SET_STATE_B

# If in state C and symbol 1 was read write symbol 1 and halt

$ADD_TURING_INSTRUCTION $IN_STATE_C $READ_SYMBOL1 $WRITE_SYMBOL1

$ADD_TURING_INSTRUCTION $IN_STATE_C $READ_SYMBOL1 $HALT

# Initialize Turing machine

$ADD_TURING_INSTRUCTION $INITIALIZE_STATE_A

Note that I have to use two iptables commands in order to implement writing a symbol and transitioning to a new state. The reason is that I can have only one target per iptables command. Certainly, it could be hidden by making those variables and pseudo-instructions fancier, but, for now this will do...

This particular  Turing machine didn't require me to have transition to a new state without moving a tape. But, there is a solution for this too. All rules have to be placed in a single user-defined chain, and then when no tape movement is required just use -g (iptables' goto target) and start all rules from start. In efect, what will happen is that all the rules will be executed again on the same packet which means on the same cell. So elegant, isn't it? :)