62 Office: & S1.27 (1st floor Strand Building)\\ |
25 Office: & S1.27 (1st floor Strand Building)\\ |
63 Slides: & KEATS (also homework is there)\\ |
26 Slides: & KEATS (also homework is there)\\ |
64 \end{tabular} |
27 \end{tabular} |
65 \end{center} |
28 \end{center} |
66 |
29 |
67 \end{frame}} |
30 \end{frame} |
68 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
31 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
69 |
32 |
70 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
33 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
71 \mode<presentation>{ |
34 \begin{frame}[c] |
|
35 |
|
36 \begin{center} |
|
37 \includegraphics[scale=0.6]{../pics/bridge-limits.png} |
|
38 \end{center} |
|
39 |
|
40 \end{frame} |
|
41 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
42 |
|
43 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
44 \begin{frame}[c] |
|
45 \frametitle{Old-Fashioned Eng.~vs.~CS} |
|
46 |
|
47 \begin{center} |
|
48 \begin{tabular}{@{}cc@{}} |
|
49 \begin{tabular}{@{}p{5.2cm}} |
|
50 \includegraphics[scale=0.058]{../pics/towerbridge.jpg}\\ |
|
51 {\bf bridges}: \\ |
|
52 \raggedright\small |
|
53 engineers can ``look'' at a bridge and have a pretty good |
|
54 intuition about whether it will hold up or not\\ |
|
55 (redundancy; predictive theory) |
|
56 \end{tabular} & |
|
57 \begin{tabular}{p{5cm}} |
|
58 \includegraphics[scale=0.265]{../pics/code.jpg}\\ |
|
59 \raggedright |
|
60 {\bf code}: \\ |
|
61 \raggedright\small |
|
62 programmers have very little intuition about their code; |
|
63 often it is too expensive to have redundancy; |
|
64 not ``continuous'' |
|
65 \end{tabular} |
|
66 \end{tabular} |
|
67 \end{center} |
|
68 |
|
69 \end{frame} |
|
70 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
71 |
|
72 |
|
73 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
74 \begin{frame}[c] |
|
75 \frametitle{Dijkstra on Testing} |
|
76 |
|
77 \begin{bubble}[10cm] |
|
78 ``Program testing can be a very effective way to show the |
|
79 presence of bugs, but it is hopelessly inadequate for showing |
|
80 their absence.'' |
|
81 \end{bubble}\bigskip |
|
82 |
|
83 unfortunately attackers exploit bugs (Satan's computer vs |
|
84 Murphy's) |
|
85 |
|
86 \vfill |
|
87 \small |
|
88 Dijkstra: shortest path algorithm, |
|
89 dining philosophers problem, |
|
90 semaphores |
|
91 \end{frame} |
|
92 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
93 |
|
94 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
72 \begin{frame}[c] |
95 \begin{frame}[c] |
73 \frametitle{Review: Proofs} |
96 \frametitle{\Large Proving Programs to be Correct} |
74 |
97 |
75 Modify the formula |
98 \begin{bubble}[10cm] |
76 \begin{center} |
|
77 \begin{tabular}{l} |
|
78 \bl{$P\;\textit{controls}\;\textit{Permitted}(O, \textit{write})$}\\ |
|
79 \end{tabular} |
|
80 \end{center} |
|
81 using security levels so that it satisfies the {\it write rule} from the {\it |
|
82 Bell-LaPadula} access policy.\bigskip |
|
83 |
|
84 Do the same again, but satisfy the {\it write rule} |
|
85 from the {\it Biba} access policy. |
|
86 |
|
87 \end{frame}} |
|
88 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
89 |
|
90 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
91 \mode<presentation>{ |
|
92 \begin{frame}[c] |
|
93 \frametitle{Review: Proofs} |
|
94 |
|
95 Assume two security levels \bl{$\textit{S}$} and \bl{$\textit{TS}$}, |
|
96 which are ordered so that \bl{$slev(\textit{S}) < slev(\textit{TS})$}. |
|
97 Assume further the substitution rules |
|
98 \begin{center} |
|
99 \bl{\begin{tabular}{@{}c@{}} |
|
100 $\Gamma \vdash slev(P) = l_1$ \hspace{2mm} $\Gamma \vdash slev(Q) = l_2$ |
|
101 \hspace{2mm} $\Gamma \vdash l_1 < l_2$\\\hline |
|
102 $\Gamma \vdash slev(P) < slev(Q)$ |
|
103 \end{tabular}} |
|
104 \end{center} |
|
105 |
|
106 \begin{center} |
|
107 \bl{\begin{tabular}{c} |
|
108 $\Gamma \vdash slev(P) = l$ \hspace{4mm} $\Gamma \vdash slev(Q) = l$\\\hline |
|
109 $\Gamma \vdash slev(P) = slev(Q)$ |
|
110 \end{tabular}} |
|
111 \end{center} |
|
112 |
|
113 |
|
114 \end{frame}} |
|
115 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
116 |
|
117 |
|
118 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
119 \mode<presentation>{ |
|
120 \begin{frame}[c] |
|
121 \frametitle{Review: Proofs}\small |
|
122 |
|
123 Let \bl{$\Gamma$} be the set containing the following six formulas |
|
124 \begin{center} |
|
125 \bl{\begin{tabular}{@{}l@{}} |
|
126 $slev(\textit{S}) < slev(\textit{TS})$\smallskip\\ |
|
127 $slev(\textit{Agent}) = slev(\textit{TS})$\smallskip\\ |
|
128 $slev(\textit{File}_1) = slev(\textit{S})$\smallskip\\ |
|
129 $slev(\textit{File}_2) = slev(\textit{TS})$\smallskip\\ |
|
130 $\forall O.\;slev(O) < slev(\textit{Agent}) \Rightarrow$\\ |
|
131 \hspace{30mm}$(\textit{Agent}\;\textit{controls}\;\textit{Permitted}(O, \textit{read}))$\smallskip\\ |
|
132 $\forall O.\;slev(O) = slev(\textit{Agent}) \Rightarrow$\\ |
|
133 \hspace{30mm}$(\textit{Agent}\;\textit{controls}\;\textit{Permitted}(O, \textit{read}))$\\ |
|
134 \end{tabular}} |
|
135 \end{center} |
|
136 Using the inference rules of access-control logic and the substitution rules shown above, |
|
137 give proofs for the two judgements |
|
138 \begin{center} |
|
139 \bl{\begin{tabular}{@{}l@{}} |
|
140 $\Gamma \vdash |
|
141 (\textit{Agent}\;\textit{says}\;\textit{Permitted}(\textit{File}_1, |
|
142 \textit{read})) \Rightarrow$\\ |
|
143 \hspace{50mm}$\textit{Permitted}(\textit{File}_1, \textit{read})$\\ |
|
144 \end{tabular}} |
|
145 \end{center} |
|
146 |
|
147 |
|
148 \end{frame}} |
|
149 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
150 |
|
151 |
|
152 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
153 \mode<presentation>{ |
|
154 \begin{frame}[t] |
|
155 \frametitle{Checking Solutions} |
|
156 |
|
157 How can you check somebody's solution without revealing the solution?\pause\bigskip |
|
158 |
|
159 Alice and Bob solve crosswords. Alice knows the answer for 21D (folio) but doesn't |
|
160 want to tell Bob.\medskip |
|
161 |
|
162 You use an English dictionary: |
|
163 |
|
164 \begin{itemize} |
|
165 \item folio \onslide<4->{$\stackrel{1}{\rightarrow}$ individual } |
|
166 \onslide<5->{$\stackrel{2}{\rightarrow}$ human} |
|
167 \onslide<6->{$\stackrel{3}{\rightarrow}$ or \ldots} |
|
168 \only<3>{ |
|
169 \begin{quote} |
|
170 ``an \alert{individual} leaf of paper or parchment, either loose as one of a series or |
|
171 forming part of a bound volume, which is numbered on the recto or front side only.'' |
|
172 \end{quote}} |
|
173 \only<4>{ |
|
174 \begin{quote} |
|
175 ``a single \alert{human} being as distinct from a group'' |
|
176 \end{quote}} |
|
177 \only<5>{ |
|
178 \begin{quote} |
|
179 ``relating to \alert{or} characteristic of humankind'' |
|
180 \end{quote}} |
|
181 \end{itemize}\bigskip\bigskip |
|
182 |
|
183 \only<7->{ |
|
184 this is essentially a hash function...but Bob can only check once he has also found the solution |
|
185 } |
|
186 |
|
187 \end{frame}} |
|
188 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
189 |
|
190 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
191 \mode<presentation>{ |
|
192 \begin{frame}[c] |
|
193 \frametitle{Zero-Knowledge Proofs} |
|
194 |
|
195 Two remarkable properties of \alert{Zero-Knowledge Proofs}:\bigskip |
|
196 |
|
197 \begin{itemize} |
|
198 \item Alice only reveals the fact that she knows a secret, not the secret itself (meaning |
|
199 she can convince Bob that she knows the secret).\bigskip |
|
200 \item Having been convinced, Bob cannot use the evidence in order to convince Carol |
|
201 that Alice knows the secret. |
|
202 \end{itemize} |
|
203 |
|
204 \end{frame}} |
|
205 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
206 |
|
207 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
208 \mode<presentation>{ |
|
209 \begin{frame}[t] |
|
210 \frametitle{\begin{tabular}{@{}c@{}}The Idea \end{tabular}} |
|
211 |
|
212 \begin{center} |
|
213 \begin{tabular}{l@{\hspace{10mm}}r} |
|
214 \\[-10mm] |
|
215 \raisebox{10mm}{\large 1.} & \includegraphics[scale=0.1]{pics/alibaba1.png}\\ |
|
216 \raisebox{10mm}{\large 2.} & \includegraphics[scale=0.1]{pics/alibaba2.png}\\ |
|
217 \raisebox{10mm}{\large 3.} & \includegraphics[scale=0.1]{pics/alibaba3.png} |
|
218 \end{tabular} |
|
219 \end{center} |
|
220 |
|
221 \begin{textblock}{7}(1,2.5) |
|
222 The Alibaba cave: |
|
223 \end{textblock} |
|
224 |
|
225 \small |
99 \small |
226 \only<2>{ |
100 {\bf Theorem:} There are infinitely many prime |
227 \begin{textblock}{12}(2,13.3) |
101 numbers.\medskip\\ |
228 Even if Bob has a hidden camera, a recording will not be convincing to anyone else |
102 |
229 (Alice and Bob could have made it all up). |
103 {\bf Proof} \ldots\\ |
230 \end{textblock}} |
104 \end{bubble}\bigskip |
231 \only<3>{ |
105 |
232 \begin{textblock}{12}(2,13.3) |
106 |
233 Even worse, an observer present at the experiment would not be convinced. |
107 similarly\bigskip |
234 \end{textblock}} |
108 |
235 |
109 \begin{bubble}[10cm] |
236 \end{frame}} |
110 \small |
237 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
111 {\bf Theorem:} The program is doing what |
238 |
112 it is supposed to be doing.\medskip |
239 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
113 |
240 \mode<presentation>{ |
114 {\bf Long, long proof} \ldots\\ |
241 \begin{frame}[c] |
115 \end{bubble}\bigskip\medskip |
242 \frametitle{Applications of ZKPs} |
116 |
243 |
117 \small This can be a gigantic proof. The only hope is to have |
244 \begin{itemize} |
118 help from the computer. `Program' is here to be understood to be |
245 \item authentication, where one party wants to prove its identity to a |
119 quite general (protocol, OS,\ldots). |
246 second party via some secret information, but doesn't want the second |
120 |
247 party to learn anything about this secret\bigskip |
121 \end{frame} |
248 \item to enforce honest behaviour while maintaining privacy: the idea is to |
122 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
249 force a user to prove, using a zero-knowledge proof, that its behaviour is |
123 |
250 correct according to the protocol |
124 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
251 \end{itemize} |
125 \begin{frame}[c] |
252 \end{frame}} |
126 \frametitle{\Large{}Mars Pathfinder Mission 1997} |
253 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
127 |
254 |
128 \begin{center} |
255 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
129 \includegraphics[scale=0.15]{../pics/marspath1.png} |
256 \mode<presentation>{ |
130 \includegraphics[scale=0.16]{../pics/marspath3.png} |
257 \begin{frame}[c] |
131 \includegraphics[scale=0.3]{../pics/marsrover.png} |
258 \frametitle{Central Properties} |
132 \end{center} |
259 |
133 |
260 Zero-knowledge proof protocols should satisfy:\bigskip |
134 \begin{itemize} |
261 |
135 \item despite NASA's famous testing procedures, the lander crashed frequently on Mars |
262 \begin{itemize} |
136 \item a scheduling algorithm was not used in the OS |
263 \item \alert{\bf Completeness} If Alice knows the secret, Bob accepts Alice ``proof'' for sure.\bigskip |
137 \end{itemize} |
264 \item \alert{\bf Soundness} If Alice does not know the secret, Bob accepts her ``proof'' with a very |
138 |
265 small probability. |
139 \end{frame} |
266 \end{itemize} |
140 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
267 \end{frame}} |
141 |
268 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
142 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
269 |
143 \begin{frame}[c] |
270 |
144 |
271 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
145 |
272 \mode<presentation>{ |
146 \begin{textblock}{11}(1,3) |
273 \begin{frame}[c] |
147 \begin{tabular}{@{\hspace{-10mm}}l} |
274 \frametitle{Graph Isomorphism} |
148 \begin{tikzpicture}[scale=1.1] |
275 |
149 \node at (-2.5,-1.5) {\textcolor{white}{a}}; |
276 \begin{center} |
150 \node at (8,4) {\textcolor{white}{a}}; |
277 \begin{tabular}{l@{\hspace{10mm}}r} |
151 |
278 \includegraphics[scale=0.8]{pics/graphs.png}\\ |
152 |
279 \end{tabular} |
153 |
280 \end{center} |
154 \only<1>{ |
281 |
155 \draw[fill, blue!50] (1,0) rectangle (3,0.6); |
282 Finding an isomorphism between two graphs is an NP complete problem. |
156 } |
283 \end{frame}} |
157 \only<2>{ |
284 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
158 \draw[fill, blue!50] (1,0) rectangle (2,0.6); |
285 |
159 \draw[fill, blue!50] (3,0) rectangle (5,0.6); |
286 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
160 \draw[fill, blue!100] (2,3) rectangle (3,3.6); |
287 \mode<presentation>{ |
161 } |
288 \begin{frame}[c] |
162 \only<3>{ |
289 \frametitle{Graph Isomorphism Protocol} |
163 \draw[fill, blue!50] (1,0) rectangle (2,0.6); |
290 |
164 \draw[fill, blue!50] (3,0) rectangle (4.5,0.6); |
291 Alice starts with knowing an isomorphism \bl{$\sigma$} between graphs \bl{$G_1$} and \bl{$G_2$}\medskip |
165 \draw[fill, blue!50] (5.5,0) rectangle (6,0.6); |
292 |
166 \draw[fill, blue!100] (2,3) rectangle (3,3.6); |
293 \begin{enumerate} |
167 \draw[fill, blue!100] (4.5,3) rectangle (5.5,3.6); |
294 \item Alice generates an isomorphic graph \bl{$H$} which she sends to Bob |
168 } |
295 \item Bob asks either for an isomorphism between \bl{$G_1$} and \bl{$H$}, or |
169 \only<4>{ |
296 \bl{$G_2$} and \bl{$H$} |
170 \node at (2.5,0.9) {\small locked a resource}; |
297 \item Alice and Bob repeat this procedure \bl{$n$} times |
171 \draw[fill, blue!50] (1,0) rectangle (2,0.6); |
298 \end{enumerate}\pause |
172 \draw[blue!50, very thick] (2,0) rectangle (4,0.6); |
299 |
173 \draw[blue!100, very thick] (2,3) rectangle (3, 3.6); |
300 these are called commitment algorithms |
174 \draw[red, <-, line width = 2mm] (2,-0.1) -- (2, -1); |
301 |
175 } |
302 \end{frame}} |
176 \only<5>{ |
303 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
177 \node at (2.5,0.9) {\small locked a resource}; |
304 |
178 \draw[fill, blue!50] (1,0) rectangle (4,0.6); |
305 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
179 \draw[blue!100, fill] (4,3) rectangle (5, 3.6); |
306 \mode<presentation>{ |
180 } |
307 \begin{frame}[c] |
181 \only<6>{ |
308 \frametitle{Graph Isomorphism Protocol (2)} |
182 \node at (2.5,0.9) {\small locked a resource}; |
309 |
183 \draw[fill, blue!50] (1,0) rectangle (2,0.6); |
310 If Alice knows the isomorphism, she can always calculate \bl{$\sigma$}.\bigskip |
184 \draw[blue!50, very thick] (2,0) rectangle (4,0.6); |
311 |
185 \draw[blue!100, very thick] (2,3) rectangle (3, 3.6); |
312 If she doesn't, she can only correctly respond if Bob's |
186 \draw[red, <-, line width = 2mm] (2,-0.1) -- (2, -1); |
313 choice of index is the same as the one she used to form \bl{$H$}. The probability |
187 } |
314 of this happening is \bl{$\frac{1}{2}$}, so after \bl{$n$} rounds the probability of her |
188 \only<7>{ |
315 always responding correctly is only \bl{$\frac{1}{2}^n$}. |
189 \node at (2.5,0.9) {\small locked a resource}; |
316 |
190 \draw[fill, blue!50] (1,0) rectangle (2.5,0.6); |
317 \end{frame}} |
191 \draw[blue!50, very thick] (2.5,0) rectangle (4,0.6); |
318 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
192 \draw[blue!100, very thick] (2.5,3) rectangle (3.5, 3.6); |
319 |
193 \draw[red, <-, line width = 2mm] (2.5,-0.1) -- (2.5, -1); |
320 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
194 } |
321 \mode<presentation>{ |
195 \only<8>{ |
322 \begin{frame}[c] |
196 \node at (2.5,0.9) {\small locked a resource}; |
323 \frametitle{Graph Isomorphism Protocol (3)} |
197 \draw[fill, blue!50] (1,0) rectangle (2.5,0.6); |
324 |
198 \draw[blue!50, very thick] (2.5,0) rectangle (4,0.6); |
325 Why is the GI-protocol zero-knowledge?\bigskip\pause |
199 \draw[blue!100, very thick] (2.5,3) rectangle (3.5, 3.6); |
326 |
200 \draw[blue!100, very thick] (2.5,3) rectangle (3.5, 3.6); |
327 A: We can generate a fake transcript of a conversation, which |
201 \draw[red, fill] (2.5,1.5) rectangle (3.5,2.1); |
328 cannot be distinguished from a ``real'' conversation.\bigskip |
202 \draw[red, <-, line width = 2mm] (2.5,-0.1) -- (2.5, -1); |
329 |
203 } |
330 Anything Bob can compute using the information obtained from |
204 \only<9>{ |
331 the transcript can be computed using only a forged transcript and |
205 \node at (2.5,0.9) {\small locked a resource}; |
332 therefore participation in such a communication does not increase |
206 \draw[fill, blue!50] (1,0) rectangle (2.5,0.6); |
333 Bob's capability to perform any computation. |
207 \draw[blue!50, very thick] (3.5,0) rectangle (5,0.6); |
334 |
208 \draw[blue!100, very thick] (3.5,3) rectangle (4.5, 3.6); |
335 \end{frame}} |
209 \draw[red, fill] (2.5,1.5) rectangle (3.5,2.1); |
336 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
210 \draw[red, <-, line width = 2mm] (3.5,-0.1) -- (3.5, -1); |
|
211 } |
|
212 \only<10>{ |
|
213 \node at (2.5,0.9) {\small locked a resource}; |
|
214 \draw[fill, blue!50] (1,0) rectangle (2.5,0.6); |
|
215 \draw[blue!50, very thick] (3.5,0) rectangle (5,0.6); |
|
216 \draw[blue!100, very thick] (3.5,3) rectangle (4.5, 3.6); |
|
217 \draw[red, fill] (2.5,1.5) rectangle (3.5,2.1); |
|
218 \draw[red, fill] (3.55,1.5) rectangle (4.5,2.1); |
|
219 \draw[red, <-, line width = 2mm] (3.5,-0.1) -- (3.5, -1); |
|
220 } |
|
221 \only<11>{ |
|
222 \node at (2.5,0.9) {\small locked a resource}; |
|
223 \draw[fill, blue!50] (1,0) rectangle (2.5,0.6); |
|
224 \draw[blue!50, very thick] (4.5,0) rectangle (6,0.6); |
|
225 \draw[blue!100, very thick] (4.5,3) rectangle (5.5, 3.6); |
|
226 \draw[red, fill] (2.5,1.5) rectangle (3.5,2.1); |
|
227 \draw[red, fill] (3.55,1.5) rectangle (4.5,2.1); |
|
228 \draw[red, <-, line width = 2mm] (4.5,-0.1) -- (4.5, -1); |
|
229 } |
|
230 \only<12>{ |
|
231 \node at (2.5,0.9) {\small locked a resource}; |
|
232 \draw[fill, blue!50] (1,0) rectangle (2.5,0.6); |
|
233 \draw[blue!50, very thick] (5.5,0) rectangle (7,0.6); |
|
234 \draw[blue!100, very thick] (5.5,3) rectangle (6.5, 3.6); |
|
235 \draw[red, fill] (2.5,1.5) rectangle (3.5,2.1); |
|
236 \draw[red, fill] (3.55,1.5) rectangle (4.5,2.1); |
|
237 \draw[red, fill] (4.55,1.5) rectangle (5.5,2.1); |
|
238 \draw[red, <-, line width = 2mm] (5.5,-0.1) -- (5.5, -1); |
|
239 \node [anchor=base] at (6.3, 1.8) {\Large\ldots}; |
|
240 } |
|
241 \only<13>{ |
|
242 \node at (2.5,0.9) {\small locked a resource}; |
|
243 \draw[fill, blue!50] (1,0) rectangle (2,0.6); |
|
244 \draw[blue!50, very thick] (2,0) rectangle (4,0.6); |
|
245 \draw[blue!100, very thick] (2,3) rectangle (3, 3.6); |
|
246 \draw[red, <-, line width = 2mm] (2,-0.1) -- (2, -1); |
|
247 } |
|
248 \only<14>{ |
|
249 \node at (2.5,3.9) {\small locked a resource}; |
|
250 \draw[fill, blue!50] (1,0) rectangle (2,0.6); |
|
251 \draw[blue!50, fill] (2,3) rectangle (4,3.6); |
|
252 \draw[blue!100, very thick] (4,3) rectangle (5, 3.6); |
|
253 \draw[blue!50, ->, line width = 2mm] (2,1) -- (2, 2.5); |
|
254 \draw[red, <-, line width = 2mm] (2,-0.1) -- (2, -1); |
|
255 } |
|
256 \only<15>{ |
|
257 \node at (2.5,3.9) {\small locked a resource}; |
|
258 \draw[fill, blue!50] (1,0) rectangle (2,0.6); |
|
259 \draw[blue!50, fill] (2,3) rectangle (4,3.6); |
|
260 \draw[blue!100, very thick] (4,3) rectangle (5, 3.6); |
|
261 \draw[red, <-, line width = 2mm] (2.5,-0.1) -- (2.5, -1); |
|
262 \draw[red, very thick] (2.5,1.5) rectangle (3.5,2.1); |
|
263 } |
|
264 |
|
265 |
|
266 \draw[very thick,->](0,0) -- (8,0); |
|
267 \node [anchor=base] at (8, -0.3) {\scriptsize time}; |
|
268 \node [anchor=base] at (0, -0.3) {\scriptsize 0}; |
|
269 \node [anchor=base] at (-1.2, 0.2) {\small low priority}; |
|
270 \only<2->{\node [anchor=base] at (-1.2, 3.2) {\small high priority};} |
|
271 \only<8->{\node [anchor=base] at (-1.5, 1.7) {\small medium pr.};} |
|
272 |
|
273 \end{tikzpicture} |
|
274 \end{tabular} |
|
275 \end{textblock} |
|
276 |
|
277 \begin{textblock}{0}(2.5,13)% |
|
278 \small |
|
279 \onslide<3->{ |
|
280 \begin{bubble}[8cm]% |
|
281 Scheduling: You want to avoid that a high |
|
282 priority process is staved indefinitely. |
|
283 \end{bubble}} |
|
284 \end{textblock} |
|
285 |
|
286 \end{frame} |
|
287 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
288 |
|
289 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
290 \begin{frame}[c] |
|
291 \frametitle{\Large Priority Inheritance Scheduling} |
|
292 |
|
293 \begin{itemize} |
|
294 \item Let a low priority process $L$ temporarily inherit |
|
295 the high priority of $H$ until $L$ leaves the critical |
|
296 section unlocking the resource.\bigskip |
|
297 \item Once the resource is unlocked $L$ returns to its original |
|
298 priority level. |
|
299 \end{itemize} |
|
300 |
|
301 \end{frame} |
|
302 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
303 |
|
304 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
305 \begin{frame}[c] |
|
306 |
|
307 |
|
308 \begin{textblock}{11}(1,3) |
|
309 \begin{tabular}{@{\hspace{-10mm}}l} |
|
310 \begin{tikzpicture}[scale=1.1] |
|
311 \node at (-2.5,-1.5) {\textcolor{white}{a}}; |
|
312 \node at (8,4) {\textcolor{white}{a}}; |
|
313 |
|
314 |
|
315 |
|
316 \only<1>{ |
|
317 \draw[fill, blue!50] (1,0) rectangle (6,0.6); |
|
318 \node at (1.5,0.9) {\small $A_L$}; |
|
319 \node at (2.0,0.9) {\small $B_L$}; |
|
320 \node at (3.5,0.9) {\small $A_R$}; |
|
321 \node at (5.7,0.9) {\small $B_R$}; |
|
322 \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6); |
|
323 \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6); |
|
324 \draw[very thick,blue!100] (3.5,0) -- (3.5,0.6); |
|
325 \draw[very thick,blue!100] (5.7,0) -- (5.7,0.6); |
|
326 } |
|
327 \only<2>{ |
|
328 \draw[fill, blue!50] (1,0) rectangle (3,0.6); |
|
329 \draw[very thick, blue!50] (3,0) rectangle (6,0.6); |
|
330 \node at (1.5,0.9) {\small $A_L$}; |
|
331 \node at (2.0,0.9) {\small $B_L$}; |
|
332 \node at (3.5,0.9) {\small $A_R$}; |
|
333 \node at (5.7,0.9) {\small $B_R$}; |
|
334 \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6); |
|
335 \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6); |
|
336 \draw[very thick,blue!100] (3.5,0) -- (3.5,0.6); |
|
337 \draw[very thick,blue!100] (5.7,0) -- (5.7,0.6); |
|
338 } |
|
339 \only<3>{ |
|
340 \draw[fill, blue!50] (1,0) rectangle (3,0.6); |
|
341 \draw[very thick, blue!50] (3,0) rectangle (6,0.6); |
|
342 \node at (1.5,0.9) {\small $A_L$}; |
|
343 \node at (2.0,0.9) {\small $B_L$}; |
|
344 \node at (3.5,0.9) {\small $A_R$}; |
|
345 \node at (5.7,0.9) {\small $B_R$}; |
|
346 \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6); |
|
347 \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6); |
|
348 \draw[very thick,blue!100] (3.5,0) -- (3.5,0.6); |
|
349 \draw[very thick,blue!100] (5.7,0) -- (5.7,0.6); |
|
350 \draw[very thick,blue!100] (3,3) rectangle (4,3.6); |
|
351 \node at (3.5,3.3) {\small $A$}; |
|
352 } |
|
353 \only<4>{ |
|
354 \draw[fill, blue!50] (1,0) rectangle (3,0.6); |
|
355 \draw[very thick, blue!50] (3,0) rectangle (6,0.6); |
|
356 \node at (1.5,0.9) {\small $A_L$}; |
|
357 \node at (2.0,0.9) {\small $B_L$}; |
|
358 \node at (3.5,0.9) {\small $A_R$}; |
|
359 \node at (5.7,0.9) {\small $B_R$}; |
|
360 \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6); |
|
361 \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6); |
|
362 \draw[very thick,blue!100] (3.5,0) -- (3.5,0.6); |
|
363 \draw[very thick,blue!100] (5.7,0) -- (5.7,0.6); |
|
364 \draw[very thick,blue!100] (3,3) rectangle (4,3.6); |
|
365 \node at (3.5,3.3) {\small $A$}; |
|
366 \draw[very thick,blue!100] (4,3) rectangle (5,3.6); |
|
367 \node at (4.5,3.3) {\small $B$}; |
|
368 } |
|
369 \only<5>{ |
|
370 \draw[fill, blue!50] (1,0) rectangle (3,0.6); |
|
371 \draw[very thick, blue!50] (3,3) rectangle (6,3.6); |
|
372 \node at (1.5,0.9) {\small $A_L$}; |
|
373 \node at (2.0,0.9) {\small $B_L$}; |
|
374 \node at (3.5,3.9) {\small $A_R$}; |
|
375 \node at (5.7,3.9) {\small $B_R$}; |
|
376 \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6); |
|
377 \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6); |
|
378 \draw[very thick,blue!100] (3.5,3) -- (3.5,3.6); |
|
379 \draw[very thick,blue!100] (5.7,3) -- (5.7,3.6); |
|
380 \draw[very thick,blue!100] (6,3) rectangle (7,3.6); |
|
381 \node at (6.5,3.3) {\small $A$}; |
|
382 \draw[very thick,blue!100] (7,3) rectangle (8,3.6); |
|
383 \node at (7.5,3.3) {\small $B$}; |
|
384 \draw[blue!50, ->, line width = 2mm] (3,1) -- (3, 2.5); |
|
385 } |
|
386 \only<6>{ |
|
387 \draw[fill, blue!50] (1,0) rectangle (3,0.6); |
|
388 \draw[fill, blue!50] (3,3) rectangle (3.5,3.6); |
|
389 \draw[very thick, blue!50] (3.5,3) rectangle (6,3.6); |
|
390 \node at (1.5,0.9) {\small $A_L$}; |
|
391 \node at (2.0,0.9) {\small $B_L$}; |
|
392 \node at (3.5,3.9) {\small $A_R$}; |
|
393 \node at (5.7,3.9) {\small $B_R$}; |
|
394 \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6); |
|
395 \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6); |
|
396 \draw[very thick,blue!100] (3.5,3) -- (3.5,3.6); |
|
397 \draw[very thick,blue!100] (5.7,3) -- (5.7,3.6); |
|
398 \draw[very thick,blue!100] (6,3) rectangle (7,3.6); |
|
399 \node at (6.5,3.3) {\small $A$}; |
|
400 \draw[very thick,blue!100] (7,3) rectangle (8,3.6); |
|
401 \node at (7.5,3.3) {\small $B$}; |
|
402 } |
|
403 \only<7>{ |
|
404 \draw[fill, blue!50] (1,0) rectangle (3,0.6); |
|
405 \draw[fill, blue!50] (3,3) rectangle (3.5,3.6); |
|
406 \draw[very thick, blue!50] (3.5,0) rectangle (6,0.6); |
|
407 \node at (1.5,0.9) {\small $A_L$}; |
|
408 \node at (2.0,0.9) {\small $B_L$}; |
|
409 \node at (3.5,3.9) {\small $A_R$}; |
|
410 \node at (5.7,0.9) {\small $B_R$}; |
|
411 \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6); |
|
412 \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6); |
|
413 \draw[very thick,blue!100] (3.5,3) -- (3.5,3.6); |
|
414 \draw[very thick,blue!100] (5.7,0) -- (5.7,0.6); |
|
415 \draw[very thick,blue!100] (6,3) rectangle (7,3.6); |
|
416 \node at (6.5,3.3) {\small $A$}; |
|
417 \draw[very thick,blue!100] (7,3) rectangle (8,3.6); |
|
418 \node at (7.5,3.3) {\small $B$}; |
|
419 \draw[blue!50, <-, line width = 2mm] (3.5,1) -- (3.5, 2.5); |
|
420 \draw[blue!50, <-, line width = 2mm] (4,3.3) -- (5.5,3.3); |
|
421 } |
|
422 \only<8>{ |
|
423 \draw[fill, blue!50] (1,0) rectangle (3,0.6); |
|
424 \draw[fill, blue!50] (3,3) rectangle (3.5,3.6); |
|
425 \draw[very thick, blue!50] (4.5,0) rectangle (7,0.6); |
|
426 \node at (1.5,0.9) {\small $A_L$}; |
|
427 \node at (2.0,0.9) {\small $B_L$}; |
|
428 \node at (3.5,3.9) {\small $A_R$}; |
|
429 \node at (6.7,0.9) {\small $B_R$}; |
|
430 \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6); |
|
431 \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6); |
|
432 \draw[very thick,blue!100] (3.5,3) -- (3.5,3.6); |
|
433 \draw[very thick,blue!100] (6.7,0) -- (6.7,0.6); |
|
434 \draw[fill,blue!100] (3.5,3) rectangle (4.5,3.6); |
|
435 \node at (4,3.3) {\small $A$}; |
|
436 \draw[very thick,blue!100] (7,3) rectangle (8,3.6); |
|
437 \node at (7.5,3.3) {\small $B$}; |
|
438 } |
|
439 \only<9>{ |
|
440 \draw[fill, blue!50] (1,0) rectangle (3,0.6); |
|
441 \draw[fill, blue!50] (3,3) rectangle (3.5,3.6); |
|
442 \draw[fill, blue!50] (4.5,0) rectangle (5,0.6); |
|
443 \draw[very thick, blue!50] (5,0) rectangle (7,0.6); |
|
444 \node at (1.5,0.9) {\small $A_L$}; |
|
445 \node at (2.0,0.9) {\small $B_L$}; |
|
446 \node at (3.5,3.9) {\small $A_R$}; |
|
447 \node at (6.7,0.9) {\small $B_R$}; |
|
448 \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6); |
|
449 \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6); |
|
450 \draw[very thick,blue!100] (3.5,3) -- (3.5,3.6); |
|
451 \draw[very thick,blue!100] (6.7,0) -- (6.7,0.6); |
|
452 \draw[fill,blue!100] (3.5,3) rectangle (4.5,3.6); |
|
453 \node at (4,3.3) {\small $A$}; |
|
454 \draw[very thick,blue!100] (7,3) rectangle (8,3.6); |
|
455 \node at (7.5,3.3) {\small $B$}; |
|
456 } |
|
457 \only<10>{ |
|
458 \draw[fill, blue!50] (1,0) rectangle (3,0.6); |
|
459 \draw[fill, blue!50] (3,3) rectangle (3.5,3.6); |
|
460 \draw[fill, blue!50] (4.5,0) rectangle (5,0.6); |
|
461 \draw[very thick, blue!50] (5,0) rectangle (7,0.6); |
|
462 \node at (1.5,0.9) {\small $A_L$}; |
|
463 \node at (2.0,0.9) {\small $B_L$}; |
|
464 \node at (3.5,3.9) {\small $A_R$}; |
|
465 \node at (6.7,0.9) {\small $B_R$}; |
|
466 \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6); |
|
467 \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6); |
|
468 \draw[very thick,blue!100] (3.5,3) -- (3.5,3.6); |
|
469 \draw[very thick,blue!100] (6.7,0) -- (6.7,0.6); |
|
470 \draw[fill,blue!100] (3.5,3) rectangle (4.5,3.6); |
|
471 \node at (4,3.3) {\small $A$}; |
|
472 \draw[very thick,blue!100] (7,3) rectangle (8,3.6); |
|
473 \node at (7.5,3.3) {\small $B$}; |
|
474 \draw[red, fill] (5,1.5) rectangle (6,2.1); |
|
475 \draw[red, fill] (6.05,1.5) rectangle (7,2.1); |
|
476 } |
|
477 \only<11>{ |
|
478 \draw[fill, blue!50] (1,0) rectangle (3,0.6); |
|
479 \draw[fill, blue!50] (3,3) rectangle (3.5,3.6); |
|
480 \draw[fill, blue!50] (4.5,0) rectangle (5,0.6); |
|
481 \draw[very thick, blue!50] (5,0) rectangle (7,0.6); |
|
482 \node at (1.5,0.9) {\small $A_L$}; |
|
483 \node at (2.0,0.9) {\small $B_L$}; |
|
484 \node at (3.5,3.9) {\small $A_R$}; |
|
485 \node at (6.7,0.9) {\small $B_R$}; |
|
486 \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6); |
|
487 \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6); |
|
488 \draw[very thick,blue!100] (3.5,3) -- (3.5,3.6); |
|
489 \draw[very thick,blue!100] (6.7,0) -- (6.7,0.6); |
|
490 \draw[fill,blue!100] (3.5,3) rectangle (4.5,3.6); |
|
491 \node at (4,3.3) {\small $A$}; |
|
492 \draw[very thick,blue!100] (7,3) rectangle (8,3.6); |
|
493 \node at (7.5,3.3) {\small $B$}; |
|
494 \draw[red, fill] (5,1.5) rectangle (6,2.1); |
|
495 \draw[red, fill] (6.05,1.5) rectangle (7,2.1); |
|
496 \draw[blue!50, ->, line width = 2mm] (7.1,0.4) -- (8, 0.4); |
|
497 \draw[blue!50, ->, line width = 2mm] (7.1,4) -- (8,4); |
|
498 } |
|
499 |
|
500 \draw[very thick,->](0,0) -- (8,0); |
|
501 \node [anchor=base] at (8, -0.3) {\scriptsize time}; |
|
502 \node [anchor=base] at (0, -0.3) {\scriptsize 0}; |
|
503 \node [anchor=base] at (-1.2, 0.2) {\small low priority}; |
|
504 \only<2->{\node [anchor=base] at (-1.2, 3.2) {\small high priority};} |
|
505 \only<10->{\node [anchor=base] at (-1.5, 1.7) {\small medium pr.};} |
|
506 |
|
507 \end{tikzpicture} |
|
508 \end{tabular} |
|
509 \end{textblock} |
|
510 |
|
511 \begin{textblock}{0}(2.5,13)% |
|
512 \small |
|
513 \onslide<11>{ |
|
514 \begin{bubble}[8cm]% |
|
515 Scheduling: You want to avoid that a high |
|
516 priority process is staved indefinitely. |
|
517 \end{bubble}} |
|
518 \end{textblock} |
|
519 |
|
520 |
|
521 \end{frame} |
|
522 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
523 |
|
524 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
525 \begin{frame}[c] |
|
526 \frametitle{\Large Priority Inheritance Scheduling} |
|
527 |
|
528 \begin{itemize} |
|
529 \item Let a low priority process $L$ temporarily inherit |
|
530 the high priority of $H$ until $L$ leaves the critical |
|
531 section unlocking the resource.\bigskip |
|
532 \item Once the resource is unlocked $L$ returns to its original |
|
533 priority level. \alert{\bf BOGUS}\pause\bigskip |
|
534 \item \ldots $L$ needs to switch to the highest |
|
535 \alert{remaining} priority of the threads that it blocks. |
|
536 \end{itemize}\bigskip |
|
537 |
|
538 \small this error is already known since around 1999 |
|
539 |
|
540 \end{frame} |
|
541 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
542 |
|
543 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
544 \begin{frame}[c] |
|
545 |
|
546 \begin{center} |
|
547 \includegraphics[scale=0.25]{../pics/p3.jpg} |
|
548 \end{center} |
|
549 |
|
550 \begin{itemize} |
|
551 \item by Rajkumar, 1991 |
|
552 \item \it ``it resumes the priority it had at the point of entry into the critical |
|
553 section'' |
|
554 \end{itemize} |
|
555 |
|
556 \end{frame} |
|
557 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
558 |
|
559 |
|
560 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
561 \begin{frame}[c] |
|
562 |
|
563 \begin{center} |
|
564 \includegraphics[scale=0.25]{../pics/p2.jpg} |
|
565 \end{center} |
|
566 |
|
567 \begin{itemize} |
|
568 \item by Jane Liu, 2000 |
|
569 \item {\it ``The job $J_l$ executes at its inherited |
|
570 priority until it releases $R$; at that time, the |
|
571 priority of $J_l$ returns to its priority |
|
572 at the time when it acquires the resource $R$.''}\medskip |
|
573 \item \small gives pseudo code and totally bogus data structures |
|
574 \item \small interesting part ``{\it left as an exercise}'' |
|
575 \end{itemize} |
|
576 |
|
577 \end{frame} |
|
578 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
579 |
|
580 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
581 \begin{frame}[c] |
|
582 |
|
583 \begin{center} |
|
584 \includegraphics[scale=0.15]{../pics/p1.pdf} |
|
585 \end{center} |
|
586 |
|
587 \begin{itemize} |
|
588 \item by Laplante and Ovaska, 2011 (\$113.76) |
|
589 \item \it ``when $[$the task$]$ exits the critical section that |
|
590 caused the block, it reverts to the priority it had |
|
591 when it entered that section'' |
|
592 \end{itemize} |
|
593 |
|
594 \end{frame} |
|
595 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
596 |
|
597 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
598 \begin{frame}[c] |
|
599 \frametitle{Priority Scheduling} |
|
600 |
|
601 \begin{itemize} |
|
602 \item a scheduling algorithm that is widely used in real-time operating systems |
|
603 \item has been ``proved'' correct by hand in a paper in 1983 |
|
604 \item but this algorithm turned out to be incorrect, despite its ``proof''\bigskip\pause |
|
605 |
|
606 \item we corrected the algorithm and then {\bf really} proved that it is correct |
|
607 \item we implemented this algorithm in a small OS called PINTOS (used for teaching at Stanford) |
|
608 \item our implementation was much more efficient than their reference implementation |
|
609 \end{itemize} |
|
610 |
|
611 \end{frame} |
|
612 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
337 |
613 |
338 |
614 |
339 |
615 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
340 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
616 \begin{frame}[c] |
341 \mode<presentation>{ |
617 \frametitle{Design of AC-Policies} |
342 \begin{frame}[c] |
618 |
343 \frametitle{Non-Interactive ZKPs} |
619 \Large |
344 |
620 \begin{quote} |
345 |
621 ''what you specify is what you get but not necessarily what you want\ldots'' |
346 \bigskip |
622 \end{quote}\bigskip\bigskip\bigskip |
347 This is amazing: Alison can publish some data that contains no data about her secret, |
623 |
348 but this data can be used to convince anyone of the secret's existence. |
624 \normalsize main work by Chunhan Wu (PhD-student) |
349 \end{frame}} |
625 |
|
626 \end{frame} |
|
627 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
628 |
|
629 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
630 \begin{frame}[c] |
|
631 \frametitle{Testing Policies} |
|
632 |
|
633 \begin{center} |
|
634 \begin{tikzpicture}[scale=1] |
|
635 %\draw[black!10,step=2mm] (-5,-3) grid (5,4); |
|
636 %\draw[black!10,thick,step=10mm] (-5,-3) grid (5,4); |
|
637 \draw[white,thick,step=10mm] (-5,-3) grid (5,4); |
|
638 |
|
639 \draw [black!20, line width=1mm] (0,0) circle (1cm); |
|
640 \draw [line width=1mm] (0,0) circle (3cm); |
|
641 \node [black!20] at (0,0) {\begin{tabular}{c}core\\[-1mm] system\end{tabular}}; |
|
642 |
|
643 \draw [red, line width=2mm, <-] (-2.1,2.1) -- (-3.5,3.2); |
|
644 \node at (-3.5,3.6) {your system}; |
|
645 \node at (-4.8,0) {\Large policy $+$}; |
|
646 |
|
647 |
|
648 \only<2>{ |
|
649 \draw [black, fill=red, line width=0.5mm] (2,1) circle (3mm); |
|
650 \draw [red, line width=2mm, <-] (2.3,1.2) -- (3.5,2); |
|
651 \node at (3.8,2.6) {\begin{tabular}{l}a seed\\[-1mm] \footnotesize virus, Trojan\end{tabular}};} |
|
652 |
|
653 \only<3>{ |
|
654 \draw [black, fill=red, line width=0.5mm] (2,1) circle (7mm); |
|
655 \node[white] at (2,1) {\small tainted};} |
|
656 |
|
657 \only<4>{ |
|
658 \begin{scope} |
|
659 \draw [clip] (0,0) circle (2.955cm); |
|
660 \draw [black, fill=red, line width=0.5mm] (2,1) circle (9mm); |
|
661 \node[white] at (2,1) {\small tainted}; |
|
662 \end{scope}} |
|
663 |
|
664 \only<5->{ |
|
665 \begin{scope} |
|
666 \draw [clip] (0,0) circle (2.955cm); |
|
667 \draw [black, fill=red, line width=0.5mm] (2,1) circle (13mm); |
|
668 \node[white] at (2,1) {\small tainted}; |
|
669 \end{scope}} |
|
670 |
|
671 \only<6->{ |
|
672 \draw[fill=white, line width=1mm] (1.265,2.665) arc (-35:183:5mm); |
|
673 \draw[fill=white, line width=1mm] (1.25,3.25) arc (-35:183:3mm); |
|
674 \node[black, rotate=10] at (1.9,3.6) {\LARGE\ldots}; |
|
675 } |
|
676 |
|
677 \end{tikzpicture} |
|
678 \end{center} |
|
679 |
|
680 \end{frame} |
350 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
681 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
351 |
682 |
352 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
683 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
353 \mode<presentation>{ |
684 \begin{frame}[c] |
354 \begin{frame}[c] |
685 \frametitle{A Sound and Complete Test} |
355 \frametitle{Non-Interactive ZKPs (2)} |
686 |
356 |
687 \begin{itemize} |
357 Alice starts with knowing an isomorphism \bl{$\sigma$} between graphs \bl{$G_1$} and \bl{$G_2$}\medskip |
688 \item working purely in the \emph{dynamic world} does not work -\!-\!- infinite state space\bigskip |
358 |
689 |
359 \begin{enumerate} |
690 \item working purely on \emph{static} policies also does not\\ work -\!-\!- because of over approximation |
360 \item Alice generates \bl{$n$} isomorphic graphs \bl{$H_{1..n}$} which she makes public |
691 \smallskip |
361 \item she feeds the \bl{$H_{1..n}$} into a hashing function (she has no control over what |
692 \begin{itemize} |
362 the output will be) |
693 \item suppose a tainted file has type \emph{bin} and |
363 \item Alice takes the first \bl{$n$} bits of the output: whenever output is \bl{$0$}, she shows |
694 \item there is a role \bl{$r$} which can both read and write \emph{bin}-files\pause |
364 an isomorphism with \bl{$G_1$} ; for \bl{$1$} she shows an isomorphism with \bl{$G_2$} |
695 \item then we would conclude that this tainted file can spread\medskip\pause |
365 \end{enumerate} |
696 \item but if there is no process with role \bl{$r$} and it will never been |
366 |
697 created, then the file actually does not spread |
367 \end{frame}} |
698 \end{itemize}\bigskip\pause |
368 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
699 |
369 |
700 \item \alert{our solution:} take a middle ground and record precisely the information |
370 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
701 of the initial state, but be less precise about every newly created object. |
371 \mode<presentation>{ |
702 \end{itemize} |
372 \begin{frame}[c] |
703 |
373 \frametitle{Problems of ZKPs} |
704 \end{frame}} |
374 |
705 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
375 \begin{itemize} |
706 |
376 \item ``grand chess master problem''\\ |
707 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
377 (person in the middle)\bigskip |
|
378 |
|
379 \item Alice can have multiple identities; once she committed a fraud she stops using one |
|
380 \end{itemize} |
|
381 |
|
382 \end{frame}} |
|
383 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
384 |
|
385 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
386 \mode<presentation>{ |
|
387 \begin{frame}[c] |
|
388 \frametitle{Other Methods for ZKPs} |
|
389 |
|
390 Essentially every NP-problem can be used for ZKPs |
|
391 |
|
392 \begin{itemize} |
|
393 \item modular logarithms: Alice chooses public \bl{$A$}, \bl{$B$}, \bl{$p$}; and private \bl{$x$} |
|
394 |
|
395 \begin{center} |
|
396 \bl{$A^x \equiv B\; mod\; p$} |
|
397 \end{center} |
|
398 \end{itemize} |
|
399 |
|
400 \end{frame}} |
|
401 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
402 |
|
403 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
404 \mode<presentation>{ |
|
405 \begin{frame}[c] |
|
406 \frametitle{Commitment Stage} |
|
407 |
|
408 \begin{enumerate} |
|
409 \item Alice generates \bl{$z$} random numbers \bl{$r_1$}, ..., \bl{$r_z$}, all less than \bl{$p - 1$}. |
|
410 \item Alice sends Bob for all \bl{$1..z$} |
|
411 \begin{center} |
|
412 \bl{$h_i = A^{r_i} \;mod\; p$} |
|
413 \end{center} |
|
414 \item Bob generates random bits \bl{$b_1$}, ..., \bl{$b_z$} by flipping a coin |
|
415 \item For each bit \bl{$b_i$}, Alice sends Bob an \bl{$s_i$} where |
|
416 |
|
417 \begin{center} |
|
418 \begin{tabular}{ll} |
|
419 \bl{$b_i = 0$}: & \bl{$s_i = r_i$}\\ |
|
420 \bl{$b_i = 1$}: & \bl{$s_i = (r_i - r_j) \;mod\; (p -1)$}\\ |
|
421 \end{tabular} |
|
422 \end{center} |
|
423 where \bl{$r_j$} is the lowest \bl{$j$} where \bl{$b_j = 1$} |
|
424 |
|
425 \end{enumerate} |
|
426 |
|
427 \end{frame}} |
|
428 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
429 |
|
430 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
431 \mode<presentation>{ |
|
432 \begin{frame}[c] |
|
433 \frametitle{Confirmation Stage} |
|
434 |
|
435 \begin{enumerate} |
|
436 \item For each \bl{$b_i$} Bob checks whether \bl{$s_i$} conforms to the protocol |
|
437 |
|
438 \begin{center} |
|
439 \begin{tabular}{ll} |
|
440 \bl{$b_i = 0$}: & \bl{$A^{s_i} \equiv B\;mod\;p$}\\ |
|
441 \bl{$b_i = 1$}: & \bl{$A^{s_i} \equiv h_i * h_j^{-1} \;mod\; p$}\\ |
|
442 \end{tabular} |
|
443 \end{center}\bigskip |
|
444 |
|
445 Bob was send |
|
446 |
|
447 \begin{center} |
|
448 \bl{$r_j - r _j$}, \bl{$r_m - r _j$}, \ldots, \bl{$r_p - r _j$ \;mod \;p} |
|
449 \end{center} |
|
450 |
|
451 where the corresponding bits were |
|
452 \bl{$1$}; Bob does not know \bl{$r_j$}, he does not know any \bl{$r_i$} where the bit was \bl{$1$} |
|
453 \end{enumerate} |
|
454 |
|
455 \end{frame}} |
|
456 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
457 |
|
458 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
459 \mode<presentation>{ |
|
460 \begin{frame}[c] |
|
461 \frametitle{Proving Stage} |
|
462 |
|
463 \begin{enumerate} |
|
464 \item Alice proves she knows \bl{$x$}, the discrete log of \bl{$B$}\\ |
|
465 she sends |
|
466 |
|
467 \begin{center} |
|
468 \bl{$s_{z+1} = (x - r_j)$} |
|
469 \end{center} |
|
470 |
|
471 \item Bob confirms |
|
472 |
|
473 \begin{center} |
|
474 \bl{$A^{s_{z+1}} \equiv B * h_j^{-1} \;mod \; p$} |
|
475 \end{center} |
|
476 \end{enumerate}\bigskip\pause |
|
477 |
|
478 In order to cheat, Alice has to guess all bits in advance. She has only \bl{$1$} to \bl{$2^z$} |
|
479 chance. \\ |
|
480 \small\hspace{7mm}\textcolor{gray}{(explanation $\rightarrow$ \url{http://goo.gl/irL9GK})} |
|
481 |
|
482 \end{frame}} |
|
483 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
484 |
|
485 |
|
486 |
|
487 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
488 \mode<presentation>{ |
|
489 \begin{frame}[c] |
708 \begin{frame}[c] |
490 \frametitle{Random Number Generators} |
709 \frametitle{Random Number Generators} |
491 |
710 |
492 \begin{itemize} |
711 \end{frame} |
493 \item Computers are deterministic. How do they generate random numbers?\bigskip\pause |
|
494 |
|
495 \item The most popular method to generate random numbers between \bl{$0$} and \bl{$m$} is: choose |
|
496 three integers |
|
497 |
|
498 \begin{center} |
|
499 \begin{tabular}{ll} |
|
500 \bl{$a$} & multiplier\\ |
|
501 \bl{$c$} & increment\\ |
|
502 \bl{$X_0$} & start value |
|
503 \end{tabular} |
|
504 \end{center} |
|
505 |
|
506 and calculate |
|
507 |
|
508 \begin{center} |
|
509 \bl{$X_{n+1} = (a * X_n + c) \;mod\; m$} |
|
510 \end{center} |
|
511 \end{itemize} |
|
512 |
|
513 \only<3->{ |
|
514 \begin{textblock}{7}(10,2) |
|
515 \begin{tikzpicture} |
|
516 \draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] |
|
517 {\begin{minipage}{3.8cm} |
|
518 \begin{tabular}{ll|l} |
|
519 \bl{$m =$} & \bl{$16$} & \bl{$16$}\\ |
|
520 \bl{$X_0 =$} & \bl{$1$} & \bl{$1$}\\ |
|
521 \bl{$a = $} & \bl{$5$} & \bl{$5$}\\ |
|
522 \bl{$c =$} & \bl{$1$} & \bl{$0$}\\ |
|
523 \end{tabular} |
|
524 \end{minipage}}; |
|
525 \end{tikzpicture} |
|
526 \end{textblock}} |
|
527 |
|
528 \end{frame}} |
|
529 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
712 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
530 \end{document} |
713 \end{document} |
531 |
714 |
532 %%% Local Variables: |
715 %%% Local Variables: |
533 %%% mode: latex |
716 %%% mode: latex |