5 ms·

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

theFco 15y ago
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...
- DanWaterworth 15y ago
  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.
hamidpalo 15y ago
If you verify the correctness of the CLR, by the same reasoning don't you have to verify the correctness of Windows as well?
- DanWaterworth 15y ago
  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.
  - larsberg 15y ago
    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/ 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.
- CurtHagenlocher 15y ago
  If you verify the correctness of Windows, don't you have to verify the correctness of all the parts in the hardware stack?

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...

DanWaterworth 15y ago
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.

hamidpalo 15y ago

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

DanWaterworth 15y ago
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.
- larsberg 15y ago
  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/ 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.
CurtHagenlocher 15y ago
If you verify the correctness of Windows, don't you have to verify the correctness of all the parts in the hardware stack?