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? :)

Search for complexity measure and where it took me...

Well, I got very interested in complex systems lately. So, I decided to write a paper for a local conference in which I tried to join information security with complexity. A part of this endeavor made me to Google for a paper that describes complexity measure. Well, I found many interesting things, but not what I was looking for, at least not yet. Still, I wanted to preserve some of those interesting pages and materials for a later reference.

The first page, and indeed it was the first page in google search, I stumbled upon Cosma Shalizi's page about Complexity Measures. Well, I have to say that he seems to have very good pages. What generated my next interest was his critique of Wolfram's book A New Kind of a Science. Actually, on the page about Complexity Measures there is a list of Disrecommended stuff, part of which is aforementioned book.

This also took me briefly to Wikipedia's page about  Jacques Derrida and then to the page about Slavoj Žižek. But the only thing that made me go to Slavoj's page on Wikipedia was the fact that his name sounds like he's from some former Yugoslavia republic, which turned out to be true; he's from Slovenia. But, let me go back to Derrida. Derrida was obviously philosopher that developed critical theory of deconstruction. To be honest, I don't understand yet what it is about, at least not enough to write something meaningful, so I'll try again later.

Still, Derrida wasn't the end of my wondering, since, while reading critique of Wolfram's book, I took a detour into tag system, then to more broad models of computation, and finally to Turing machine. Well, Wikipedia, as usual, has very good text about it and it is now also on my todo list.

Somewhere along the way I also checked the Wikipedia page about Kolmogorov, and subsequently about Per_Martin-Löf because he's mentioned as extending Kolmogorov complexity measure into very interesting direction. Also, I checked page about randomness. Supposedly, on this page truly random data can be obtained which is collected from some atmospheric measurements, but again, I'm not certain that it is the truth. Cosma Shalizi has many other interesting pages, one of which is his critique of using gzip for complexity measure. Last, but not least, I also stumbled on Cellular automata FAQ because Wolfram's book claims that universe is certain kind of CA and that the existing approach of using complex formulas to describe it is wrong.

I wrote this blog entry for two reasons. First one is to save links in order to check them again. And the second reason is that I wasn't aware of the controversy surrounding Wolfram's book.