High-tech analysis of a 2011 DARPA Challenge shows why we can’t have nice things
Meet Adam. He’s a mid-level engineer at a mid-level software company in a cookie-cutter California office park. He can code a handful of languages, has a penchant for computer vision and enjoys soccer and skiing. In short, Adam has little to distinguish him from legions of other programmers in the Bay Area. Except that over a couple of nights in 2011, he stopped thousands of people from sharing in $50,000, nudged the American military in a new direction, and may have changed crowdsourcing forever.
This is the previously untold story of how and why Adam humbled some of the brightest brains in computer science, their years-long search to find him, and the researchers who now believe that the wisdom of the crowd might be nothing more than a seductive illusion.
To understand why Adam was able to make such an unwelcome impact, we must go back to 2009. Back then, the ability of crowdsourcing to crack big problems seemed unlimited. That was in large part due to DARPA’s Network Challenge, a competition organized by the Pentagon’s R&D agency to locate large balloons hidden in plain sight across the United States.
The task, declared “impossible” by one senior intelligence analyst, was actually solved in a matter of hours by a team of MIT students and scientists with the help of crowdsourcing and social networks. They developed a recursive incentive scheme that split the Challenge’s $40,000 prize money between the finders of each balloon, their recruiters, the people who recruited them, and so on. Over five thousand people joined MIT’s pyramid scheme, which DARPA later called “a clear demonstration of the efficacy of crowdsourcing.”
The high profile challenge spawned further contests, including DARPA’s follow-up Shredder Challenge, in 2011. The Shredder Challenge had clearer intelligence applications. Participants had to piece together documents sliced and diced using high-end shredding machines — the kind of evidence that military operatives might find at terrorist training camps. Five handwritten documents were shredded into thousands of tiny pieces half a centimeter long. The first puzzle had just a couple hundred shreds, the fiendish final one over 6,000. Images of these minuscule chads were posted online, and the first team to reconstruct the pages would win $50,000.
“If finding the balloons was a sprint, the Shredder Challenge was a marathon,” remembers Manuel Cebrian, who was part of MIT’s winning team in the earlier challenge and ready for a new adventure. “We had to get a crowd really, really engaged for weeks rather than hours.”
It would be the perfect test for Cebrian. The energetic computational social scientist divides his time between the University of Melbourne in Australia and MIT in Cambridge, his research focusing on how social networking can make it easier to find people and tackle real-world problems like global epidemics and disaster response.
For the Shredder Challenge, Cebrian turned to new collaborators: smart grad students at the University of California San Diego (UCSD) who wanted to repeat Cebrian’s success at MIT. They were researchers in crypto-analysis, game theory and network science. “My role was to be very enthusiastic and then get these people to do the difficult work,” Cebrian says with a laugh. The team swiftly settled on rewards similar to those in the Network Challenge. If it won, users would get $1 for each edge they matched correctly. The person who recruited them would receive 50 cents, and the person above that a quarter. Though the UCSD group was not the only one to use crowdsourcing, it was the only competitor planning a completely open platform, allowing anyone, anywhere, to join online.
But this time Cebrian would not be competing just against other crowds. Some of the 9,000 teams that signed up were using sophisticated algorithms to automatically match the myriad pieces with machine learning and computer vision. (Despite this being the world’s toughest jigsaw puzzle, a few people even tried to solve the puzzles manually. Tellingly, only 70 teams managed to complete even the easiest of the five puzzles).
To make matters worse, Cebrian’s group didn’t get going until two weeks after the competition started on October 27. They quickly developed a web interface and collaborative work space for the crowd to re-assemble the documents — essentially a giant virtual jigsaw mat. But they didn’t have time to construct digital defenses, such as verifying users’ identities or limiting their access to completed sections of the puzzle. “We were crossing our fingers, hoping we wouldn’t get sabotaged,” says Wilson Lian, the team’s security expert.
Trouble in the crowd
At first the hive mind functioned flawlessly. Cebrian’s winning history helped recruit over 3,600 users, who blasted effortlessly through the simpler puzzles. Individual players made errors, of course, but nearly 90 percent of those mistakes were fixed by others in the crowd in a matter of minutes. In just four days, the UCSD group had rebuilt the first three documents and was rated second overall. In late November DARPA updated its leader board to reflect UCSD’s meteoric progress — and that’s when their troubles began.
DARPA shredder challenge honorable mention submissions.
Overnight that night, and for the two following nights, saboteurs hiding in UCSD’s crowd went to work. At first, the attackers just scattered pieces that had already been correctly assembled, like a child petulantly trashing a half-finished jigsaw. Then the attacks became more sophisticated, exploiting bugs in the team’s code to pile hundreds of chads one on top of another, or moving important pieces far off the virtual mat where they couldn’t be seen.
An army of genuine users valiantly tried to repair the damage but the attackers seemed too numerous and too fast. Not once, but twice the group was forced to reset the puzzle to a previously saved configuration.
“Our first response was ‘Oh crap!’ Then we looked in the database for patterns of destruction, and rolled everything back to before that,” remembers Lian. As the attacks continued, the team tried blocking individual accounts they suspected of being malicious, and then whole IP addresses to contain the destruction. “I lost five kilos doing this Challenge,” says Cebrian. “I got really sick. We were working without sleep for days in a row.”
On November 24, an email from an anonymous Hushmail address landed in the team’s inbox. It taunted UCSD about the team’s security lapses, claimed that the sender had recruited his own horde of hackers from the notorious 4chan bulletin board, and revealed exactly how he had used proxy servers and virtual private networks (VPNs) to launch his attacks.
“I too am working on the puzzle and feel that crowdsourcing is basically cheating,” read the email. “For what should be a programming challenge about computer vision algorithms, crowdsourcing really just seems like a brute force and ugly plan of attack, even if it is effective (which I guess remains to be seen).” He signed off with the phrase “All Your Shreds are Belong to U.S.”
That was the jokey name of the team then in first place. Its leader, an experienced coder and inventor named Otavio Good, vehemently denied responsibility for the attacks. And the San Francisco-based Shreds team did seem legit: it was using custom computer vision algorithms to solve the puzzles, with humans double-checking the software’s work.
But paranoia reigned at UCSD. “We looked at the Shreds team members and wondered, is this person capable of sabotage? Or this one?” says Lian. He even tried to geo-locate their IP addresses to see where they lived. Nothing led back to the attacker. Meanwhile, the team was desperately trying to shut the stable door: changing the interface to permit only one move every 30 seconds, preventing pieces from being stackable, and making registration mandatory. There was also a plan to develop a reputation system, where only the best performing users would be allowed to contribute to the puzzle. Nothing helped.
Hundreds of users melted away before the team’s eyes, and those that remained were disorganized and demoralized. Not a single new productive player joined
the UCSD effort following the attacks.
Overall, their crowd was only two thirds as efficient as it was before, and nearly ten times slower to recover. A week later, on December 1, All Your Shreds are Belong to U.S. completed the fifth and final document to claim DARPA’s $50,000 prize.
The identity of the attacker remained a secret. Cebrian vowed to continue to investigate the sabotage. But he was doubtful that his quest would succeed. “We will probably never know the true story about this,” he said then.
The data detective
That would have likely have been true, if not for a young French data scientist called Nicolas Stefanovitch. In 2011, Stefanovitch was half a world away from the Shredder Challenge, teaching computer science at Dauphine University in Paris. Two years later, and now a post-doc researcher in Abu Dhabi, a fascinating dataset arrived from Cebrian in Australia: the log-in and move tables from UCSD’s Shredder Challenge. The tables contained a complete record of the position and movement of each of the thousands of puzzle pieces, who had moved them, and the IP addresses they had used; over 300,000 entries in all.
Just as the Challenge teams had reassembled documents from a mess of tiny shreds, Cebrian asked Stefanovitch to painstakingly recreate the contest itself, hunting through a haystack of genuine users for the telltale pinpricks of those who wanted to unravel the crowd’s best efforts. Unlike UCSD’s legions, though, Stefanovitch was a crowd of one.
After a month of crunching the numbers, Stefanovitch was getting nowhere. With so many users working on the puzzle simultaneously, it was proving impossible to distinguish attacks from normal gameplay. Then he had a thought: if the shredded documents were a problem in vision, perhaps the attacks could be solved the same way? Stefanovitch animated the data, ignoring the content of the shreds themselves but plotting their movements over time.
When the first animation ran, he knew he was on to something. Dozens of likely attackers jumped off his laptop screen. These users either placed and removed chads seemingly at random, or moved pieces rapidly around the board. It was hardly surprising that the UCSD researchers believed they were under attack from a large group. But Stefanovitch was still a long way from a solution. “It was super hard to determine who was a saboteur,” he says. “Most of the people who looked like attackers, were not.”
Many of the high-speed moves turned out to be from genuine players responding to attacks, whereas others were just the actions of inept puzzlers. A few assaults were so rapid, however, that Stefanovitch thought the saboteurs might have deployed specialized software attack tools.
Stefanovitch set about identifying features — unique characteristics in the data — that he could match with behaviors on the board. He ended up with 15 features to separate saboteurs from honest users, and slowly honed in on those whose actions were destructive. There were far fewer than anyone had suspected: less than two dozen email addresses.
“I found a peak in recruitment that corresponds almost exactly to when the attacker claims he made an announcement on 4chan,” says Stefanovitch. “But I detected only a very small scale attack at this time, an attack so tiny you couldn’t even see it if you didn’t know it was there.”
Stefanovitch speculates that any 4chan hackers who logged on to wreak havoc soon got bored. “They might have been attackers but they weren’t motivated; they had nothing to gain from scorching our puzzle.”
Once he had eliminated the 4chan wave, Stefanovitch could identify the hardcore attackers. He then tracked their behavior forward and backward through time. When he re-watched his simulation of the very first attack, he struck gold. The initial assault was a sluggish affair, about ten times slower than subsequent hacks, as though the saboteur was still feeling out the system’s weaknesses. “When he realized he maybe could be traced, he logged off. Twenty minutes later, he logged in again with a different email address and continued doing the same stuff,” remembers Stefanovitch.
Crucially for Stefanovitch, the attacker had left his digital fingerprints on the system. When he logged in again from the same IP address, Stefanovitch was able to associate the two email accounts. As the attacks accelerated, the team in San Diego banned the attacker’s usernames. He, in turn, opened a stream of webmail accounts, eventually leading UCSD to block his IP address. The attacker then hijacked a neighbor’s wifi router and used a VPN to log in from different IPs. Yet he stumbled again, connecting from the new IPs with old, discredited usernames. No matter how many disposable emails the attacker now used, Stefanovitch could link them all back to him.
Three years after the Challenge, and after six months of solid work, Stefanovitch was finally able to sketch out a map of email addresses and IPs that covered all the destructive accounts.
He had solved the first-ever documented attack on a deployed crowdsourcing system. And the results were terrifying.
By Stefanovitch’s reckoning, just two individuals had accounted for almost all the destruction, eviscerating the completed puzzle in about one percent of the moves and two percent of the time it had taken a crowd of thousands to assemble it. Yet the attacker had left one more clue, a blunder that pointed right back to his door. During the first attack, he had logged in with an email address from his very own domain.
Inside job
Late last year, Stefanovitch and Cebrian collaborated on a paper about the Challenge. When I read it, I asked Stefanovitch whether he had tried contacting the attacker. “Tracing him was the most exciting aspect of the project, it felt like a thriller,” says Stefanovitch, who still had a few technical questions about the attacks. “But I was very busy so I just dropped it.”
He was, however, happy to share the attacker’s email with me. I got in touch with Adam and we finally spoke just before Christmas. It was a confusing experience at first. I found it hard to reconcile the softly spoken, modest voice on the phone with the high-octane firebrand I was expecting. Adam was thoughtful, even hesitant, choosing his words with care. But once we started talking about the Challenge, he gradually opened up.
Adam had first heard about the Shredder Challenge on a Reddit hacker thread, while working on character recognition and computer vision at a document imaging firm. “I had a little bit of background in that arena and decided to take a stab at it,” he told me. “My team, basically just me and a friend, was not super organized. We were having fun with it and didn’t really expect to win.”
DARPA shredder challenge winning teams submissions.
Like Manuel Cebrian’s group, Adam and his buddy started late but managed to crack the first two puzzles fairly easily, placing them in the top 50 worldwide. Between coding sessions, Adam would check out his rivals, including UCSD’s crowdsourcing platform.
“I don’t remember the point that I made a conscious decision to attack them,” he said. “I guess it was a spur of the moment kind of a thing.” He moved a few shreds around and noticed he could pile them up on top of each other. “They had hardly any constraints to prevent users from doing what they shouldn’t.”
Adam logged off to read the Challenge’s guidelines and consider his options. He couldn’t see anything in the rule book to prevent him from infiltrating UCSD’s crowd. And the more he thought about it, the more justifiable it seemed. “The scenario for the competition was a defense agency gathering documents on the battlefield. In that case, it makes total sense that there might be somebody out there who doesn’t want them put back together and might try to prevent it,” he says.
Adam ditched his personal email address (too late, as it turns out) and asked another friend, a design student who happened to be at his house, to join him. Together they got serious about destruction. The UCSD team had incorporated a feature (“multi select”) that allowed users to select and move many pieces at once — they thought it might help players with the early stages of each puzzle. In fact, it became Adam’s most powerful weapon against them.
“There was one night when I figured out they had multi select,” says Adam. “I picked up huge swathes of the puzzle space and made one huge pile. It was suddenly much easier for one person to do a lot of damage.”
As genuine users pulled pieces out of the stack, Adam would grab a bunch and drop them back in. “I definitely had the advantage,” he says.
It was this devastating multi select mode that had Cebrian chasing his tail looking for an army of attackers, and later Stefanovitch imagining the hackers with a powerful software attack tool. In reality, it was just Adam and his fast fingers, gleefully routing the hard-working crowd “for the lulz,” he admits. “Pure malign mischief.”
The end of crowdsourcing?
In Stefanovitch’s and Cebrian’s paper, they conclude: “The real impact of the attack was not to destroy the assembled pieces but to destroy the user base of the platform, and to disrupt the recruitment dynamics.”
All the motivation generated by weeks of good PR, a fun task and a smart financial incentive scheme evaporated in the face of attacks by a single person lasting, in total, no more than a couple of hours. The researchers warned, “Our results raise caution in the application of crowdsourced problem solving for sensitive tasks involving financial markets and national security.” DARPA might have already reached the same conclusion: the agency has issued no further crowdsourcing challenges since 2011. The agency did not respond to my request for an interview about how the Shredder Challenge attacks might have shaped their decisions.
DARPA red balloon network challenge, 2009. Photos by Doug McCaughan.
But don’t pity Cebrian as someone who was blindsided by an unforeseen enemy. His experience at the previous challenge had schooled him quite thoroughly on crowdsourcing’s susceptibility to sabotage, long before he got shredded. “I didn’t say much about this at the time because I wanted to really sell the recursive structure,” he says. “But the truth is that the real challenge in the 2009 balloon competition was filtering out misinformation.” Of over 200 balloon sightings received by the MIT team in DARPA’s Network Challenge, just 30 to 40 were accurate. Some of the fake reports were utterly convincing, including expertly Photoshopped photos that put Adam’s ad hoc hacks to shame.
“Myself and others in the social sciences community tend to think of such massive acts of sabotage as anomalies, but are they?” wondered Cebrian. To settle the question, Cebrian analyzed his (and other) crowdsourcing contests with the help of Victor Naroditskiy, a game theory expert at the University of Southampton. The results shocked him. “The expected outcome is for everyone to attack, regardless of how difficult an attack is,” says Cebrian. “It is actually rational for the crowd to be malicious, especially in a competition environment. And I can’t think of any engineering or game theoretic or economic incentive to stop it.”
Even worse, their analysis suggests that dissuading attacks, such as by making a crowdsourcing platform more robust or authenticating users, actually makes things worse. “Raising the cost of the attack doesn’t help you because you need to invest resources to do it,” says Cebrian. “And because that investment doesn’t pay off very well, eventually everyone is worse off.” Basically, in a competitive crowdsourcing environment, game theory says you will always get more bang for your buck by attacking rather than defending.
Every crowd has a silver lining
Luckily for platforms like Wikipedia or Amazon’s Mechanical Turk, the prospect for longer-term crowdsourcing projects are not so bleak. Game theorists have found that systems where individuals can build up a good reputation, are (probably) not as prone to devastating attacks from within.
But wily humans are good at finding their way around even the most secure digital systems. In a paper last year, researchers at the University of California, Santa Barbara, used AI software to detect spammers in China’s Weibo social network with an accuracy of up to 99%. Despite that, the authors concluded that “adversarial attacks are effective against all machine learning algorithms, and coordinated attacks are particularly effective.”
DARPA’s brief, intensely competitive challenges have produced something far more valuable than a new way of locating balloons or stitching together documents: a realization that crowds are far more complex, and far less wise, than they
first appeared to be.
Three years later, Cebrian doesn’t harbor any ill will towards Adam: “One way of looking at this saboteur is as someone who loves machines. If you read his emails, he thinks crowdsourcing is crappy and he wants to lend machines a hand because they are still improving. I think we’re going to see a bit of that in the next few years: people who actually prefer machines.”
Despite his astonishingly successful efforts to disrupt the UCSD’s crowd, Adam would prefer to be remembered as someone who improved crowdsourcing rather than killing it off. “I have some faith in the wisdom of the crowds,” he tells me with a smile in his voice. “But there will always be a caveat, always a wild card.”
In other words, the future of crowdsourcing is yet another puzzle that won’t be solved by putting our heads together.