Technology | DOI: 10.1145/2240236.2240242
The eight-person winning team used original computer algorithms
to narrow the search space and then relied on human observation
to move the pieces into their final positions.
YOu accIdentally Shredded an important document. Could you put it back to- gether? Would it be worth the effort? What if it would
stop a terrorist plot, or release an innocent person from jail?
Intelligence agencies around the
world face questions like these, most
famously when the East German secret
police abandoned tons of torn pages
after the fall of the Berlin Wall in late
1989. Those documents are still being
reconstructed, and the creation of a
computer program called the e-Puzzler
in 2010 increased hopes of finishing
the job by 2013. But that program was
written to reconstruct those particular
documents. It is optimized to handle
hand-torn pieces as the East German
secret police were forced to manually
destroy many of the documents.
To seek “unexpected advances”
that could be applied to such situations, the U.S. Defense Advanced
Research Projects Agency (DARPA) issued its Shredder Challenge in October 2011, daring the public to unshred
five documents and extract their hidden messages. The puzzles were designed to be progressively difficult
on multiple axes, ranging from about
200 chads to more than 6,000 each.
Text files accompanying the scanned
chads provided questions, with points
reflecting each question’s difficulty.
For example, puzzle #3 asked “What
is the indicated location?” while the
reassembled document showed a
set of geographic coordinates and a
drawing of Cuba. (Naming the country was worth two points; the city of
Cienfuegos was worth an additional
six.) Solvers needed to both answer
the questions and show how their reconstruction of the document led to
that answer. More than 9,000 teams
DARPA Shredder Challenge puzzle #1
consisted of more than 200 chads of torn,
yellow lined paper with handwritten text.
applied for the challenge, but only 69
of them answered one or more questions correctly.
The winning team was the only one
to answer all of the questions in all
five puzzles, taking home the $50,000
prize while ending the contest on Dec.
2, 2011, three days ahead of schedule.
Like other contest leaders, the eight-person “All Your Shreds Are Belong
To U.S.” team employed original computer algorithms to narrow the search
space, and then relied on human observation to move the pieces into their
final positions. In the process the All
Your Shreds team discovered unexpected difficulties—and also a peculiarity in the contest that gave it an unexpected edge.
Play to Win
The contest’s parameters had a strong
effect on how competitors approached
the problem. As Don Engel of the two-person, second-place “Schroddon”
team says, “If we had taken a completely manual approach, we’d lose
because teams can be of any size. If
we’d taken only a computer-driven approach, we’d also lose because there
are people out there who are better at
computer vision.” In fact, a team from
University of California, San Diego attempted to crowdsource the challenge,
setting it up as a sort of game and inviting the public to help them via the
Internet. Saboteurs foiled the team’s
strategy, accusing it of “cheating” and
moving shreds to incorrect positions.
The team responded by implementing
security measures, which also slowed
its progress, knocking it from third to
The winning All Your Shreds team
took advantage of the fact the shred-
ded documents were apparently pho-
tocopied before being placed face-up
on a solid background and scanned,
resulting in a phenomenon known as
printer steganography. “High-quality
printers and photocopiers, in the Unit-
ed States at least, have a watermark on
them so the Secret Service can track
phony money,” explains team member
Otávio Good, founder of Quest Visual.
“It’s a repeating pattern of yellow dots.
If you can find it, you can use that to
your advantage. It’s essentially like a
map of how the pieces go together.”
However, Good pointed out they were
“yellow dots on yellow paper, and the
chads were small. It helped us tremen-
dously, but we were pretty much in the
lead even before we found the dots. In
my opinion, we were still on track to
win... it was part of the game.”
“The challenge and its component
puzzles were designed to resemble the
problem facing an intelligence ana-
lyst,” says Norman Whitaker, deputy
director of DARPA’s Information In-
novation Office. “That analyst is often
less interested in putting the pieces to-
gether than in getting crucial informa-
tion off the page in the shortest time
possible.” In explaining why the chal-
lenge could only be a small represen-
tation of what is found in the field, he
says, “[It’s] narrow in scope to make it
tractable. It concerned English, hand-