From 641032c5c1adc790f41020863d9af3d8d8522499 Mon Sep 17 00:00:00 2001 From: Ali Younis Date: Thu, 3 Nov 2016 12:46:44 -0700 Subject: [PATCH] Changes --- doc2/iotcloud.tex | 324 +++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 318 insertions(+), 6 deletions(-) diff --git a/doc2/iotcloud.tex b/doc2/iotcloud.tex index e882dd9..712f152 100644 --- a/doc2/iotcloud.tex +++ b/doc2/iotcloud.tex @@ -83,6 +83,10 @@ $RejectedSlotList$ = ordered list of the sequence numbers of slots that this cli \subsection{Helper Functions} The following helper functions are needed:\\ +$MaxSlot(SL_s)= \tuple{s, sv} \mid \tuple{s, sv} \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \geq s_s$ \\ +$MinSlot(SL_s)= \tuple{s, sv} \mid \tuple{s, sv} \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \leq s_s$ \\ + + % Get Size \noindent\fbox{% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} @@ -116,7 +120,7 @@ Get the next sequence number for insertion into the block chain.\\ \begin{algorithmic}[1] \Function{GetNextSeq}{$k$} \LeftComment{Get the largest known sequence number} - \State $seq_{ret} \gets seq$ such that $\tuple{seq, DE}\in LocalSlots \land (\forall \tuple{seq', DE'} \in LocalSlots, seq \geq seq')$\\ + \State $seq_{ret} \gets seq$ such that $\tuple{id, seq}\in LastSlo \land (\forall \tuple{id', seq'} \in LastSlo, seq \geq seq')$\\ \LeftComment{Add one to the largest seq number to generate the new seq number} \State \Return{$seq_{ret} + 1$} @@ -366,7 +370,7 @@ A new key data entry is always live.\\ \noindent\fbox{% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} \textbf{Check Abort Live:}\\ -Check if an abort data entry is live or not. Abort is dead if the device whos transaction was aborted sees the abort. This is checked by seeing if that device inserted a slot into the block chain which has a sequence number that is larger than the aborts sequence number.\\ +Check if an abort data entry is live or not. Abort is dead if the device whos transaction was aborted sees the abort. This is checked by seeing if that device inserted a slot into the block chain which has a sequence numberl that is larger than the aborts sequence number.\\ \begin{algorithmic}[1] \Function{CheckAbortLive}{$abort_a, seq_a$} \State $\tuple{seq_{a_{trans}},id_a} \gets abort_a$\\ @@ -547,7 +551,6 @@ Generate a commit data entry.\\ \end{varwidth}% } - % Data Entry Set Has Space \noindent\fbox{% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} @@ -608,6 +611,310 @@ Generate the data entry rescued version of the entry. For some data entry types \end{varwidth}% } +% Check Slot Hmacs +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Check Slot HMACs:}\\ +Check that each slot has not been tampered with by checking that the stored HMAC matches the calculated HMAC. Also check thatthe slot number reported by the server matches the slot number of the actual slot.\\ +\begin{algorithmic}[1] +\Function{CheckSlotsHmacAndSeq}{$Slots_a$} + \ForAll{$slot_a \in Slots_a$} + \State $\tuple{seq_{a_1}, \tuple{seq_{a_2},id_a,DE_a,hmac_{a_p},hmac_{a_c}}} \gets slot_a$ + \State $calchmac \gets $ \Call{GenerateHmac}{$seq_{a_2}, id_a, DE_a, hmac_{a_p}$} + + \If{$seq_{a_1} \neq seq_{a_2}$} + \State \Call{Error}{"Slot sequence number mismatch"} + \ElsIf{$calchmac \neq hmac_{a_c}$} + \State \Call{Error}{"Slot HMAC mismatch"} + \EndIf + \EndFor +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + +% Check HMAC Chain +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Check HMAC Chain:}\\ +Check that the HMAC chain has not been violated.\\ +\begin{algorithmic}[1] +\Function{CheckHmacChain}{$Slots_a$} + \State $SlotsList \gets Slots_a$ sorted by sequence number\\ + + + \LeftComment{Check all new slots} + \ForAll{$index \in [2: |SlotsList|]$} + \State $\tuple{seq_{a_1}, \tuple{seq_{a_2},id_a,DE_a,hmac_{a_p},hmac_{a_c}}} \gets SlotList[i-1]$ + \State $\tuple{seq_{b_1}, \tuple{seq_{b_2},id_b,DE_b,hmac_{b_p},hmac_{b_c}}} \gets SlotList[i]$ + + \If{$hmac_{b_p} \neq hmac_{b_c}$} + \State \Call{Error}{"Invalid previous HMAC."} + \EndIf + \EndFor\\ + + \LeftComment{Check against slots that we already have in the block chain} + \If{$|LocalSlots| \neq 0$} + \State $\tuple{seq, SDE} \gets $\Call{MaxSlot}{$LocalSlots$} + \State $\tuple{seq{last_2},id_{last},DE_{last},hmac_{last_p},hmac_{last_c}} \gets SDE$\\ + + \State $\tuple{seq_{a_1}, \tuple{seq_{a_2},id_a,DE_a,hmac_{a_p},hmac_{a_c}}} \gets SlotList[1]$\\ + + \If{$(seq_{last_2} + 1) = seq_{a_1}$} + \If{$hmac_{a_p} \neq hmac_{last_c}$} + \State \Call{Error}{"Invalid previous HMAC."} + \EndIf + \EndIf + \EndIf + +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + + +% Check For Old Slots +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Check For Old Slots:}\\ +Check if the slots are not new. Checks if the "new" slots are actually new or if they are older than the most recent slot that we have.\\ +\begin{algorithmic}[1] +\Function{CheckOldSlots}{$Slots_a$} + \State $\tuple{seq_{new}, Dat_{new}} \gets$ \Call{MinSlot }{$Slots_a$} \Comment{Get the oldest new slot} + \State $\tuple{seq_{local}, Dat_{local}} \gets$ \Call{MaxSlot }{$LocalSlots$} \Comment{Get the newest slot seen}\\ + + \If{$seq_{new} \leq seq_{local}$} \Comment{The slots were not newer than what was already seen} + \State \Call{Error}{"Server sent old slots."} + \EndIf\\ + + \LeftComment{Check if slots have the same sequence number but different data entries} + \ForAll{$\tuple{seq, Dat} \in Slots_a$} + \If{$\exists \tuple{seq', Dat'} \in (LocalSlots \cup Slots_a), seq'=seq \land Dat' \neq Dat$} + \State \Call{Error}{"Slot sequence number match but data does not"} + \EndIf + \EndFor + +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + +% Get All Queue States with Sequence numbers +% \noindent\fbox{% +% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +% \textbf{Get All Queue States with Sequence numbers:}\\ +% Gets all the queue states with the sequence number of the slot that the queue state was inside. +% \begin{algorithmic}[1] +% \Function{GetQStateWithSeq}{$Slots_a$} +% \State $QSet \gets \emptyset$\\ + +% \ForAll{$\tuple{seq_1', \tuple{seq_2',id',DE',hmac_p', hmac_c'}} \in Slots_a$} +% \ForAll{$de' \in DE'$} +% \If{$de'$ is a $qstate$} +% \State $QSet \gets QSet \cup \{\tuple{seq_1', de'}\}$ +% \EndIf +% \EndFor +% \EndFor\\ + +% \State \Return{$QSet$} +% \EndFunction +% \end{algorithmic} +% \end{varwidth}% +% } + +% Get All Queue States +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Get All Queue States:}\\ +Gets all the queue states from the slots that were passed in.\\ +\begin{algorithmic}[1] +\Function{GetQState}{$Slots_a$} + \State $QSet \gets \emptyset$\\ + + \ForAll{$\tuple{seq_1', \tuple{seq_2',id',DE',hmac_p', hmac_c'}} \in Slots_a$} + \ForAll{$de' \in DE'$} + \If{$de'$ is a $qstate$} + \State $QSet \gets QSet \cup \{de'\}$ + \EndIf + \EndFor + \EndFor\\ + + \State \Return{$QSet$} +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + + +% Check Size With Gap +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Check Size With Gap:}\\ +Checks that the block chain size is correct when there is a gap in the block chain. This check makes sure that the server is not hiding any information from the client. If there is a gap and there is only 1 queue state in the new slot entries then there must have at least that many slots since the old slot entry must have been purged. If there is more than 1 queue state then the block chain is still growing check the smallest max size and there should be at least that many slots. \\ +\begin{algorithmic}[1] +\Function{CheckSizeWithGap}{$Slots_a$} + %\State $QSSet \gets $ \Call{GetQStateWithSeq}{$Slots_a$} + %\State $\tuple{seq_{max}, size_{max}} \gets \tuple{seq, size}$ such that $\tuple{seq, size} \in QSSet \land \forall \tuple{seq', size'} \in QSSet, size \geq size'$ \Comment{Get largest size} + %\State $\tuple{seq_{min}, size_{min}} \gets \tuple{seq, size}$ such that $\tuple{seq, size} \in QSSet \land \forall \tuple{seq', size'} \in QSSet , size \leq size'$ \Comment{Get smallest size} + + \State $QSet \gets $ \Call{GetQState}{$Slots_a$} + \State $size_{max} \gets size$ such that $size \in QSet \land \forall size' \in QSet, size \geq size'$ + \State $size_{min} \gets size$ such that $size \in QSet \land \forall size' \in QSet, size \leq size'$ + \State $Slots_{oldmax} \gets \emptyset$\\ + + + \LeftComment{If only 1 max size then we must have all the slots for that size} + \If{$(|QSSet| = 1) \land (|Slots_a| \neq size_{max})$} + \State \Call{Error}{"Missing Slots"} + \EndIf\\ + + \LeftComment{We definitely have all the slots} + \If$|Slots_a| = size_{max}$ + \State \Return{} \Comment{We have all the slots} + \EndIf\\ + + \LeftComment{We must have at least this many slots} + \If$|Slots_a| < size_{min}$ + \State \Call{Error}{"Missing Slots"} + \EndIf\\ + +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + +% Check Size +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Check Size:}\\ +\begin{algorithmic}[1] +\Function{CheckSize}{$Slots_a$} + \State $\tuple{seq_{old_{max}}, Dat_{old_{max}}} \gets $ \Call{MaxSlot}{$LocalSlots$} + \State $\tuple{seq_{new_{max}}, Dat_{new_{max}}} \gets $ \Call{MinSlot}{$Slots_a$}\\ + + \If{$(seq_{old_{max}} + 1) = seq_{new_{max}}$} + \LeftComment{No Gap so cannot say anything about the size} + \State \Return{} + \Else + \LeftComment{Has a gap so we need to do checks} + \State \Call{CheckSizeWithGap}{$Slots_a$} + \EndIf +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + +% Initialize the expected size of the block chain +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Initialize the expected size of the block chain:}\\ +Initialize the expected size of the block chain based on the size at the server.\\ +\begin{algorithmic}[1] +\Function{InitExpSize}{$seq_a$} + \State $startingsize \gets 0$\\ + + \If{$seq_a < max\_size$} \Comment{Check whether saves slots are full on server} + \State $startingsize \gets seq_a$ + \Else + \State $startingsize \gets max\_size$ + \EndIf\\ + + \State \Return{$startingsize$} +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + +% Update the expected size of the block chain +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Update the expected size of the block chain:}\\ +Update the expected size of the block chain.\\ +\begin{algorithmic}[1] +\Function{UpdateExpSize}{$size_a$} + \State $size_a \gets size_a + 1$\\ + + \If{$size_a > max\_size$}\Comment{Expected size $\leq max\_size$} + \State $ssize_a \gets max_\_size$ + \EndIf\\ + + \State \Return{$size_a$} +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + + + + + + + +% Validate and Update +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Validate Update:}\\ +Validate the block chain and insert into the local block chain.\\ +\begin{algorithmic}[1] +\Function{ValidateUpdate}{$NewSlots_a$} + \State $\tuple{seq_{oldest}, Dat_{oldest}} \gets$ \Call{MinSlot}{$NewSlots_a$} + \State $\tuple{seq_{newest}, Dat_{newest}} \gets$ \Call{MaxSlot}{$NewSlots_a$} + + \State $currsize \gets $\Call{InitExpSize}{$seq_{oldest}$}\\ + + \State \Call{CheckSlotsHmacAndSeq}{$NewSlots_a$} \Comment{Check all the HMACs} + \State \Call{CheckHmacChain}{$NewSlots_a$} \Comment{Check HMAC Chain} + \State \Call{CheckOldSlots}{$NewSlots_a$} \Comment{Check if new slots are actually old slots} + \State \Call{CheckSize}{$NewSlots_a$} \Comment{Check if the size is correct}\\ + + \ForAll{$slot_a \in NewSlots_a$} \Comment{Process each slot} + \State $\tuple{seq_{a_1}, \tuple{seq_{a_2},id_a,DE_a,hmac_{a_p},hmac_{a_c}}} \gets slot_a$ + \ForAll{$de_a \in DE_a$} \Comment{Process each data entry} + + \EndFor\\ + + \State $currsize \gets $ \Call{UpdateExpSize}{$currsize$}\\ + \State $LocalSlots \gets LocalSlots \cup \{slot_a\}$ \Comment{Add to local Chain} + \EndFor + + + %Delete from local chain to maintain size + +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + + + + + + + + + + + +% Decrypt Validate Insert Slots +\noindent\fbox{% +\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} +\textbf{Decrypt Validate Insert Slots:}\\ +Decrypts slots, validates (checks for malicious activity) slots and inserts the slots into the local block chain.\\ +\begin{algorithmic}[1] +\Function{DecryptValidateInsert}{$NewSlots_a$} + \State $DecryptedSlots \gets \emptyset$ + \State $DDat \gets NULL$\\ + + \ForAll{$\tuple{seq', EDat'} \in NewSlots_a$} + \State $DDat \gets $ \Call{Decrypt}{$EDat'$} + \State $DecryptedSlots \gets DecryptedSlots \cup \tuple{seq',DDat}$ + \EndFor\\ + \State \Call{ValidateUpdate}{$DecryptedSlots$} +\EndFunction +\end{algorithmic} +\end{varwidth}% +} + % Check and Create Last Message Data Entry \noindent\fbox{% \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax} @@ -862,7 +1169,10 @@ Try to insert a transaction into the block chain. Does resizing, rescues and ins \State $DE \gets$ \Call{OptionalRescue}{$DE$}\\ \LeftComment{Send to server.} - \State $\tuple{sendsuccess, newslots} \gets $ \Call{SendToServer}{$seq, DE, newsize$} + \State $\tuple{sendsuccess, newslots} \gets $ \Call{SendToServer}{$seq, DE, newsize$}\\ + + \LeftComment{Insert the slots into the local bloakc chain} + \State \Call{DecryptValidateInsert}{$newslots$}\\ \State \Return{$transinserted \land success$} \Comment{Return if succeeded or not} @@ -871,8 +1181,6 @@ Try to insert a transaction into the block chain. Does resizing, rescues and ins \end{varwidth}% } - - \subsection{Client Interfaces} % Put KV pair @@ -952,4 +1260,8 @@ Commits the transaction into the block chain. Keeps attempting to insert the tr \end{varwidth}% } + + + + \end{document} -- 2.34.1