Informatik

Ich habe viel Zeit an der Uni verbracht, darüber aber hier nur selten geschrieben. Mittlerweile arbeite ich seit ein paar Jahren und das Studium wird mehr und mehr eine ferne Erinnerung. Zeit, ein paar Erfahrungen festzuhalten.

Der Start war ein Informatikstudium an der TU Darmstadt, das ich vor fast genau einer Dekade abgeschlossen habe. Es war nur ein Bachelorstudium, den Master machte ich anderswo. Die Rahmenbedingungen waren gut: Die TU galt als gute Uni. Auch wenn es noch Diplomstudenten gab – einer davon wurde unser D&D-Dungeonmaster – war der Umstieg vom Diplomsystem mittlerweile fertig, es gab auch keine Wahl mehr, das schuf Fakten und Klarheit. Unsicherheit kam von den asozialen Studiengebühren, doch die wurden mir im ersten Semester erlassen und im zweiten dank Ypsilanti ganz abgeschafft. Das Studium selbst war von Seiten der Universität ziemlich toll organisiert, aber es war viel Arbeit und die Zeit insgesamt für mich ziemlich chaotisch.

Der Ablauf des Studiums

Da es keine Zulassungsbeschränkung gab saß ich am Anfang des Studiums mit sehr vielen anderen neuen Studenten in völlig überfüllten Hörsälen. Am schlimmsten war da Mathe 1, da passten die Leute nichtmal mehr auf die Stufen neben den Stühlen. Das blieb natürlich nicht so: Es würde mich sehr wundern, wenn mehr als 50% das Studium abgeschlossen haben, zudem sparten sich bald selbst viele die weitermachten die Vorlesungen.

Die Übungen waren sowieso wichtiger: In ihnen kam der Stoff vor, der dann in den Prüfungen getestet wurde. Geleitet wurden diese Übungen meist von Studenten, als Nebenjob. Alle meine Prüfungen waren schriftlich, mündliche Prüfungen gab es in anderen Kursen, aber sie waren selten und galten als schwierig. Bei allen regulären Vorlesungen gab es am Ende stattdessen eine schriftliche Prüfung. Ohne irgendeinen Tests an Scheine zu kommen war mit dem Diplomsystem so ziemlich abgeschafft worden, ging aber noch in Seminaren – da wurde dann eine Präsentation bewertet. Das war natürlich der große Stressfaktor: Dass man durch Prüfungen und nach dreimaligen Scheitern an einer Prüfung sogar durch das ganze Studium durchfallen konnte. Zum Glück blieb mir der Drittversuch erspart, aber nicht alle Prüfungen konnte ich auf Anhieb bestehen. Auch deswegen war es die oben erwähnte chaotische Zeit.

Die Massenvorlesungen am Anfang deckten die Grundthemen ab. Grundlagen der Informatik (GDI), Formale Grundlagen der Informatik (FGDI), Technische Grundlagen der Informatik (TGDI), Mathe. Davon gab es jeweils drei Kurse, nur TGDI blieb bei zweien. Nach den ersten Semestern kamen dann Kanonikfächer hinzu, "Einführung in X" – Computational Engineering, Computer Microsystems, Foundations of Computing, Human Computer Systems, Data and Knowledge Engineering und Net Centric Systems.

Gegen Ende gab es noch Wahlpflichtfächer, wo man sich aus einer Auswahl von Themen die seinen raussuchen konnte, das war die minimale Spezialisierungsmöglichkeit. Bei mir wurde das Kryptographie, Mensch-Computer-Interaktion (HCI) und Künstliche Intelligenz. Man musste ein Bachelorpraktikum abliefern, aber was da die Optionen waren krieg ich nicht mehr zusammen. War das mit der Bachelorarbeit kombiniert? Denn die galt es ganz zuletzt zu schreiben, wobei man dafür noch einen Kurs besuchen konnte und dann mit Kommilitonen den Fortschritt besprach, was sehr hilfreich war.

Studiumsinhalte

Worum ging es jeweils? Ich werde nicht alles durchgehen, will aber einen Eindruck der wichtigsten Inhalte geben.

In GDI ging es ums Bauen von Software. Am Anfang schlicht ums Programmieren: Wir lernten erst Scheme (jetzt Racket, ein LISP), dann Java, programmierten zusammen ein Spiel und lernten über die Komplexität von Algorithmen (O-Notation). Und das war alles GDI 1. An spätere Inhalte erinnere ich mich weniger gut. Ein kurzer Abschnitt wurde in C programmiert. Aber wir müssen auch Stoff über Wasserfallmodelle, Pflichtenhefte, Designpatterns und UML gehört haben – das meiste davon war anders als die erste Vorlesung im Nachhinein irrelevant, aber gut zu wissen dass es das mal gab. Spezielle Algorithmen wie Quicksort kamen später auch vor, das war schon hilfreicher, auch Datenstrukturen wie Bäume waren ein wichtiges und nützliches Thema.

FGDI war Logik. Meine Anleitungen um einen Zustandsautomaten zu mimieren und zum Markierungsalgorithmus stammen daher, ob das nun FGDI 1 oder 2 war ist mir unklar. Anfangs ging es um Grundlagen wie Prädikatenlogik. Ich habe es gehasst, die Artikel landeten im Blog um mir Inhalte ins Hirn zu prügeln und anderen zu helfen. Ich muss aber zugeben, dass es später hilfreich und notwendig war solche formalen Logikausdrücke lesen zu können. FGDI 3 war etwas anders: Da ging es um die Verifikation von Programmen. Die wurden dafür in einer Spezialsprache geschrieben und ihre Richtigkeit musste dann Annahme für Annahme bewiesen werden. Auf der einen Seite absurd komplett nicht praxistauglich, auf der anderen konnte man sich vorstellen, wie das irgendwann doch praxistauglich werden könnte, es hieß sogar Prozessorhersteller würden das bereits machen (und später las ich, sie hätten das größtenteils aufgegeben).

TGDI hasste ich nicht, aber diese technischen Grundlagen hatte ich nie gehabt. Und-, Oder-, XOR-Schaltungen, Verilog und damit irgendwas anfangen – ich schnappte ein paar Grundlagen auf und kam durch die Prüfung. Im zweiten Kurs ging es dann mehr um Prozessorarchitekturen. Ob wir hier oder in GDI in Assembler programmiert haben krieg ich nicht mehr zusammen, aber das war auf jeden Fall spaßig.

Bei Mathe kann ich kaum noch auch nur die Inhalt benennen. Mathe 1 und 2 war ein wilder Mischmasch von irgendwelchen Mathematikkenntnissen – irgendwas mit Reihen, Ableitungen, Beweisen. Mathe 3 war Computation (und Statistik?), also Mathematik vom Computer lösen lassen, was oft andere Ansätze braucht. Das hatte etwas Berechtigung. Aber Mathematik wie es dort zuvor gemacht wurde war ein pures Aussiebefach und vermittelte wenig, was irgendwie hängenblieb oder ich bisher nochmal gebraucht hätte. Teilweise wiederholten sich Inhalte in den spezialisierteren Fächern, die waren dann relevant und gut sie schonmal gehört zu haben, Gruppen beispielsweise. Aber hätte es kein Siebfach gebraucht hätte man Mathe schlicht weglassen und die Inhalte dort lehren können wo sie benutzt wurden.

Bei den "Einführung in X"-Fächern ging es um ganz verschiedene Themen. Bis jetzt lernten wir ja nur allgemeine Grundlagen. Net Centric Systems z.B. konnte dann über Netzwerke und über das Internet reden. Es ging auch darum grob die Forschungsbereiche der Informatik abbilden. Die Wahlpflichtfächer gingen da dann später etwas tiefer, für die, die Interesse an einem bestimmten Thema hatten.

Besondere Inhalte und Lektionen

Besonders prägend war Grundlagen der Informatik. Wegen dem Fach mit seinen Inhalten waren die meisten Studenten in dem Studiengang, mich eingeschlossen. Tatsächlich lernte man dort dann auch viele Konzepte, die für jeden Programmierer völlig relevant sind: Objektorientierte und funktionale Programmierung, Datentypen, Rekursion, Komplexität, aber auch generell das Entwerfen von und Arbeiten mit Algorithmen sowie das Planen von Programmen.

Trotz diesem praktischen Aspekt des Studiums wurde gepredigt, dass ein Informatiker Konzepte lernt und die dann in jeder beliebigen Programmiersprache anwenden kann. Ich merkte später: Das stimmt nur so halb. Um abstrakte Konzepte wirklich anzuwenden muss man die Sprache beherrschen, das braucht Übung mit ihr. Bevor ich Ruby lernte – eigenständig im Master – konnte ich zum Beispiel faktisch kaum Serveranwendungen bauen, völlig egal ob ich die Konzepte drauf hatte. Aber es stimmt, dass sich viel übertragen lässt, und zwischen ähnlichen Sprachen zu wechseln ist kein großes Problem. Es stimmt aber auch der Vorwurf am Hochschulstudium, dass selbst das Bachelorstudium noch zu abstrakt ist um den Studenten wirklich das Programmieren beizubringen. Das müssen sie aus eigenem Antrieb zusätzlich oder später machen, selbst GDI mit seinem Praxisteil schafft nur wenige Grundlagen. Oder zumindest war das damals so.

