\chapter{Nesetřízené útržky}

\section{Adresářová struktura a stromy}

V této práci se zaměříme primárně na adresářové stromy POSIXového světa. V
tomto světě je každá položka adresáře odkazem (hard link) na \emph{inode},
který již jednoznačně určuje vše kromě názvu. Kromě toho každý adresář obsahuje
speciální odkazy {\tt .} a {\tt ..}, které odkazují na sebe samotného a
nadřazený adresář. Kromě těchto speciálních odkazů každý adresář může mít právě
jeden odkaz.

Právě díky tomu se můžeme na libovolnou rozumnou adresářovou strukturu dívat
jako na konečný zakořeněný strom -- každý adresář je položkou právě jednoho
jiného adresáře. V případě, že na soubor existuje více odkazů, budeme se ke
každému z nich chovat jako k jinému souboru.  Z toho již vyplývá, že každý
odkaz má jednoznačně určenou cestu z počátku.

\subsection{Terminologie}

Pro definice pojmů, které budeme v práci používat, si vypůjčíme termíny z
teorie grafů. Speciálně, na libovolný adresářový strom se budeme dívat jako na
orientovaný zakořeněný strom, kde vrcholy jsou všechny odkazy, které jsou
dosažitelné a orientované hrany ukazují vztah \uv{adresář obsahuje odkaz}.

Abychom nepracovali s adresářovým stromem jako s abstraktním grafem, zavedeme
si specializovanou terminologii.

\begin{definice}
Nechť $a$ je vrchol. Potom \emph{položky} $E(a)$ jsou všichni
besprostřední synové vrcholu $a$. Podstrom zakořeněný v $a$ budeme značit
$T(a)$, striktní podstrom $T'(a) = T(a) \setminus a$.

Pro každou položku $e \in E(a)$ je $a$ \emph{nadřazeným adresářem} $p(e)$.
\end{definice}

Každý vrchol je určen svým názvem a odkazem na soubor. Proto, pokud mluvíme v
kontextu adresářových stromů, budeme vrcholy rovněž nazývat \emph{soubory} Z
této definice se nám z jednoho souboru (daného svým inodem), na který odkazuje
více vrcholů, stane více rozlišitelných souborů.

\section{Požadavky na formát popisu}

Při sestavování formátu popisu, ve které se reprezentuje adresářový strom, byly
kladeny tyto požadavky:

\begin{itemize}
\item Jednoznačnost výsledných dat
\item Minimalizace potřebného prostoru pro uložení celého stromu a času na
jeho přečtení, minimalizace počtu průchodů a zpětných skoků
\item Zpětná kompatibilita s dřívějšími verzemi programu a dopředná syntaktická
kompatibilita
\end{itemize}

Protože každá adresářová struktura odpovídá stromu, můžeme k jeho popisu využít
metody kódování stromů do seznamu. Pak není třeba si pro každý vrchol pamatovat
celou jeho cestu.

Aby bylo toto stromové uspořádání jednoznačné, potřebujeme pro každý adresář
$a$ určit lineární uspořádání $T(a)$. Pro účely čtení nejlépe funguje
preorder uspořádání, kde v každém adresářovém podstromu $T(a)$ je na prvním
místě $a$ a navíc $E(a)$ jsou uspořádané lexikograficky, pro jejich podstromy
postoupíme rekurzivně.

Rekonstrukce cesty k danému souboru je potom v tomto uspořádání při lineárním
průchodu velmi jednoduchá. Při průchodu pro každý podstrom narazíme na jeho
kořen jako první, tudíž jde udržovat bez větších problémů aktuální větev celého
stromu.

Toto uspořádání nám rovněž poskytuje velmi jednoduchý způsob, jak přeskakovat
celý podstrom. Stačí si u jeho kořene zapamatovat adresu na konec podstromu
nebo velikost jeho reprezentace.

Tyto volby nám již stačí k tomu, aby celý formát záznamu byl přečitelný na
jeden lineární průchod.

Z těchto požadavků dále vyplývá, že za účelem šetření prostoru budeme
preferovat binární formát oproti formátu textovému. Binární formát však nelze
otevřít v libovolném textovém editoru a pak jej číst/upravovat. V tomto případě
jsou úpravy naštěstí nežádoucí. Na druhou stranu to znamená, že pro jejich
čtení bude potřeba použít program k tomu přímo uzpůsobený.

