Finish fsverify section of realisierung

3 files changed, 165 insertions, 1 deletions

diff --git a/doc/class-assignment/fsverify.pdf b/doc/class-assignment/fsverify.pdf
index a666f6d..5fcaac0 100644
--- a/doc/class-assignment/fsverify.pdf
+++ b/doc/class-assignment/fsverify.pdf
diff --git a/doc/class-assignment/fsverify.tex b/doc/class-assignment/fsverify.tex
index ad8ebf2..5eca6fb 100644
--- a/doc/class-assignment/fsverify.tex
+++ b/doc/class-assignment/fsverify.tex
@@ -11,7 +11,7 @@
 \usepackage{svg}
 \usepackage{setspace}
 \usepackage{tocbibind}
-\usepackage[style=reading,backend=bibtex]{biblatex}
+\usepackage{minted}
 
 \hypersetup{
 	colorlinks   = true,    % Colours links instead of ugly boxes
diff --git a/doc/class-assignment/realisierung/fsverify.tex b/doc/class-assignment/realisierung/fsverify.tex
index cc32dd1..6277f32 100644
--- a/doc/class-assignment/realisierung/fsverify.tex
+++ b/doc/class-assignment/realisierung/fsverify.tex
@@ -5,6 +5,8 @@ Hierbei war google's dm-verity, welches in Android und ChromeOS geräten genutzt
 \subsubsection{Partitionslayout}
 Inspiriert an dm-verity, entschied ich mich dafür, die Datenbank auf eine eigene Partition zu speichern, also war das erste Ziel ein gutes Partitionslayout zu Entwickeln, in der die Datenbank und Metadata so gut wie möglich gespiechert werden kann.
 \\
+%\pagebreak
+\\
 Die erste Version des Layouts war recht simpel, es hatte alles was wirklich wichtig war, eine magic number, die signatur, größe des Dateisystems und größe der Datenbank:
 \begin{verbatim}
 <magic number> <signature> <filesystem size> <table size>
@@ -25,7 +27,169 @@ Die erste Version des Layouts war recht simpel, es hatte alles was wirklich wich
     \hline
   \end{tabular}
 \end{center}
+In der implementierung dieses Layouts viel dann auf, dass es keinen Sinn macht, die Datenbankgröße in MB festzulegen
+\\
+\\
+Die zweite Version fügt ein weiteres Feld hinzu um die Einheit der Datenbankgröße festzulegen:
+\begin{verbatim}
+<magic number> <signature> <filesystem size> <table size> <table unit>
+\end{verbatim}
+
+\begin{center}
+  \begin{tabular}{|c | c | c | c|}
+    \hline
+    Feld & Größe & Nutzen & Wert \\ [0.5ex]
+    \hline
+    magic number & 2 bytes & Sanity check & 0xACAB \\
+    \hline
+    signature & 302 bytes & minisign signatur & - \\
+    \hline
+    filesystem size & 4 bytes & größe des originalen Dateisystems in GB & - \\
+    \hline
+    table size & 4 bytes & größe der Datenbank in MB & - \\
+    \hline
+    table unit & 1 byte & datentyp des Feld ``table size'' & - \\
+    \hline
+  \end{tabular}
+\end{center}
+\hfill \break
+\\
+Die nächste version teilte die Signatur in zwei teile auf. Da minisign signaturen aus einem kommentar, einer vertrauten signatur, einem weiteren kommentar und einer nicht vertrauten signatur
+\begin{verbatim}
+<magic number> <untrusted signature hash> <trusted signature hash>
+<filesystem size> <table size> <table unit>
+\end{verbatim}
 
+\begin{center}
+  \begin{tabular}{|c | c | c | c|}
+    \hline
+    Feld & Größe & Nutzen & Wert \\ [0.5ex]
+    \hline
+    magic number & 2 bytes & Sanity check & 0xACAB \\
+    \hline
+    untrusted signature & 100 bytes & nicht vertrauter signatur & - \\
+    \hline
+    trusted signature & 88 bytes & vertraute signatur & - \\
+    \hline
+    filesystem size & 4 bytes & größe des originalen Dateisystems in GB & - \\
+    \hline
+    table size & 4 bytes & größe der Datenbank in MB & - \\
+    \hline
+    table unit & 4 bytes & datentyp des Feld ``table size'' & - \\
+    \hline
+  \end{tabular}
+\end{center}
+
+\subsubsection{Datenbanklayout}
+Nachdem der Header der Partition festgelegt wurde, muss festgelegt werden, wie die Datenbank festgelegt ist.
+bbolt, die Datenbankbibliothek die fsverify nutzt, hat ein key/value system, das heißt, dass jeder Wert mit einem Schlüssel verbunden ist. Zudem benutzt bbolt das konzept von ``Buckets'', einem Eimer in dem Datenpaare sortiert werden können.\\
+Das erste Layout war für eine implementation von fsverify die nur auf einem Thread läuft, besteht aus einem Bucket ``Nodes'', in dem jede Node gespeichert wird.
+Eine Node sieht wie folgt aus:
+
+\begin{minted}{go}
+// Node.go
+type Node struct {
+  BlockStart int
+  BlockEnd int
+  BlockSum string
+  PrevNodeSum string
+}
+\end{minted}
+
+\begin{center}
+  \begin{tabular}{|c | c|}
+    \hline
+    Feld & Nutzen \\ [0.5ex]
+    \hline
+    BlockStart & Der hex offset and dem der Block anfängt \\
+    \hline
+    BlockEnd & Der hex offset and dem der Block ended \\
+    \hline
+    BlockSum & Der sha1 hash des Blocks \\
+    \hline
+    PrevBlockSum & Der sha1 hash aus allen Feldern der vorherigen Node \\
+    \hline
+  \end{tabular}
+\end{center}
+
+\\
+Jeder Block, welcher 2kb groß ist, bekommt eine Node zugewiesen, diese Nodes werden in der Datenbank aneinandergereiht, mit dem wert von PrevBlockSum als den key.
+Der Wert PrevBlockSum erlaubt es, während der Verifizierung Fehler in der Datenbank zu finden. Wird eine Node verändert, stimmt der PrevBlockSum der nächsten Node nicht mehr, dass heißt, dass es nicht mehr möglich ist, den Key zu der nächsten Node zu berechnen, wodurch die Verifizierung fehlschlägt.
+\begin{verbatim}
++-----+     +------+     +------+        +------+
+|0x000|     |0xFA0 |     |0x1F40|        |0x3E80|
+|0xFA0| --> |0x1F40| --> |0x3E80| -----> |0x4E20|
+|aFcDb|     |cDfaB |     |4aD01 |        |2FdCa |
+|     |     |adBfa |     |1Ab3d |        |bAd31 |
++-----+     +------+     +------+        +------+
+\end{verbatim}
+\pagebreak
+Wird hier eine Node verändert, stimmt die restliche Kette nicht mehr
+\begin{verbatim}
+                         Hash passt nicht mehr
+                                    |
++-----+     +------+     +------+   |    +------+
+|0x000|     |0xFA0 |     |0x1F40|   |    |0x3E80|
+|0xFA0| --> |0x1F40| --> |0x3E80| --|--> |0x4E20|
+|aFcDb|     |AAAAA | <-+ |4aD01 |   |    |2FdCa |
+|     |     |adBfa |   | |1Ab3d | <-+--> |bAd31 |
++-----+     +------+   | +------+        +------+
+                       |
+                 Veränderter Wert
+\end{verbatim}
+\\
+Da die erste Node keinen vorränger hat, von dem es PrevNodeSum berechnen kann, wird ihr der wert ``Entrypoint'' gegeben.
+\\
+Diese Datenbankstruktur hat ohne Probleme funktioniert, jedoch war fsverify viel zu langsam wenn es auf einem Thread läuft. Das Problem bei dem Multithreading jedoch ist, dass man Nodes nicht wahrlos aufgreifen kann, sondern eine vorherige Node oder die entrypoint Node braucht. Die Lösung ist recht einfach, die anzahl der Threads wird in verifysetup bereits angegeben und somit in fsverify fest einprogrammiert. Somit gibt es in der Datenbank mehrere entrypoint Nodes, die sich durch eine hinzugefügte Nummer unterscheiden. Dadurch ist es weiterhin möglich die Datenbank zu verifizieren, während es multithreaded läuft.
+
+\subsubsection{Datenbanksignatur}
+Um sicherzustellen, dass die Datenbank nicht modifiziert wurde, wird eine Signatur generiert die mit der gelesenen Datenbank verglichen wird.\\
+Wie bereits erwähnt, wird für die Signatur das Programm minisign benutzt. Minisign beruht auf ein public/private key system, wodurch eine Signatur von dem privaten Schlüssel generiert wird und durch den öffentlichen Schluss verifiziert werden kann.\\
+Die Signatur wurde bereits im Partitionsheader gespeichert, was übrig bleibt ist der öffentliche Schlüssel.\\
+\\
+Da der öffentliche Schlüssel und die Signatur gebraucht werden, um eine Datenbank zu verifizieren, muss sichergestellt werden, dass beide seperat gespeichert werden und zumindest der öffentliche Schlüssel nicht bearbeitet werden kann.\\
+Die erste Idee um dies zu lösen wäre, dass man einfach den Schlüssel in eine Datei schreibt, und die Datei schreibgeschutzt Speichert. Jedoch ist bei diesem weg der speicherort der Datei das problem, wie soll man sicher sein, dass nicht das ganze Dateisystem verändert wurde um einen neuen Schlüssel zu beinhalten?
+\\
+\\
+Das heißt, dass man ein Schreibgeschütztes, möglichst seperates und immer vertraubares Speichermedium braucht, auf der man den Schlüssel speichert.\\
+Die lösung: Microcontoller. Sie können über usb-serial (also /dev/ttyACM* in Linux) Daten übertragen, können durch das Modifizieren bestimmter Sektoren permanent schreibgeschützt werden, und sind sehr klein, also können sie von dem Nutzer mitgetragen werden oder in dem Gerät direkt verbaut sein.
+\\
+Um dieses konzept zu testen, habe ich einen Arduino UNO genutzt, dieser ist zwar immer schreibbar, hat aber keine Technischen unterschiede die die Datenübertragung ändern würden.
+\\
+Der Code für den Arudino sieht wie folgt aus:
+\begin{verbatim}
+// publicKey.c
+void setup() {
+  Serial.begin(9600); // set up a serial tty with the baud rate 9600
+  Serial.print("\tpublic key\t"); // Write the public key to the tty
+}
+void loop() {}
+\end{verbatim}
+
+Es wird eine Serielle Konsole auf einer Baudrate von 9600 geöffnet, auf der einmalig der öffentliche Schlüssel ausgegeben wird. Es ist wichtig zu beachten, dass der Schlüssel mit Tabstops (\backlash t) ausgegeben wird, diese benutzt fsverify um zu wissen, ob der volle Schlüssel aufgenommen wird, fehlt der Tabstop am anfang oder am Ende, ist es sehr wahrscheinlich, dass der Schlüssel auch nicht vollständig aufgenommen wurde.
+
+\subsubsection{Optimierung}
+Wie bereits gesagt, lief die erste version von fsverify auf einem Thread, dies führte zu einer laufzeit von über einer Stunde bei einer Partitionsgröße von 1gb. Da fsverify beim booten des systems ausgeführt werden soll, ist eine laufzeit von einer Stunde nicht akzeptabel.
+\\
+Die ersten schritte der Optimierung war es, die größe der Blocks zu verringern und von sha256 zu sha1 zu wechseln. Da das lesen von daten viel schneller erfolgt als das hashen von daten, ist es besser mehr zu lesen und dadurch kleinere Datenmengen zu hashen, der wechsel von sha256 zu sha1 mag erstmal schlecht wirken, jedoch macht dies keine Probleme, da hier keine Passwörter oder ähnliches verschlüsselt werden, also sind bruteforce attacken hier kein risiko.\\
+Mit diesen Optimierungen hat sich die Laufzeit etwas verbessert, von 60 Minuten zu ungefähr 50. Nicht viel besser.
+\\
+Der nächste schritt war es, fsverify mit multithreading zu implementieren, die dafür notwendigen änderungen in der Datenbank wurden bereits erklärt. In fsverify selber hat sich die art geändert, wie die Daten von der Partition gelesen werden. Anstatt alles auf einmal zu lesen und durchzugehen, wird die größe der Partition genommen, durch die anzahl der Threads geteilt, und somit für jeden Thread genau die anzahl an bytes gelesen, die für die Node-kette nötig ist. Dies stellt sicher, dass keine Kette sich überlappt und korruptionen von Nodes in ketten auffallen, da sie durch Korruptionen versuchen könnten, bytes zu lesen die sie garnicht lesen sollten.\\
+Durch das multithreading hat sich die Laufzeit von den singlethreaded 50 Minuten zu nur 6 Sekunden verringert.
+\\
+\\
+Fsverify hatte eine Laufzeitoptimierung von 60000\% in einer Woche:
+\begin{verbatim}
+10.02.2024: fsverify takes 60minutes to complete for 1gb
+optimizations: none
+
+12.02.2024: fsverify takes 52minutes to complete for 1gb
+optimizations: block size 2k, sha1 instead of sha256
+
+17.02.2024: fsverify takes ~6 seconds to complete for 1gb with 12 threads (p7530)
+optimizations: block size 2k, sha1 instead of sha256, multithreaded, db batch operations
+unoptimizations: manual connecting of arduino, ~1 second penalty
+\end{verbatim}
 %%% Local Variables:
 %%% mode: LaTeX
 %%% TeX-master: "../fsverify"