Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Surprisingly Turing-Complete

gwern.net

Post reply on HN
Print view View original

11–20 of 50 posts

Re: Surprisingly Turing-Complete

#11

Post by codeflo »

jdsully wrote: post #8
codeflo wrote: post #4

Earlier quoted context omitted.

I’m not sure why that’s explicitly mentioned, I believe that for analyzing security, TC is a bit of an academic red herring. (Warning: not an expert.) There are two kinds of security implication to consider here I think. One, can certain input data cause a large usage of computing resources (processing time or memory)? Non-TC mechanisms have repeatedly failed this test: ZIP bombs and XML entity bombs are notorious ex…

Both can have exploits as you've shown, but you haven't addressed the difficulty of securing one or the other. Turing complete systems have a dramatically larger state space than non turing complete implementations and so at a fundamental level are more difficult to secure.

I simply don't think Turing completeness is the deciding factor in determining that difficulty. Hopefully someone can define this more clearly, but in my opinion, the issue is not abstract "state space", but implementation complexity and attack surface.

For example, it's a lot easier to write a secure Brainfuck interpreter (a very simple Turing complete language that can only access STDIN and STDOUT) than a program that securely extracts a ZIP file to disk.

Re: Surprisingly Turing-Complete

#12

Post by zokier »

> This matters because, if one is clever, it provides an escape hatch from system which is small, predictable, controllable, and secure, to one which could do anything. It’s hard enough to make a program do what it’s supposed to do without giving anyone in the world the ability to insert another program into your program, which can then interfere with or take over its host

I take issue with the statement that TC means that something could "do anything". It means it can theoretically compute anything, but Turing completeness does not in itself give access to any additional resources; being TC does not magically allow something to talk to internet or write to disk or spawn new processes, or possibly not even allocate new memory. Computers do so much more than just compute; TC might be the first step towards being able to "do anything" but it certainly is not the final step.

From security point of view, what TC can (but not necessarily!) is open the host to denial of service by excessive resource consumption, or by non-terminating program. But as another comment noted, also non-TC systems can consume impractically large amounts of resources even if their resource consumption is not theoretically unbounded (as it is afaik with Turing machines).

Re: Surprisingly Turing-Complete

#13

Post by zokier »

zokier wrote: post #12

> This matters because, if one is clever, it provides an escape hatch from system which is small, predictable, controllable, and secure, to one which could do anything . It’s hard enough to make a program do what it’s supposed to do without giving anyone in the world the ability to insert another program into your program, which can then interfere with or take over its host I take issue with the statement that TC mea…

I do want to add (as my parent comment was bit negative) that I do think non-TC programming is an area that deserves more research, as is the research around better characterizing TC programs (http://raml.co/ being example of that)

Re: Surprisingly Turing-Complete

#14

Post by zokier »

saagarjha wrote: post #10
masklinn wrote: post #5

Earlier quoted context omitted.

Also it at least implies a guaranteed resource leak / DOS capability, which is a problem though it may or may not be considered a security issue.

Well, that depends; you can slap a rlimit on a process and it will no longer DOS you, even if it's executing Turing complete code. It does mean that inside the Turing machine you can't really apply protections, but from the outside a Turing-complete language cannot magically escape its sandbox unless you give (or accidentally include) it a tool to do so.

Unless I'm completely off my mark, any resource limited system is not true universal Turing machine in the theoretical sense. So depending on your level of pedantry, TC can mean guaranteed DoS.

Re: Surprisingly Turing-Complete

#15

Post by saagarjha »

woodruffw wrote: post #7
greesil wrote: post #2

Does finding weird and unexpected ways to do computation always imply a security risk?

I do research in this space professionally. The answer is not always, but sometimes: discovering unintended states or transitions in the execution contract of a program is a common building block for exploits. However, proving that the execution contract of a program can be coerced into representing computations in a TC language doesn't necessarily prove that you can do anything interesting. Complex formats like PDF…

Just a heads up: I think the second post has a typo; the code has named "new_item" but is referred to as "item" throughout. (I'm also not sure I understand the safety added by dynamic_cast.)

Re: Surprisingly Turing-Complete

#16

Post by joe_the_user »

"Peano arithmetic: addition & multiplication on natural numbers is enough to be TC;"

My head swims when the situation is described with this level of vagueness. I mean, sure the task of proving a theorem using the modern version of the Peano postulates is undeciable and so I'd assume a map from theorems in the Peano system to proofs of theorems would be Turing complete.

But a computation system based on calculating the values of simple arithmetic expressions isn't Turing complete. An express involving just adding and multiplying constant integer values will terminate.

Re: Surprisingly Turing-Complete

#19

Post by tdullien »

zokier wrote: post #12

> This matters because, if one is clever, it provides an escape hatch from system which is small, predictable, controllable, and secure, to one which could do anything . It’s hard enough to make a program do what it’s supposed to do without giving anyone in the world the ability to insert another program into your program, which can then interfere with or take over its host I take issue with the statement that TC mea…

Author of one of the cited papers here. The author of the post falls into a common misconception of the weird machine literature (which led me to write my paper): conflating TC (the ability to compute any function worth computing) with the ability to transition the victim machine into states that should be unreachable via paths that should not exist (“weird machine programming”). It is a bit unfortunate that this misunderstanding is pervasive in early WM papers :-/ - this ensures perpetuation of the misunderstanding.

Re: Surprisingly Turing-Complete

#20

Post by mattkrause »

zokier wrote: post #14
saagarjha wrote: post #10

Earlier quoted context omitted.

Well, that depends; you can slap a rlimit on a process and it will no longer DOS you, even if it's executing Turing complete code. It does mean that inside the Turing machine you can't really apply protections, but from the outside a Turing-complete language cannot magically escape its sandbox unless you give (or accidentally include) it a tool to do so.

Unless I'm completely off my mark, any resource limited system is not true universal Turing machine in the theoretical sense. So depending on your level of pedantry, TC can mean guaranteed DoS.

But...that's your whole computer too then.
Post reply on HN