Session-IDs performant filtern

Wir kennen und ~~hassen~~ lieben sie alle: Sitzungskennungen, auch Session-IDs in Neudeutsch genannt. Da das HTTP uns es als Webentwicklern nicht einfach macht, Benutzer über mehrere Aufrufe wiederzuerkennen, muss man zwangsweise auf diese Krücke zurückgreifen.

Wir stellen uns hier nicht die Frage, ob das Übermitteln der SID als Teil der URI (als GET-Parameter also) oder als Inhalt eines Cookies sinnvoller, performanter, schöner oder massentauglicher ist. Vielmehr geht es hier darum, zu prüfen, wie wir die wie auch immer übermittelte SID am effizientesten von Sonderzeichen bereinigen können, um SQL-Injections vermeiden zu können.

Spontan fallen da 3 Varianten auf:

Man durchwandert die SID in einer Schleife und löscht jedes „böse“ Zeichen einzeln. Danach prüft man, ob die SID immer noch die Länge einer sauberen SID (variiert von System zu System, mal sind es MD5-Hashes (32 Zeichen), mal SHA-1 (40 Zeichen) und mal ganz andere Sachen) hat.
Man durchwandert wie bei (1) die SID und löscht alles Böse. Aber bereits beim ersten Treffer bricht man ab. Diese Variante entlarvt (1) schon als unnötig lang.
Man durchwandert die SID gar nicht, sondern wendet einen kurzen regulären Ausdruck auf sie an und prüft, ob dieser zutrifft oder eben nicht.

Im Endeffekt stehen sich also die iterative und reguläre Vorgehensweise gegenüber. Bei der regulären erwarten wir durch das Kompilieren des Ausdrucks einen kleinen Overhead und wollen nun schauen, ob dieser auch wirklich ins Gewicht fällt.

Unsere Testszenario geht von folgender Einstellung aus: Wir erzeugen für jeden Benutzer einen SHA-1-Hash aus der aktuellen Uhrzeit, IP und Datum. Eine gültige SID umfasst also 40 Zeichen, bei denen es nicht auf Groß- und Kleinschreibung ankommt.

Um sowohl den Worst Case als auch den Best Case abzudecken, erzeugen wir zum Testen einmal eine lange Liste gültiger Session-IDs und einmal eine lange Liste ungültiger Session-IDs. Im täglichen Einsatz ist — wenn überhaupt — eine unter zehntausend SIDs gefälscht und das Mittel eines Angriffs. Nur zu prüfen, wie sich die Varianten bei gefälschten SIDs verhalten, wäre also weltfremd, da nunmal 99,99…% der Daten gültig sind.
Dieser Anteil ist dabei durchaus von Relevanz, da es schon einen Unterschied macht, ob unsere Prüf-Schleife alle 40 Zeichen durchwandern muss oder eben direkt beim ersten Zeichen abbrechen kann.

Nicht verwundern sollte, dass wir aus Performance-Sicht den Worst Case mit gültigen SIDs simulieren und den Best Case mit den ungültigen.

Ein kleines Skript erzeugt uns zum Testen eine ausreichend große Menge an zufälligen SIDs, einmal saubere und einmal mit allerhand Sonderzeichen, Apostrophen und Anführungszeichen:

