Turing at CCS'10

Today we had two papers at CCS'10 introducing new, Turing complete languages. The second one is "Return-Oriented Programming Without Returns" by Stephen Checkoway, Lucas Davi, Alexandra Dmitrienko, Ahmad-Reza Sadeghi, Hovav Shacham and Marcel Winandy and extends the concept of return-oriented programming into "jump-oriented programming" that uses jump instructions instead of return instructions to build gadgets and this has severe security implications as the authors showed at the examples of x86 processors and Android based devices running on ARM chips. But the first paper "Platform-Independent Program" by Sang Kil Cha, Brian Pak, David Brumley and Richard J. Lipton was even more impressive.

However, before I continue to write about the paper, I should give a short explanation of Turing complete languages and why these are important: In 1937, a few years before the first programmable computer was built, the mathematician Alan Turing invented the concept of a Turing machine to prove that a universal (or programmable) machine can be built that can solve any computable problem. Although no universal Turing machine will ever be built since it requires infinite memory, this is basically the most important result of computer science. If you take a set of instructions which are sufficient to simulate such a Turing machine (with exception of the infinite memory), this set is called "Turing complete". This certainly is not the biggest deal in the world since all modern processors have Turing complete instruction sets. And indeed, in both papers, the Turing completeness of the languages is only used to prove that their languages do not lack fundamental concepts.

So let me now explain what's so special about the language introduced in "Platform-Independent Program". Commonly the instruction sets of two different processors overlap to a certain extent but are not equal; a program for x86 processors will never run on an ARM processor and vice versa. So the authors of the paper started looking at the overlap of the instruction sets to find jump instructions that will have the following effect:

• If executed on platform a, jump to address x.
• If executed on platform b, jump to address y.

Now they can place instructions for platform a at position x and instructions for platform b at position y. Out of such short code sequences the authors build gadgets and all the gadgets together form a turing complete language. (The instructions at x and y do not have to have the same effect; on platform a the program might be a harmless desktop gimmick, on platform b it might be malware.) The really amazing thing about this is, that (to my knowledge) this is the first language that is at least semi-platform independent but does not require a virtual machine such as Java or an interpreter to achieve platform independence. (It still needs to have enough overlap in the instruction sets.)