Nemá smysl se snažit dodržovat fixní šířku reprezentace všech dat. Pro mnoho
dat nemáme zaručenou jejich velikost. Proto pro jejich reprezentaci v tomto
případě musíme určit velikost jejich přihrádky a zde nastávají dva problémy.

Buď by byla zvolená velikost příliš malá, potom ale nemáme dost místa na
uložení dat, nebo při nastavení příliš velkého rozsahu se použije zbytečně
mnoho prostoru. Jako nejlepší řešení je proto použití kódování variabilní délky
pro ta data, u kterých neznáme jejich rozsah velikostí předem, přestože si tím
zkomplikujeme zápis i čtení.

\section{Formát popisu}

Syntaktická část je obecná pro všechna použití a snaží se být kompatibilní
dopředně i zpětně. Naopak sémantická specifikace se snaží být kompatibilní
pouze zpětně a závisí na verzi programu. Nejprve se podíváme na syntaxi.

Jak jsme již naznačili předem, celý formát záznamu bude binární. Ten se bude
skládat ze čtyřech částí:

\begin{enumerate}
\item Hlavička popisu, obsahující:
\begin{itemize}
\item Identifikátor formátu souboru
\item Metadata vztahující se na celou reprezentaci struktury
\item Specifikace sloupečků pro každý záznam
\end{itemize}
\item Samotné záznamy vrcholů, obsahující povinné a podmnožinu nepovinných
sloupečků
\end{enumerate}

Pro zjednodušení zápisu proměnných si nadefinujeme speciální notaci.

\def\bstr{{:}}
\def\Bstr{{::}}
\def\VarInt{\textsc{VarInt}}
\def\norm#1{\| #1 \|}

\begin{definice}
$k \bstr n$ značí binární řetězec $k$ délky $n$.
Pokud je navíc $k$ složený z~podřetězců $k_1,\dots,k_m$, potom $k$ lze rovněž
zapsat jako ${k\langle k_1,\dots,k_m\rangle} \bstr n$. Podřetězce
$k_1,\dots,k_n$ mohou být uvnitř zapsány stejným způsobem.

Pokud je binární řetězec $k$ délky $8n, n > 0$ (tedy zarovnaný na celé bajty),
lze rovněž použít značení $k \Bstr n$ ekvivalentní s $k \bstr 8n$.
\end{definice}

\begin{prikl} Ukažme si nyní značení na několika jednoduchých příkladech:
\begin{itemize}
\item Binární zápis $32$-bitového čísla $i$ lze značit $i \Bstr 4$ nebo $i \bstr 32$.
\item $10$-bitový řetězec $r$ rozdělený na dva $5$-bitové podřetězce $r_1$ a
$r_2$ má značení ${r\langle r_1 \bstr 5, r_2 \bstr 5\rangle} \bstr 10$.
%\item Bitové pole $p = p_1,\dots,p_6$ reprezentované binárním řetězcem délky 6
%označíme ${p\langle p_1, \dots, p_6\rangle} \bstr 6$.
\item Řetězec $r$ o délce $n$ bajtů lze zapsat jako $r \Bstr n$.
\end{itemize}
\end{prikl}

V tomto formátu souboru budeme pro nezáporné číslo $k$ často používat speciální
reprezentaci, která používá variabilní počet bajtů závisející na jeho
velikosti, nejvýše však 64 bitů. Tomuto zápisu budeme říkat \VarInt.

Pokud se binární zápis $x$ vejde do $7n$ bitů, ale ne do $7(n-1)$
bitů, na jeho zápis použijeme $n$ bajtů. Prvních $n$ bitů prvního bajtu je
$1^{n-1}0$, v případě $n=9$ uvažujeme pouze $1^8$.
Zbytek nevyužitých bitů i v prvním bajtu je použit na zápis čísla $x$.

Počet bajtů, kolik zabere \VarInt{} zápis čísla $x$, budeme značit $\norm x$.

Jak vypadají všechny možné zápisy, lze vidět v tabulce \ref{tab:VarInt}.

\begin{table}[h]

