Slashdot Mirror
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."
Link is a malicious site, don't click. Shock site with malicious jacascript.
this is my sig
I think even most slashdotters could get an award for passing the Turing Test! (In all seriousness, congratulations to the winners - I haven't read the details yet, but it's quite an accomplishment.)
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.
At least DDJ isn't somebody's blog, but why not link directly to ACM's press release?
In The Slashdot Universe, "model checking" is all about logic analysis.
Despite the fact that the models we'd much rather be checking are all from Playboy/Hustler etc.
Surely we can get together enough of a crowd to award a prize for that?
Visit CryptoGnome in his home.
I think the work of Alexander Stepanov and David Musser in Generic Programming deserves a Turing award.
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.
- For the complete works of Shakespeare: cat
...can they determine whether my program will halt or not?
Causation can cause correlation
Model checking surely has it's merits, but how are you going to check the model for errors? If I have learned one thing writing software, it is that there is a difference between what people want, and what people say they want. And there is, and never will be, no software that can check if those two are the same. Actually, I'm beginning to think there might be a lot to be gained if computer scientists team up with psychologists to get better specifications out of customers.
PS: Good news, guys: psychology has lots of female students, so we might solve two problems in one blow.
"It's too bad that stupidity isn't painful." - Anton LaVey
Then why is the article titled 2007 Turing Award Winners Announced?
.... Did he flunk you?
Seriously, I had the same questions about formal, mathematical specifications when I learned of them. In my own experience (mostly business software), most re-work in software comes from a mismatch with the functional specification, or because of stuff that was left out of the functional spec but should have been in there. There are still actual programming or logic errors, but improved testing methodes and test functions of development frameworks have helped catch those bugs ever earlier in the development cycle.
But perhaps formal methods have their use for certain kinds of software.
If construction was anything like programming, an incorrectly fitted lock would bring down the entire building...
Fabio Somenzi at the University of Colorado contributes to an open source tool to perform model checking called VIS (Verification Interacting with Synthesis) available at: http://vlsi.colorado.edu/~vis/. I recommend anyone interested in this to check it out. It can perform model checking on Verilog modules directly.
I hope this will help push the use of formal methods, particularly in software development. There is no way that software development can be carried out in the massively distributed / multi-core era using the test-and-tweak, black magic approach that has so far dominated software creation and that has led to the big mess that we are in.
I was a PhD student of Ed, so great news for being at a "Turing award distance" 1. The model checking technique has indeed come a long way since its inception in 1981. It is more successful in hardware verification, then in software verification, so much so that most chip makers use it in one form or another. To those who say that the specification becomes as complex as the original program itself, there is some truth to that. However, one can also start with simple specifications, like After a request is made to a bus arbiter, it is always granted (within a few cycles, or eventually), or that there is no deadlock, etc. These are simple specifications, that can be "model checked". Moreover, people have developed sugar coating around mathematical languages used for writing the specs, and for analyzing specs themselves, etc. etc. There are techniques such as "equivalence checking", which can be thought of as a special case of model checking, where two designs need to proven equivalent to each other (say one version of RTL v/s a low power version of the same RTL). In this case, the specs become really simple (like which inputs and outputs corresponds between the two designs, and the relative timings).
:)
PS: Too lazy to create a slashdot account, so posting as an AC, besides, what's there in a name.
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).
What a fool believes, he sees, no wise man has the power to reason away.
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 unjust law is no law at all. - St. Augustine
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.
I have been hearing about formal verification for hardware design for the last 10 years and at some point I had to opportunity to do minor work on one of the formal verification products that my company produces. The technology is really interesting and contrary the the uninformed opinion of other slashdotters in this thread, it delivers tangible results and provides a clear advantage over classic verification techniques (vector testing, testbenches and so for).
It took a long time but a lot of the major design houses (Intel, PMC sierra, Freescale, ST micro, IBM and such), now use a form or another of formal verification during their design cycle. It has been a silent revolution, but be assured that many modern microchips have been verified this way.
Perhaps some day we could have a succesful formal verification product for software (After all, Verilog and VHDL could be seen as programming languages no?). In the meantime, it has proven its worth on the hardware side. Congratulations are due to these pioneers.
That said, you do have a point that formulating the models is not justified for a lot of routine code. Furthermore, in practice, as I understand it, in many application domains model checking is still computationally infeasible despite the work done on tackling state explosion.
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
fking jackass. DO NOT click this link!
A set of awards to recognize individual and professional achievements in Java, .NET and Rich Web is being organized alongside a Developer Summit in Bangalore later this year. The awards will honor "product and innovation excellence of the hundreds of software products and tools that aid developer productivity, across 12 different categories. The selection criteria applied by an international stature panel places emphasis on functionality, usability, innovation excellence, bleeding-edge quotient, and feedback from the developer ecosystem." Seems like a transparent process; you can nominate your selection here http://developersummit.com/awards.html#nominate.