Ich stieß neulich auf einen interessanten Artikel zum Thema reguläre Ausdrücke, der mich so faszinierte, dass ich zunächst einmal wieder mal in einen Kaninchenbau abstürzte und als ich wieder daraus emportauchte ernsthaft überlegte, einen weiteren Ausflug in Gebiete zu machen, die ich zuvor nie ernsthaft in Betracht gezogen hätte:

Ich trage mich jetzt ernsthaft mit dem Gedanken, als Fingerübung selbst eine Engine zur Auswertung regulärer Ausdrücke zu schreiben.

Der Grund dafür ist die - meiner Ansicht nach - wunderbar klare Beschreibung in dem genannten Artikel wie man eine solche Engine "richtig" schreibt und die Tatsache, dass die beschriebenen Probleme immer noch existieren (der Artikel ist bereits ein wenig angejahrt). Für die, die keine Lust haben, den ganzen Artikel zu lesen - hier eine kurze Zusammenfassung: Es gibt mehrere grundsätzliche Wege, eine solche Engine zu implementieren und in vielen Bibliotheken / Sprachen wurde diejenige gewählt, die nicht nur die schlechtere Performance liefert, sondern Angreifern die Möglichkeit gibt, die gesamte Anwendung lahmzulegen, wenn es ihnen ermöglicht wird, eigene reguläre Ausdrücke auswerten zu lassen.

In meinem $dayjob bin ich bereits gelegentlich an entsprechenden CVEs vorbeigekommen, die einen Availability Impact für verschiedene Bibliotheken zur Auswertung regulärer Ausdrücke beschreiben - allerdings ging ich bisher davon aus, dass es sich hierbei um einfach zu behebende Programierfehler handelt - nun weiß ich, dass das systematische Probleme der gewählten Implementierung darstellt.

Aber der Artikel ist bereits ein wenig älter - daher wollte ich mich nicht auf die dort gemachten Angaben verlassen, sondern das beschriebene Verhalten selbst nachvollziehen und messen. Ich hielt mich daher an das im Artikel beschriebene Vorgehen und erzeugte einen regulären Ausdruck der Gestalt a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaa den ich auf den Input aaaaaaaaaaaaaaaaaaaaaaaaaaaaa anwendete. Das tat ich mit Java in der Version 17 (weil ich gerne Java benutze und der Originalartikel dazu nichts schrieb) und Python in der Version 3.12.3 (Ubuntu 24.04) weil der Originalartikel lediglich Angaben zu Python 2 machte.

Eindrucksvoll die Ergebnisse: Die Auswertung mittels der Java Standardimplementierung java.util.regex nahm 00:00:08.603305 Sekunden in Anspruch, Python benötigte für dieselbe Aufgabe 22.9082 Sekunden.

Damit war mir klar, dass ich einen der Gründe gefunden hatte, weshalb es so viele konkurrierende Java Bibliotheken für die Auswertung regulärer Ausdrücke gibt - ich nehme an, dass es für Python ein ebenso breites Angebot alternativer Implementierungen gibt, habe das aber nicht explizit überprüft.

Für Java habe ich mir einige der Angebote angesehen und kam - immer mit derselben Testaufgabe auf folgende Ergebnisse: Die Implementierung com.florianingerl.util.regex benötigte 00:00:16.301038 Sekunden - hier liegt die Daseinsberechtigungen in den weitaus machtigeren Features der Engine. Die Implementierung dk.brics.automaton benötigte 00:00:00.016161 Sekunden und die Implementierung tcl-regex-java benötigte 00:00:00.088418 Sekunden.

Ich würde mich - wenn ich mich hier und jetzt entscheiden müsste für dk.brics.automaton entscheiden, da tcl-regex-java für meinen Geschmack viel zu viele transitive Dependencies zu einem Projekt hinzufügt - das kommt natürlich auch immer auf die Struktur des jeweiligen Projektes an - wenn diese Abhängigkeiten eh schon im Projekt benötigt werden, fällt dieses Argument natürlich flach.

Artikel, die hierher verlinken