Was stimmte: Die Predigt vom Dekan ziemlich am Anfang des Studiums, dass er keinen von uns in gewöhnlichen Studentenjobs sehen will, wir seien alle jetzt schon als Programmierer beschäftigbar. Naja, vielleicht galt das nicht für alle, aber tatsächlich waren die Anfangsinhalte die wichtigsten und Firmen hätte mit den motivierteren Studenten definitiv arbeiten können.

Wieviel weiteres nützliches man aus dem Studium ziehen konnte hing aber auch von den Wahlpflichtfächern ab. Meine Themenwahl sehe ich heute noch mit Wohlwollen.

Künstliche Intelligenz war vor dem aktuellen Boom, neuronale Netze ein veraltetes Nischenthema. Trotzdem oder gerade deswegen war die Vorlesung super – denn KI hat im Kern das Thema, das mich an Informatik anfangs so faszinierte, nämlich wie man mit Algorithmen Probleme lösen kann. Der auf einem Infotag präsentierte Dijkstra-Algorithmus, der ein Wegfindeproblem lösen kann, hatte damals erst den Ausschlag gegeben dieses Studium zu wählen. Ich sehe KI als die komprimierte Essenz der Informatik, entsprechend spannend war die Vorlesung. Wobei ich wenig konkrete Inhalte aus ihr bisher anwenden konnte, wohl aber viele Ansätze.

Kryptographie zu belegen war überraschend lohnenswert, weil IT-Sicherheit in jedem Projekt ein Thema ist und die Grundlagen von damals mich immer noch tragen. Zudem war der Professor Johannes Buchmann, der es einfach drauf hatte die Vorlesung interessant und verständlich zu halten. Ich glaube, das war auch die Vorlesung für die ich RSA in Bash implementierte, was ein bisschen zeigt wie locker man das Thema angehen konnte.

Außerdem war HCI ein prägender Kurs zu Usability. Als Informatiker fand ich das besonders toll, weil es einen Weg vorwärts versprach wie man alles andere anwenden konnte. Nicht nur viel wissen, sondern auch herausfinden können was man überhaupt bauen soll und womit Nutzer umgehen können. Damit wollte ich weitermachen, also wurde das Thema mein Masterstudium – was nicht ganz klappte, aber dazu später mal mehr.

Und schließlich, etwas allgemeiner: Diese übliche Prophezeiung, dass im Studium viele gute Leute zusammenkommen und die dann auch oft besser sind als du, in Darmstadt stimmte das für mich. Auch eine Erfahrung.

Leben als Student in Darmstadt

Bild von lapping auf Pixabay

Nach etwas Eingewöhnungszeit wurde das Studieren zum Alltag. Ich besuchte die Vorlesungen fast immer, nahm an den Übungen teil, und füllte die verbliebene Zeit mit anderen Dingen.

Am Anfang hatte ich keine Zeit über, denn anfangs bin ich von meinem Heimatort nach Darmstadt gependelt, was großer Mist war. Dass ich seitdem mit einer kurzen Ausnahme nie wieder gependelt bin ist kein Zufall. Erstens kriegte ich anfangs vom Studentenleben wenig mit, zweitens fühlte ich mich wegen der unsicheren Heimreise in Darmstadt nicht wohl, drittens schadete es der Motivation an den Vorlesungen und Übungen teilzunehmen und damit dem Studium. Gerade kommt mir der Gedanke: Man konnte beides damals nicht von Zuhause machen, vielleicht ginge zumindest die fachliche Seite mittlerweile trotz der Distanz etwas besser?

Später wohnte ich im Studentenheim, das half sehr. Es gab dort aber die absurde Situation, pfeilschnelles Internet zu haben, aber nur 10 oder 20 GB Traffic, danach wurde die Leitung für den Monat abgeschaltet. Ich hoffe, das ist heute Geschichte – ah, sie sind jetzt bei 120GB, das sind immer noch nur 2 AAA-Spiele. Peinlich. Und es half anfangs nicht gerade beim Sicherheitsgefühl in der neuen Heimat.

Studentenjobs an der Uni dagegen waren eine gute Sache für mich. Eine Weile war ich Mentor für Erstsemester, ihr einer Pflichttermin. Diese Tätigkeit hatte das außerhalb der üblichen Anliegen der Menties so gar nichts mit Informatik zu tun, das war eine interessante Erfahrung. Später als Tutor in Übungen lernte ich immerhin noch, wie schwer diese Rolle ist und wieviel man von dem Stoff auch wieder vergessen hat.

In meiner Freizeit verbrachte ich als Informatiker viel Zeit vor dem Rechner, klar. Von Darmstadt habe ich nicht viel mitbekommen, um in Cafes rumzusitzen zum Beispiel hätte mir auch schlicht das Geld gefehlt. Aber so ein bisschen Studentenleben nahm ich doch mit: Mit Jugger eine ungewöhnliche Sportart; Serien bekamen durch das Studentennetzwerk eine neue Bedeutung, Filme ebenso durch den Mathefilmabend (mit schlechten Filmen) und dem Studentenkino im Audimax (mit besseren); auf Vorschlag einer Kommilitonin lernte ich mit ihr Salsa, ich war und bin darin untalentiert, aber es war aus Gründen später eine der wichtigsten Sachen die ich hätte lernen können. Die D&D-Gruppe erwähnte ich oben über den Spielemeister, eine Brettspielgruppe fand sich auch, meine erste. Ein paar Klischees erlebte ich zudem: Den sich nie als nützlich erweisenden Sprachkurs, krude Charaktere in WGs, sogar eine für mich gescheiterte WG, ein paar wenige Studentenfeiern.

Man kann sich ja gerade bei Informatik auf den Standpunkt stellen, dass das Studium nicht lohnt. Einfach alles relevante online lernen, oder eine Ausbildung im Unternehmen machen und so früh wie möglich mit dem Arbeiten anfangen, beides bringe am Ende durch die gesparte Zeit mehr Gehalt. Stimmt monetär vielleicht. Aber wenn nicht gerade eine Pandemie alles sowieso blockiert, dann verpasst man so eben auch dieses Leben. Das zwar bei all der Arbeit, dem geringen Einkommen und dem dauernden Prüfungsstress auch nicht immer toll war, aber im Nachhinein echt keine schlechte Zeit.

Fazit

Man wurde im Informatikstudium mit Stoff bombardiert. Das schaffte viele Grundlagen, um Neues zu verstehen und auch anzuwenden. So brauchte ich beispielsweise diesen Schubs, um die praktische Funktion von Datenbanken zu verstehen und in meine Projekte einbauen zu können. Generell wurde alles was irgendwie praxisrelevant war besonders interessant: Beispielsweise auch der Bayes-Algorithmus wegen meinem Bayes-Spamblockplugin. Aber das funktionierte auch andersrum: Praktisch alles, für das ich einen Zugang finden konnte – was mir nicht komplett unergründlich war – hatte in den Folgejahren nochmal irgendwie eine Relevanz. Selbst manche der Mathematikkenntnisse, sogar die Logikformeln aus den formalen Grundlagen erleichterten später mindestens das Lesen mancher Veröffentlichungen.

Gut, manches war zu speziell oder ist mittlerweile veraltet. Das Wasserfallmodell als Entwicklungsmodell mit Lasten und Pflichtenheft zum Beispiel – klar gibt es das noch, aber es ist aus gutem Grund nicht der Standard. UML-Diagramme hätte man auch weniger machen können, damit Programme zu planen wurde sicher nicht die Zukunft der Programmierung. Wobei: No-Code-Programmierung baut ja irgendwo schon auf den gleichen Ideen auf, dafür gibt es derzeit verstärkt Aufmerksamkeit. Bei den Software-Designpatterns weiß ich nicht mehr, ob meine bis heute anhaltende kritische Haltung vom Dozent vermittelt wurde oder ob ich damals schon ihre Probleme wahrnahm. Aber das Thema zeigt die Gefahr, dass man an der Uni auch Dinge lernen kann, die einem Programmierer in der Praxis eher schaden – wie das übertriebene Anwenden von Desingpatterns.

Doch insgesamt: Für jemanden, der später Software bauen wollte, war das Informatikstudium in Darmstadt eine gute Wahl. Dass ich mir ein eigenes Bachelorarbeitsthema aussuchen konnte, direkt einen tollen Betreuer fand und daran dann auch noch bei der Telekom arbeiten konnte war dann noch ein guter Endpunkt eines guten Studiums. Rückblickend muss ich auch loben, wie gut die Uni ausgestattet war (schon der PC-Pool im Keller mit sauber funktionierenden Linux-Computern), wie fähig die Professoren Vorlesungen hielten und wie gut das Studium organisiert war, abgesehen nur vom damals fast unschaffbar überfrachteten dritten Semester.