fwrite($f,"<?php\n\n\$data = array(");
for ( $i=0; $i < 100000; $i++ ) {      fwrite($f,"\n\t'".makerand(40)."',");
}   
fwrite($f,"\n);\n\n
?>");

Wobei unser Zeichenvorrat von makerand() folgendermaßen aussieht:

abcdefghijklmnopqrstuvwxyz ABCDEFGHIJKLMNOPQRSTUVWXYZ 1234567890 !\"§$%&/()=?<>|-_:.;,°^*+'

(Die untere Zeile ist nur bei den gefälschten SIDs enthalten.)

Die erzeugten data.php und data_clean.php enthalten dann die Testdaten, die von unseren 3 Testscripts ausgewertet werden:

Script #1 – vollständiger Durchlauf jeder SID

$good   = '1234567890abcdefghijklmnopqrstuvwxyz'; 
$falses = 0;  
$trues  = 0;    
foreach ( $data as $sid ) { 
   for ( $i = 0; $i < strlen($sid); ++$i ) {
      if ( strpos($good,strtolower($sid[$i])) === false ) { 
         $str[$i] = ''; 
      } 
    }  
   if ( strlen($sid) < 40 ) {   
      $falses++; 
   } 
}

Script #2 – verkürztes Durchlaufen jeder SID

$good   = '1234567890abcdefghijklmnopqrstuvwxyz';  
$falses = 0;    
foreach ( $data as $sid ) {      
   for ( $i = 0; $i < 40; ++$i ) {          
      if ( strpos($good,strtolower($sid[$i])) === false ) {              
         $falses++;              
         break;          
      }     
   }  
}

Script #3 – regulärer Ausdruck

 
$falses = 0;    
foreach ( $data as $sid ) {      
   if ( !preg_match("#^[a-z0-9]+$#i",$sid) ) {          
      $falses++;      
   }  
}

Lassen wir die 3 Scripte gegeneinander antreten, erhalten wir auf einem alten Laptop (Celeron 2,6 GHz, 512 MB RAM, WinXP, PHP 5.2.0 im CLI-Modus) folgende Ergebnisse (Durchschnittswerte nach je 10 Durchläufen pro SID-Liste):

Volle for-Schleife:
Best Case: 9,615 (pro SID 0,00009615)
Worst Case: 9,435 (pro SID 0,000094354)

Kurze for-Schleife:
Best Case: 0,759 (pro SID 0,000007589)
Worst Case: 7,799 (pro SID 0,000077997)

Regex:
Best Case: 0,648 (pro SID 0,00000648)
Worst Case: 0,441 (pro SID 0,000004418)

Die verwendeten Scripts sind zusammen mit den Testdaten am Ende des Artikels verlinkt.

Vergleichen wir jeweils den Best und Worst Case, sehen wir, dass die regulären Ausdrücke sogar noch etwas schneller wurden, wenn die SIDs gültig sind. Die kurze for-Schleife nähert sich erwartungsgemäß bei gültigen SIDs an die Laufzeit der langen for-Schleife an. Beide Schleifen-Varianten sind im Normfall also weit abgeschlagen mit der mehr als 10fachen Laufzeit der regulären Ausdrücke.

Doch die Sache hat einen Haken: Kompilierte reguläre Ausdrücke werden pro Thread zwischengespeichert. Das ist für die mehrmalige Anwendung ganz nett, aber im Normalfall wird der Ausdruck genau 1x pro Seitenaufruf/Thread benötigt. Der Cache sitzt in der PCRE-Erweiterung und speichert pro Thread bis zu 4096 kompilierte Ausdrücke. Der Overhead ist also nur bei einem von 100.000 Durchläufen zu spüren.

Unter diesem Gesichtspunkt kann man den Test nur sehr eingeschränkt wiederholen, um realistischere Ergebnisse zu erhalten. Ein neues Script (combo.php) sieht dabei so aus, dass es 1.000x die clean_combo.php aufruft, die dann wiederum insgesamt 4 Prüfungen vornimmt:

kurze for-Schleife
regulärer Ausdruck (unkompiliert)
regulärer Ausdruck (kompiliert, im Cache)
kurze for-Schleife

Da wir von 99,99% gültigen SIDs ausgehen, lassen wir den separaten Test von langer und kurzer for-Schleife aus und nehmen nur die kurze Variante.

Die Ergebnisse gehen wieder an die combo.php, die sie notiert und danach ausgibt. Wir testen die Varianten diesmal nur 1.000x, damit der Artikel auch diesen Monat noch fertig wird.
Nach den Durchläufen, die aus technischen Gründen auch auf einem etwas neueren Computer (Athlon 2500+, 512 MB RAM, WinXP, PHP 5.1.4) getätigt wurden, sehen die Ergebnisse folgendermaßen aus:

1. Durchlauf der for-Schleife:
Best Case: 0,13326
Worst Case: 0,27104

1. Durchlauf regulärer Ausdruck:
Best Case: 0,32467
Worst Case: 0,31730

2. Durchlauf regulärer Ausdruck (im Cache):
Best Case: 0,03799
Worst Case: 0,03149

2. Durchlauf der for-Schleife:
Best Case: 0,02978
Worst Case: 0,13721

Und was lernen wir aus den Ergebnissen? Das Anwenden eines neuen regulären Ausdrucks dauert 10x so lange wie das Anwenden eines Ausdrucks, der sich bereits im Cache befindet.
Warum die erste Schleife so viel länger braucht als die zweite, ist mir auch unklar. Falls dazu jemand Ideen hat, nur raus damit!

Vergleichen wir nun die Zeiten des regulären Ausdrucks (ohne Cache) mit den Zeiten der Schleifen-Variante, so erhalten wir als endgültiges Ergebnis, dass die for-Schleife in beiden Fällen die bessere Wahl ist.

Wird der Ausdruck jedoch mehrmals benötigt (oder sollen an mehreren Stellen Daten derart gesäubert/geprüft werden), so ist die Variante mit den regulären Ausdrücken schneller. Dank des Caches.

Von Seiten der Code-Eleganz ist aber sicherlich die RegEx-Variante vorzuziehen ????

Zum Nachvollziehen der Beispiele gibts natürlich alles als Archiv verpackt. Sorry, dass es eien rar-Datei ist, aber die zip wog 6,5 MB, während die rar-Datei mit 70 kb auskommt.

Da Sicherheit eine immer größere Rolle in der Webentwicklung spielt, denke ich, dass dieses Thema wichtig ist, denn wie sagte schon ein M$-Mitarbeiter in einem Buch: „All incoming data is evil“. Also auch Session-IDs!

Kommentar von daryl: Dieser Beitrag wurde exklusiv für PHP Performance von Christoph Mewes geschrieben. Falls ihr das Thema spannend findet und euch weitere Beiträge von Christoph über PHP, MySQL und was alles so dazugehört, vorstellen könnt, wäre ein Kommentar sehr erwünscht!