This is an archived web site made available for research purposes. The web site is no longer maintained.

Qualifier Challenge - KPRCA_00032


Original Versions

Known Vulnerabilities

  • CWE-122 - Heap-based Buffer Overflow
  • CWE-755 - Improper Handling of Exceptional Conditions
  • CWEs are listed as indicated by the challenge author.

Scores

  • CodeJitsu: 0.0
  • Disekt: 0.0
  • ForAllSecure: 0.0
  • TECHx: 0.0
  • Shellphish: 0.0
  • CSDS: 0.0
  • FuzzBOMB: 0.0
  • TrailofBits: 0.0
  • DeepRed: 0.0
  • The maximum score for each challenge in CQE is 4, following the CQE Scoring Document.

Passed consensus evaluation

  • CodeJitsu - CB1
  • CSDS - CB1
  • DeepRed - CB1
  • Disekt - CB1
  • ForAllSecure - CB1
  • FuzzBOMB - CB1
  • Shellphish - CB1
  • TECHx - CB1
  • TrailofBits - CB1

Proved a POV in reference challenge

Defense against reference POVs

  • ForAllSecure: 100.0% - CB1
  • CodeJitsu: 100.0% - CB1
  • TECHx: 100.0% - CB1
  • Disekt: 100.0% - CB1
  • CSDS: 100.0% - CB1

No submission

  • Eighth Place Team
  • Eleventh Place Team
  • Fifth Place Team - Finalist
  • First Place Team - Finalist
  • Fourth Place Team - Finalist
  • Ninth Place Team
  • Second Place Team - Finalist
  • Seventh Place Team - Finalist
  • Sixth Place Team - Finalist
  • Tenth Place Team
  • Third Place Team - Finalist
  • Thirteenth Place Team
  • Twelfth Place Team

All Submissions

DARPA performer group

Kaprica Security (KPRCA)

Description:

This service implements an anagram game and solver with a simple binary interface. At launch, the service is sent an initial dictionary that is used to sort the anatree. THe user can then add more words, remove words, query for anagrams, or play a game.

Feature List

The anagram solver can answer queries for normal anagrams and subset anagrams. The solver is built using an anatree where each level of the tree represents a letter of the alphabet and the edges represent number of occurences of that letter. While this is slower than the alternative hash-based algorithm, it can support subset anagrams without explosion of runtime. The game will send the user ten words and the user must respond with half of the possible anagrams for each word in order to win.

Vulnerability

The vulnerability is triggered in atree_add (atree.c:255) when there is an out-of-memory condition. The error handling code fails to correct the number of degrees which results in it becoming larger than the max degree, and thus causing a buffer overflow or overread later. One way that the overflow can occur is if degree is too large and then a word at the beginning of the array is deleted, which causes the memmove in atree_remove (atree.c:301) to modify memory that is outside of the buffer. An overread can occur in atree_query trivially if degree is too large.

Generic class of vulnerability

Heap-based Buffer Overflow

CWE classification

CWE-122: Heap-based Buffer Overflow CWE-755: Improper Handling of Exceptional Conditions

Challenges

The unique challenge for this service is exploiting an out-of-memory condition. Due to the limitations of the environment, the only reliable way to cause an out-of-memory condition that is exploitable is by exhausting the amount of virtual memory available to the process. The only way to do this reliably is by controlling the allocation in read_initial_words.

Patching the bug may be difficult. The trivial patch would be exiting the service if an out-of-memory condition occurs. This is tested for by a poller, however, which should make that patch invalid. Either fixing degree or detecting the out-of-bounds access would be valid patches.


Curated by Lunge Technology, LLC. Questions or comments? Send us email