3 ms·
Title is verifiably false. First, formal verification doesn't create anything. It only certifies code created by other means. Second, formal verification only
by ncmncm 7y ago
Title is verifiably false.
First, formal verification doesn't create anything. It only certifies code created by other means.
Second, formal verification only certifies that the software implements the machine-expressible details of the spec. It doesn't certify anything expressed only in English.
Finally, it doesn't and can't ever certify that the spec itself is correct or complete. Most bugs and security holes result from incorrect, incomplete, or inconsistent specs. (Any program satisfies an inconsistent spec, but inconsistent specs can at least be identified by formal means.) Very few specs can be formally expressed completely.
So, formal verification is useful, but neither creates hacker-proof code, nor ensures that code is hacker-proof.
- sterlind 7y agoThere are formal methods both for specs (e.g. TLA+ checked by TLC and TLAPS) and for implementations (e.g. ADA-Spark checked by GNAT). The spec can indeed be checked that invariants or liveness properties are honored. Some formal modeling tools for specs can actually extract implementations that satisfy the spec, though I think you're being nit-picky on the semantics of "create." Specs don't have to be English, you know. I write my specs for machines first and humans second.
- ncmncm 7y agoMay I take "I write my specs for machines" to mean that you simply omit the parts of the specification that are not expressible in the formalism at hand? A specification with parts deliberately omitted is deliberately incomplete. An implementation of a sufficiently incomplete specification may be formally verified to satisfy the spec without ensuring much of anything, although it may suffice to justify payment. This attitude is typical in formal specification.
- sterlind 7y agoNo, I didn't mean that. in my particular domain (a distributed systems library) I have a collection of specifications for things like commands, locks and collections, which are compact enough that I feel I can describe them fully. There has been one case where I had to simplify the model, which I consider a great failure, since that was the one time I had bugs appear that I didn't catch during model testing. Take the example of a reader/writer lock. I claim it's possible to completely define the spec of such a lock, so that any question about the intended behavior of the lock can be decided by the machine. Sure, it's a simple example, but my library is a collection of simple recipes. Do you disagree?
- ncmncm 7y agoI agree that you can usefully, formally specify certain behaviors by choosing to ignore, e.g., implementation details. There are a lot of implementation details: stack depth, instruction mix, power consumption, timing fluctuation, memory placement. Incorporate too many, and you lose clarity, even usability. But implementation details are often what hackers rely on. So, yes, formal modeling is useful, sometimes essential, but does not eliminate hackability. Overselling it does harm.
- kyboren 7y agoThat's not entirely true. Synthesis is a popular topic within the "formal verification" umbrella. I agree that proving the software satisfies some safety properties and is always consistent with some specification doesn't mean that a system is truly "hacker proof". However: 1. It's a step in the right direction, and something like a necessary condition but not a sufficient condition. 2. It's an attractive, succinct way to describe the value of formal methods and their potential (as the cited DeepSpec project intends to realize) to indeed make a truly hacker-proof system.
- ncmncm 7y agoIt's an attractive, succinct way to mislead people about the value of formal methods and their potential. Synthesis from specifications completely fails to address omissions and errors in the specifications, except insofar as they get translated to something that is more evidently wrong, or are revealed to be inconsistent.