Müsste ich nochmal von vorne anfangen, würde ich direkt wieder dieses Studium wählen und auch wieder nach Darmstadt gehen. Stattdessen ging es mit einem Master weiter, über den es auch einiges zu erzählen gibt.

direkt

Die Argumentation im Video ist nicht unbedingt neu, wenn man etwas im Thema ist. Aber gerade deswegen ist es ein anschauliches Beispiel für Planungsfehler, die möglicherweise dem Spiel geschadet haben.

Vorab: Sie ist auch kritisierbar. Ein Spiel wie Cyberpunk kann man nicht von Anfang an in einem veröffentlichbaren Zustand halten. Auch die verlinkte Präsentation zu Sea of Thieves ist da kein echtes Gegenargument, da wurde dieses Entwicklungsmodell nur teilweise adoptiert (immerhin!), und das Spiel ist viel kleiner und war am Ende wohl auch nicht besonders gut. Das geht mit Werkzeugen, bei denen schon ein kleiner Teil des geplanten nützlich wäre. Vielleicht bei Spielen mit einer sehr simplen Grafik, Mechanik und Frust-Spaß-Schleife (dass die bei Sea of Thieves zu simpel ist war in Tests der größte Kritikpunkt). Aber es geht nicht mit storygetriebenen echten AAA-Spielen, die bei ihrer Vollständigkeit eine hohe Messlatte erreichen müssen um auch nur ein bisschen spaßig zu sein.

Außerdem hatte CD Projekt ja ursprünglich kein Releasedatum genannt, ist also anfangs der im Video vertretenen Theorie gefolgt. Das war sicher eben um flexibel sein zu können. Interessant wäre eher ein Blick auf die Dynamik, die das Entwicklerstudio trotz dieses Starts zum verfrühten und auf alten Konsolen wohl nahezu ungetesten Release verleiteten. Alternativen gab es nicht viele, die angesprochene, nur auf den alten oder neuen Konsolen zu veröffentlichen, war in dem Moment keine Option mehr als einmal etwas anderes angekündigt worden war, auch ohne die Ankündigung wäre es nach dem Release der neuen Konsolen nicht machbar gewesen. Denn: Zu wenige Leute haben die neuen Konsolen bereits, aber die neuen nicht zu beliefern wäre für jedes AAA-Spiel ein PR-Desaster. Tatsächlich war die veröffentlichte Version auch die, die auf die Last-Gen-Konsolen zugeschnitten sein sollte. Was wirklich schiefging werden erst später gute Reportagen wie der zu Andromeda erklären können, bis jetzt gibt es nur Erklärungsansätze.

Die Argumentation des Youtubers ist also völlig daneben. Faszinierenderweise ist sie gleichzeitig völlig richtig. Denn die Grundargumentation im Video passt. Zumindest im letzten Jahr der Entwicklung sind die Entwickler nach allem was bekannt ist genau in die beschriebene Planungsfalle gelaufen. Gleichzeitig einen festen (fast, einmal wurde es ja nochmal verschoben) Termin treffen zu wollen ohne das Spiel nach all den Trailern deutlich verschlanken zu können war keine gewinnbare Situation. Entwicklerteams vergrößern ist, richtig, keine Hilfe. Da ging also etwas wie vom Youtuber beschrieben komplett schief. Das zeigt der Crunch: Scheinbar wurde wider besseren Wissens gehofft, Entwickler länger als 4 bis 5 Tage lange Stunden arbeiten zu lassen verkürze die Entwicklungszeit. Eine Verzweiflungsentscheidung, die offensichtlich verkehrt ist, denn ausgebrannte Entwickler werden höchstens grantig aber keinesfalls schneller. Das weiß eigentlich jeder, es trotzdem zu versuchen ist genau das kritisierte Wunschdenken.
Wenn das anfängliche Scheitern Cyberpunks dazu führt, dass mehr Firmen die Unsinnigkeit von Crunchentwicklung erkennen, hätte das ganze nochmal was gutes.

Objekte die immutable sind können in keiner Weise modifiziert werden. Doch was bringt das?

Das Konzept

Viele Sprachen – nicht alle natürlich – unterstützen das Konzept, mal für alle Datentypen, mal nur für spezielle. Aber grundsätzlich könnte es so aussehen:

class Car
   immutable doors = ['door1', 'door2']
end

Wenn der Entwickler sich dann später ein entsprechendes Objekt erstellt, dann kann er das doors-Attribut nicht ändern:

myCar = new Car();
myCar.doors.add('door3')   #=> Error!

Immutability ist ein Konzept, das man besonders oft bei funktionalen Programmiersprachen finden wird. Wer sich Gedanken über Seiteneffekte macht, der wird auch Immutability bedacht haben. Es kann auch massiv dem Compiler helfen, wenn Objekte entsprechend markiert sind und er so weiß, dass diese Objekte sich nie ändern können. Programme werden so schneller oder sicherer.

Wobei, von wegen funktional, const geht ja in eine ganz ähnliche Richtung.

Ein Anwendungsfall

Doch hilft es dem Entwickler? Das allerwichtigste ist Entwicklerzeit, -effizienz und -komfort. Immutability schadet dabei oft. Wenn ich als Entwickler ein geschütztes Attribut ändern will, habe ich wahrscheinlich einen guten Grund. Wenn ich jetzt nur des Compilers wegen ein neues angepasste Objekt erstellen und am besten noch einige Attribute kopieren muss, dann stimmen die Prioritäten nicht.

Aber jetzt lief ich in diesen Fall: Ich hatte eine Liste. Und irgendwas veränderte diese Liste. Und zwar wurde der letzte Eintrag in ihr länger. Doch nirgends in meinem Programm gab es eine solche Zuweisung, zumindest keine die eindeutig zu erkennen war.

Was wohl passiert war: Es gab ein Fold.

newList = originalList;
targetMap = newList.fold({}, (prev, element) => prev..addAll(element));

Und dazu einige andere solcher Akkumulatoren, die meine Originalliste zusammenfassten (die in Wirklichkeit auch keine einfache Liste war, sondern eine Liste von Listen von Ojekten in einem Elternobjekt). Und irgendeiner davon hatte als Nebeneffekt, dass die Originalliste – denn in dieser Sprache werden meist Referenzen übergeben – ebenfalls verändert wurde.

Die Lösung: Die Liste als immutable markieren.

Die Akkumulatorfunktionen wie das fold funktionierten immer noch. Aber anstatt die Originalliste zu verändern, erstellten sie sich automatisch ihre eigene Kopie. Die Originalliste blieb unverändert, der Bug war gefixt.

Es ist also keinesfalls so, dass Immutability nur den Code verkompliziert. Im Gegenteil, richtig eingesetzt kann es ein Programm wesentlich einfacher zu verstehen machen, dann dient das Konzept dem Entwickler. Besonders in Sprachen, die Referenzen einsetzen anstatt direkt Werte zu kopieren.

Ich mochte diesen Vortrag. Man muss den Anfang mit seinem "das wichtigste Video ever" ignorieren, aber danach hat es ein paar gute Punkte (die sich nicht alle im zugehörigen Artikel finden). Es wird ziemlich überzeugend erklärt, was die Schwachstellen der objektorierentierten Programmierung sind: Dass dessen Ideal nicht erreicht werden kann und gar kein Ideal ist, warum Objektarchitekturen gerne ausufern und wieso man oft an Fragen gelangt, die nicht entscheidbar sind. Es sind zudem ein paar gute praktische Tricks drin die man in seinen Code einbauen kann, auch wenn die meisten nicht gerade neu sind. Aber sie sind gut gebündelt und im Kontext des Hauptarguments angemessen, lange Funktionen zu rechtfertigen und gekapselte lokale Funktionen ins Spiel zu bringen ist erfrischend.

Vor allem wird betont, dass Abstraktion nicht etwas positives ist, sondern automatisch Komplexität bedeutet, was sehr schlecht ist. Und das ist mindestens so richtig und wichtig wie es oft ignoriert wird. Es kollidiert mit vielem was gelehrt wird, aber ganz besonders mit den Paradigmen aus der Enterprise-Ecke. Man kann diesen Ansatz auch mit vielen gegenteiligen Entwicklungen im Javascriptuniversum vergleichen und wird ihn bestätigt finden.

Allerdings, was es für mich verdächtig komfortabel macht: Ich sehe einige Überschneidungen mit meiner angestrebten Programmarchitektur, die ich vor ein paar Jahren hier im Blog beschrieben habe und die sich seitdem nicht groß geändert hat. Wobei ich meinen Code wesentlich objektorientierter halte als es Brian Will (von dem der Vortrag stammt) wahrscheinlich gut fände. Doch wo der Code letztens Endes lebt ist in der Argumentation nicht so wichtig, solange er nicht unnötig abstrakt und über das Programm verteilt ist, und das war so ziemlich mein Hauptziel. Dieser Aspekt und die funktionalen Anleihen, die ich mittlerweile gerne einbaue, passen gut zu den Ideen des Videos.

