UCSD team's effort in DARPA's Shredder Challenge derailed by sabotage
By Chris Palmer
San Diego, Calif., December 8, 2011 -- After a strong start in the U.S. Defense Department’s $50,000 ‘Shredder Challenge’, researchers at the University of California, San Diego (UCSD) fell short of taking the top prize, in part because of an anonymous attack on the team’s online “crowdsourcing” approach to solving the challenge.
|
The public competition -- which was hosted by the Pentagon’s research and development branch, the Defense Advanced Research Projects Agency (DARPA) -- involved piecing together roughly 10,000 pieces from different documents that had been cross-shredded.
On Dec. 2, the Pentagon announced that the San Francisco-based team “All Your Shreds Are Belong to U.S.” completed the challenge 33 days after it began and two days before the contest’s deadline. The team was able to answer a series of questions about coded messages printed on several shredded documents that they reconstructed using a combination of custom-built, computer-vision software and intensive human-based labor to verify their software’s puzzle solutions.
The UC San Diego team, led by Computer Science and Engineering (CSE) research scientist Manuel Cebrian, placed sixth in the competition, receiving an ‘honorable mention’ from DARPA. The team, which included CSE graduate students Andrea Vattani, Karyn Benson, Wilson Lian and Dan Ricketts, completed four of the five puzzles and made significant progress on the 6,000-piece fifth and final puzzle before the challenge ended.
UCSD’s team took a crowdsourcing approach to solving the puzzles and set up an online program that enlisted the help of more than 3,600 people from all over the world who worked around the clock to painstakingly piece together the shredded elements.
Though the UCSD team did not hear about the challenge until two weeks after the competition started, it made it into the top three (out of more than 9,000 teams) only five days after entering the contest. The team’s position on the leader board was updated on the DARPA website on Nov. 20.
“That’s when the attacks started,” said Cebrian, who is also associated with the UCSD division of the California Institute for Telecommunications and Information Technology (Calit2).
The Sabotage
On the night of Nov. 20, at least one individual who signed up as a crowdsourcing volunteer sabotaged the UCSD team’s puzzles by removing pieces that had been successfully matched to neighboring pieces and piling them up on top of other pieces.
A similar act of sabotage occurred the next night. “The attacks always occurred overnight,” said Cebrian.
The following night, a third attack occurred, this time with the saboteur pushing pieces off the UCSD team’s virtual puzzle board.
UCSD logged every move of the puzzle pieces and had no trouble ‘rolling back’ the sabotaged puzzles. However, to thwart future attacks, they had to implement a reputation system to verify the propriety of their volunteers. This system hindered the progress that new users could make in the challenge. For the final puzzle, the UCSD team was forced to limit volunteer participation to a subset of the top 20 performers from the first four puzzles.
The most dramatic consequence, however, was the disruption to the morale of the volunteers.
“People just panicked, and confidence is something hard to restore in an online setting,” said Cebrian.
By the time the “All Your Shreds Are Belong to U.S.” team had completed the challenge, the UCSD team had discovered one of the three clues in the fifth puzzle.
“I am fully confident that we could have solved the challenge in one week had we not been sabotaged,” said Cebrian.
The Saboteur
More than 3,600 people from around the world volunteered to help UCSD reconstruct a series of shredded doucuments, each of which contained clues that would help solve an overarching puzzle.
On Nov. 24, one day after the third attack, Cebrian received an email from someone using the name ‘ucsdsaboteur’. The sender of the email accurately recounted many details of the attacks and pointed out the security weaknesses in the website the UCSD team set up for volunteers to work on the puzzles:
“Anyways [sic]...I thoroughly enjoyed myself, and hope you all learned something about crowd sourcing and will give a bit more thought to security when considering your next implementation.”
The saboteur ended the email by revealing his or her involvement in the Shredder Challenge, suggesting that the contest should be about computer-vision algorithms, not crowdsourcing:
“As for my motivation, I too am working on the puzzle and personally feel that crowd sourcing is basically cheating (and I'm not the only one that feels this way). Sure, if you get enough people together and working on it they will be able to solve nearly any puzzle. It's only a matter of time, however for what should be a programming challenge about computer vision algorithms, crowd sourcing really just seems like a brute force and ugly plan of attack, even if it is effective (which I guess remains to be seen yet...). With all that said, good luck to you, and may all your shreds belong to us.”
“Our reconstructed history of the attacks matched perfectly what the saboteur described in his or her email,” said Cebrian. He added that though his team will continue to investigate the nature of the sabotage, “We will probably never know the true story about this.”
At the time of the attacks, the “All Your Shreds Are Belong to U.S.” team was ranked number one in the contest and was one of only two teams to employ computer-vision algorithms, the other being Seattle-based “Wasabi”.
Otavio Good, team leader for “All Your Shreds Are Belong to U.S.”, denies any involvement of his team in the sabotage. “To the best of my knowledge, no one on my team was responsible,” said Good. “If we were taking credit before [in the email to Cebrian], why would we deny it now?”
Added Good about the sabotage, “Since the UCSD team used an open platform for its crowdsourcing, of course we discussed it, but everyone agreed not to do it.” He went on to say that the sabotage was likely perpetrated by someone on the internet who saw their “catchy team name and the fact we were in first place” and decided to have fun by causing trouble.
Cebrian noted the paradox in the saboteur’s email about the attacks. “If you really believe in the effectiveness of your [computer vision] technology, why would you attempt to disrupt a team engaged in crowdsourcing?”
The Birth of ‘Competitive Crowdsourcing’
Despite the sabotage, Cebrian remains magnanimous about the experience, acknowledging that there were no provisions in the challenge rules about interfering with other teams’ efforts to solve the puzzles.
“It is a great day for network science, as this is one of the most important crowdsourcing experiments ever done,” said Cebrian about the challenge and his team’s participation. “What happened actually reflects a real-life scenario in that, in a tactical situation, you have to deal with all types of challenges.”
The UCSD team recognizes that the sabotage of their puzzles is perhaps the most important piece of the scientific knowledge gained from this challenge.
“One of the lessons we learned about crowdsourcing is that people can be malicious to a much higher level of sophistication and coordination than we suspected,” said Cebrian who sees the type of sabotage that occurred as giving birth to a new field of network science that he dubs "competitive crowdsourcing".
Cebrian and his team are grateful to DARPA for hosting the challenge and to the many volunteers who helped them with the challenge, noting that they were the only team who successfully used a crowdsourcing strategy to solve any of the puzzles.
Cebrian also noted that even though the winning solution was based primarily on computer-vision algorithms, the winning team relied heavily on human brainpower to complete the challenge: “I don’t think a fully automated approach can be used for this type of problem.”
Cebrian was a member of the MIT team that won DARPA’s last public challenge in 2009. That team also employed crowdsourcing techniques, coordinating thousands of volunteers to locate 10 large, red weather balloons at undisclosed locations across the U.S. in only nine hours.
The computer scientist views the Shredder Challenge as a much more difficult, and much more important, challenge than the balloon challenge. “The 2009 challenge taught us about the power of the Internet,” said Cebrian, “whereas the 2011 challenge taught us the limitations of the Internet.”
Cebrian and his collaborators are excited to analyze the enormous amount of data generated about their volunteers’ participation in solving the puzzles, as well as the sabotage that occurred, and plan to present their results and the lessons they have learned at network science conferences and in journal articles.
Media Contact: Tiffany Fox, tfox@ucsd.edu, (858) 246-0353
Scientific Contact: Manuel Cebrian, mcebrian@eng.ucsd.edu, (858) 534-6441
Media Contacts
Media Contact: Tiffany Fox, tfox@ucsd.edu, (858) 246-0353
Scientific Contact: Manuel Cebrian, mcebrian@eng.ucsd.edu, (858) 534-6441
Related Links
Related Articles
$50,000 to Solve the Most Complicated Puzzle Ever Attempted