From 5032249cfba8039fe7a518870a8ce42278a3bf6a Mon Sep 17 00:00:00 2001
From: axtloss <axtlos@getcryst.al>
Date: Sun, 3 Mar 2024 00:49:30 +0100
Subject: Finish realisierung

---
 doc/class-assignment/realisierung/fsverify.tex | 53 ++++++++++++--------------
 1 file changed, 25 insertions(+), 28 deletions(-)

(limited to 'doc/class-assignment/realisierung/fsverify.tex')

diff --git a/doc/class-assignment/realisierung/fsverify.tex b/doc/class-assignment/realisierung/fsverify.tex
index 6277f32..6c61313 100644
--- a/doc/class-assignment/realisierung/fsverify.tex
+++ b/doc/class-assignment/realisierung/fsverify.tex
@@ -3,10 +3,7 @@ Da das Konzept der Festplattenverifizierung nichts neues ist, habe ich mir erstm
 Hierbei war google's dm-verity, welches in Android und ChromeOS geräten genutzt wird, die beste Hilfe, da es am besten dokumentiert und ausgetestet ist.
 
 \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
-\\
+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.\\
 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>
@@ -27,10 +24,8 @@ 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:
+In der implementierung dieses Layouts fiel dann auf, dass es keinen Sinn macht, die Datenbankgröße in MB festzulegen
+Die zweite Version fügt aus diesem Grund ein weiteres Feld hinzu um die Einheit der Datenbankgröße festzulegen:
 \begin{verbatim}
 <magic number> <signature> <filesystem size> <table size> <table unit>
 \end{verbatim}
@@ -53,7 +48,6 @@ Die zweite Version fügt ein weiteres Feld hinzu um die Einheit der Datenbankgr
   \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>
@@ -82,7 +76,8 @@ Die nächste version teilte die Signatur in zwei teile auf. Da minisign signatur
 
 \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.\\
+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.
+\bigbreak \noindent
 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:
 
@@ -111,10 +106,9 @@ type Node struct {
     \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.
+Jeder Block 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.
+\pagebreak
 \begin{verbatim}
 +-----+     +------+     +------+        +------+
 |0x000|     |0xFA0 |     |0x1F40|        |0x3E80|
@@ -123,7 +117,6 @@ Der Wert PrevBlockSum erlaubt es, während der Verifizierung Fehler in der Daten
 |     |     |adBfa |     |1Ab3d |        |bAd31 |
 +-----+     +------+     +------+        +------+
 \end{verbatim}
-\pagebreak
 Wird hier eine Node verändert, stimmt die restliche Kette nicht mehr
 \begin{verbatim}
                          Hash passt nicht mehr
@@ -137,20 +130,17 @@ Wird hier eine Node verändert, stimmt die restliche Kette nicht mehr
                        |
                  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.
-\\
+\bigbreak \noindent
 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?
-\\
-\\
+\bigbreak \noindent
 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.
 \\
@@ -166,7 +156,7 @@ void setup() {
 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.
+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 (\symbol{92} 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.
@@ -176,20 +166,27 @@ Mit diesen Optimierungen hat sich die Laufzeit etwas verbessert, von 60 Minuten
 \\
 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.
-\\
-\\
+\bigbreak \noindent
 Fsverify hatte eine Laufzeitoptimierung von 60000\% in einer Woche:
 \begin{verbatim}
-10.02.2024: fsverify takes 60minutes to complete for 1gb
+10.02.2024:
+fsverify takes 60minutes to complete for 1gb
 optimizations: none
-
-12.02.2024: fsverify takes 52minutes to complete for 1gb
+\end{verbatim}
+\pagebreak
+\begin{verbatim}
+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
+\end{verbatim}
+\begin{verbatim}
+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"
-- 
cgit v1.2.3

