\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
-\note{Define server state as an appropriate tuple and then give pseudocode here for updating that tuple...}\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
the entry owner inserts a newer update into the queue.}\r
\item Queue state entry: Includes queue size \newline {The purpose \r
of this is for the client to tell if the server lies about the number \r
-of slots in the queue, e.g. if there are 2 queue state entry in the queue, \r
+of slots in the queue, e.g. if there are 2 queue state entries in the queue, \r
e.g. 50 and 70, the client knows that when it sees 50, it should expect \r
at most 50 slots in the queue and after it sees 70, it should expect \r
50 slots before that queue state entry slot 50 and at most 70 slots. \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
+\textbf{Helper Function} \\\r
+$MaxSlot(SL')= \langle s, sv \rangle \mid \langle s, sv \rangle \r
+\in SL' \wedge \forall \langle s', sv' \rangle \in SL', s \geq s'$ \\\r
+$MinSlot(SL')= \langle s, sv \rangle \mid \langle s, sv \rangle \r
+\in SL' \wedge \forall \langle s', sv' \rangle \in SL', s \leq s'$ \\\r
+$SeqN(\langle s, sv \rangle)=s$ \\\r
+$SlotVal(\langle s, sv \rangle)=sv$ \\\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_p,sv_p,max'$}\r
+\If{$(max' \neq \emptyset)$}\Comment{Resize}\r
+\State $max \gets max'$\r
+\EndIf\r
+\State $\langle s_n,sv_n \rangle \gets MaxSlot(SL)$\Comment{Last sv}\r
+\State $s_n \gets SeqN(\langle s_n,sv_n \rangle)$\r
+\If{$(s_p = s_n + 1)$}\r
+ \If{$n = max$}\r
+ \State $\langle s_m,sv_m \rangle \gets MinSlot(SL)$\Comment{First sv}\r
+ \State $SL \gets SL - \{\langle s_m,sv_m \rangle\}$\r
+ \Else \Comment{$n < max$}\r
+ \State $n \gets n + 1$\r
+ \EndIf\r
+ \State $SL \gets SL \cup \{\langle s_p,sv_p \rangle\}$\r
+ \State \Return{$true$}\r
+\Else\r
+ \State \Return{$(false,\{\langle s,sv \rangle \in SL \mid \r
+ s \geq s_p\})$}\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