\centering
\begin{tabular}{rccl}
Rozsah $x$ & Bitů nejvýše & Počet bajtů $\norm x$ & Výsledný \VarInt \\
\hline
$0      \dots 2^7-1$	& 7 & 1	& {\tt 0xxxxxxx} \\
$2^{7}  \dots 2^{14}-1$	& 14& 2	& {\tt 10xxxxxx} + 1 bajt \\
$2^{14} \dots 2^{21}-1$	& 21& 3	& {\tt 110xxxxx} + 2 bajty\\
$\cdots$ & $\cdots$ & $\cdots$ & $\cdots$ \\
%$2^{21} \dots 2^{28}-1$	& 28& 4	& {\tt 1110xxxx} \\
%$2^{28} \dots 2^{35}-1$	& 35& 5	& {\tt 11110xxx} \\
%$2^{35} \dots 2^{42}-1$	& 42& 6	& {\tt 111110xx} \\
%$2^{42} \dots 2^{49}-1$	& 49& 7	& {\tt 1111110x} \\
$2^{49} \dots 2^{56}-1$	& 56& 8	& {\tt 11111110} + 7 bajtů\\
$2^{56} \dots 2^{63}-1$	& 63& 9	& {\tt 11111111} + 8 bajtů\\
\end{tabular}
\caption{Všechny možné rozsahy \VarInt{}u}
\label{tab:VarInt}
\end{table}

\subsection{Hlavička popisu}

\XXX{Magic, metadata, specifikace povinných sloupečků.}

Celý soubor obsahuje na svém začátku svůj identifikátor -- krátký řetězec
identifikující třídu formátů a číslo identifikující jeho verzi.

Po tomto identifikátoru následuje seznam metadat. Každá položka metadat začíná
svým sémantickým identifikátorem $h = \langle str \bstr 1,id \rangle \Bstr 4$.
Konec seznamu metadat nastává, když $h = 0^{32}$. V~opačném případě následuje
délka položky metadat $k$ uložena ve \VarInt{}u. Nakonec následuje $k$ bajtů
obsahujících obsah dané položky.

Interpretace metadat závisí pouze na sémantické hodnotě $id$. Pokud je pro
aktuální verzi programu hodnota $id$ neznámá, smí program tuto položku
ignorovat. Je doporučeno v~takovém případě vypsat chybovou hlášku včetně obsahu
metadat. Bit $str$ je naopak nápověda pro program, zda daná metadata lze
interpretovat jako textový řetězec.

Jestliže se vyskytne více instancí metadat se stejným $id$ (nezáleží na bitu
$str$), budou platná pouze ta poslední.

Nyní následují seznamy povinných a nepovinných sloupečků každého záznamu. Obojí je
specifikováno stejným způsobem:

Každá položka v~seznamu sloupečků začíná identifikátorem $h = \langle type
\bstr 2, str \bstr 1, id \rangle \Bstr 4$. Stejně, jako u~specifikace metadat,
$h = 0^{32}$ značí konec seznamu. $type$ značí, o~jaký typ sloupečku se jedná:

\begin{itemize}
\item $00$ -- data fixní šířky. V~takovém případě následuje ještě
\VarInt{} $k$ značící délku dat.
\item $01$ -- číslo ve \VarInt{}u.
\item $10$ -- data variabilní délky.
\item $11$ -- v~současné verzi formátu nevuyžito.
\end{itemize}

Tyto tři hlavní typy jsou dostatečně obecné, aby šla zaznamenat libovolná data.
Bližší specifika typu sloupečku jsou závislá na jeho sémantickém významu podle
$id$. Význam bitu $str$ je stejný, jako u~specifikace metadat.

Pokud se v~tomto případě vyskytne více sloupečků se stejným $id$, každá
instance se vyskytuje v~záznamech, pouze data z~posledního výskytu jsou platná.
Program navíc není povinen podporovat všechny dvojice $(id,type)$. V~případě
neznámého $id$ nebo dvojice $(id, type)$ musí program stále číst sloupečky
(jelikož se stále v~záznamech vyskytují), ale jejich obsah smí zahodit.

\begin{prikl}
Nyní se podívejme na ukázkovou hlavičku. Mějme dvě položky metadat, první je řetězec
\texttt{Hello World} identifikovaný číslem $42$. Druhá položka je 64-bitové číslo \texttt{0xdeadbeef0badf00d} identifikované číslem $2018$. Potom seznam metadat je uložen takto:

