I always find in many papers discussing different kind of system security subject that the authors always trying to highlight the danger of some vulnerabilities by assuming an attacker, by exploiting them, can achieve Turing completeness. What is Turing completeness and what is the danger behind it if achieved by an attacker?


An exploit that provides a turing-complete execution environment allows the attacker to run any algorithm they wish. They will not be limited by the number of available instructions.

A system of data manipulation rules (script, program, instruction set, etc) is considered turing-complete if it can be used to simulate a Turing machine. Turing equivalence states that two turing-complete constructs are identical in their capabilities. In other words, if someone can execute turing-complete code on a vulnerable computer, they can compute anything, barring resource limitations. The Church-Turing thesis conjectures that a Turing machine can compute any value that can also be computed by an algorithm. From the Wikipedia article:

To show that something is Turing complete, it is enough to show that it can be used to simulate some Turing complete system. For example, an imperative language is Turing complete if it has conditional branching (e.g., "if" and "goto" statements, or a "branch if zero" instruction; see one instruction set computer) and the ability to change an arbitrary amount of memory (e.g., the ability to maintain an arbitrary number of variables). Since this is almost always the case, most if not all imperative languages are Turing complete if the limitations of finite memory are ignored.

This is particularly relevant in the case of ROP, an exploitation technique where existing code is executed out-of-order. A sufficiently complex vulnerable program can make for turing-complete ROP, which means that the attacker is not limited to only certain types of computation.

So, why does something as abstract as computation matter, rather than just the capabilities of the exploited program? Imagine if you had access to a shell, running as root. Obviously root can do pretty much everything, but what if the only things you can do on the shell is run echo, id, and cd? No if statements, no mv, no sed... You'd be pretty limited in what you can do. That scenario would not be turing-complete because you do not have enough commands to make it turing-complete. A turing-complete ROP chain is a similar concept, but rather than utilizing shell commands, it utilizes machine code. If you can only run a few instructions, you can't do much.


Turing completeness basically means, that the attackers can do whatever they want inside the application. It is the same as being able to run arbitrary code.

Turing complete machine is in information theory a machine, that can compute any solvable problem. In practice, it usually means the attackers can run arbitrary code on your machine. In some cases, there may be other ways to achieve Turing Complete Access, but the implications are the same. A vulnerability that does not give attackers Turing completeness may pose some more limited problems. Consider for example, that a buffer overflow in a banking application allows attackers to change their balance, but it does not allow them to change the transaction history. This kind of vulnerability would be bad, bud because the correct balance could be recalculated from the transaction history, it would not by as bad as full Turing Complete access.

  • I don't think this is exactly what turing-completeness is. The capabilities provided by an exploited application have only to do with what has been exploited, whereas turing-completeness deals specifically with processing capability (e.g. if you cannot use branch conditions, your exploit will lack any conditional execution behavior, regardless of what permissions the exploited process has).
    – forest
    Apr 20 '18 at 8:34
  • @forest Yes, I was trying to give as simple of an answer as possible. Your answer is more detailed but harder to understand. Apr 20 '18 at 8:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.