3 ms·
Absolutely, but if you ask them, they will tell you that they don't think their process could be done efficiently enough for general purpose software. More impo
by pron 10y ago
Absolutely, but if you ask them, they will tell you that they don't think their process could be done efficiently enough for general purpose software. More importantly: it shouldn't be. End-to-end verification is absolutely unnecessary for all but the most critical pieces of software. No one believes this can be done easily.
When doing software verification we must keep our eyes open, know that it is hard and why:
* There is no general solution
* The difficulty is not a result of code structure, organization or syntactic abstractions.
* The difficulty cannot be avoided with languages -- through totality or abstractions (although some aspects regarding local properties can certainly be aided by language design; see below).
* The difficulty cannot be modularized away.
* The main issue is the size of the state space.
So the main idea is reduction of the state space (and heuristic approaches -- like SAT solvers -- that allow us to tackle larger state spaces). For reduction of the state space to be useful we need to find properties that survive the abstraction and are still important (memory safety is a classic example). The more local the property, the greater the chance that it can survive reductions. Which local properties are important is an empirical question which must be studies.
As for the rest, it's up to careful design, use of simplified algorithms, a lot of grunt work, and a lot of experience, which often involves a manual reduction of the state space.