2008 Turing Award Winners Announced

The Association for Computing Machinery has announced the 2008 Turing Award Winners. Edmund M. Clarke, Allen Emerson, and Joseph Sifakis received the award for their work on an automated method for finding design errors in computer hardware and software. "Model Checking is a type of "formal verification" that analyzes the logic underlying a design, much as a mathematician uses a proof to determine that a theorem is correct. Far from hit or miss, Model Checking considers every possible state of a hardware or software design and determines if it is consistent with the designer's specifications. Clarke and Emerson originated the idea of Model Checking at Harvard in 1981. They developed a theoretical technique for determining whether an abstract model of a hardware or software design satisfies a formal specification, given as a formula in Temporal Logic, a notation for describing possible sequences of events. Moreover, when the system fails the specification, it could identify a counterexample to show the source of the problem. Numerous model checking systems have been implemented, such as Spin at Bell Labs."

Comments

Just moves the errors up one level

[hoggoth]

I took a Computer Science course on discrete logic with a professor who was very into "model checking". By the end of the course I finally understood that all we had done was move the logic and the source of errors from the computer program to the formal specification. The formal specification was just as rigorous and complex as a computer program. The program became little more than a different expression of the formal specifications, such that it would be possible not only to check that a program had no "errors" and followed the specification exactly, but it would also be possible to have an automated process translate the formal specification into a program directly. The professor proclaimed that we now had a system that could prove programs correct. I pointed out that we had not, we had only changed programming languages to a mathematical one instead of a more typical computer programming language.

Re:Just moves the errors up one level

[Deef]

Just because this is true (that program correctness proofs are themselves very complex) doesn't mean that the technique is without value. If you have such a formal specification for a program, you now have supposedly identically operating code written in two different languages, which can be checked against each other for errors, hopefully automatically.

Having a fully provable program like this is like having a test suite that checks 100% of the branches in your program. It can substantially reduce errors that otherwise might slip by due to having failed to write a test for various conditions.

Yes, every time you find a mismatch, you have to consider whether it is the program or the specification that is wrong. Still, the errors that you miss will be those for which the specification and the program are wrong in THE SAME WAY, which should be very uncommon.

Truly helpful for optimizations

[bunratty]

Your professor was correct. Yes, the computer can automatically write a program from the specification. On the other hand, it probably isn't very efficient. You could write a deviously clever program to produce the same output, and when others don't buy into the tricks you've used, you can prove conclusively that your program is 100% correct. The same technique can prove that the latest processor optimizations don't have bugs (think of the Pentium division problem).