DARPA Shredder Challenge 2011

Last updated

DARPA Shredder Challenge 2011 was a prize competition for exploring methods to reconstruct documents shredded by a variety of paper shredding techniques. The aim of the challenge was to "assess potential capabilities that could be used by the U.S. warfighters operating in war zones, but might also identify vulnerabilities to sensitive information that is protected by shredding practices throughout the U.S. national security community". [1] The competition was sponsored by the Defense Advanced Research Projects Agency (DARPA), a research organization of the United States Department of Defense. [2] Congress authorized DARPA to award cash prizes to further DARPA’s mission to sponsor revolutionary, high-payoff research that bridges the gap between fundamental discoveries and their use for national security.

Contents

As an example, solution of puzzle 2 from the DARPA Shredder Challenge. Puzzle2 Solution DARPA.png
As an example, solution of puzzle 2 from the DARPA Shredder Challenge.

Under the rules of the competition, the $50,000 challenge award would be granted to the first team to submit the answers to questions relating to a hidden mystery. The mystery verified that the team was able to extract meaningful intelligence from the page that was thought destroyed. The secret answers could be acquired by reconstructing five individual puzzles that were created by shredding one or more single-sided hand-written documents. [2]

In addition to the Shredder Challenge, DARPA has also conducted prize competitions in other areas of technology.

Winning team

Nearly 9,000 teams participated [3] [4] [5] between 12:00PM EDT on October 27, 2011, and the deadline of 11:59PM EST on December 4, 2011, [2] with the San Francisco-based team "All Your Shreds are Belong to U.S." winning the competition three days ahead of schedule. [6] [7] [8]

The team used a combination of techniques to solve the puzzles: custom-coded computer-vision algorithms were created to suggest fragment pairings to human assemblers for verification. [5] The eight-person team led by a technology entrepreneur Otavio Good also included Keith Walker, Winnie Tong, Luke Alonso, Zina Tebaykina, and Sohana Ahmed with two more persons joining to help in the end. [3] The team's three programmers had strong image-processing skills that enabled them to win this challenge: at the time of DARPA Shredder Challenge 2011, Otavio Good was leading the development of the visual translation tool Word Lens, Luke Alonso was a developer of the mobile phone application "Cabana", and Keith Walker was a programmer working on a satellite software at Lockheed Martin. [4]

Approximately 600 worker-hours were dedicated by the team to reconstruct five documents shredded into more than 10,000 pieces. [5] [7] [9] According to Good, the team's name was based on an Internet meme "All your base are belong to us". [3]

Other teams

Second placed team, "Schroddon", was composed just of husband and wife Marianne and Don Engel living in Baltimore, Maryland. [10] In contrast to the winning team, Schroddon used a human-assisted algorithm that the couple created. Both physicists, Marianne used her background in cryptography and Don used his background in computer science. [11] The couple was ranked first from November 14 until November 18, 2011.

University of California, San Diego (UCSD) reconstructed three puzzles through an online crowdsourcing approach, but their work-in-progress was repeatedly sabotaged. [12] [13]

Top performing teams

In the final standings, [14] the top 10 teams reported are:

PlaceNamePoints
1All Your Shreds are Belong to U.S.50
2Schroddon30
3wasabi26
4MKI22
5mmvd22
6UCSD22
7Craig Landrum19
8mkelly19
9Icandoit19
10Goldsong17

See also

Related Research Articles

<span class="mw-page-title-main">DARPA</span> Agency of the U.S. Department of Defense

The Defense Advanced Research Projects Agency (DARPA) is a research and development agency of the United States Department of Defense responsible for the development of emerging technologies for use by the military.

<span class="mw-page-title-main">Paper shredder</span> Device used to cut paper into pieces

A paper shredder is a mechanical device used to cut sheets of paper into either strips or fine particles. Government organizations, businesses, and private individuals use shredders to destroy private, confidential, or otherwise sensitive documents.

