HE SETI@home program, the distributed computing project
that harnesses the power of personal computers to look for signs of
extraterrestrial intelligence, signed up its three millionth user
last week. SETI, which began in 1999, has quickly become the most
popular public computing project of all time.
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
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
"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
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