Entartung (Informatik)

Eine Datenstruktur wird als entartet bezeichnet, wenn sie final einen Zustand angenommen hat, in der sie anders als vor der Entartung nachteilig wirkt. Dies kann aufgrund ungünstiger Eingabedaten geschehen.

Beispiel

Eine grundlegende Datenstruktur sind sortierte Binärbäume. Diese bestehen aus Knoten mit jeweils zwei Nachfolgerknoten, wobei alle Knoten des linken Teilbaumes (= linker Nachfolgerknoten und dessen Nachfolger, auch die indirekten) kleiner und alle Knoten des rechten Teilbaumes größer als dieser sind:

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

Was solche binären Bäume auszeichnet, ist, dass der Baum stets sortiert ist. Das Einfügen neuer Knoten hat die Komplexität O(log(N)), im Gegensatz zu O(N) bei einer sortierten Liste.

Kommen die Knoten beim Erstellen des Baumes jedoch in ungünstiger Reihenfolge, so kann eine Entartung des Baumes die Folge sein:

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

Jetzt ist der Baum zwar immer noch sortiert, der Aufwand des Einfügens neuer Knoten ist jedoch nur noch O(N), da er praktisch eine sortierte Liste ist.

Anfälligkeit

Viele gebräuchliche Datenstrukturen sind für Entartung anfällig, Beispiele hierfür sind der oben erwähnte sortierte binäre Baum und viele Implementierungen von Hash-Tabellen ohne Feedback.

Je nach Datenstruktur ist die Anfälligkeit gegen Entartung verschieden. Bei obigem binären Baum reicht es aus, dass die Eingabedaten sortiert sind; bei determiniert oder stachastisch konfigurierten Hashtabellen und vernünftigen Hashfunktionen ist eine Entartung aber sehr unwahrscheinlich und wird deshalb meist vernachlässigt.

Es gibt aber auch Datenstrukturen, die durch spezielle Maßnahmen gegen Entartung immun sind, z.B. Rot-Schwarz-Bäume. Die Absicherung kostet in der Regel etwas Effizienz, erhöht dafür aber die Worst-Case-Effizienz erheblich.

Sicherheitsaspekte

Der Einsatz von Datenstrukturen, die entarten können, macht das betreffende Programm anfällig für Denial of Service-Attacken. Dazu kann ein Angreifer das Programm so mit Eingabedaten füttern, dass die internen Datenstrukturen des Programms entarten und das Programm dadurch erheblich mehr Rechenzeit als üblich benötigt - im Extremfall so viel, dass das Programm seinen Zweck nicht mehr erfüllen kann.

Als Gegenmaßnahmen wurde in die Hashtabellen der auf vielen Webservern verwendeten Programmiersprache Perl eine Zufallskomponente eingebaut, die bei jedem Programmstart für eine neue interne Verteilung zu speichernder Werte in die Hashtabelle sorgt und einen DoS-Angriff durch absichtliche Entartung damit erheblich erschwert.