Vor kurzem schrieb ich darüber, wie ich mit dem SAX-Parser besser mit XML-Dateien umgehen konnte. Besser bedeutete, mit weniger Speicherbedarf schneller die gesuchten Informationen aus teils relativ großen XML-Dateien zu holen. Es half, aber der Server hatte immer noch spürbare Last durch die anderen Datenquellen: Den CSV-Dateien. Sie benutzen manche der Datenausgeber statt XML, und auch bei ihnen führte das naive Vorgehen zu extremen Speicher- und Prozessorbedarf.

Das naive Vorgehen war grob so:

hardwares = Database.instance.getHardwares
hardwares.each do |hardware|
    csv = cache.getset('csvApi') do
        csvGz = open("https://url/zur/csv.gz")
        unzippedCsv = Zlib::GzipReader.new(csvGz).read
        csv = CSV.parse(unzippedCsv, :headers => true)
        csv
    end
    return csv.detect{|line| line['id'] == hardware.id }
end

Es gab also ein Array mit den Bezugsobjekten, zu denen die Zeile mit ihrer ID aus der CSV-Datei gezogen werden soll. Optimiert ist da bereits, dass die CSV-Datei nicht mehrfach heruntergeladen wird. Dafür sorgt der lru-cache.

Wie geht es besser?

1. Speichereffizienter parsen

Der erste Schritt ist das Parsen der CSV-Datei. Der bisherige Code macht das in einem Rutsch und baut – ähnlich wie bei XML-Dateien – ein CSV-Objekt. Wenn wir stattdessen Zeile für Zeile durchgehen entsteht eine Chance, den Speicherbedarf zu reduzieren. Dalibor Nasevic hat dazu Codebeispiele und Benchmarkergebnisse. Der Code ändert sich so:

unzippedCsv = Zlib::GzipReader.new(csvGz)
csvFile = CSV.new(unzippedCsv, headers: true)
while line = csvFile.shift
     # do something
end

Der GzipReader liest nicht mehr die Datei auf einmal in den Speicher, mit diesem neuen Startpunkt geht der CSV-Parser zeilenweise durch die Datei. Wenn wir jetzt einfach das CSV-Objekt nachbauen bringt das nicht viel, aber es gibt uns die Möglichkeit etwas besseres zu bauen.

2. Mit fastcsv schneller parsen

Doch bleiben wir erstmal beim Parsen selbst. Derzeit benutzt der Code das in Ruby integrierte CSV-Modul. Doch es gibt Alternativen, insbesondere fastcsv. Das Gem kann in vielen Fällen das normale CSV-Modul direkt ersetzen und war in meinen Tests etwa doppelt so schnell.

require 'fastcsv'
csvFile = FastCSV.new(unzippedCsv, headers: true)

Nett, aber das Parsen der CSV-Datei war gar nicht das Problem. Das sparte ein paar Sekunden. Das eigentliche Problem war das spätere Durchsuchen des erstellten CSV-Objekts.

3. Mit Hash nicht suchen, sondern nachschlagen

Das ist eine Optimierung, die in jeder Sprache funktionieren wird.

Wenn CSV.parse ein CSV-Objekt erstellt, ist das im Grunde ein großes Array mit Arrays (headers: false) oder Hashs (headers: true) in den Arrayeinträgen. Entsprechend durchsucht der Code von oben dieses Array mit dem üblichen Enumerable.detect. Doch das bedeutet, dass für jedes Suchobjekt die CSV-Struktur durchgegangen werden muss, bis etwas gefunden wurde. Oder bis die Struktur durch ist und eben nichts gefunden wurde. Wenn es nur eine Datenstruktur gäbe, die für eine ID direkt die passende Zeile ausgeben könnte…

Die gibt es natürlich, genau das ist in Ruby der Hash. Da wir jetzt zeilenweise durch die CSV-Datei durchgehen und die Struktur selbst bauen können wir sie nutzen:

csv = cache.getset('csvApi') do
    …
    csv = {}
    while line = csvFile.shift
        csv[line['id']] = line
    end
    csv
end
return csv[hardware.id]

Das hier ist die große Optimierung. Anstatt mehrfach durch die riesige Datenmenge zu stöbern am Anfang mit etwas Mehraufwand die Hashstruktur zu erstellen spart danach so viel Zeit bei jedem Suchvorgang, dass minuten- bis stundenlange Prozesse in wenigen Sekunden fertig werden.

4. Ungenutzte Datenfelder rausschmeißen

Moment, da gibt es noch eine mögliche Optimierung, wieder völlig unabhängig von Ruby. Eventuell braucht es später gar nicht alle Felder, die in der CSV-Datei gespeichert sind. Vielleicht wird später nur nach price und available geschaut. Wenn dem so ist, dann ist genau hier der Moment die überflüssigen Felder zu entfernen und so den Speicherbedarf zu senken:

while line = csvFile.shift
    csv[line['id']] = line.to_h.keep_if{|k, _| k == 'price' || k == 'available' }
end

Die Kombination dieser vier Schritte ist sehr mächtig. Was vorher viele Minuten rödelte und Prozessorkerne voll auslastete ist in ein paar Sekunden erledigt. Aber es ist ja auch ein Idealfall. Es gab genau eine ID, wir in einer Hashmap als Key nutzen und dann nachschlagen konnten. Was, wenn es mehr als einen Key gibt?

5. SQLite für mehrere IDs

In meinem Anwendungsfall gab es manchmal neben der id noch die sku, also einen zweiten Key. Dann reicht ein Hash nicht, denn es gibt keine mir bekannte Möglichkeit, einen zweiten Key einzusetzen. Klar, wir könnten einen zweiten Hash erstellen. Aber würde das nicht den Speicherbedarf verdoppeln? Nein, es wäre besser einen zweiten Key als Index über die alte Hashmap zu legen. In Ruby wüsste ich nicht wie das geht (wenn du schon: Ein Kommentar wäre klasse!). Aber SQLite macht das mit links und ist in jeder Sprache verfügbar.

Die Idee also ist: Statt einer Hashmap erstellen wir eine SQLite-Datenbank im Arbeitsspeicher. Primary Key wird die id, aber für die sku baut SQLite einen Index. Das Durchsuchen geht dann mit ein bisschen SQL. YAML serialisiert die CSV-Zeile, die im Zweifel auch wieder wie in Schritt 4 speicheroptimiert werden könnte.

csv = cache.getset('csvApi') do
    …
    csvFile = FastCSV.new(result, :headers => true)
    db = SQLite3::Database.new(':memory:')
    db.execute "CREATE TABLE csv(id TEXT PRIMARY KEY, sku TEXT, line TEXT)"
    while line = csv.shift
        db.execute("INSERT OR IGNORE INTO csv(id, sku, line) VALUES(?, ?, ?)", line['id'], line['sku'], YAML::dump(line))
    end
    db.execute "CREATE INDEX csv_sku ON csv(sku)"
    db.execute "ANALYZE"
    db
end        

row = csv.execute("SELECT line FROM csv WHERE id = ?", hardware.id).first
unless row
    row = csv.execute("SELECT line FROM csv WHERE sku = ?", hardware.sku).first
end

if row
    return YAML::load(row[0])
end

SQLite ist unheimlich schnell, die CSV-Datei wird in sekundenschnelle durchsucht sein, je nach Größe natürlich.

Fazit

Wenn man es mal richtig macht… Ich fand das ein gutes Beispiel für einen Anwendungsfall von Informatik-Grundkenntnissen. Statt ein Array zu durchsuchen die Datenstruktur zu ändern und eine Hashmap zu nehmen ist Grundlagenstoff des Studiums, Standardbeispiel für O(1) statt O(n). Aber ich brauchte einen Moment um zu erkennen, dass das hier möglich ist, das komfortable CSV.parse hatte mir das versteckt. SQLite einzubauen und nach einem schnelleren Gem zu schauen ist dann vielleicht etwas mehr aus praktischer Erfahrung gezogen, aber liegt wenn man mal optimiert und und nach dem Datenbankkurs auch nicht mehr fern.

Mir hat dabei auch geholfen, diese Aufgabe als eigenes Projekt zu betrachten. Ursprünglich war das nur eine kleine Ecke im Code des Überprojekts (pc-kombo), schnell mal gebaut, abgewandelt aus Code der eine REST-API nach den Informationen fragt (wo solche Optimierungen nicht möglich sind). Jetzt ist die Ecke ausgelagert in ihr eigenes Git-Repository und der Code ist auf genau diese Aufgabe reduziert. Das macht es einfacher, solche Optimierungsmöglichkeiten zu sehen.

