Hacker News Reader

Comment by DanWaterworth | Hacker News Reader

Hmmm, they didn't verify the correctness of the translator or CLR?

Verification does not need to be an all of nothing approach. Having one part of a system verified means that you are sure certain bugs can't appear on that code. So, there are less bugs in total, and when facing such a bug you know where you don't need to look. Otherwise you never end, you have to verify your code, the compiler, the operating system, the processor, quantum physics, the creator of the universe...

That's not quite true. You can't make any assertions about the behaviour of the system if only one part of it is verified.

The way to verify the entire system is not to verify that quantum physics works; that doesn't help. Instead you have to assume that the logic gates you are using are deterministic which is impossible to prove. Then you work up from there.

Despite this, I do agree that having part of the system verified is better than having none of it verified.

If you verify the correctness of the CLR, by the same reasoning don't you have to verify the correctness of Windows as well?

If you verify the correctness of Windows, don't you have to verify the correctness of all the parts in the hardware stack?

Yes, I hadn't thought of that. The point is that proving part of a process correct without proving correct the entire stack, is no guarantee that it does anything like what it's supposed to.

But, if you don't even try to prove part of a process correct, it's almost certainly wrong. See the excellent work that John Regehr's group is doing related to compiler and optimization verification/testing (http://www.cs.utah.edu/~regehr/research/ ), much of which has been talked about here.

There are other folks who have successfully done formal verification of operating systems, device drivers, hardware design, etc. It's a big, hard problem, but we'll get to the "whole stack" eventually.

Reply on news.ycombinator.com