|0x80|0|0|42| |11| |Hello World| |0|0|2018| |8| |0xdeadbeef0badf00d| |0|0|0|0|

\XXX{Zlepšit formátování příkladu}

\end{prikl}

\subsection{Formát záznamu}

Po hlavičce následuje uspořádaný seznam jednotlivých záznamů souboru. Nechť $C$
je seznam povinných a $O$ seznam nepovinných sloupečků. Každý sloupeček v
seznamech si pamatuje svůj $id$, $type$ a $k$, pokud $type = 00$.

Záznam začíná svou délkou $n$ ve \VarInt{}u. Samotné $\norm{n}$ se do této
délky nezapočítává.

Nyní pro každý sloupeček z $C$ následují jeho data v záznamu. Pro data fixní či
variabilní délky jednoduše následuje $k$ bajtů dat. U dat variabilní délky je
navíc před těmito $k$ daty uloženo $k$ jako \VarInt. Pro $type = 01$ je daty
sloupečku číslo ve \VarInt{} podobě.

Po seznamu dat povinných sloupečků následuje bitové pole $q$ velikosti $\lceil
|O|/8 \rceil$, kde $i$-tý nejnižší bit $q$ značí, zda záznam obsahuje data
$i$-tého nepovinného sloupečku v seznamu $O$.

Poté následují data nepovinných sloupečků $O$. Jestliže $q[i] = 0$, není
uloženo nic. Jinak jsou uložena data stejným způsobem, jako u dat povinných
sloupečků.

\section{Hešování vrcholů}

Abychom mohli rozpoznávat, že se podstromy změnily vůči sobě, potřebujeme
způsob, jak je od sebe rozpoznat. Názvy jsou hlavní klíče, v případě rozdílných
názvů považujeme tyto vrcholy za úplně nezávislé. Pro rozpoznání, zda se
změnily stejné vrcholy, proto potřebjeme nějakou signaturu. 

Ta se skládá ze dvou částí. První část jsou metadata, jakožto typ vrcholu,
velikost podstromu, apod. Druhá, mnohem důležitější část, je signatura
samotného obsahu souboru. Pro symbolické linky budeme jejich obsah uvažovat
jejich cílovou adresu. O tom, jak budeme uvažovat obsah adresářů, povíme více v
sekci \ref{sect:hesovani_adresaru}.

Ne všechny vrcholy ale mají dobře definovaný obsah. Roury a zařízení, které se
mohou v POSIXovém souborovém systému nacházet, mají velmi pomíjivý obsah.
Navíc se může stát, že při čtení obsahu souboru nastane chyba a nebudeme
schopni jej celý přečíst. Z tohoto důvodu se může u některých vrcholů obsah
nevyskytovat.

Protože obsahy souborů mohou být potenciálně velmi velké, nemůžeme je používat
přímo. Z tohoto důvodu budeme obsahy hešovat a poté porovnávat pouze tyto heše.

\subsection{Výběr hešovací funkce}

Heše obsahu, kromě metadat, budou jediný způsob, jak rozpoznat rozdílné obsahy
mezi dvěma verzemi vrcholu. Tudíž je velmi důležité vybrat takovou hešovací
funkci, ve které je pravděpodobnost, že nastane kolize, takřka nulová.

Zamiřme tudíž ke kryptografickým hešům, od kterých tuto vlastnost očekáváme. Podívejme se speciálně na tyto kandidáty:

\begin{itemize}
\item MD5 byla populární funkce na počítání signatury obsahu, avšak se již
dávno ukázalo, že ji lze velmi snadno rozbít [\cite{wang2005break}]. Tudíž je
nevhodná.
\item SHA-1 je rovněž velmi rozšířená funkce, kterou například používá
verzovací systém git. Bohužel i na tuto funkci se nedávno podařilo úspěšně
zaútočit [\cite{stevens2017first}].
\item SHA-2 je novější množina hešovacích funkcí, která vychází z SHA-1.
\item SHA-3 je nejmladší z rodiny hešovacích funkcí SHA, jenž, na rozdíl od svých předků, používá permutaci Keccak. [\cite{dworkin2015sha}]
\end{itemize}

\XXX{Přidat výběr SHA-256, paralelní hešování, Sakura}

\subsection{Hešování adresářů}\label{sect:hesovani_adresaru}