Auf jeden Fall lohnt sich der Aufwand. Zusammen mit der Reduzierung der Last durch XML-Dateien kann ich den großen Server bald wieder abschalten, der nach dem Scaleway-Umzug die temporäre Heimat dieses Mikroservice wurde. Aus dem Mikroservice wurde jetzt tatsächlich auch ein kleines Programm, das auf schmalerer Hardware wird laufen können. Das reduziert die Strom- oder die Hostingkosten dann schnell um ein paar hundert Euro im Jahr.

Weil die Übermedien nicht wissen was ein Angreifermodell ist, verfallen sie in einer Analyse eines Panorama-Interviews in den Panikmodus. Ein Informant sei unzureichend geschützt worden, Panorama sei unfähig. Der Themenkomplex ist in der Nähe meiner Doktorarbeit, daher ein paar Erklärungen hierzu.

Es geht um den Cum-Ex-Skandal, ein wirklich unfassbar dreister Betrug des Kapitals, bei dem der Staat sich über Jahrzehnte willfährig ausnehmen ließ. Der Interviewte ist ein Insider und zukünftiger Kronzeuge. Dementsprechend soll er anonym bleiben: Er fürchtet seine Mittäter und Konsequenzen im Privaten. Panorama hat also sein Gesicht verborgen und seine Stimme verzerrt und ihn so vor der Kamera unkenntlich gemacht.

Die Übermedien meinen das reicht nicht:

Doch dieser Schutz ist unzureichend. Und das wissen Journalisten spätestens seit dem Frühjahr 2014. Auf der Forensiker-Tagung im Mai in Münster wurde nämlich die Methode offenbar, mit der Ermittler durch Analyse der elektrischen Netzfrequenz vermummte und verkleidete Informanten, deren Stimme verzerrt wurde, enttarnen können.

Die Aussage stimmt, und doch ist ihre Folgerung falsch. Warum ist interessant.

Die Netzfrequenzanalyse betrifft erstmal genau solche Interviewszenarios. Die Netzfrequenz ist nicht mehr stabil, ihre Abweichung wird dauernd protokolliert. Sie lässt sich auch aus Aufnahmen wie der Interviewvideoaufnahme ablesen. Wann eine solche Aufnahme gemacht wurde lässt sich damit also bestimmen, man schaut einfach nach wann die Abweichung im Video mit der protokollierten übereinstimmt. Die Uebermedien glauben man würde auch den Ort herauslesen können – ich glaube das stimmt nicht, ich bin mir aber nicht ganz sicher (für diesen Artikel ist es egal).

Wenn man aber den Aufnahmezeitpunkt hat und den Ort bestimmen kann – was ein Geheimdienst ja auch mit anderen Methoden hinkriegt – dann kann ein entsprechend ausgestatteter Akteur den Interviewten identifizieren. Er muss nur Überwachungskameras auswerten und von den paar tausend Leuten, die so wahrscheinlich gefunden werden, über ihre Profile mögliche Träger der Information herauspicken. Einer der so gefundenen ist der Informant. Ein Geheimdienst macht dann was er eben so macht, NSU-Zeugen landen in brennenden Autos, Feinde Putins werden vergiftet, es bleibt sicher immer sehr stilvoll.

Warum also haben die Übermedien nicht recht mit der Anschuldigung, warum hat Panorama hier nicht furchtbar geschlampt? Das liegt schlicht am Angreifermodell und am Schutzziel.

Der Interviewte hier muss nicht umfassend vor Geheimdiensten geschützt werden. Er ist dem System bereits bekannt, er ist ein Kronzeuge, seine Aussage wird bald öffentlich und seine Identität dann bekannt sein. Es geht nur um Schutz vor den Mittätern. Das sind seine Kollegen, seine Nachbarn vielleicht, aber es sind keine Geheimdienste. Wären die hier verwickelt wüssten sie seine Identität über seine Kronzeugenrolle sowieso schon und hätten sich schon eine passende Eliminierungsmethode ausgesucht.

Das ist also praktisch der umgekehrter Fall von "Die US-Regierung wird uns nicht mit Musketen angreifen."

Meine Nachbarn sind nett, intelligent und fähig, aber sie haben nicht die Ressourcen des BND an der Hand. Sie würden in einem solchen Fall keine Überwachungsvideos auswerten und tausende Profile anlegen, sie würden wahrscheinlich die Netzfrequenzanalye nichtmal kennen. Es ist praktisch gegeben, dass dies im Fall dieses Informanten genauso ist. Denn die Mittäter sind ja wohl kaum Geheimdienste, sondern Privatpersonen – eventuell sehr reiche und skrupellose Banker, schlimm genug, aber doch keine KGB-Agenten. Damit fällt die Netzfrequenzanalyse als Angriffsvektor komplett raus. Ohne sie sind Verfremdung von Gesicht und Stimme dann auch ausreichend, um für den kurzen Zeitraum bis zur Kronzeugenaussage die Anonymität des Insiders zu wahren.

Denn interessanterweise stimmt dieser stark klingende Satz eben nicht:

Doch ein bisschen anonym ist problematisch. Das funktioniert genauso wenig wie ein bisschen schwanger.

Ein bisschen schwanger geht nicht, ein bisschen anonym geht durchaus. Das ist nicht ganz intuitiv, aber Stand der Anonymitätsforschung. Denn praktisch immer ist Anonymität eben doch ein Grad und nicht absolut.

Ein Beispiel: Wenn ein geehrter Leser dieses Artikels hierdrunter einen fiesen Kommentar schreibt und einen falschen Namen benutzt ist er wahrscheinlich mir gegenüber anonym. Ich habe kaum Möglichkeiten die civil identity dieses fiktiven Kommentators zu finden, dann zu ihm zu fahren und ihm eins auf die Nase zu hauen. Glücklicherweise ist das auch nie nötig, meine Kommentatoren immer nett.
Jetzt nehmen wir aber mal an der Kommentator schrieb nicht einfach einen fiesen Kommentar, sondern kündigt einen islamistischen Terrorangriff an. Ich habe zwar immer noch keine Methode ihn aufzuspüren. Aber so etwas würde die Polizei und die Geheimdienste alarmieren, und die könnten dann über die Vorratsdatenspeicherung den Kommentatorterroristen ganz schnell identifizieren. Hat er technische Vorkehrungen getroffen geht es vielleicht etwas weniger schnell, aber es gibt im Internet kaum absolute Anonymität.

Das gleiche gilt auch bei anderen Kommunikationswegen. In fast jeder Situation kann man Leute finden, gegen die ein vermummter Kommunikationsteilnehmer anonym ist, aber von dem andere Stellen durchaus die Identität kennen oder kennen könnten.

Das Foto hier taugt dafür als zweites Beispiel. Ich weiß nicht wer das ist. Gegenüber dem Großteil des Internets ist die junge Dame anonym. Aber der Fotograf dürfte wissen wer das ist, ein entsprechend begabter Detektiv kann ihre Identität wohl aufdecken. Und ihre Mutter würde sie wohl auch erkennen.

Deshalb ist bei solch einer Situation wie dem Panorama-Interview der Kontext so wichtig. Er bestimmt das Angreifermodell: Wer wird die Identität aufdecken wollen und welche Fähigkeiten hat er dafür? Dementsprechend sind ganz unterschiedliche Anonymitätsgrade erforderlich. Man kann sich auch überlegen: Wie schlimm wäre es, wenn die Identität bekannt würde? Auch das kann in die Entscheidung reinfließen.

Den Aussagen des Chefredakteus zufolge wurde genau das sorgfältig und richtig gemacht. Die Übermedien hätten seine Aussagen nicht nur zitieren sollen, sondern sie hätten Beachtung verdient gehabt. Denn mit dem richtigen Hintergrundwissen widerlegen sie alleine komplett den dort lancierten Artikel. Aber ich will die Übermedien gar nicht zu stark kritisieren: Anonymität ist ein erstaunlich kompliziertes Thema. Hier fehlte sicher einfach etwas Hintergrundwissen, um falsche Schlussfolgerungen zu vermeiden – obwohl der genannte Autor es besser wissen müsste heißt die Autorenangabe ja nicht, dass alles aus seiner Feder stammt.

Denn ein bisschen anonym geht eben doch. Man ist sogar immer nur ein bisschen anonym, genau wie Sicherheit niemals absolut ist. Und in anderen Kontexten haben gerade das die Übermedien ja durchaus verstanden.

Monitorama PDX 2014 - James Mickens from Monitorama on Vimeo.

James Mittens erklärt die Verbindung von Batmans Bane mit NoSQL, die Herausforderungen für Sicherheit angesichts des männlichen Faktors, und warum die US-Regierung uns nicht mit Musketen angreifen wird. Und einiges mehr.

Tom Murphy mit einem weiteren absurd-genialen NES-Video.

