The great shredding challenge

David Heath
Sunday, 11 December 2011 08:13

Business IT - Security

DARPA recently ran a competition to 'recover' a suite of shredded documents.  Here's how it went.

According to DARPA's (Defence Advanced Research Projects Agency) Shredder Challenge website in setting the scene, "Today's troops often confiscate the remnants of destroyed documents in war zones, but reconstructing them is a daunting task. DARPA's Shredder Challenge called upon computer scientists, puzzle enthusiasts and anyone else who likes solving complex problems to compete for up to $50,000 by piecing together a series of shredded documents.

"The goal was to identify and assess potential capabilities that could be used by our warfighters operating in war zones, but might also create vulnerabilities to sensitive information that is protected through our own shredding practices throughout the U.S. national security community."

DARPA provided 5 scanned images of shredded pages and offered a $50,000 prize for the best entry.

Interestingly, once "un-shredded" each image contained a puzzle to be solved.

Five weeks after launching the competition, a winner was announced.  Out of the almost 9,000 teams who entered, the San Francisco-based team, calling itself, 'All your shreds are belong to U.S.' was first to correctly reconstruct the shredded pages and solve the puzzles.

"Lots of experts were skeptical that a solution could be produced at all let alone within the short time frame," said Dan Kaufman, director, DARPA Information Innovation Office. "The most effective approaches were not purely computational or crowd-sourced, but used a combination blended with some clever detective work. We are impressed by the ingenuity this type of competition elicits."

The winning team used custom-coded computer-vision algorithms which produced sets of fragment-pairings for human verification.  In total they spent less than 600 hours developing the software and matching the shreds.