Degeneration (computer science)

A data structure is referred to as degenerate if it has finally assumed a state in which it has a disadvantageous effect other than before the degeneration. This can happen due to unfavorable input data.

example

Sorted binary trees are a basic data structure . These consist of nodes with two successor nodes each, whereby all nodes of the left subtree (= left successor node and its successors, including the indirect ones) are smaller and all nodes of the right subtree are larger than this:

       [7]
      /   \
   [3]     [12]
   / \     /  \
 [1] [4] [9]  [15]

What distinguishes such binary trees is that the tree is always sorted. Inserting new nodes has the complexity O (log (N)), in contrast to O (N) for a sorted list .

However, if the nodes come in an unfavorable order when the tree is created, the tree may degenerate:

[1]
  \
  [3]
    \
    [4]
      \
      [7]
        \
        [9]
          \
          [12]
             \
             [15]

Now the tree is still sorted, but the effort of adding new nodes is O (N) because it is practically a sorted list.

susceptibility

Many common data structures are susceptible to degeneracy, examples of which are the sorted binary tree mentioned above and many implementations of hash tables without feedback.

The susceptibility to degeneration varies depending on the data structure. With the above binary tree it is sufficient that the input data are sorted; In the case of determined or stochastically configured hash tables and sensible hash functions, however, degeneration is very unlikely and is therefore usually neglected.

But there are also data structures that are immune to degeneration through special measures, e.g. B. Red-black trees . The protection usually costs some efficiency, but it increases the worst-case efficiency considerably.

Security aspects

The use of data structures that can degenerate makes the program in question susceptible to denial of service attacks. For this purpose, an attacker can feed the program with input data in such a way that the internal data structures of the program degenerate and the program therefore requires considerably more computing time than usual - in extreme cases so much that the program can no longer fulfill its purpose.

As a countermeasure, a random component was built into the hash tables of the Perl programming language used on many web servers , which ensures a new internal distribution of values ​​to be saved in the hash table each time the program is started and thus makes a DoS attack considerably more difficult due to deliberate degeneration.