4 ms·
This looks very interesting, some of the application areas sound really useful. One thing struck me: "It is written in C++ and comprises about 152,000 SLOC."
by mpweiher 8y ago
This looks very interesting, some of the application areas sound really useful.
One thing struck me:
"It is written in C++ and comprises about 152,000 SLOC."
OK, so how do I trust the results of this theorem prover? I can't find it right now, but I remember a talk by someone from Google who is/was also on the C++ standards committee saying that they have probably the best C++ programmers in the world, and nobody there can write code that is actually correct according to the standard, IIRC particularly but not limited to UB.
While I am generally fine with testing for most applications, something that says it provides proofs probably needs to be held to a higher standard. Or we call it a "theorem demonstrator"?
- nurettin 8y agoDo you mean "is it tested?" if so, I can see some results in table 1. Or do you mean "too big, therefore prone to UB, therefore not usable"?
- UncleEntity 8y agoBefore <safe_language_of_the_day> came out people managed to shoot rockets to the moon...
- mpweiher 8y agoUB exploitation is not about <safe_language_of_the_day>, C compilers used to be a lot saner than they are now. We shot people to the moon long, long before that change happened. See https://news.ycombinator.com/item?id=19659555 https://news.ycombinator.com/item?id=19659555
- profquail 8y agoWhat Vampire and similar “automated theorem provers” are doing is searching for a proof of some logical statement (that you specify). That proof search is a really tough problem, so there’s a ton of research that goes into finding ways of speeding up the search e.g. through novel data structures. Proof verification —- the process of verifying the correctness of some claimed proof —- is much faster.
- pfdietz 8y agoIf the prover provides a written proof, then verifying that the proof (of the particular theorem) is correct is a much easier problem.
- ghettoimp 8y agoThere's a tremendous amount of work that's been done on trustworthy theorem provers (see LCF, HOL, HOL Light, Milawa, ...), verified SAT solving and SMT solving, proof-producing first-order solvers, etc. All of this is cool and interesting. But from an industry perspective, there's plenty to like about plain old unverified C/C++ solvers and verification tools. They might crash sometimes, and they might occasionally have a soundness problem. But the odds that (1) your prover has a bug and (2) you will accidentally exploit that bug to "prove" something that isn't true are low. To argue by analogy: plenty of people use unverified compilers, and of course these do have bugs. Even so, when your program isn't doing what you expect, it's still almost always a bug with your own code.
- pfdietz 8y agoSome on the parts of some verified compilers are not "really" verified, in that there is no proof they always work. Rather, what is proved is that IF the compiler successfully compiles the program, THEN the result is correct. This can be easier, because it only requires that the compiler be able to provide a checkable certificate that its output is correct. Consider a register allocator that uses graph coloring. In this case, the compiler just needs to check that the coloring that is produced is really a coloring: that it uses k colors, and that no two adjacent nodes in the associated graph are assigned the same color. This checking routine must be proved correct, but that's an easier task. For a theorem prover to be verified in the same way, it just needs to produce an explicit proof, and then have a proof checker that is proved correct. The theorem prover itself, the part that produces the proof, doesn't have to be shown to always work (and indeed it won't, since it will very often time out.)