From 63606f2c98ef31f5dbc17cdd0a8849d1dc32a439 Mon Sep 17 00:00:00 2001 From: rtrimana Date: Thu, 7 Jul 2016 14:03:52 -0700 Subject: [PATCH] Adding client algorithm; modifying some parts of server algorithm - first draft --- doc/iotcloud.tex | 155 ++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 132 insertions(+), 23 deletions(-) diff --git a/doc/iotcloud.tex b/doc/iotcloud.tex index c0aaf1b..12266ac 100644 --- a/doc/iotcloud.tex +++ b/doc/iotcloud.tex @@ -2,11 +2,11 @@ \newcommand{\tuple}[1]{\ensuremath \langle #1 \rangle} \usepackage{color} \usepackage{amsthm} -\usepackage{algpseudocode} +\usepackage{algpseudocode}% http://ctan.org/pkg/algorithmicx \newtheorem{theorem}{Theorem} \newtheorem{defn}{Definition} \newcommand{\note}[1]{{\color{red} \bf [[#1]]}} - +\newcommand{\pushcode}[1][1]{\hskip\dimexpr #1\algorithmicindent\relax} \begin{document} \section{Approach} @@ -69,7 +69,7 @@ or user-level data) is dead if there is a newer slot from the same machine. \item Queue state entry is dead if there is a newer queue state entry. {In the case of queue state entries 50 and 70, this means that queue state -entry 50 is dead and 70 is live. However, not until the number of slotes reaches +entry 50 is dead and 70 is live. However, not until the number of slots reaches 70 that queue state entry 50 will be expunged from the queue.} \end{enumerate} @@ -125,46 +125,155 @@ Client can make a request to resize the queue. This is done as a write that comb \subsection{Server Algorithm} \begin{algorithmic}[1] -\Function{Server}{$m$,$max$,$s$,$Data*$} +%\Function{CallServer}{$m$,$max$,$s$,$Data*$} +\Function{CallServer}{$m,max,s,Data*$} \textit{ \newline{// m = client message (read/write/resize)} \newline{// max = maximum number of slots (input only for resize message)} \newline{// n = number of slots} \newline{// s = sequence number} -\newline{// t = latest sequence number on server} +\newline{// t = sequence numbers of slots on server} \newline{// d = sequence number difference (1 by default)} \newline{// Data = array of slots written/read (input only for write)} \newline{// Q = queue of slots on server} +\newline{// Slot = one data slot)} \newline{// Resize() returns the old last slot in the queue} \newline{// Append() updates Q and latest s after appending the new slot} \newline{// Append() returns the latest Slot written with its correct s} } \If{$m = read$} -\If{$s \in T = \{t_1, t_2, \dots, t_n\}$} -\State $Data := \{Slot_{s}, Slot_{s+1}, \dots, Slot_{t_n}\} \forall Slot_i \in Q$ -\Else -\State $Data := \emptyset$ -\EndIf + \If{$s \in T = \{t_1, t_2, \dots, t_n\}$} + \State $Data \gets \{Slot_{s}, Slot_{s+1}, \dots, Slot_{t_n}\} \forall Slot_i \in Q$ + \Else + \State $Data \gets \emptyset$ + \EndIf \ElsIf{$m = write$} -\If{$s = t_n + d$ \textbf{and} $n \leq max$ \textbf{and} $Data.length = 1$} -\State $newSlot := Data[1]$ -\If{$n = max$} -\State $DeleteFirst(Q)$ -\Else -\State // $n < max$ -\State $n := n + 1$ -\EndIf -\State $Data := Append(newSlot,Q)$ -\Else -\State $Data := \emptyset$ -\EndIf + \If{$(s = t_n + d) \land (n \leq max) \land (Length(Data) = 1$)} + \State $newSlot \gets Data[1]$ + \If{$n = max$} + \State $Data[2] \gets RemoveFirst(Q)$ + \State $Data[1] \gets Append(newSlot,Q)$ + \Else \Comment{$n < max$} + \State $n \gets n + 1$ + \State $Data[1] \gets Append(newSlot,Q)$ + \EndIf + \Else + \State $Data \gets \emptyset$ + \EndIf \ElsIf{$m = resize$} -\State $Data := Resize(max)$ + \State $Data \gets Resize(max)$ \EndIf \State \Return{$Data$} \EndFunction \end{algorithmic} +\subsection{Client Algorithm} +\begin{algorithmic}[1] +\Function{CallClient}{$uid,pw,d,m,max,s,Data*,Result*$} +\textit{ +\newline{// uid = user identification} +\newline{// pw = password} +\newline{// d = new data for write} +\newline{// m = client message (read/write/resize)} +\newline{// max = maximum number of slots (input only for resize message)} +\newline{// n = number of slots} +\newline{// s = sequence number for server request} +\newline{// t = sequence numbers of slots on server} +\newline{// mid = machine identification} +\newline{// seq = sequence number inside slot} +\newline{// newSlot = new slot} +\newline{// expSlot = expunged/expired slot} +\newline{// slotSeqE = slot sequence entry} +\newline{// M = list of all machines/devices with their respective latest s on client} +\newline{// Data = array of slots written/read (input only for write)} +\newline{// Result = array of decrypted and valid slots after a read} +\newline{// Slot = one data slot)} +\newline{// DSlot = one decrypted data slot)} +} +\State $SK = Hash(uid + pw)$ +\If{$m = read$} + \State $Data \gets CallServer(m,max,s,Data)$ + \If{$Data = \emptyset$} + \State $ReportError(\emptyset,read)$ + \Else + \If{$\neg HasCurrentQueueStateEntry(Data)$} + \State $ReportError(DSlot_i,read)$ + \EndIf + \ForAll{$Slot_i \in Data$} + \State $DSlot_i \gets Decrypt(SK,Slot_i)$\Comment{Check s and HMAC} + \If{$\neg (ValidSeqN(DSlot_i) \land ValidHmac(DSlot_i) \land $\\ + \pushcode[1] $ValidPrevHmac(DSlot_i))$} + \State $ReportError(DSlot_i,read)$ + \Else\Comment{Check only live entries} + \If{$IsLiveSlotSequenceEntry(DSlot_i)$} + \State $lastS \gets LastSeqN(DSlot_i)$ + \State $lastMid \gets LastMachineId(DSlot_i)$ + \If{$lastS \neq LastSeqN(lastMid,M)$} + \State $ReportError(DSlot_i,read)$ + \EndIf + \ElsIf{$IsLiveKeyValueEntry(DSlot_i)$} + \State $mid \gets MachineId(DSlot_i)$ + \State $seq \gets SeqN(DSlot_i)$ + \If{$IsOwnMid(mid)$} + \If{$IsLastS(mid,seq,Data) \land $\\ + \pushcode[1] $(seq \neq LastSeqN(mid,M))$} + \State $ReportError(DSlot_i,read)$ + \EndIf + \Else\Comment{Check s for other machines} + \If{$IsLastS(mid,seq,Data) \land $\\ + \pushcode[1] $(seq < LastSeqN(mid,M))$} + \State $ReportError(DSlot_i,read)$ + \EndIf + \EndIf\Comment{Check queue state entry} + \ElsIf{$IsLiveQueueStateEntry(DSlot_i)$} + \If{$IsCurrentQueueState(DSlot_i)$} + \If{$Length(Data) > QueueLength(DSlot_i)$} + \State $ReportError(DSlot_i,read)$ + \EndIf + \EndIf + \Else + \State $ReportError(DSlot_i,read)$ + \EndIf + \EndIf + \State $Result \gets Concat(Result, DSlot_i)$ + \EndFor + \EndIf + +\ElsIf{$m = write$} + \State $newSlot \gets CreateSlot(d)$ + \State $Data[1] \gets Encrypt(SK,newSlot)$ + \State $Data \gets CallServer(m,max,s,Data)$ + \If{$Data = \emptyset$} + \State $ReportError(\emptyset,write)$ + \Else\Comment Check for valid return value from server + \If{$\neg ValidOldLastEntry(Data[1])$} + \State $ReportError(Data[1],write)$ + \Else\Comment{Check if we need slot sequence entry} + \If{$Length(Data) = 2$} + \State $expSlot \gets Decrypt(SK,Data[2])$ + \State $mid \gets MachineId(expSlot)$ + \State $seq \gets SeqN(expSlot)$ + \If{$seq = LastSeqN(mid,M)$}\Comment{Liveness check} + \State $slotSeqE \gets CreateSlotSeqE(mid,seq)$ + \State $Data[1] \gets Encrypt(SK,slotSeqE)$ + \State $Data \gets CallServer(m,max,s,Data)$ + \EndIf + \Else + \State $ReportError(Data,write)$ + \EndIf + \EndIf + \EndIf + +\ElsIf{$m = resize$} + \State $Data \gets CallServer(m,max,s,Data)$ + \If{$Data = \emptyset$} + \State $ReportError(\emptyset,resize)$ + \EndIf +\EndIf +\State \Return{$Result$} +\EndFunction +\end{algorithmic} + \subsection{Formal Guarantees} \textit{To be completed ...} -- 2.34.1