Vor ein paar Jahren versuchte man mir zu erklären, wie RSA funktioniert. Als Übung - und mit der üblichen Warnung, unseren Code nie zu benutzen - sollten wir es selbst implementieren, denn nur dann wird es verstanden. Machte ich mit Freude, natürlich in Bash, einfach weil ich es konnte. Und ich noch heute grinsen muss beim Gedanken an die Schimpfworte, die der Tutor bei der Bewertung benutzt haben müsste (wenn ich mich richtig erinnere, bekam ich sogar die volle Punktzahl - was mich dann doch überraschte).

War mir sicher, das hier verbloggt zu haben, konnte es aber (anlässlich noqqes Implementierung) nicht mehr finden. Daher, uneditiert aus der Abgabemail (oder hier als gist):

#!/bin/bash

getPrim() {
    local range="$1"
    local prim=$(getRandom $range)
    until [[ $prim -gt 1 ]] && isPrim $prim;do
        prim=$(getRandom $range)
    done
    echo $prim
    return 0
}

#Miller-Rabin-Test
isPrim() {
    local prim=$1
    if [[ $(echo "$prim % 2" | bc) -eq 0 ]];then
        return 1
    fi

    #won't find an "a" for them: 
    if [[ $prim -eq 3 ]] || [[ $prim -eq 5 ]];then
        return 0
    fi

    prim_range=${#prim}
    
    local i=0
    while [[ $i -lt 10 ]];do
        
        local a=$(getRandom $(($RANDOM % (prim_range + 1) )) )
        until [[ $(echo "$a < ($prim - 2) && $a > 2" | bc) -eq 1 ]];do
            a=$(getRandom $(($RANDOM % (prim_range + 1) )) )
        done
        

        if isWitness $prim $a;then
            return 1
        fi
        let i++
    done
    return 0
}

function isWitness() {
    prim=$1
    a=$2

    prim_minus_one=$(echo "$prim - 1" | bc)
    test=1
    local i=${#prim_minus_one}
    i=$(($i - 1))
    while [[ $i -ge 0 ]];do
        
        x=$test
        
        test=$(echo "$x^2 % $prim" | bc)
        
        if [[ $test -eq 1 ]] && [[ $x -ne 1 ]] && [[ $x -ne $prim_minus_one ]];then
            return 0
        fi
        let i--
    done
    
    test=$(powmod $a $prim_minus_one $prim)
    
    if [[ $test -ne 1 ]];then
        return 0
    else
        return 1
    fi
}

setBasics() {
    local range="$1"
    local try="$2"

    if [[ -z "$range" ]];then
        #the length of sqrt(m) for p and q fits to the necessary length of n
        range=$(echo "sqrt($m)" | bc)
        range=${#range}
    fi
    if [[ -z "$try" ]];then
        try=1
    fi
    
    doBasics $range $try
    #bash's comparison won't work with big numbers
    until [[ $(echo "$n > $m" | bc) -eq 1 ]];do
        let try++
        if [[ $try -gt $(($range * 10)) ]] || [[ ${#n} -lt $(( ${#m} -2 ))  ]];then
            let range++
            try=1
        fi
        doBasics $range $try
    done
}

function doBasics() {
    local range="$1"
    local try="$2"
    
    #two primenumbers
    p=$(getPrim $range)
    q=$(getPrim $range)

    until [[ p -ne q ]];do
        p=$(getPrim $range)
        q=$(getPrim $range)
    done

    #RSA-Modul
    n=$(echo "$p*$q" | bc -l)

    #eulersche
    phi=$(echo "($p-1)*($q-1)" | bc -l)
}

#choose e coprime to phi
getPublicKey() {
    local e=$(($RANDOM))
    until [[ $(echo "$e < $phi" | bc) -eq 1 ]];do
        e=$(($RANDOM))
    done
    local i=2
    while [[ $(echo "$i < $e" | bc) -eq 1 ]];do
        if [[ $(echo "$phi % $i" | bc ) -eq 0 ]] && [[ $(echo "$e % $i" | bc) -eq 0 ]];then
            getPublicKey
            exit
        fi
        let i++
    done
    echo $e
}

getPrivateKey() {
    local result=($(extended_euclid $e $phi))
    local d=${result[0]}
    until [[ $d -gt 0 ]];do
        d=$(echo "$d+$phi" | bc -l)
    done
    echo $d
}

function extended_euclid() {
    a=$1
    b=$2
    local x=0
    local lastx=1
    local y=1
    local lasty=0
    while [[ $b -ne 0 ]];do
        local quotient=$(echo "$a / $b" | bc)
        
        local temp=$b
        b=$(echo "$a % $b" | bc)
        a=$temp
        
        temp=$x
        x=$(echo "$lastx - ($quotient * $x)" | bc)
        lastx=$temp
        
        temp=$y
        y=$(echo "$lasty - ($quotient * $y)" | bc)
        lasty=$temp
    done
    local result=($lastx $lasty $a)
    echo "${result[*]}";
    return 0
}


#a^b%m: Square & Multiply
powmod() {
    local a=$1
    local b=$2
    local mod=$3

    local i=0
    local res=1

    #b in binary for binary exponentiation
    b=$(echo "ibase=10;obase=2; $b" | bc)

    while [[ $i -lt ${#b} ]];do
        res=$(echo "$res^2 * $a ^ ${b:$i:1} % $mod" | bc)
        let i++
    done
    echo $res
}

getRandom() {
    local range="$1"
    if [[ -z "$range" ]];then
        range=$RANDOM
    fi
    local r=$((RANDOM % 10))
    while [[ $r -eq 0 ]];do
        r=$((RANDOM % 10))
    done
    local i=1
    while [[ $i -lt $range ]];do
        local temp=$((RANDOM % 10))
        r=${r}${temp}
        let i++
    done
    echo $r
}

encrypt() {
    local m="$1"
    local c=$(powmod $m $e $n)
    echo "$c"
}

decrypt() {
    local c="$1"
    local m=$(powmod $c $d $n)
    echo "$m"
}
    

export BC_LINE_LENGTH=0
m=91011121314151617181920212223242526272829
old_m=$m

setBasics
e=$(getPublicKey)
echo "Public Key: ($e, $n)"
d=$(getPrivateKey)
echo "Private Key: ($d, $n)"
echo

c=$(encrypt "$m")
echo "c: $c"
m=$(decrypt "$c")
echo "m: $m"

if [[ $m -ne $old_m ]];then
    echo "Error: Wrong message decrypted:" >&2
    echo "p: $p" >&2
    echo "q: $q" >&2
    echo "Public Key: ($e, $n)" >&2
    echo "Private Key: ($d, $n)" >&2
    echo "c: $c" >&2
    echo "m: $m" >&2
fi

#Ausgabe
#onli@Fallout:~$ uni/ts/rsa.sh
#p: 783057321236353042573
#q: 444786834379004491147
#Public Key: (2969, 348293587050020677086428785700425092601231)
#Private Key: (137252777651911145904238835165856311899289, 348293587050020677086428785700425092601231)
#
#c: 134886886292723664083288725067434182648518
#m: 91011121314151617181920212223242526272829

My point is that a good programmer in this time does not just write programs, a good programmer builds a working vocabulary - in other word, a good programmer does language design, though not from scratch, but building on the frame of a base language.

Willkommen in der Zukunft. Durch Quantencomputer ist Primfaktorzerlegung kein Problem mehr, RSA und andere Verfahren sind nutzlos geworden. Das unheimlich wichtige Dokument D=(1,1,0) soll aber trotzdem signiert werden, also braucht es dafür ein anderes Verfahren mit einer anderen Sicherheitsbedingung. Das Lamport-Diffie Einmail-Signaturverfahren (LD-OTS) eilt zur Rettung.

LD-OTS braucht nur eine funktionierende Hashfunktion, dass eine solche noch existiert ist Mindestvoraussetzung. Und dann ist es ganz einfach, der Signierer bietet schlicht die passenden Urbilder zu den vorher veröffentlichten und durchs Dokument ausgewählten Hashs an.

Also so: Für jedes Bit im Dokument hat der Signierer zwei Werte, die geheim bleiben, den Signaturschlüssel, hier: x = (x01, x11; x02, x12; x03, x13).
Veröffentlicht wird vorher der Verifizierungsschlüssel: y = (y01, y11; y02, y12; y03, y13) = (H(x01), H(x11); H(x02), H(x12); H(x03), H(x13))

Zum Signieren des Dokuments D = (1, 1, 0) veröffentlicht der Signierer dann je nach Bit an der jeweiligen Stelle seinen Teil des Signaturschlüssels und damit die Urbilder der Hashfunktion als Signatur, hier also: (x11, x12, x03). Der Verifizierer braucht dann dann nur zu schauen, ob die veröffentlichten Signaturschlüsselteile mit dem vorher veröffentlichten Verifizierungsschlüssel übereinstimmen, also H(x11) = y11, H(x12)=y12 und H(x03)=y03 ist.

Angestoßen von dieser Diskussion über die Performance des Bayes-Plugins schreibe ich hier mal die theoretische Grundlage des Plugins und damit auch eines generischen Bayes-Spamfilters auf, damit man sich bei einer eventuellen Überarbeitung hierdran orientieren kann.

Bayes-Formel

Das Bayes-Theorem wurde entdeckt, verworfen und schließlich wiederentdeckt. Ich glaube, die mathematischen Einwände gegen die Formel finden sich manchmal noch in der Kritik an solchen Filtern wieder, deshalb sei ihr Vorhandensein erwähnt.
Die allgemeine Formel lautet:



P(A) ist die Wahrscheinlichkeit für A, P(A|B) ist die Wahrscheinlichkeit für A unter der Bedingung B, also wenn B eingetreten ist.

Wie sieht das nun für Spam aus? So:



Zu beachten ist, dass wir diese Spamwahrscheinlichkeit für jedes Wort im Kommentar wissen wollen, daher am Ende mehrere Wahrscheinlichkeiten aufaddieren und normalisieren müssen.

Aufdröselung

Es gibt also genau drei Variabeln zu berechnen: Die Inverse Wahrscheinlichkeit, die Wahrscheinlichkeit von Spam und die Wahrscheinlichkeit für das Auftreten solcher Wörter. Das für jedes Wort. Was genau bedeuten die Formeln jeweils?

P(Wort|Spam)

Dies ist die Wahrscheinlichkeit, dass in einem Spamkommentar dieses Wort vorkommt: Spamkommentare mit diesem Wort / Spamkommentare

P(Spam)

Die Gesamtwahrscheinlichkeit, dass ein Kommentar Spam ist: Spamkommentare / Kommentare.

P(Wort)

Die Wahrscheinlichkeit, dass dieses Wort überhaupt in einem Kommentar vorkommt: Kommentare mit diesem Wort / Kommentare

Programmiertechnische Konsequenzen

Es ist völlig klar, dass eine Datenbank gebraucht wird und die Bewertung größtenteils aus dem Heraussuchen der richtigen Daten zu den Worten besteht. Zuerst muss ein sogenannter Tokenizer den Kommentar in seine Einzelwörter zerlegen. Im Wesentlichen ist das ein:

tokenize(text) {
    tokens = split("\W", text )
    return unique(tokens)
}

Das Lernen eines Kommentars als Ham oder Spam ist nun nichts anderes, als diese Tokens in diese Datenbank namens "tokens" zu schreiben:

token (text) | ham (number) | spam (number)

Ist das Token schon vorhanden, wird der zugehörige Ham- bzw Spamwert um eins erhöht. Gleichzeitig wird der Gesamtzähler Hamkommentare bzw Spamkommentare um eins erhöht.
Diese Datenbank zusammen mit den Gesamtzählern gibt uns nun alle nötigen Werte:

P(Wort|Spam)

spam = sql_query("Select spam from tokens where token = Wort")
spam / (Spamkommentare)

P(Spam)

Spamkommentare / (Spamkommentare + Hamkommentare)

P(Wort)

ham, spam = sql_query("Select ham, spam from tokens where token = Wort)"
(ham + spam) / (Spamkommentare + Hamkommentare)

Formelveränderungen

Schaut man sich nun die Bewertungsfunktion im Bayes-Plugin an wird man feststellen, dass der PHP-Code nicht nur wesentlich unschöner als mein Pseudocode aussieht, sondern auch anders funktioniert. Das liegt daran, dass das Plugin auf b8 aufbaute, und b8 nicht simpel das Bayes-Theorem benutzt, die Wahrscheinlichkeiten addiert und dann durch ihre Anzahl teilt. Diese Änderungen basieren auf Tests und anderen theoretischen Annahmen als den hier gezeigten. Insbesondere die folgenden Änderungen sind enthalten oder denkbar:

Law of total probability

Wer Vorkenntnisse hat oder nachrecherchierte, dem könnte aufgefallen sein, dass Wikipedias Bayes-Spamfilterformel anders aussieht:



P(Wort) wird hier gemäß dem Law of total probability umgeformt. Ohne das gerade nachgerechnet zu haben vermute ich, dass die Werte gleich sein sollten und diese Formel nur P(Wort) anders betrachtet.

Häufigkeit von Tokens im Kommentar

Wie oft ein Wort im Kommentar auftaucht sollte die Wahrscheinlichkeit beeinflussen. Dieser Artikel hier ist kein Spam, obwohl nun Viagra auftaucht, aber wäre jedes Wort Viagra, wäre er durchaus Spam. Deshalb beachtet b8 die Häufigkeit eines Tokens.

Wichtigkeit

Eine beliebte Spammertaktik ist, Kommentare mit ewig langem Fülltext auszustaffieren und den Spammerinhalt so zu verstecken. Der Gedanke dabei ist, dass die vielen harmlosen Worte den ganzen Kommentar harmlos erscheinen lassen. Die auch von b8 genutzte Taktik dagegen ist die Einführung eines Wichtigkeitsfaktors: Beziehe nur die Tokens in die Schlussrechnung ein, die eine Tendenz zu Spam oder Ham haben, also um einen bestimmten Faktor von der Mitte 0,5 abweichen. Der Gedanke dahinter ist, dass die vielen Füllwörter die Bewertung sonst gegen 0,5 tendieren lassen würden.

Optimierungsmöglichkeiten

Ich schrieb oben, dass dieser Artikel die theoretischen Grundlagen zwecks einer späteren Optimierung des Filters deutlich machen soll.
Diese Optimierungsmöglichkeiten sehe ich bis jetzt:

Ham-Spam-Faktor

Der Anstoßgeber dieses Eintrags ist diese Diskussion. Grischa schlug vor, über irgendeinen Faktor auszugleichen, dass ein typischer Blog sehr viel mehr Spam als Ham bekommt und daher der Filter zu streng werden würde. Meiner Meinung nach ist das nicht wirklich ein Problem, da diese Verteilung elementar für den Filter ist, und nicht automatisch neuer Spam eingelernt wird, wenn man das nicht will.

Wikipedia erwähnt, dass P(Spam) generell 0,8 sei. Vielleicht würde es helfen, diesen Wert festzusetzen statt ihn empirisch zu bestimmen?

Häufigkeit von Tokens

Wie oben beschrieben ist die Häufigkeit von Wörtern innerhalb eines Kommentars ein wichtiger Faktor. Zur Zeit fließt das aber nur indirekt in die Bewertung ein, indem es bei der Bewertung selbst ignoriert wird, beim Einlernen aber beachtet wird. Statt in der Tabelle den Ham- bzw Spamwert um eins zu erhöhen, wird er um die Anzahl der Tokens erhöht. Bei der Bewertung aber wird jedes Token nur einmal beachtet, selbst wenn es mehrmals vorkommt. Das könnte man ändern.

Es ist auch ein kritischer Punkt, weil man sich hier leicht mit Anzahl der Tokens und Anzahl der Kommentare verheddern kann. Die Formel müsste genau geprüft werden.

Konstanten

Bei der Übernahme von b8 wurde die Klassifizierungsberechnung blind übernommen. In ihr enthalten sind einige Konstanten, die auf den Testergebnissen beruhen. Es geht um diese Zeile:

$ratings[$word] = (0.15 + (($stored_tokens[$word]['ham'] + $stored_tokens[$word]['spam']) * $rating)) / (0.3 + $stored_tokens[$word]['ham'] + $stored_tokens[$word]['spam']);

0,15 und 0,3 sind die Konstanten, die hier direkt die Bewertung beeinflussen und entfernt bzw verändert werden könnten.

Schlusswort

Es ist nunmal Mathematik. Ich hoffe, die Erklärung macht die Funktionsweise des Filters trotzdem klarer. Die Optimierung des Filters könnte ein sehr interessantes Projekt sein, aber auch sehr zeitaufwändig. Hinweise zu Fehler in den Formeln nehme ich dankend entgegen

Vll tritt da eine Schwäche von mir bei den formalen Grundlagen zutage, aber sowohl Currying als auch Monads sind so Begriffe, die ich (z.B. bei Hackernews) öfter mal lese, die mir aber schlicht nichts sagen. Kann mich nicht erinnern, darüber je was gelernt zu haben. Dabei hatte ich ja funktionale Programmierung, mochte sie schlußendlich sogar, und da wird wohl beides genutzt.

Nach meiner Faustregel hat es niemand verstanden, den ich bis jetzt gelesen habe, denn ich finde keine einfache Erklärung. Vielleicht kann hier jemand helfen? Ich beschreibe mal, was ich bisher habe.

Currying

Abgeleitet aus der comp.lang.functional-FAQ: Das scheint total unspannend zu sein. Hat man nur einen Parameter zur Verfügung, dann kann man um

 f(x,y)

auszudrücken, x durch eine Funktion ersetzen, also:

(f'(x))(y) = f (x,y)

Das solls sein?

Gut, mir ist klar, dass man das gebrauchen kann, wenn man in einer seltsamen Sprache zwar lambda zur Verfügung hat, aber nur einparametrige Funktionen. Das wäre dann ein theoretisches Konstrukt ohne Praxisrelevanz, das höchstens dann gut ist, wenn eine solche Sprache zu leichteren Beweisen führt und man sie nutzt, weil man bewiesen richtigen Programmcode braucht.

Monads

Hier geht mein im Studium gestählter Bullshit-Sensor an. Und zwar, weil hier die FAQ jede Antwort darüber verweigert, was es ist, und nur darüber schreibt, wofür es gut ist:

What is a "monad", and what are they used for?

The concept of a monad comes from category theory; full details can be found in any standard textbook on the subject. Much of the interest ...

Was mich wieder zu meiner Frage führt, ob es wirklich Dinge gibt, die so kompliziert und trotzdem wichtig sind, dass man sie nicht mehr mit einfachen Worten ausdrücken kann (siehe die Sprachbarriere bei FGdI).

Wie auch immer, aus diesem Paper und Wikipedia wird die Essenz des Begriffs nicht wirklich klar. Laut dem Paper: Ein Monad ist ein Ding M, das Seiteneffekte darstellt, und das man deswegen vor den normalen Typ stellt? Das Divisionsbeispiel aus der Wikipedia ist für mich an sich einleuchtend (abgesehen von der grauenhaften Syntax):

(//) :: Maybe a -> Maybe a -> Maybe a
_ // Nothing = Nothing
Nothing // _  = Nothing
_ // Just 0 = Nothing
Just x // Just y = Just (x / y)

Statt eine Division / zu definieren, die Zahlen zurückgibt (und dann Sonderfälle wie die Division durch 0 fangen zu dürfen), definiere ich eine Division //, die entweder Zahlen oder einen Ausweichtyp ausgibt. Ähnlich wie Listen, die entweder Elemente oder ein Schlußsymbol beinhalten. Und wieder: Ist das alles?

Ich muss es bezweifeln, sonst könnte man es einfach erklären.

Das Konzept von Salts ist eigentlich ein sehr einfaches. Da ich jetzt aber ein paarmal über Menschen gestolpert bin, denen das Konzept nicht klar wurde (und es auch selbst am Anfang für etwas hoch-komplexes hielt), versuche ich mich mal an einer einfachen Erklärung.

Funktionsweise

Angenommen, man hat eine Webanwendung, in die sich Leute mit einem Passwort einloggen können (sie könnte Serendipity heißen). Selbstverständlich speichert man das Passwort dieser Nutzer nicht im Klartext ab, weil dann ein einfacher Blick in die Datenbank genügen würde, um das Passwort zu verraten. Stattdessen speichert man den Hash H des Passworts, der durch eine beliebige kryptographische Hashfunktion generiert wird:

H = hash(Passwort)

hash() ist im wesentlichen eine Einwegfunktion, also kann aus H nicht direkt Passwort rekonstruiert werden. Es existiert kein unhash(H) == Passwort.

Bei einem Loginversuch mit dem Passwort wird dann das Hashen wiederholt und mit dem gespeicherten H in der Datenbank verglichen:

bool loginCorrect?(passwort) {
    return (hash(passwort) == H)
}

Nur wenn die beiden Hashes übereinstimmen, stimmen die durch die Hashes repräsentierten Passwörter und der Nutzer kann sich erfolgreich einloggen.

Nun kommt der Salt dazu. Der wird zufällig gewählt, ist also eine zufällige Zeichenfolge, und wird dem Passwort angehängt:

hash(Passwort + Salt) = salted_H

Das wird nun bei jeder Passworterstellung gemacht, also insbesondere jedes Mal ein neuer Salt berechnet. Vom Prinzip her ist das alles.

Der Salt wird natürlich mit dem salted_H in der Datenbank gespeichert. Das ist notwendig, denn bei einem Loginversuch wird ja wieder ein Hash berechnet und mit dem gespeicherten verglichen:

bool loginCorrect?(passwort) {
    return (hash(passwort + Salt) == salted_H)
}

Warum?

Bleibt die Frage, warum man einen solchen Salt nutzen sollte. Die Antwort: Sicherheit. Es soll verhindert werden, dass aus den Hashes indirekt das Passwort berechnet werden kann. In der Konsequenz geht es um ein Gegenmittel gegen Rainbow-Tables.

Die Datenbank der Webanwendung könnte gestohlen werden, wie das ja in letzter Zeit reihenweise passierte. Ziel des Angreifers ist es danach, das Passwort im Klartext herauszufinden. Aus zwei Gründen:

1. Wenn er nur die Datenbank hat, könnte er sich dann in der Webanwendung einloggen und Aktionen durchführen
2. Viele Nutzer verwenden Passwörter mehrfach, sodass der Angreifer bei vielen anderen Diensten gültige Logins und Passwörter bekommen würden

Im Idealfall hat der Angreifer bisher nur die Datenbank mit dem Nutzernamen (der natürlich auch gehasht werden könnte), dem salted_H und dem Salt jedes Nutzers. Schon dank des Hashens reicht das nicht, um sich einzuloggen. Denn die Loginfunktion hasht ja wieder, gibt man den salted_H da ein entsteht also:

return (hash(salted_H + Salt) == salted_H))

Auch ohne den Salt wäre das false, denn man kann davon ausgehen, dass hash(hash(X)) != hash(X).

Ohne den Salt würde der Angreifer jetzt versuchen, eine Rainbow-Table aufzubauen. Dafür nutzt er seinen privaten Rechencluster in etwa so:

1000000000.times {
    passwort = guess_password()
    rainbow_table[hash(passwort)] = passwort
}

Er erstellt also eine Liste von gehashten Passwörtern und ihrem Klartext. Danach braucht er nur in der Datenbank zu schauen, ob der Hash verwendet wurde, und weiß deswegen, welches Passwort verwendet wurde um den Hash zu erstellen. Schon hat er das Passwort im Klartext.

Genau das verhindert der Salt. Da zwei Datenbanken oder sogar zwei Nutzer in einer Datenbank unterschiedliche Salts benutzen, unterscheidet sich ihr salted_H, selbst wenn sie das gleiche Passwort benutzen. Wird also eine Datenbank gestohlen, muss zwingend für jeden einzelnen Nutzer geguckt werden, ob

hash(guess_password() + Salt) == salted_H 

gilt. Eine Rainbow-Table, die die Salts mitspeichert würde absurd groß werden:

for salt in salts {
    1000000000.times {
        passwort = guess_password()
        rainbow_table[salt][hash(passwort +salt)] = passwort
    }
}

Daher kommt auch die Bewegung, teure Hashfunktionen wie bcrypt zu nutzen und sie möglichst noch mehrmals durchlaufen zu lassen. Bei einem Login ist die benötigte Zusatzzeit kaum bemerkbar, aber bei einem Knacken der Hashes tut jede ms weh.

Kurz

Ein Hash mit Salt ist einfach hash(X + Salt). Er schützt nicht generell vor schwachen Passwörtern, aber er erschwert es, dass Passwörter aus dem Hash rekonstruiert werden können.

Stanford bietet von September bis Dezember eine KI-Vorlesung als offene Online-Version an (via). Das Video zeigt ein paar der Inhalte:

Mich erinnerte es sehr an meine KI-Vorlesung. Klar, wir sind nicht mit Robotern durch die Stadt gefahren, aber die gezeigten Inhalte hatten wir größtenteils. Und er basierte auf dem gleichen Buch, was wohl wirklich das Standardwerk ist (Artificial Intelligence: A Modern Approach).
Was mir wieder klar machte, wie toll ich das Thema finde. KI ist nicht einfach eine simple Untermenge der Informatik. Wenn Informatik das Beherrschen von Informationen, das algorithmische Lösen von Problemen ist, dann ist das genau die Definition der KI. Die Algorithmen der schwachen KI haben mehr als andere den Ansatz, ein Problem generisch zu lösen statt es direkt lösen zu lassen, oder sind eher das Zusammenspiel von Algorithmen zur generischen Lösung eines Problems.

Beispiel Schach. Um dafür eine Lehrbuch-KI zu schreiben ist zwar Unmengen an Können notwendig, doch eigentlich braucht man "nur" eine eine performante Min-Max-Variante, plus den nötigen Optimierungen um der Komplexität beizukommen. In denen liegt dann die Schwierigkeit, aber Min-Max selbst ist ein sehr simpler Algorithmus, der einfach alle möglichen Varianten durchgeht und dann den Zug wählt, der für den Spieler das beste Ergebnis hat. Der Pseudocode hat 5 Zeilen.

Daher sah ich KI als praktisches Anwenden des Algorithmik-Kurses (der selbst schon ziemlich praxisbezogen war) und als Versuch, Probleme geschickt zu lösen. Da wird kein Data erschaffen, sondern Spiele gespielt, was nichts anderes als Problemlösen ist.

Und Problemlösen, darum geht es doch immer. Deshalb ist das Ansehen des Stanford-Kurs für die meisten Informatiker und Programmierer, die einen solchen Kurs noch nicht gehört haben, wahrscheinlich eine gute Idee.