From: rtrimana Date: Mon, 8 Aug 2016 16:19:30 +0000 (-0700) Subject: Fixing SM list mechanism as it is checked against cr entries X-Git-Url: http://plrg.eecs.uci.edu/git/?p=iotcloud.git;a=commitdiff_plain;h=cab3eecac2985a717e5e47643ec9bad04879dd83 Fixing SM list mechanism as it is checked against cr entries --- diff --git a/doc/iotcloud.tex b/doc/iotcloud.tex index bffd87e..ad52a69 100644 --- a/doc/iotcloud.tex +++ b/doc/iotcloud.tex @@ -215,15 +215,15 @@ $slot_s = \tuple{s, E(Dat_s)} = \textit{$MS_g$ = set MS to save all $\tuple{id, s_{last}}$ pairs while traversing DT after a request to server (initially empty)} \\ \textit{SK = Secret Key} \\ -\textit{$SM$ = associative array of $\tuple{s, id}$ of all slots in a previous read +\textit{$SM$ = associative array of $\tuple{s, id}$ of all slots in previous reads (initially empty)} \\ \\ \textbf{Helper Functions} \\ $MaxSlot(SL_s)= \tuple{s, sv}$ \textit{such that} $\tuple{s, sv} -\in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \geq s_s$ \\ + \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \geq s_s$ \\ $MinSlot(SL_s)= \tuple{s, sv}$ \textit{such that} $\tuple{s, sv} -\in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \leq s_s$ \\ + \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \leq s_s$ \\ $Slot(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$ \\ + \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s = s_s$ \\ $SeqN(\tuple{s, sv})=s$ \\ $SlotVal(\tuple{s, sv})=sv$ \\ $CreateLastSL(s,sv,id)=\tuple{s,sv,id}=sl_{last}$ \\ @@ -235,11 +235,11 @@ $GetPrevHmac(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=hmac_p$ \\ $GetCurrHmac(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=hmac_c$ \\ $GetDatEnt(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=DE$ \\ $GetLiveSS(SS_{live},ss_s)= ss$ \textit{such that} $ss \in SS_{live} -\wedge \forall ss_s \in SS_{live}, ss = ss_s$ \\ + \wedge \forall ss_s \in SS_{live}, ss = ss_s$ \\ $GetLiveCR(CR_{live},cr_s)= cr$ \textit{such that} $cr \in CR_{live} -\wedge \forall cr_s \in CR_{live}, cr = cr_s$ \\ + \wedge \forall cr_s \in CR_{live}, cr = cr_s$ \\ $GetLivEntLastS(LV_s,kv_s)= s$ \textit{such that} $\tuple{kv, s} \in LV_s -\wedge \forall \tuple{kv_s, s_s} \in LV_s, kv_s = kv$ \\ + \wedge \forall \tuple{kv_s, s_s} \in LV_s, kv_s = kv$ \\ $GetKV($key-value data entry$)=\tuple{k_s,v_s} = kv_s$ \\ $GetSS($slot-sequence data entry$)=\tuple{id_s,s_{s_{last}}} = ss_s$ \\ $GetQS($queue-state data entry$)=qs_s$ \\ @@ -251,11 +251,13 @@ $GetSLast(ss = \tuple{id, s_{last}})=s_{last}$ \\ $GetS(cr = \tuple{s, id})=s$ \\ $GetId(cr = \tuple{s, id})=id$ \\ $GetKeyVal(DT_s,k_s)= \tuple{k, v}$ \textit{such that} $\tuple{k, v} -\in DT_s \wedge \forall \tuple{k_s, v_s} \in DT_s, k = k_s$ \\ + \in DT_s \wedge \forall \tuple{k_s, v_s} \in DT_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}}$ \\ + \wedge \forall \tuple{id_s, s_{s_{last}}} \in MS_s, s_{last} \geq s_{s_{last}}$ \\ $MinLastSeqN(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} \leq s_{s_{last}}$ \\ + \wedge \forall \tuple{id_s, s_{s_{last}}} \in MS_s, s_{last} \leq s_{s_{last}}$ \\ +$MinCRSeqN(CR_s)= s$ \textit{such that} $\tuple{s, id} \in CR_s + \wedge \forall \tuple{s_s, id_s} \in CR_s, s \leq s_s$ \\ \begin{algorithmic}[1] \Procedure{Error}{$msg$} @@ -347,8 +349,8 @@ $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \end{algorithmic} \begin{algorithmic}[1] -\Function{AddCRLivEnt}{$CR_{s_{live}},de_s$} -\State $cr_s \gets GetCR(de_s)$ +\Function{AddCRLivEnt}{$CR_{s_{live}},cr_s$} +%\State $cr_s \gets GetCR(de_s)$ \State $cr_t \gets GetLiveCR(CR_{s_{live}},cr_s)$ \If{$cr_t = \emptyset$} \State $CR_{s_{live}} \gets CR_{s_{live}} \cup \{cr_s\}$\Comment{First occurrence} @@ -383,6 +385,15 @@ $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \EndFunction \end{algorithmic} +\begin{algorithmic}[1] +\Function{UpdateSM}{$SM_s,CR_s$}\Comment{Remove if dead} +\State $s_{cr_{min}} \gets MinCRSeqN(CR_s)$ + \State $SM_s \gets SM_s - \{\tuple{s_s,id_s} \mid \tuple{s_s,id_s} + \in SM_s \wedge s_s < s_{cr_{min}}\}$ +\State \Return{$CR_{s_{live}}$} +\EndFunction +\end{algorithmic} + \begin{algorithmic}[1] \Procedure{CheckLastSeqN}{$MS_s,MS_t$} \For {$\tuple{id, s_t}$ in $MS_t$}\Comment{Check $MS_t$ based on the newer $MS_s$} @@ -407,22 +418,15 @@ $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \State $id_s \gets GetId(cr_s)$ \State $s_{s_{last}} \gets GetLastSeqN(MS_s,id_s)$ \If{$s_{s_{last}} < s_s$} - \State $\Call{CheckColRes}{SM_s,cr_s}$ + \State $id_t \gets SM_s[s_s]$ + \If{$id_s \neq id_t$} + \State \Call{Error}{'Invalid $id$ for this slot update'} + \EndIf \EndIf \EndIf \EndProcedure \end{algorithmic} -\begin{algorithmic}[1] -\Procedure{CheckColRes}{$SM_s,cr_t$}\Comment{Check $id_s$ in $SM_s$} -\State $s_t \gets GetS(cr_t)$ -\State $id_s \gets SM_s[s_t]$ -\If{$id_s \neq id_t$} - \State \Call{Error}{'Invalid $id$ for this slot update'} -\EndIf -\EndProcedure -\end{algorithmic} - \begin{algorithmic}[1] \Function{StoreLastSlot}{$MS_s,sl_l,s_s,sv_s,id_s$} \State $s_{min} \gets MinLastSeqN(MS_s)$ @@ -455,14 +459,16 @@ $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \begin{algorithmic}[1] \Procedure{ProcessSL}{$SL_g$} \State $MS_g \gets \emptyset$ -\State $SM_{curr} \gets \emptyset$ +%\State $SM_{curr} \gets \emptyset$ \State $\tuple{s_{g_{min}},sv_{g_{min}}} \gets MinSlot(SL_g)$ \State $\tuple{s_{g_{max}},sv_{g_{max}}} \gets MaxSlot(SL_g)$ \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 $Dat_g \gets Decrypt(SK,sv_g)$ + \State $id_g \gets GetMacId(Dat_g)$ + %\State $SM_{curr} \gets SM_{curr} \cup \{\tuple{s_g,id_g}\}$ + \State $SM \gets SM \cup \{\tuple{s_g,id_g}\}$ \State $s_{g_{in}} \gets GetSeqN(Dat_g)$ \If{$s_g \neq s_{g_{in}}$} \State \Call{Error}{'Invalid sequence number'} @@ -498,13 +504,14 @@ $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \ForAll{$de_{g_{cr}} \in DE_{g_{cr}}$} \State $cr_g \gets GetCR(de_{g_{cr}})$ \State $\Call{CheckCollision}{MS,SM,cr_g}$ - \State $CR_{live} \gets \Call{AddCRLivEnt}{CR_{live},de_{g_{cr}}}$ + %\State $CR_{live} \gets \Call{AddCRLivEnt}{CR_{live},de_{g_{cr}}}$ + \State $CR_{live} \gets \Call{AddCRLivEnt}{CR_{live},cr_g}$ \EndFor \EndIf \State $sl_{last} \gets \Call{StoreLastSlot}{MS,sl_{last},s_g,sv_g,id_g}$ \State $DT \gets \Call{UpdateDT}{DT,DE_g,LV,s_g}$ \EndFor -\State $SM \gets SM_{curr}$ +%\State $SM \gets SM_{curr}$ \If{$m + |SL_g| \leq max_g$}\Comment{Check actual size against $max_g$} \State $m \gets m + |SL_g|$ \Else @@ -513,6 +520,7 @@ $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \State $\Call{CheckLastSeqN}{MS_g,MS}$ \State $\Call{UpdateSSLivEnt}{SS_{live},MS}$ \State $\Call{UpdateCRLivEnt}{CR_{live},MS}$ +\State $\Call{UpdateSM}{SM,CR_{live}}$ \EndProcedure \end{algorithmic} @@ -1018,7 +1026,7 @@ starting before $\mathsf{r_1}$ and ending before $p$. \item Case 2.2.1: Some message in $\mathsf{X}$ was accepted. Let $\mathsf{s_{w_J}}$ be the greatest sequence number of the messages that client $\mathsf{J}$ sent in the path of message $\mathsf{w}$. In this case, before sending $\mathsf{p}$, -$\mathsf{J}$'s value in $\mathsf{SM_J}$ for its own latest sequence number would +$\mathsf{J}$'s value in $\mathsf{MS_J}$ for its own latest sequence number would be strictly greater than $\mathsf{s_{q_J}}$. If there is a sequence of messages with contiguous sequence numbers that $\mathsf{J}$ receives between $\mathsf{r_1}$ and $\mathsf{p}$, $\mathsf{J}$ throws an error for a similar reason as Case 1.1. Otherwise,