3 ms·
Ah, but there's a difference between formal verification and programming languages. The problem of general formal verification (known in general as the model-ch
by pron 11y ago
Ah, but there's a difference between formal verification and programming languages. The problem of general formal verification (known in general as the model-checking problem[1], regardless of the approach used which could be model-theoretic or proof-theoretic) is literally the hardest problem in all of computer science. Any computational problem can be reduced in polynomial time to program verification (i.e. model checking). In fact, all NP-complete and PSPACE-complete problems are trivially reduced. Finding a general tractable solution (even if it includes human intelligence) is therefore a mathematical impossibility. The best we hope for is a solution that is applicable to programs people write. The question is then whether there is one well defined "class" of programs humans write to which an efficient algorithm (again -- even one involving humans in the loop) applies. So far results from decades of verification research show that this is not the case, and there are at least several such classes, but maybe the classes aren't general enough. If humans are part of the algorithm (e.g. interactive proofs, manual dependent types), the class might be wide, but our experience has shown that verifying programs in this way takes tremendous effort, even for small programs, and even when the programs are kept especially simple for the sake of verification. Even if there is a solution that is applicable to most (I'll settle for most) programs, it is so far nowhere in sight. Most efforts are directed at finding partial solutions for specific domains.
[1]: Called that because it is the problem of checking whether a given program is a satisfying theory -- i.e. a model -- for the given logical property.
- lmm 11y agoThat it's a hard problem doesn't necessarily mean we're approaching it wrong. Indeed the fact that it's mathematically proven to be hard offers some confidence that we might not be. Are there examples of cases where a system was very hard to verify with any one general technique, but much more practical to verify by using several domain-specific techniques and some kind of bridge between them (i.e. not simply coming up with a general approach for which the specialized techniques were, well, specializations - since as far as I can tell your quote is advocating for something different)?
- seanwilson 11y ago> Are there examples of cases where a system was very hard to verify with any one general technique, but much more practical to verify by using several domain-specific techniques and some kind of bridge between them I'm not sure what you mean by bridge but the halting problem comes to mind: the general case is impossible but you can prove common algorithms halt by showing they're structurally recursive (the recursive parameter always get smaller) or some metric always decreases on the recursive call (e.g. the sum of the length of two lists always gets smaller on the recursive call).
- lmm 11y ago> you can prove common algorithms halt by showing they're structurally recursive (the recursive parameter always get smaller) or some metric always decreases on the recursive call (e.g. the sum of the length of two lists always gets smaller on the recursive call) Right, but those are just special cases of the same technique - you can combined them by using dependent types to lift the list length to the type level and then this metric technique is just a special case of structural recursion.
- pron 11y agoDependent types are not a verification technique. They are just one way of encoding statements about your program (in intuitionistic logic). The technique to prove those statement are either manual or manually-assisted (e.g. Coq), or automated using various model-checking algorithms (Liquid types). Deciding to encode program properties in dependent types (e.g. Idris) or direct logic (e.g. Java+JML) doesn't make verification any easier or harder. It's just a form of stating the properties you wish to verify.
- lmm 11y agoSure. What I'm saying is that you can encode statements about values and statements about types the same way, by using dependent types, and once you do that then you can verify halting of metric-recursive functions using exactly the same approach that you use to verify halting of structurally-recursive functions. So proving halting using a combination of proofs that metric-recursive functions halt and proofs that structurally-recursive functions halt isn't an example of it being useful to use two different approaches for different parts of the proof of correctness of a program, and doesn't make the case for having multiple approaches to verification and bridges between them.