Nachdem die Zeit auf dem Congress mal wieder viel zu schnell rum ging und man als Engel da von den Vorträgen immer recht wenig mitbekommt, nahm ich mir die Tage einfach mal die Zeit für die diversen Vorträge. Gestern Abend war dann der Vortrag zum Thema „The Science of Insecurity“ dran.
Der Vortrag an sich war auch recht gut aufgebaut und sehr informativ aber an einer Stelle fragte man sich dann doch … was erzählen die da? Konkret meine ich den Punkt bzgl. der Nutzung von Längenfeldern. Die Aussage der Vortrageden war ungefähr „Längenfelder dürfen nicht verwendet, werden weil diese nicht kontextfreie Sprachen erzeugen.“ Nunja, stimmt nicht.
Aber der Reihe nach. Wie im Vortrag ziemlich richtig beschrieben, kann man mit verschieden komplexen Sprachklassen unterschiedlich viele Dinge anstellen. So lassen sich mit regulären Sprachen – oder oftmals auch regulären Ausdrücken genannt – nicht alle Dinge beschreiben, die eine kontextfreie oder gar eine kontextsensitive Sprache erlaubt. Soweit auch richtig im Vortrag dargestellt.
Nun möchte man, auch hier stimme ich den Vortragenden durchaus zu, möglichst einen kleinen Sprachumfang haben. D.h. wenn ich zum Prüfen meines Datenpakets für die Bestellung eines Sacks Reis bei einer Webanwendung ein Halteproblem lösen muss, um zu entscheiden, ob die Bestellung gültig ist, ist der Inhalt des Datenpaketes wahrscheinlich zu komplex gedacht. Andererseits soll man laut den Autoren aber einfache Techniken wie Längenangaben für eingebettete Daten nicht verwenden, da diese nicht kontextfrei darstellbar wären.
Und ab diesem Moment schlug mein Bullshit-Meter mit etwa 10 kBullshit aus. Denn Längenfelder sind, entgegen den Behauptungen der Vortragenden durchaus kontextfrei in einer Sprache integrierbar; sie sind im Gegenteil sogar regulär 😉
Mal ein Beispiel. Nehmen wir ein einfaches Datenpaket, welches ein Längenfeld mit 4 Bit Breite, gefolgt von 0..2`4-1 Elementen des Typs Buchstabe haben soll. Moment, ich glaube, die Sprache lässt sich durch folgende Elemente beschreiben:
(?:0(?:0(?:0(?:0|1C)|1(?:0|1C)CC)|1(?:0(?:0|1C)|1(?:0|1C)CC)CCCC)|1(?:0(?:0(?:0|1C)|1(?:0|1C)CC)|1(?:0(?:0|1C)|1(?:0|1C)CC)CCCC)CCCCCCCC)
Und siehe da, wenn wir C durch unser Element ersetzen, also z.B. . für beliebiges Zeichen, oder die Syntax für eine wohl definierte Struktur, dann hat man eine wunderbar einfache, durch eine reguläre Sprache beschriebene Datenstruktur. Und was ist daran nun bitte nicht kontextfrei?
Ach ja, wo wir gerade dabei sind: Selbst wenn man das Längenfeld mit in die Längenangabe einbezieht, lässt sich mit nur wenig Aufwand der passende reguläre, deterministisch-kontextfreie Ausdruck dafür angeben. Es brauch dazu nicht mal viel Magie, sondern einfach etwas kurzen Hirnschmalz. Wobei man im Zweifelsfall nicht mit einem regulären Ausdruck validieren möchte, sondern eher mit einem vernünftigen Parser. Aber gut, das ist wiederum eine andereGeschichte 😉
Sobald man sich auf endliche Sprachen beschränkt, was natürlich auf quasi alle existenten Protokolle zutrifft, wird der ganze Vortrag etwas moot 🙂 . Auch das Halteproblem wird in O(1) entscheidbar, wenn man nur in 4GB kodierbare Turingmaschinen betrachtet.
Gehen wir einfach mal praxisfern davon aus, dass eine Sprache wie { s_2(|w|) # w | w in {0,1}* } gemeint war, s_2 sei die Binärkodierung. Dann ist es tatsächlich nicht schwierig, über das Pumping-Lemma die Kontextfreiheit zu widerlegen und stattdessen einen akzeptierenden LBA anzugeben.
Kommentar by Kha — 29.01.2012 @ 16:16:19