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

Qualifier Challenge - CROMU_00024


Original Versions

Known Vulnerabilities

  • CWE-476 - NULL Pointer Dereference
  • CWEs are listed as indicated by the challenge author.

Scores

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

Passed consensus evaluation

Proved a POV in reference challenge

Defense against reference POVs

  • CodeJitsu: 100.0% - CB1
  • CSDS: 100.0% - CB1
  • DeepRed: 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

Author Information

Steve Wood swood@cromulence.co

DARPA performer group

Cromulence

Description

The program is an application for the storage and quick retrieval of string data. Internally, a token is created for each string and the token is used as the key for a Binary Search Tree where the data is stored. This allows for very quick retrieval of strings, provided that data is not stored in such a sequence that the tree degenerates into a linked list. Most BST's do not allow for duplicate keys, but this implimentation does, storing the data common to one key in a linked list that must be sequentially searched. However, key collisions should be rare and therefore sequential searches very short. In addition, identical string data is not allowed, further limiting the possibility of key overlap.

Feature List

The program allows for strings to be a)dded, d)eleted, f)ound, the entire tree to be w)alked, and tree s)tatistics to be printed. Strings are added by the command a/ for example. Strings to be added must be at least 10 characters in width.

Vulnerability

The vulnerability occurs in the processing of how data for duplicate keys is handled. If more than one data element resolves to the same key, the data items are stored in a linked list attached to that that BST node. During find or delete operations, they key is used to rapidly find the node and the attached linked list is sequentially walked and the string data compared to that being searched for. If a match is found, the operation completes. The vulnerability lies in an improper update of a pointer during a delete operation. If there is a linked list, and the last node of the list is being deleted, the current pointer is updated to the "next" pointer before the memory is released with free(). At the end of the list, this causes a null pointer to be passed to free(), resulting in a SEGFAULT.

Generic class of vulnerability

NULL Pointer Dereference.

CWE classification

CWE-476

Challenges

This vulnerability requires two steps to demonstrate it crashing the program. First two values with the same resulting token must be found, and then the second and only the second one being deleted will result in a SEGFAULT. It is certainly an "edge case" condition for the program that would not readily show up with purely random fuzzing.


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