2013: Advent Computing: Numbers changing numbers

by on December 9, 2013

The Turing machine we saw has its instructions, which we often think of as its program, and its tape, which is its memory. That’s not really accurate, though, and hasn’t really been accurate since we stopped writing programs by punching holes in bits of cardboard.

A more accurate way of thinking about it is that both the program and the memory it’s using exist in the numbers written on the tape, and the book of instructions for what the computer should do is simply the interpretation of the machine language, i.e. the translation from numbers on the tape to actions the computer should perform.

One of the important side effects of this is that, just as a program can erase and rewrite some of it’s data store (such as when you tell your architecture program that a room should be 10m wide rather than 15m), a program is just as capable of rewriting itself. If a program were to rewrite the bit of it that performs an action only if one number is less than another to actually happen when one number is greater, you can completely change the nature of the program.

As a programmer, this is rarely something you want to do. It makes it much harder to predict how your program will behave, because the behaviour of the program itself can change. If you’ve ever played the card game Fluxx, you’ll know how confusing this can be (and if you haven’t, you should).

There is one place this behaviour is useful, however, for given values of “useful”: if you can get a program to overwrite itself with some data you control, or to treat some bit of data you control as if it were machine language, you might just be able to get it to do the things you want it to rather than the things it was meant to. This is one of the primary ways people writing computer viruses can take control of your computer. Once they’ve found a way to trick your computer to run some small bit of code they’ve written, they can use that little bit of code to “bootstrap” the full virus, getting your computer to run a whole bunch of machine code it was never meant to.

Thankfully, that isn’t so easy any more: because it’s very rare for a program to want to rewrite itself, an operating system (which is in a position to watch all the programs running on a computer) can detect a program that is rewriting itself, guess that this is unwanted behaviour, and stop the program from doing so. Some operating systems will go so far as to use a trick called “address space layout randomization” or “ASLR”, which will rearrange the machine language program in a semi-random fashion before it’s run, meaning that even if a virus were to find a way of rewriting part of a program, it would have a much harder time finding a useful part of the program to rewrite to be sure its malicious instructions would be interpreted and run.

Leave a Reply