The DARPA Grand Challenge is a prize competition for American autonomous vehicles, funded by the Defense Advanced Research Projects Agency, the most prominent research organization of the United States Department of Defense. Congress has authorized DARPA to award cash prizes to further DARPA's mission to sponsor revolutionary, high-payoff research that bridges the gap between fundamental discoveries and military use. The initial DARPA Grand Challenge in 2004 was created to spur the development of technologies needed to create the first fully autonomous ground vehicles capable of completing a substantial off-road course within a limited time. The third event, the DARPA Urban Challenge in 2007, extended the initial Challenge to autonomous operation in a mock urban environment. The 2012 DARPA Robotics Challenge, focused on autonomous emergency-maintenance robots, and new Challenges are still being conceived. The DARPA Subterranean Challenge was tasked with building robotic teams to autonomously map, navigate, and search subterranean environments. Such teams could be useful in exploring hazardous areas and in search and rescue.

Topcoder is a crowdsourcing company with an open global community of designers, developers, data scientists, and competitive programmers. Topcoder pays community members for their work on the projects and sells community services to corporate, mid-size, and small-business clients. Topcoder also organizes the annual Topcoder Open tournament and a series of smaller regional events.

The Portable Open Source Security Elements (POSSE) project was a co-operative venture between the University of Pennsylvania Distributed Systems Laboratory, the OpenBSD project and others. It received funding through a grant from the United States Defense Advanced Research Projects Agency (DARPA). The project's goal was to increase the security of some open source projects, including Apache and OpenSSL. The project ran from 2001 to April 2003, when the grant from DARPA was prematurely terminated.

<span class="mw-page-title-main">Crowdsourcing</span> Sourcing services or funds from a group

Crowdsourcing involves a large group of dispersed participants contributing or producing goods or services—including ideas, votes, micro-tasks, and finances—for payment or as volunteers. Contemporary crowdsourcing often involves digital platforms to attract and divide work between participants to achieve a cumulative result. Crowdsourcing is not limited to online activity, however, and there are various historical examples of crowdsourcing. The word crowdsourcing is a portmanteau of "crowd" and "outsourcing". In contrast to outsourcing, crowdsourcing usually involves less specific and more public groups of participants.

Fragapalooza is an annual video game festival/LAN party that takes place in Leduc, Alberta, Canada. The name Fragapalooza was derived from the Military Slang "Frag" and "palooza" which is the suffix for any type of named festival or gathering, such as Lollapalooza. Traditionally held in the summer, Fragapalooza runs over a period of four days. In 2008, it was Canada's largest LAN party event, having reached approximately 900 attendees at its peak.

There are a number of competitions and prizes to promote research in artificial intelligence.

The 2009 DARPA Network Challenge was a prize competition for exploring the roles the Internet and social networking play in the real-time communications, wide-area collaborations, and practical actions required to solve broad-scope, time-critical problems. The competition was sponsored by the Defense Advanced Research Projects Agency (DARPA), a research organization of the United States Department of Defense. The challenge was designed to help the military generate ideas for operating under a range of circumstances, such as natural disasters. Congress authorized DARPA to award cash prizes to further DARPA's mission to sponsor revolutionary, high-payoff research that bridges the gap between fundamental discoveries and their use for national security.

Adaptive Vehicle Make was a portfolio of programs overseen by DARPA, of the United States Department of Defense. AVM attempted to address revolutionary approaches to the design, verification, and manufacturing of complex defense systems and vehicles. The three primary programs were META, Instant Foundry Adaptive through Bits (iFAB), and Fast Adaptable Next-Generation Ground Vehicle programs. Many components of the program leveraged crowdsourcing and were open source and the ultimate intent was to crowdsource a next generation combat vehicle. The program was managed by Nathan Wiedenman under DARPA's Tactical Technology Office. A Proposer's Day was held and several Broad Agency Announcements released on 7 October 2010. The AVM program was ended in February 2014 without building and testing a complete vehicle.

<span class="mw-page-title-main">Otávio Good</span> American computer programmer

Otávio Good is a Brazilian and American computer programmer and inventor. He is the original author of Word Lens, the first augmented reality translation application that replaces printed text into the desired language in video without connection to the Internet.

<span class="mw-page-title-main">EteRNA</span> 2010 browser-based video game

Eterna is a browser-based "game with a purpose", developed by scientists at Carnegie Mellon University and Stanford University, that engages users to solve puzzles related to the folding of RNA molecules. The project is supported by the Bill and Melinda Gates Foundation, Stanford University, and the National Institutes of Health. Prior funders include the National Science Foundation.

<span class="mw-page-title-main">Competitive programming</span> Mind sport

