It is definitely in theory possible to fix all the bugs. It is even in theory possible to make a box that will autonomously [1] fix all the bugs. The box consists of a theorem statement saying “attackers cannot breach the system”, a proof checker, a sufficiently-but-not-unboundedly good code & proof model, and the instruction to prove the theorem statement while minimizing behavioral change, finding and fixing all bugs required to do this along the way. I am working on this box. The biggest question in my mind is whether we can get the capabilities in the right order to get this box in time.
- ↩︎
Provided the box has the access to update the software, we have an adequate model of the hardware, the attacker model is software only and relatively standard (e.g., attacker is purely remote and can send and receive network packets), and we have a weak proxy for attacker-controlled action (something that never happens under normal operation, that we expect any attacker could in theory do, e.g., wipe the hard drive, send secret files directly over the network)
I agree with Adam that you are overstating the difficulty of spec elicitation. If you carve reality at the right points, specification is easy. To take a currently-talked-about example, you may not know how to spec Linux, you may not know the full spec of a hypervisor, it’s pretty easy to spec an inescapable sandbox (“no program in the sandbox can write to any file outside of it”). If you have a model of the machine, this makes your spec of Linux, KVM, virtualization, etc, internal. While this spec is useless in isolation, proving that a small set of patches to Linux results in satisfaction of this specification (or proving that you have this property and also that you agree with the behavior of Linux on almost all inputs) is pretty strong. Alas, nobody has released a full machine-readable model of any hardware used in production yet.
Some minor comments on your FM tools list:
This one is key.
Verified compilers are just a cost-saving (proof-sharing) technique for binary-level verification.
If we are verifying everything, why not just verify that we have caught all bugs that could ever be caught by fuzzing?
Adding the obvious omission: MetaRocq