Comment by Taikonerd
4 days ago
> Moving theorem proving upstream into compilers, sandboxes, and the browser seems like the future
The way I saw this proposed, back in the 2000s: "proof-carrying code."[0]
The idea is: the compiler compiles the program, and simultaneously generates a proof that the program doesn't violate X, Y, or Z safety rules.
Later, the end-user downloads the program and the proof together, and the local execution environment (the browser, the OS itself, etc) verifies that proof.
The idea being: constructing proofs is hard and sometimes involves manual steps. But verifying a proof is easy and automatic. So do the slow, manual thing once, and the fast thing each time the program is downloaded.
Sounds a bit like Microsoft's Singularity project, though I don't know if they even used a proof system to ensure a program couldn't do bad stuff(TM). After verification they just let the program run in Ring 0 (kernel space) of the CPU to skip even the performance hit of the cpu's isolation.
I thought Singularity was just building an OS on a memory-safe language and runtime, C# and .NET.
The same thing Java tried to do with applets at the browser level.
I listened to an interview with one of the researchers. They had a component to verify "this binary will never allocate mem outside it's allowed area" and by statically verifying that they could enable high performance IPC. Also, that was the source for the decision to allow it to run on Ring 0. That's what stuck in my mind.
1 reply →