\newcommand{\tuple}[1]{\ensuremath \langle #1 \rangle}\r
\usepackage{color}\r
\usepackage{amsthm}\r
+\usepackage{amsmath}\r
+\usepackage{algpseudocode}% http://ctan.org/pkg/algorithmicx\r
\newtheorem{theorem}{Theorem}\r
\newtheorem{defn}{Definition}\r
\newcommand{\note}[1]{{\color{red} \bf [[#1]]}}\r
-\r
+\newcommand{\push}[1][1]{\hskip\dimexpr #1\algorithmicindent\relax}\r
\begin{document}\r
\section{Approach}\r
\r
Server has finite length queue of entries + max\_entry\_identifier +\r
server login key\r
\r
-\textbf{Login}\r
-\note{Look at formal algorithm descriptions elsewhere, this is just informal prose... It really needs to be more precise...}\r
-\r
-\begin{enumerate}\r
-\item In the beginning, there are $d$ devices. Each of the \r
-devices has a randomly/user-chosen self-generated $m$-bit user \r
-identification $i$ and $n$-bit password $p$.\note{All devices being known in the beginning seems unreasonable...How about 1 device initially, and devices can be added at any time...}\r
-\item Each device registers these $i$ and $p$ with the server. \r
-The server appends ‘salt’ values, $k$-bit random strings $s1$ \r
-and $s2$, and generate hash values $j=h(i+s1)$ and \r
-$o=h(p+s2)$ for each $i$ and $p$. All $s1$, $s2$, $j$ and $o$ \r
-are then stored in the database.\note{Are these the same $i$ and $p$ as below, if so, you just gave away the password}\r
-\item Device to server validation is done by checking the hash values \r
-$j\textsc{\char13}$ and $o\textsc{\char13}$ from $i\textsc{\char13}$ and \r
-$p\textsc{\char13}$ that are given by users at login time against \r
-$i$ and $p$ that are stored in the database.\r
-\end{enumerate}\r
-\r
-\textbf{Symmetric Keys}\r
-\note{The user uses the same username/key to log into all devices}\r
-\begin{enumerate}\r
-\item In the beginning, there are $d$ devices. Each of the \r
-devices has a randomly/user-chosen self-generated $m$-bit user \r
-identification $i$ and $n$-bit password $p$. These $i$ and $p$ \r
-are used for device login on server.\r
-\item All of $d$ agree on a hash function $h$ that is not known by \r
-the server.\note{Doesn't make sense to agree on a hash function...People have a shared key.}\r
-\item A symmetric key for each device is generated by applying $h$\r
-to the value $(i + p)$ that gives $SK=h(i + p)$.\r
-\item This value $SK$ is pre-known and pre-stored by all other \r
-devices prior to operation of the data structure.\r
-\end{enumerate}\r
-\r
-\textbf{Data Structure on Server}\r
-\begin{enumerate}\r
-\item Server maintains a finite length $q$-entry FIFO queue \r
-$Q=\{0, 1, …, q-1\}$. It has a head and a tail pointers that keep track \r
-of head and tail slots.\r
-\item Server records a max entry identifier $max$ as a limit for $q$. \r
-It keeps track that $q \leq max$ at all times. When $q=max$, the queue \r
-mechanism allows this sequence of events when there is a new slot added:\r
-\begin{enumerate}\r
-\item Pointer for entry $0$ now points to entry $1$, making it the new \r
-entry $0$.\r
-\item Entry $0$ is expunged from the queue.\r
-\item New entry is added to the end of the queue, making it entry $q$.\r
-\item Pointer for entry $q-1$ is advanced to entry $q$, making it the new \r
-entry $q-1$.\r
-\end{enumerate}\r
-\item For client login, server maintains a table with values $i$, $p$,\r
-$s1$, and $s2$ that are generated when device registers itself on server \r
-for the first time.\r
-\end{enumerate}\r
-\r
\subsection{Entry layout}\r
Each entry has:\r
\begin{enumerate}\r
\r
\item Queue state entry is dead if there is a newer queue state entry.\r
{In the case of queue state entries 50 and 70, this means that queue state \r
-entry 50 is dead and 70 is live. However, not until the number of slotes reaches \r
+entry 50 is dead and 70 is live. However, not until the number of slots reaches \r
70 that queue state entry 50 will be expunged from the queue.}\r
\end{enumerate}\r
\r
(a) a slot with the message, and\r
(b) a request to the server\r
\r
+\subsection{Server Algorithm}\r
+$s \in SN$ is a sequence number\\\r
+$sv \in SV$ is a slot's value\\\r
+$slot_s = \tuple{s, sv} \in SL \subseteq SN \times SV$ \\\r
+\r
+\textbf{State} \\\r
+\textit{SL = set of live slots on server} \\\r
+\textit{max = maximum number of slots (input only for resize message)} \\\r
+\textit{n = number of slots} \\\r
+\r
+\begin{algorithmic}[1]\r
+\Function{GetSlot}{$s_g$}\r
+\State \Return{$\{\tuple{s, sv} \in SL \mid s \geq s_g\}$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{PutSlot}{$s',sv',max'$}\r
+\If{$(max' \neq \emptyset)$}\Comment{Resize}\r
+\State $max \gets max'$\r
+\EndIf\r
+\If{$(s' = s_n + d)$}\r
+ \If{$n = max$}\r
+ \State $SL \gets SL - \{\langle s_n,sv_n \rangle\}$\r
+ \Else \Comment{$n < max$}\r
+ \State $n \gets n + 1$\r
+ \EndIf\r
+ \State $SL \gets SL \cup \{\langle s',sv' \rangle\}$\r
+ \State \Return{$true$}\r
+\Else\r
+ \State \Return{$(false,\{\langle i,sv_i \rangle \in SL \mid \r
+ s' \leq i \leq s_n\})$}\r
+\EndIf\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\subsection{Client Algorithm}\r
+\begin{algorithmic}[1]\r
+\Function{CallClient}{$uid,pw,d,m,max,s,Data*,Result*$}\r
+\textit{\r
+\newline{// uid = user identification}\r
+\newline{// pw = password}\r
+\newline{// d = new data for write}\r
+\newline{// m = client message (read/write/resize)}\r
+\newline{// max = maximum number of slots (input only for resize message)}\r
+\newline{// n = number of slots}\r
+\newline{// s = sequence number for server request}\r
+\newline{// t = sequence numbers of slots on server}\r
+\newline{// mid = machine identification}\r
+\newline{// seq = sequence number inside slot}\r
+\newline{// newSlot = new slot}\r
+\newline{// expSlot = expunged/expired slot}\r
+\newline{// slotSeqE = slot sequence entry}\r
+\newline{// M = list of all machines/devices with their respective latest s on client}\r
+\newline{// Data = array of slots written/read (input only for write)}\r
+\newline{// Result = array of decrypted and valid slots after a read}\r
+\newline{// Slot = one data slot)}\r
+\newline{// DSlot = one decrypted data slot)}\r
+}\r
+\State $SK = Hash(uid + pw)$\r
+\If{$m = read$}\r
+ \State $Data \gets CallServer(m,max,s,Data)$\r
+ \If{$Data = \emptyset$}\r
+ \State $ReportError(\emptyset,read)$\r
+ \Else\r
+ \If{$\neg HasCurrentQueueStateEntry(Data)$}\r
+ \State $ReportError(DSlot_i,read)$\r
+ \EndIf\r
+ \ForAll{$Slot_i \in Data$}\r
+ \State $DSlot_i \gets Decrypt(SK,Slot_i)$\Comment{Check s and HMAC}\r
+ \If{$\neg (ValidSeqN(DSlot_i) \land ValidHmac(DSlot_i) \land $\\\r
+ \push[1] $ValidPrevHmac(DSlot_i))$}\r
+ \State $ReportError(DSlot_i,read)$\r
+ \Else\Comment{Check only live entries}\r
+ \If{$IsLiveSlotSequenceEntry(DSlot_i)$}\r
+ \State $lastS \gets LastSeqN(DSlot_i)$\r
+ \State $lastMid \gets LastMachineId(DSlot_i)$\r
+ \If{$lastS \neq LastSeqN(lastMid,M)$}\r
+ \State $ReportError(DSlot_i,read)$\r
+ \EndIf\r
+ \ElsIf{$IsLiveKeyValueEntry(DSlot_i)$}\r
+ \State $mid \gets MachineId(DSlot_i)$\r
+ \State $seq \gets SeqN(DSlot_i)$\r
+ \If{$IsOwnMid(mid)$}\r
+ \If{$IsLastS(mid,seq,Data) \land $\\\r
+ \push[1] $(seq \neq LastSeqN(mid,M))$}\r
+ \State $ReportError(DSlot_i,read)$\r
+ \EndIf\r
+ \Else\Comment{Check s for other machines}\r
+ \If{$IsLastS(mid,seq,Data) \land $\\\r
+ \push[1] $(seq < LastSeqN(mid,M))$}\r
+ \State $ReportError(DSlot_i,read)$\r
+ \EndIf\r
+ \EndIf\Comment{Check queue state entry}\r
+ \ElsIf{$IsLiveQueueStateEntry(DSlot_i)$}\r
+ \If{$IsCurrentQueueState(DSlot_i)$}\r
+ \If{$Length(Data) > QueueLength(DSlot_i)$}\r
+ \State $ReportError(DSlot_i,read)$\r
+ \EndIf\r
+ \EndIf\r
+ \Else\r
+ \State $ReportError(DSlot_i,read)$\r
+ \EndIf\r
+ \EndIf\r
+ \State $Result \gets Concat(Result, DSlot_i)$\r
+ \EndFor\r
+ \EndIf\r
+\r
+\ElsIf{$m = write$}\r
+ \State $newSlot \gets CreateSlot(d)$\r
+ \State $Data[1] \gets Encrypt(SK,newSlot)$\r
+ \State $Data \gets CallServer(m,max,s,Data)$\r
+ \If{$Data = \emptyset$}\r
+ \State $ReportError(\emptyset,write)$\r
+ \Else\Comment Check for valid return value from server\r
+ \If{$\neg ValidOldLastEntry(Data[1])$}\r
+ \State $ReportError(Data[1],write)$\r
+ \Else\Comment{Check if we need slot sequence entry}\r
+ \If{$Length(Data) = 2$}\r
+ \State $expSlot \gets Decrypt(SK,Data[2])$\r
+ \State $mid \gets MachineId(expSlot)$\r
+ \State $seq \gets SeqN(expSlot)$\r
+ \If{$seq = LastSeqN(mid,M)$}\Comment{Liveness check}\r
+ \State $slotSeqE \gets CreateSlotSeqE(mid,seq)$\r
+ \State $Data[1] \gets Encrypt(SK,slotSeqE)$\r
+ \State $Data \gets CallServer(m,max,s,Data)$\r
+ \EndIf\r
+ \Else\r
+ \State $ReportError(Data,write)$\r
+ \EndIf\r
+ \EndIf\r
+ \EndIf\r
+\r
+\ElsIf{$m = resize$}\r
+ \State $Data \gets CallServer(m,max,s,Data)$\r
+ \If{$Data = \emptyset$}\r
+ \State $ReportError(\emptyset,resize)$\r
+ \EndIf\r
+\EndIf\r
+\State \Return{$Result$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
\subsection{Formal Guarantees}\r
\r
\textit{To be completed ...}\r
\r
\begin{defn}[System Execution]\r
-Formalize a system execution as a sequence of slot updates... There\r
-is a total order of all slot updates.\r
+Let \\\r
+\begin{center}\r
+$Q = \{slot_{sn_1}, slot_{sn_2}, \dots, Slot_{sn_n}\}$, \\\r
+$SN = \{sn_1, sn_2, \dots, sn_n\}$ \\\r
+\end{center}\r
+denote a queue $Q$ of $n$ slots, with each slot entry being denoted by a\r
+valid sequence number $sn_i \in SN$. $Q$ represents a total order of all \r
+slot updates from all corresponding machines.\r
+%\textit{Formalize a system execution as a sequence of slot updates...\r
+%There is a total order of all slot updates.}\r
\end{defn}\r
\r
\begin{defn}[Transitive Closure]\r
-Define transitive closure relation for slot updates... There is an\r
-edge from a slot update to a slot receive event if the receive event\r
-reads from the update event.\r
+A transitive closure $\tau : \tau = \epsilon_{update(slot_i)} R $\r
+$\epsilon_{receive(slot_i)}$ is a relation from slot update event\r
+$\epsilon$ to a slot receive event $\epsilon$ for $slot_i$.\r
+%Define transitive closure relation for slot updates... There is an\r
+%edge from a slot update to a slot receive event if the receive event\r
+%reads from the update event.\r
\end{defn}\r
\r
\begin{defn}[Suborder]\r
-Define suborder of total order. It is a sequence of contiguous slots\r
-updates (as observed by a given device).\r
+Let \\\r
+\begin{center}\r
+$q = \{slot_{i}, slot_{i+1}, \dots, slot_{j}\}, \r
+sn_1 \leq i \leq j \leq sn_n \Longrightarrow q \subseteq Q$\r
+\end{center}\r
+denote a suborder of the total order. Set q is a sequence of contiguous\r
+slot updates that is a subset of a total order of all slot updates in Q.\r
+%Define suborder of total order. It is a sequence of contiguous slots\r
+%updates (as observed by a given device).\r
\end{defn}\r
\r
\begin{defn}[Prefix of a suborder]\r
-Given a sub order $o=u_{i},u_{i+1},...,u_j, u_{j+i},..., u', ...$ and\r
-a slot update $u'$ in $o$, the prefix of $o$ is a sequence of all\r
-updates that occur before $u'$ and $u'$.\r
+Given a suborder \\ \r
+\begin{center}\r
+$q' = \{slot_{i}, slot_{i+1}, \dots, slot_{j}, \dots\}, \r
+sn_1 \leq i \leq j \leq sn_n \Longrightarrow \r
+q' \subseteq Q$\r
+\end{center}\r
+with $slot_{j}$ as a slot update in $q'$, the prefix of $q'$ is a sequence \r
+of all slot updates $\{slot_{i}, slot_{i+1}, \dots, slot_{j-1}\} \cup\r
+slot_{j}$.\r
+%Given a sub order $o=u_{i},u_{i+1},...,u_j, u_{j+i},..., u', ...$ and\r
+%a slot update $u'$ in $o$, the prefix of $o$ is a sequence of all\r
+%updates that occur before $u'$ and $u'$.\r
\end{defn}\r
\r
\begin{defn}[Consistency between a suborder and a total order]\r
-A suborder $o$ is consistent with a total order $t$, if all updates in $o$ appear in $t$ and they appear in the same order.\r
+A suborder $q'$ is consistent with a total order $T$ of $Q$, if all\r
+updates in $q'$ appear in $T$ and they appear in the same order, as \r
+the following:\r
+\begin{center}\r
+$q' = \{slot_{i}, slot_{i+1}, \dots, slot_{j}\},$\r
+$T = \{slot_{sn_1}, \dots, slot_{i}, slot_{i+1}, \dots, slot_{j}, \dots,\r
+slot_{sn_n}\},$ \\ $sn_1 \leq i \leq j \leq sn_n \Longrightarrow\r
+q' \subseteq T$\r
+\end{center}\r
+%A suborder $o$ is consistent with a total order $t$, if all updates in $o$ %appear in $t$ and they appear in the same order.\r
\end{defn}\r
\r
\begin{defn}[Consistency between suborders]\r
-Define notion of consistency between suborders... Two suborders U,V\r
-are consistent if there exist a total order T such that both U and V\r
-are suborders of T.\r
+Two suborders U and V are consistent if there exist a total order T \r
+such that both U and V are suborders of T.\r
+\begin{center}\r
+$U = \{slot_{i}, slot_{i+1}, \dots, slot_{j}\},$ \\\r
+$V = \{slot_{k}, slot_{k+1}, \dots, slot_{l}\},$ \\\r
+$sn_1 \leq i \leq j \leq k \leq l \leq sn_n,$ \\\r
+$U \subset T \land V \subset T$ \\\r
+$T = \{slot_{sn_1}, \dots, slot_{i}, slot_{i+1}, \dots, slot_{j}, $\\\r
+$\dots, slot_{k}, slot_{k+1}, \dots, slot_{l}, \dots, slot_{sn_n}\}$\r
+\end{center}\r
+%Define notion of consistency between suborders... Two suborders U,V\r
+%are consistent if there exist a total order T such that both U and V\r
+%are suborders of T.\r
\end{defn}\r
\r
\begin{defn}[Error-free execution]\r
-Define error-free execution --- execution for which the client does\r
-not flag any errors...\r
+An error-free execution, for which the client does not flag any errors\r
+is defined by the following criteria:\r
+\begin{enumerate}\r
+\item Item 1\r
+\item Item 2\r
+\end{enumerate}\r
+%not flag any errors...\r
+%Define error-free execution --- execution for which the client does\r
+%not flag any errors...\r
\end{defn}\r
\r
\begin{theorem} Error-free execution of algorithm ensures that the suborder\r
\r
Idea is to separate subspace of entries... Shared with other cloud...\r
\end{document}\r
+\r
projects / iotcloud.git / blobdiff