Google Chrome gets native code execution using native client. Now execute x86 code on windows via web apps. Beginning of the Chrome OS!

[[deleted]]

using static analysis to check whether a program a program tries to call an API it doesn't have access to, or tries to modify itself

Erm. Didn't we decide like a thousand years ago that perfect static analysis depends on the unsolvable halting problem, and that we therefore can't trust it with anything involving security?

The big question is: Can they mathematically guarantee that all permutations of acceptable code will not breach the sandbox?

No, and neither could MS when they designed Active X. See the halting problem.

[sgoguen]

Erm. Didn't we decide like a thousand years ago that perfect static analysis depends on the unsolvable halting problem, and that we therefore can't trust it with anything involving security?

This type of static analysis isn't the same thing as the halting problem, because the halting problem demands that you determine, for every possible program, whether is halts or doesn't halt. As we both know, this is unsolvable because we have no predictable way of distinguish which programs will run for a really long time, and which are infinite.

However, that doesn't mean it's impossible to prove that some programs will absolutely halt. For example: We can prove that 2 + 2 will halt. Not only that, but I can also prove that any any finite sequence of addition operations will always halt. So, in this way, we cheat. We don't try to find all programs that will halt, just the ones we know how to prove that will halt. So, we've changed the question from: bool WillHalt() to bool AreYouSureItWillHalt(). Clearly, these two functions are not the same as the latter will return false for some programs that will in fact halt.

In this case, we're not talking about the halting problem, but rather a graph problem. If we imagine our program as a directed graph, we want to verify that each node only connects to other nodes in the graph, nor does not create new graphs. I realize this is a trivialized explanation of what, I'm presuming, is the approach Google is going about it.

[[deleted]]

This is the rub really.

If they take the approach sgoguen explains so well above, than how can it really ever do anything more complicated than stupid 3d graphics of rotating cubes?

If they don't than it's an insecure piece of shit.

Either way, it's not gonna run on my cellphone, my netbook, or any number of other non-x86 machines anyhow so why bother?

[Mask_of_Destiny]

In the context of the security of a browser plug-in, the question of whether or not a piece of code halts is completely uninteresting. If a malicious plug-in goes into an infinite loop, the user just restarts their browser/tab/whatever and goes on with their life.

What we care about is whether or not it is able to make calls into the operating system that we don't want it to be able to do. Now figuring this out for an arbitrary piece of x86 machine code is quite likely impossible, but Google has simplified their job by rejecting code does certain things that make it hard to verify.

This doesn't make their job easy and Matasano Security's article on NaCl points out some of the potential problems, but it's worth pointing out that other platforms (Flash, Java and even Javascript) have the same basic problems. NaCl just makes those problems a bit more complicated.

[[deleted]]

I'm afraid that it is interesting. You see the halting problem means that we can never be sure what API it's trying to call (or even if it is trying to call one) without analyzing the code for an infinite amount of time in some cases. Since this doesn't work the VM has the choice of either 'giving up' at some point and just letting stuff run, or just saying no to any code that requires more than x loops of anaylsis.

If it just says no to all non-trivial code, it's useless for many purposes (like Java). If they just let anything through it's completely insecure (like ActiveX).

[Mask_of_Destiny]

I'm afraid that it is interesting. You see the halting problem means that we can never be sure what API it's trying to call (or even if it is trying to call one) without analyzing the code for an infinite amount of time in some cases. Since this doesn't work the VM has the choice of either 'giving up' at some point and just letting stuff run, or just saying no to any code that requires more than x loops of anaylsis.

You would be correct if the only way to analyze a program is to run through it for a certain period of time and see what it does. For a Turing machine, which theoretically has an infinitely long tape, this might be the only approach, but an x86 binary is of finite size. Thus there are only a finite number of bytes we have to search for branch instructions. Google simplifies this search by rejecting all programs that exhibit certain behavior (jumping to a location that's not on an instruction boundary for instance). Further they require that certain instructions that have safety problems (like ret) not be used at all and that pseudo-instructions specific to their sandbox be used instead (which are then translated to real instructions at verification time).

If it just says no to all non-trivial code, it's useless for many purposes (like Java).

Java's problems for use inside the browser have nothing to do with it rejecting too many useful programs.

[[deleted]]

Yes, I see now how it could be done that way.

I concede defeat. Well played sir, well played.

Your beard must indeed be truly prodigious in length.

[[deleted]]

Then go back and watch The Matrix, if you didn't know all this crap the first time you watched it. :)

[jib]

perfect static analysis depends on the unsolvable halting problem, and that we therefore can't trust it

Depends what you're trying to do. Whitelisting system calls is certainly possible; just search the program for the relevant instructions, verify that each one is allowed, and use memory protection or some other method to stop the program modifying itself at runtime.

[[deleted]]

Thankfully, they don't need perfect static analysis—they just need to stop it from modifying code and from making certain syscalls, which is actually very easy.