From ca082f4127a2a5a1e5fe13e954e14d99386bed67 Mon Sep 17 00:00:00 2001 From: rtrimana Date: Mon, 18 Jul 2016 16:58:15 -0700 Subject: [PATCH] Adding client part that puts slots on server; handling kv and cr entries; in progress of integrating handling qs and ss entries --- doc/iotcloud.tex | 205 ++++++++++++++++++++++++++++++++++++----------- 1 file changed, 160 insertions(+), 45 deletions(-) diff --git a/doc/iotcloud.tex b/doc/iotcloud.tex index db89d2b..08c71c6 100644 --- a/doc/iotcloud.tex +++ b/doc/iotcloud.tex @@ -177,6 +177,7 @@ $SlotVal(\tuple{s, sv})=sv$ \\ \end{algorithmic} \subsection{Client Algorithm} +\subsubsection{Reading Slots} \textbf{Data Entry} \\ $de$ is a data entry \\ $k$ is key of entry \\ @@ -201,14 +202,14 @@ $sv_s = \tuple{s, E(Dat_s)} = \textit{DT = set of $\tuple{k,v}$ on client} \\ \textit{MS = set of $\tuple{id, s_{last}}$ of all clients on client (initially empty)} \\ -\textit{$MS_c$ = set MS to save all $\tuple{id, s_{last}}$ pairs while +\textit{$MS_g$ = set MS to save all $\tuple{id, s_{last}}$ pairs while traversing DT after a request to server (initially empty)} \\ \textit{$SM$ = set of $\tuple{s, id}$ of all slots in a previous read (initially empty)} \\ -\textit{$max_c$ = maximum number of slots (initially $max_c > 0$)} \\ +\textit{$max_g$ = maximum number of slots (initially $max_c > 0$)} \\ \textit{m = number of slots on client (initially $m = 0 and m \leq n$)} \\ -\textit{$hmac_p$ = the HMAC value of the previous slot ($hmac_p = \emptyset$ -for the first slot)} \\ +\textit{$hmac_{p_g}$ = the HMAC value of the previous slot +($hmac_{p_g} = \emptyset$ for the first slot)} \\ \textit{$id_{self}$ = machine Id of this client} \\ \textit{SK = Secret Key} \\ \\ \textbf{Helper Functions} \\ @@ -249,9 +250,8 @@ $GetKeyVal(DT_s,k_s)= \tuple{k, v}$ \textit{such that} $\tuple{k, v} \end{algorithmic} \begin{algorithmic}[1] -\Function{ValidHmac}{$Dat_s,SK_s$} -\State $hmac_{stored} \gets GetCurrHmac(Dat_s)$ -\State $hmac_{computed} \gets Hmac(Dat_s,SK_s)$ +\Function{ValidHmac}{$DE_s,SK_s,hmac_{stored}$} +\State $hmac_{computed} \gets Hmac(DE_s,SK_s)$ \If{$hmac_{stored} = hmac_{computed}$} \State $valid \gets true$ \Else @@ -262,12 +262,11 @@ $GetKeyVal(DT_s,k_s)= \tuple{k, v}$ \textit{such that} $\tuple{k, v} \end{algorithmic} \begin{algorithmic}[1] -\Function{ValidPrevHmac}{$Dat_s,hmac_{p_s}$} +\Function{ValidPrevHmac}{$DE_s,hmac_{p_s},hmac_{p_{sto}}$} \If{$hmac_{p_s} = \emptyset$}\Comment{First slot - no previous HMAC} \State $valid \gets true$ \Else - \State $hmac_{stored} \gets GetPrevHmac(Dat_s)$ - \If{$hmac_{stored} = hmac_{p_s}$} + \If{$hmac_{p_{sto}} = hmac_{p_s}$} \State $valid \gets true$ \Else \State $valid \gets false$ @@ -279,7 +278,7 @@ $GetKeyVal(DT_s,k_s)= \tuple{k, v}$ \textit{such that} $\tuple{k, v} \begin{algorithmic}[1] \Function{GetQueSta}{$Dat_s$} -\State $DE_s \gets GetDatEnt(Dat_s)$ +\State $DE_s \gets GetDatEnt(DE_s)$ \State $de_{qs} \gets de_s$ \textit{such that} $de_s \in DE_s, de_s \in D \land de_s = qs$ \If{$de_{qs} \neq \emptyset$} @@ -389,46 +388,48 @@ $GetKeyVal(DT_s,k_s)= \tuple{k, v}$ \textit{such that} $\tuple{k, v} \end{algorithmic} \begin{algorithmic}[1] -\Function{GetKVPairs}{$s$} -\State $SL_c \gets \Call{GetSlot}{s}$ -\State $MS_c \gets \emptyset$ +\Procedure{ProcessSL}{$SL_g$} +\State $MS_g \gets \emptyset$ \State $SM_{curr} \gets \emptyset$ -\State $\tuple{s_{c_{max}},sv_{c_{max}}} \gets MaxSlot(SL_c)$ -\State $s_{c_{max}} \gets SeqN(\tuple{s_{c_{max}},sv_{c_{max}}})$ -\State $\tuple{s_{c_{min}},sv_{c_{min}}} \gets MinSlot(SL_c)$ -\State $s_{c_{min}} \gets SeqN(\tuple{s_{c_{min}},sv_{c_{min}}})$ -\For{$s_c \gets s_{c_{min}}$ \textbf{to} $s_{c_{max}}$}\Comment{Process slots - in $SL_c$ in order} - \State $\tuple{s_c,sv_c} \gets Slot(SL_c,s_c)$ - \State $SM_{curr} \gets SM_{curr} \cup \{\tuple{s_c,sv_c}\}$ - \State $s_c \gets SeqN(\tuple{s_c,sv_c})$ - \State $sv_c \gets SlotVal(\tuple{s_c,sv_c})$ - \State $Dat_c \gets Decrypt(SK,sv_c)$ - \State $s_{c_{in}} \gets GetSeqN(Dat_c)$ - \If{$s_c \neq s_{c_{in}}$} +\State $\tuple{s_{g_{max}},sv_{g_{max}}} \gets MaxSlot(SL_g)$ +\State $s_{g_{max}} \gets SeqN(\tuple{s_{g_{max}},sv_{g_{max}}})$ +\State $\tuple{s_{g_{min}},sv_{g_{min}}} \gets MinSlot(SL_g)$ +\State $s_{g_{min}} \gets SeqN(\tuple{s_{g_{min}},sv_{g_{min}}})$ +\For{$s_g \gets s_{g_{min}}$ \textbf{to} $s_{g_{max}}$}\Comment{Process slots + in $SL_g$ in order} + \State $\tuple{s_g,sv_g} \gets Slot(SL_g,s_g)$ + \State $SM_{curr} \gets SM_{curr} \cup \{\tuple{s_g,sv_g}\}$ + \State $s_g \gets SeqN(\tuple{s_g,sv_g})$ + \State $sv_g \gets SlotVal(\tuple{s_g,sv_g})$ + \State $Dat_g \gets Decrypt(SK,sv_g)$ + \State $s_{g_{in}} \gets GetSeqN(Dat_g)$ + \If{$s_g \neq s_{g_{in}}$} \State \Call{ReportError}{'Invalid sequence number'} \EndIf - \If{$\neg \Call{ValidPrevHmac}{Dat_c,hmac_p}$} + \State $DE_g \gets GetDatEnt(Dat_g)$ + \State $hmac_{p_{stored}} \gets GetPrevHmac(Dat_g)$ + \If{$\neg \Call{ValidPrevHmac}{DE_g,hmac_{p_g},hmac_{p_{stored}}}$} \State \Call{ReportError}{'Invalid previous HMAC value'} \EndIf - \If{$\neg \Call{ValidHmac}{Dat_c,SK}$} + \State $hmac_{c_g} \gets GetCurrHmac(Dat_g)$ + \If{$\neg \Call{ValidHmac}{DE_g,SK,hmac_{c_g}}$} \State \Call{ReportError}{'Invalid current HMAC value'} \EndIf - \State $hmac_p \gets Hmac(Dat_c,SK)$\Comment{Update $hmac_p$ for next slot check} - \State $qs_c \gets \Call{GetQueSta}{Dat_c}$\Comment{Handle qs} - \If{$qs_c \neq \emptyset \land qs_c > max_c$} - \State $max_c \gets qs_c$ + \State $hmac_{p_g} \gets Hmac(Dat_g,SK)$\Comment{Update $hmac_{p_g}$ for next check} + \State $qs_g \gets \Call{GetQueSta}{Dat_g}$\Comment{Handle qs} + \If{$qs_g \neq \emptyset \land qs_g > max_g$} + \State $max_g \gets qs_g$ \EndIf %Check for last s in Dat - \State $id_c \gets GetMacId(Dat_c)$\Comment{Handle last s} - \State $MS_c \gets \Call{UpdateLastSeqN}{id_c,s_c,MS_c}$ + \State $id_g \gets GetMacId(Dat_g)$\Comment{Handle last s} + \State $MS_g \gets \Call{UpdateLastSeqN}{id_g,s_g,MS_g}$ %Check for last s in DE in Dat - \State $\tuple{id_d,s_{d_{last}}} \gets \Call{GetSlotSeq}{Dat_c}$\Comment{Handle ss} + \State $\tuple{id_d,s_{d_{last}}} \gets \Call{GetSlotSeq}{Dat_g}$\Comment{Handle ss} \If{$\tuple{id_d,s_{d_{last}}} \neq \emptyset$} - \State $MS_c \gets \Call{UpdateLastSeqN}{id_d,s_{d_{last}},MS_c}$ + \State $MS_g \gets \Call{UpdateLastSeqN}{id_d,s_{d_{last}},MS_g}$ \EndIf \State $\tuple{s_e,id_e} \gets - \Call{GetColRes}{Dat_c}$\Comment{Handle cr} + \Call{GetColRes}{Dat_g}$\Comment{Handle cr} \If{$\tuple{s_e,id_e} \neq \emptyset$} \State $s_e \gets GetS(\tuple{s_e,id_e})$ \State $id_e \gets GetId(\tuple{s_e,id_e})$ @@ -437,17 +438,24 @@ $GetKeyVal(DT_s,k_s)= \tuple{k, v}$ \textit{such that} $\tuple{k, v} \State $\Call{CheckColRes}{SM,\tuple{s_e,id_e}}$ \EndIf \EndIf - \State $DT \gets \Call{UpdateDT}{DT,Dat_c}$ + \State $DT \gets \Call{UpdateDT}{DT,Dat_g}$ \EndFor \State $SM \gets SM_{curr}$ -\If{$m + |SL_c| \leq max_c$}\Comment{Check actual size against $max_c$} - \State $m \gets m + |SL_c|$ +\If{$m + |SL_g| \leq max_g$}\Comment{Check actual size against $max_g$} + \State $m \gets m + |SL_g|$ \Else - \State \Call{ReportError}{'Actual queue size exceeds $max_c$'} + \State \Call{ReportError}{'Actual queue size exceeds $max_g$'} \EndIf -\State $\Call{CheckLastSeqN}{MS_c,MS}$ -\State \Return{$DT$} -\EndFunction +\State $\Call{CheckLastSeqN}{MS_g,MS}$ +\EndProcedure +\end{algorithmic} + +\begin{algorithmic}[1] +\Procedure{GetKVPairs}{} +\State $s_g \gets GetLastSeqN(MS,id_{self}) + 1$ +\State $SL_c \gets \Call{GetSlot}{s_g}$ +\State $\Call{ProcessSL}{SL_c}$\Comment{Process slots and update DT} +\EndProcedure \end{algorithmic} \begin{algorithmic}[1] @@ -459,6 +467,113 @@ $GetKeyVal(DT_s,k_s)= \tuple{k, v}$ \textit{such that} $\tuple{k, v} \EndFunction \end{algorithmic} +\subsubsection{Writing Slots} +\textbf{Data Entry} \\ +$k$ is key of entry \\ +$v$ is value of entry \\ +$kv$ is a key-value entry $\tuple{k,v}$\\ +$D = \{kv,ss,qs,cr\}$ \\ +$DE = \{de \mid de \in D\}$ \\ +$Dat_s = \tuple{s,id,hmac_p,DE,hmac_c}$ \\ +$sv_s = \tuple{s, E(Dat_s)} = +\tuple{s, E(\tuple{s,id,hmac_p,DE,hmac_c})}$ \\ \\ + +\textbf{States} \\ +\textit{$cp$ = data entry $DE$ maximum size/capacity} \\ +\textit{$cr_p$ = saved cr entry $\tuple{s,id}$ on client if there is a collision +(sent in the following slot)} \\ +\textit{$ck_p$ = counter of $kv \in KV$ for putting pairs (initially 0)} \\ +\textit{$ck_g$ = counter of $kv \in KV$ for getting pairs (initially 0)} \\ +\textit{$id_{self}$ = machine Id of this client} \\ +\textit{$hmac_{c_p}$ = the HMAC value of the current slot} \\ +\textit{$hmac_{p_p}$ = the HMAC value of the previous slot +($hmac_{p_p} = \emptyset$ for the first slot)} \\ +\textit{$KV$ = set of $\tuple{ck, \tuple{k,v}}$ of kv entries on client} \\ +\textit{$ST$ = set of $DE$ objects on client} \\ +\textit{$SL_p$ = set of returned slots on client} \\ +\textit{SK = Secret Key} \\ + +\textbf{Helper Functions} \\ +$CreateDat(s,id,hmac_p,DE,hmac_c)=Dat_s=\tuple{s,id,hmac_p,DE,hmac_c}$ \\ +$Encrypt(Dat_s,SK_s)=sv_s$ \\ +$GetStatus(\tuple{status,SL})=status$ \\ +$GetSL(\tuple{status,SL})=SL$ \\ +$GetColSeqN(SL_s,s_s)= \tuple{s, sv}$ \textit{such that} $\tuple{s, sv} +\in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s = s_s$ \\ +$CreateCR(s,id)=\tuple{s,id}$ \\ +$GetKV(KV_s,k_s)= \tuple{ck,\tuple{k, v}}$ \textit{such that} +$\tuple{ck,\tuple{k, v}} \in KV_s \wedge +\forall \tuple{ck_s,\tuple{k_s, v_s}} \in KV_s, k = k_s$ \\ +$MaxLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s +\wedge \forall \tuple{id_s, s_{s_{last}}} \in MS_s, s_{last} \geq s_{s_{last}}$ \\ + +\begin{algorithmic}[1] +\Function{PutKVPair}{$KV_s,\tuple{k_s,v_s}$} +\State $k_s \gets GetKey(\tuple{k_s,v_s})$ +\State $\tuple{ck_s,\tuple{k_s,v_t}} \gets GetKV(KV_s,k_s)$ +\If{$\tuple{ck_s,\tuple{k_s,v_t}} = \emptyset$} + \State $KV_s \gets KV_s \cup \{\tuple{ck_p, \tuple{k_s,v_s}}\}$ + \State $ck_p \gets ck_p + 1$ +\Else + \State $KV_s \gets (KV_s - \{\tuple{ck_s, \tuple{k_s,v_t}}\}) \cup + \{\tuple{ck_s, \tuple{k_s,v_s}}\}$ +\EndIf +\State \Return{$KV_s$} +\EndFunction +\end{algorithmic} + +\begin{algorithmic}[1] +\Function{GetDEPairs}{$KV_s$} +\State $DE_{ret} \gets \emptyset$ +\State $cp_s \gets cp$ +\If{$cr_p \neq \emptyset$} + \State $DE_{ret} \gets DE_{ret} \cup cr_p$ + \State $cp_s \gets cp_s - 1$ +\EndIf +\If{$|KV_s| \leq cp$}\Comment{KV set can extend multiple slots based on $cp$} + \State $DE_{ret} \gets DE_{ret} \cup + \{\tuple{k_s,v_s} \mid \tuple{ck_s,\tuple{k_s,v_s}} \in KV_s\}$ +\Else + \State $DE_{ret} \gets DE_{ret} \cup + \{\tuple{k_s,v_s} \mid \tuple{ck_s,\tuple{k_s,v_s}} \in KV_s, + ck_g \leq ck_s < ck_g + cp_s\}$ + \If{$|DE_{ret}| = cp$} + \State $ck_g \gets ck_g + cp_s$\Comment{Middle of KV set} + \Else + \State $ck_g \gets 0$\Comment{End of KV set} + \EndIf +\EndIf +\State \Return{$DE_{ret}$} +\EndFunction +\end{algorithmic} + +\begin{algorithmic}[1] +\Function{PutDataEntries}{$max'_p$} +\State $s_p \gets MaxLastSeqN(MS)$ +\State $DE_p \gets GetDEPairs(KV)$ +\State $hmac_{c_p} \gets Hmac(DE_p,SK)$ +\State $Dat_p \gets CreateSlot(s_p,id_{self},hmac_{p_p},DE_p,hmac_{c_p})$ +\State $hmac_{p_p} \gets hmac_{c_p}$ +\State $sv_p \gets Encrypt(Dat_p,SK)$ +\State $\tuple{stat_p,SL_p} \gets \Call{PutSlot}{s_p,sv_p,max'_p}$ +\State $stat_p \gets GetStatus(\tuple{stat_p,SL_p})$ +\State $SL_p \gets GetSL(\tuple{stat_p,SL_p})$ +\If{$\neg stat_p$}\Comment{Handle collision} + \State $\tuple{s_{col},sv_{col}} \gets GetColSeqN(SL_p,s_p)$ + \State $s_{col} \gets SeqN(\tuple{s_{col},sv_{col}})$ + \State $sv_{col} \gets SlotVal(\tuple{s_{col},sv_{col}})$ + \State $Dat_{col} \gets Decrypt(SK,sv_{col})$ + \State $id_{col} \gets GetMacId(Dat_{col})$ + \State $\tuple{s_{col},id_{col}} \gets CreateCR(s_{col},id_{col})$ + \State $cr_p \gets \tuple{s_{col},id_{col}}$ +\Else + \State $cr_p \gets \emptyset$ +\EndIf +\State $\Call{ProcessSL}{SL_p}$ +\State \Return{$ST$} +\EndFunction +\end{algorithmic} + \subsection{Formal Guarantees} \textit{To be completed ...} -- 2.34.1