CIRCUITS

The Search for E.T. Yields Earthly Cheats

By J. D. BIERSDORFER (NYT) 862 words

But what may appear to be the search for E. T. phoning home has sometimes turned out to be the signals of people cheating the project by falsifying results. Unfortunately for the dishonest, Philippe Golle and Ilya Mironov, both doctoral students in the computer science department at Stanford University, have come up with a set of security schemes that can help thwart those trying to claim computing work that they did not actually complete.

''It is worth bearing in mind that it takes only one talented or lucky hacker to potentially ruin a distributed computation,'' Mr. Golle wrote in an e-mail message.

In their recent paper, ''Uncheatable Distributed Computations,'' Mr. Golle and Mr. Mironov explain how to verify that the work has been done, by inserting special checkpoints, or ''ringers,'' into a unit of distributed data. If the data is returned to the sender without the purposely planted material among the results, the organization knows the data was not processed and the user is trying to cheat.

The idea that someone might cheat SETI@home is almost as shocking as the actual discovery of little green men would be. SETI@home is a typical example of a large-scale, Internet-based distributed computing project: users donate their computers' spare processing time by installing software to crunch data from Arecibo Radio Observatory and return the results to the sender.

The SETI@home people were well aware that some participants might cheat, whether by tampering with the data file they were given to process or hacking the program's settings. Although fewer than 1 percent of the work units appear to have been tampered with, Dr. David Anderson, the project coordinator for SETI@home, estimated that there had been some months during the project when half of its resources were devoted to smoking out cheaters.

''What we ended up doing,'' Dr. Anderson said, ''for a variety of reasons, is to process each piece of data several times and wait until all the results get back and compare them.''

The SETI project relies on unpaid volunteers; the cheaters seem motivated purely by a desire to get a high user ranking on a project Web page. Dr. Anderson said it was fairly easy to reject work submitted by cheaters and to cancel their SETI@home accounts, even though the cheaters could get other accounts.

The potential for cheating is increasingly worrisome as commercial distributed computing ventures that offer cash or credit to participants, like Ubero (www.ubero.net), become more commonplace.

''As soon as you offer any kind of incentive, you will invite cheating,'' said Armin Lenz, a former executive at a commercial distributed computing company who is familiar with the need for security in online projects. ''Be it stats, money or giveaways -- it is just human nature to try to get things the easy way.''

In the case of SETI@home, a bigger concern is not that the data unit returned by a user was completed or not, but that the result returned was accurate and free of incorrect results from tampering or faulty user hardware. ''The challenge of being absolutely confident that that result is the output of that program and not something else is really, really hard,'' Dr. Anderson said. ''The stuff that those guys from Stanford have done -- it doesn't exactly solve that problem, but it's a a way of verifying that at least their computer did all the work it was supposed to do. It still doesn't guarantee that the answer they give you back is correct.''

Along with Stuart Stubblebine, a vice president at CertCo Inc., an online security firm, Mr. Golle has also written a paper called ''Distributed Computing With Payout'' that complements his work with Mr. Mironov and discusses methods to streamline redundant computing for those who do not have a surplus of resources.

''The trick is that while most tasks are only ever assigned once in our scheme, some tasks are assigned twice or more, so that it is never possible for a participant to determine when it is safe to cheat,'' Mr. Golle explained. (For those wanting to read them, both papers are available on the Web at crypto.stanford .edu\pgolle.)

While commercial distributed computing operations may want to incorporate the work of Mr. Golle, Mr. Mironov and Mr. Stubblebine into their security measures, at least SETI@home can rely on its millions of users to help cross-check results and make sure that any potential discoveries are really from authentic aliens, not the ethically alienated.