Competitive programming or sport programming is a mind sport involving participants trying to program according to provided specifications. The contests are usually held over the Internet or a local network. Competitive programming is recognized and supported by several multinational software and Internet companies, such as Google and Meta.

The MyHeartMap Challenge is a community improvement initiative and part of a research study being conducted at the University of Pennsylvania to map automated external defibrillators (AEDs) in the city of Philadelphia.

A scrap metal shredder, also sometimes referred to as a metal scrap shredder, is a machine used for reducing the size of scrap metal. Scrap metal shredders come in many different variations and sizes.

<i>Exit</i> (game show) American TV series or program

Exit is an American game show on Syfy that premiered on June 4, 2013.

<span class="mw-page-title-main">Iyad Rahwan</span> Syrian-Australian computational social scientist

Iyad Rahwan, is a Syrian-Australian scientist. He is the director of the Center for Humans and Machines at the Max Planck Institute for Human Development. Between 2015 and 2020, he was an associate professor of Media Arts & Sciences at the MIT Media Lab. Rahwan's work lies at the intersection of the computer and social sciences, where he has investigated topics in computational social science, collective intelligence, large-scale cooperation, and the social aspects of artificial intelligence.

<span class="mw-page-title-main">Printer tracking dots</span> Digital watermark tracking code produced by many printers

Printer tracking dots, also known as printer steganography, DocuColor tracking dots, yellow dots, secret dots, or a machine identification code (MIC), is a digital watermark which many color laser printers and copiers produce on every printed page that identifies the specific device that was used to print the document. Developed by Xerox and Canon in the mid-1980s, the existence of these tracking codes became public only in 2004.

Over the years, the U.S. Defense Advanced Research Projects Agency (DARPA) has conducted a number of prize competitions to spur innovations. A prize competition allows DARPA to establish an ambitious goal, which makes way for novel approaches from the public that might otherwise appear too risky to undertake by experts in a particular discipline.

References

  1. Geller, Tom (August 2012). "DARPA Shredder Challenge Solved". Communications of the ACM. Retrieved 2022-02-17.
  2. 1 2 3 "DARPA's Shredder Challenge Rules". DARPA. Archived from the original on February 21, 2013. Retrieved May 20, 2013.
  3. 1 2 3 Walker, Richard (December 20, 2011). "How 8 Enthusiasts Beat 9,000 Teams To Solve DARPA's 'Shredder' Challenge". AOL Government. Archived from the original on April 28, 2012. Retrieved January 1, 2012.
  4. 1 2 Aron, Jacob (December 3, 2011). "DARPA's Shredder Challenge has been solved". New Scientist . Retrieved January 1, 2012.
  5. 1 2 3 Drummond, Katie (December 2, 2011). "Programmers Shred Pentagon's Paper Puzzle Challenge". Wired . Retrieved December 5, 2011.
  6. "DARPA's Shredder Challenge Solved". DARPA. Archived from the original on December 4, 2011. Retrieved December 5, 2011.
  7. 1 2 Orlin, Jon (December 2, 2011). ""All Your Shreds Are Belong to U.S." Wins $50,000 DARPA Shredder Challenge". TechCrunch . Retrieved January 1, 2012.
  8. Bingham, Amy (December 2, 2011). "Calif. Programmers Win $50K in Pentagon's Un-Shredding Contest". ABC News . Retrieved January 1, 2012.
  9. Dillow, Clay (December 5, 2011). "DARPA's Impossible-Sounding Shredder Challenge is Already Solved". Popular Science . Retrieved January 1, 2012.
  10. Ruediger, Nicole (Winter 2012). "Puzzle Pair". UMBC. Archived from the original on 2014-10-15.
  11. "UMBC Team Places Second in the DARPA Shredder Challenge". UMBC. 3 December 2011. Retrieved December 3, 2011.
  12. Harris, Mark (February 9, 2015). "How a Lone Hacker Shredded the Myth of Crowdsourcing" . Retrieved 2022-02-17.
  13. Rahwan, Iyad (October 2, 2014). "How Crowdsourcing Turned On Me". Nautil.us. Retrieved 2022-02-17.
  14. "DARPA Shredder Challenge 2011 Final Standings". DARPA. Archived from the original on February 21, 2013. Retrieved May 20, 2013.