Re:What I suspect Google is up to with Native Client
by DarkShikari on Wednesday December 07, 2011 @12:10AM
(#3322556)
At first I thought this amounted to a claim that the halting problem had been solved,
That's not what the halting problem means! There is no rule that says you cannot prove a program is safe: the rule is only that you cannot prove any arbitrary program is safe. NaCl gets around that by adding checks to the code (bounds checks, etc) to anywhere that it can't prove is safe.
Re:What I suspect Google is up to with Native Client
by smosher on Wednesday December 07, 2011 @12:19AM
(#3322577)
Perfect static analysis is certainly halting-equivalent. What you're describing falls short of perfection, which is what I've suggested.
Re:What I suspect Google is up to with Native Client
by comex on Wednesday December 07, 2011 @01:05AM
(#3322699)
It's still Turing complete because it can perform arbitary computation; it just can't cause arbitrary behavior at the machine code level. (Indeed, making a VM that's both Turing complete and safe is not generally a hard problem - for example, most Brainfuck interpreters qualify. The hard problems are making safe interfaces to the rest of the system, and speed.)
Re:What I suspect Google is up to with Native Client
by jmesserly on Wednesday December 07, 2011 @12:13AM
(#3322563)
I don't know exactly what NaCL does, but the JVM/CLR verification is all about making sure you don't write over someone else's memory, jump to some arbitrary address, etc. Essentially the problem is: how do you run untrusted code in the same address space, without it getting all of your process's permissions.
More info here: http://en.wikipedia.org/wiki/Java_Virtual_Machine#Bytecode_v...
Re:What I suspect Google is up to with Native Client
by smosher on Wednesday December 07, 2011 @12:26AM
(#3322588)
Ah, thanks. I think I have a handle on the size and shape of it.
Re:What I suspect Google is up to with Native Client
by willvarfar on Wednesday December 07, 2011 @03:08AM
(#3322987)
Halting problem is literally that the program will halt. That's not provable, even if you offer it on rentacoder.com.
JVM bytecode, .NET CLR bytecode, NACL bytecode are all verified as containing no illegal API calls. That's completely different. And its completely possible.
Re:What I suspect Google is up to with Native Client
by djmdjm on Wednesday December 07, 2011 @01:46AM
(#3322813)
It doesn't have to solve the halting problem, just contain the code from interacting with the wider system except through tightly-defined interfaces. "does this code make any far jumps" is an answerable question when you can constrain the machine code generated and ban self-modifying code.
I am having a hard time with this. At first I thought this amounted to a claim that the halting problem had been solved, or else that Java and NaCl are not Turing complete. I'm guessing the problem is with the term "perfect." So something interesting must be going on or it wouldn't be worth mentioning. What's being verified? That the code can't execute data and won't call certain interrupts, or is something more interesting happening?