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

WARNING: GNAA

[SirBudgington]

Link is a malicious site, don't click. Shock site with malicious jacascript.

What about those...

[joey_knisch]

Russian chat bots that convinced men not only that they were easy to score with females but needed a credit card up front.
http://science.slashdot.org/article.pl?sid=07/12/09/1356201

That has to be worth some kind of reward.

Re:A Dubious Prize

[Anonymous Coward]

That's interesting BalorTFL. Why do you think that?

Primary Source

[jdschulteis]

At least DDJ isn't somebody's blog, but why not link directly to ACM's press release?

Re:A Dubious Prize

[Anonymous Coward]

PARITY ERR ... 85362 ???
PARITY ERR ... 16376 ???
PARITY ERR ... 56721 ???
PARITY ERR ... 23423 ???
PARITY ERR ... RECOVERED
PARITY

HELLO BigJClark, MY NAME IS DOCTOR SBAITSO.

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

[Bozdune]

This is precisely the problem with such ideas. As you said, if a program is sufficiently rigorously specified that an automated proof-of-correctness can be generated, then the specification of the program is obviously complex enough to require that it, too, must undergo testing to ensure that it is correct, and so on. We might end up with 2 = 2, but that doesn't help much if we wanted 3.

The DoD has funded these efforts heavily since the 1970's, and computer science graduate students have been all over them for as long as I can remember. I've read way too many dull papers on the topic, as one amateur modern algebraist after another discovers the wonders of Hoare and rushes into print with his or her "unique" twist, all to the end of starting yet another unremarkable academic career.

Of course, the illusion of "perfect" software never fails to amuse me, since I remember an Interdata 32 overheating in the lab and making serious fixed point arithmetic errors. Sort of grounds one in reality, doesn't it, when the machine can't add. Sure glad the program was declared "correct," though.

Re:Just moves the errors up one level

[Picolino]

The purpose of model checking is rarely to specify the whole behavior of the program, but to ensure that some condition are always true or false. Such condition can be the absence of buffer overflow ... relatively easy to formulate, hard to discover ...

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.

Re:Just moves the errors up one level

[El Cabri]

The formal specification for, say, liveness of an interlocking system is a one-liner in a typical temporal logic notation, and you can apply it without significant modification to any number of different implementations, of any number of different applications, whatever their complexity. This is leverage : you put your trust in a very short piece of "code" (the formal spec for your property) and in the tool itself (which is the same kind of trust you put in your compiler), and in return you get trust on a huge complicated piece of software that you wrote. Then you break down your testing into many, independent property checks that all validate one aspect of one big piece of inter-mangled software. That's hugely powerful.

I hope your prof failed you.

Re:Just moves the errors up one level

[rayadoCanyon]

Once I went to a talk about applications of model checking to the verification of software. A programmer was constantly changing a state-based algorithm for call setup in a telephone switch, and was having trouble keeping it correct. Enter model checking. Two people wrote temporal specifications of call setup, and every night or so, they'd grind the model checker on the latest version of the code. No, that didn't prove the code was correct, but it did catch an enormous number of bugs in a tricky piece of concurrent code.

Oh. The programmer was Ken Thompson. The people applying the model checker were Gerard Holzmann (the designer of SPIN) and Margaret Smith.

I'm not saying the technology is applicable everywhere, but you gotta give Clarke, Emerson, and Sifakis a lot of credit for opening a good door.

Re:Guarding the guard

[El Cabri]

You're not expected to model the full behavior of your program. Model checking is useful for testing individual properties such as bounds on ressource allocation, non-deadlock of thread synchronization, or security-related invariants.

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).

I dropped Emerson's class

[omnirealm]

I signed up for Emerson's graduate course on model checking and reactive systems a couple of years back. The first day of class, he walked in 15 minutes late and said something like, "Welcome to my class. No homework or tests. Everyone gets an 'A'. Let's see what kind of papers we can come up with." He then dived right into some intense theory as if he were casually picking up a conversation he left off the semester before. I spent the next few hours feeling like total deadweight (several other grad students just sat there silent the whole time, with expressions on their faces like deer caught in headlights). I wound up just dropping the class; it took me another year of grad courses to get all the background theory I needed to just keep pace, and I hate wasting time, even for an easy 'A'. Too bad I graduated just before he taught his class again; I would have given it another shot before leaving UT Austin.

An open source model checker for Java

[martinde]

NASA released an open source model checker for Java called JPF. It's a JVM implemented in Java that can do model checking on "generic" Java apps, finding deadlocks and things like that.