# HG changeset patch # User Christian Urban # Date 1418398897 0 # Node ID da5713bcdbb09ad9ec14c901f2348d0225a49e41 # Parent cd8d18f7b7ac585539e7ffd3bce663ba37a156ae updated diff -r cd8d18f7b7ac -r da5713bcdbb0 handouts/ho09.tex --- a/handouts/ho09.tex Thu Dec 11 23:51:08 2014 +0000 +++ b/handouts/ho09.tex Fri Dec 12 15:41:37 2014 +0000 @@ -62,13 +62,13 @@ Our starting point is a small, idealised programming language. It is idealised because we cut several corners in comparison with real programming languages. The language we will study -contains, amongst other things, variables holding integers. We -want to find out what the sign of these integers (positive or -negative) will be when the program runs. This sign-analysis -seems like a very simple problem, but it will turn out even -such simple problems, if approached naively, are in general -undecidable, just like Turing's halting problem. I let you -think why? +contains, amongst other things, variables holding integers. +Using static analysis, we want to find out what the sign of +these integers (positive or negative) will be when the program +runs. This sign-analysis seems like a very simple problem. But +it will turn out even such simple problems, if approached +naively, are in general undecidable, just like Turing's +halting problem. I let you think why? Is sign-analysis of variables an interesting problem? Well, @@ -108,11 +108,13 @@ sequences of statements. Statements are either labels, variable assignments, conditional jumps (\pcode{jmp?}) and unconditional jumps (\pcode{goto}). Labels are just strings, -which can be used as the target of a jump. The conditional -jumps and variable assignments involve (arithmetic) -expressions. Expressions are either numbers, variables or -compound expressions built up from \pcode{+}, \pcode{*} and -\emph{=} (for simplicity reasons we do not consider any other +which can be used as the target of a jump. We assume that in +every program the labels are unique---otherwise if there is a +clash we do not know where to jump to. The conditional jumps +and variable assignments involve (arithmetic) expressions. +Expressions are either numbers, variables or compound +expressions built up from \pcode{+}, \pcode{*} and \emph{=} +(for simplicity reasons we do not consider any other operations). We assume we have negative and positive numbers, \ldots \pcode{-2}, \pcode{-1}, \pcode{0}, \pcode{1}, \pcode{2}\ldots{} An example program that calculates the @@ -173,20 +175,58 @@ complexity is really beside the point here. Furthermore, real machine code has many instructions for manipulating memory. We do not have this at all. This is actually a more serious -simplification because we assume numbers to be arbitrary -precision, which is not the case with real machine code. In +simplification because we assume numbers to be arbitrary small +or large, which is not the case with real machine code. In real code basic number formats have a range and might -over-flow or under-flow from this range. Also the numbers of -variables in our programs is unlimited, while memory, of -course, is always limited somehow on any actual machine. To -sum up, our language might look very simple, but it is not -completely removed from practically relevant issues. +over-flow or under-flow from this range. Also the number of +variables in our programs is potentially unlimited, while +memory in an actual computer, of course, is always limited +somehow on any actual. To sum up, our language might look very +simple, but it is not completely removed from practically +relevant issues. \subsubsection*{An Interpreter} -Designing a language is like being god: you can say what -each part of the program should mean. +Designing a language is like playing god: you can say what +names for variables you allow; what programs should look like; +most importantly you can decide what each part of the program +should mean and do. While our language is rather simple and +the meaning is rather straightforward, there are still places +where we need to make a real choice. For example with +conditional jumps, say the one in the factorial program: + +\begin{center} +\code{jmp? n = 0 done} +\end{center} + +\noindent How should they work? We could introduce Booleans +(\pcode{true} and \pcode{false}) and then jump only when the +condition is \pcode{true}. However, since we have numbers in +our language anyway, why not just encoding \emph{true} as +zero, and \pcode{false} as anything else? In this way we can +dispense with the additional concept of Booleans, but also we +could replace the jump above by + +\begin{center} +\code{jmp? n done} +\end{center} + +\noindent which behaves exactly the same. But what does it +mean that two jumps behave the same? + +I hope the above discussion makes it already clear we need to +be a bit more careful with our programs. Below we shall +describe an interpreter for our programs, which specifies +exactly how programs are supposed to be run\ldots{}at least we +will specify this for all \emph{good} programs. By good +programs we mean where for example all variables are +initialised. Our interpreter will just crash if it cannot find +out the value for a variable, because it is not initialised. + +First we will pre-process our programs. This will simplify +our definition of our interpreter later on. We will transform +programs into \emph{snippets}. \end{document} diff -r cd8d18f7b7ac -r da5713bcdbb0 slides/slides11.pdf Binary file slides/slides11.pdf has changed diff -r cd8d18f7b7ac -r da5713bcdbb0 slides/slides11.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/slides/slides11.tex Fri Dec 12 15:41:37 2014 +0000 @@ -0,0 +1,138 @@ +\documentclass[dvipsnames,14pt,t]{beamer} +\usepackage{../slides} +\usepackage{../langs} +\usepackage{../graphics} +\usepackage{../data} +\usepackage{../grammar} + +% beamer stuff +\renewcommand{\slidecaption}{APP 11, King's College London} +\newcommand{\bl}[1]{\textcolor{blue}{#1}} + +\begin{document} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{% + \begin{tabular}{@ {}c@ {}} + \\ + \LARGE Access Control and \\[-3mm] + \LARGE Privacy Policies (11)\\[-6mm] + \end{tabular}}\bigskip\bigskip\bigskip + + \normalsize + \begin{center} + \begin{tabular}{ll} + Email: & christian.urban at kcl.ac.uk\\ + Office: & S1.27 (1st floor Strand Building)\\ + Slides: & KEATS (also homework is there)\\ + \end{tabular} + \end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + +\begin{itemize} +\item you can still send me your homework\bigskip +\item Unix AC question: use a terminal-based editor (vm, + vim)\bigskip +\item exams: 2 out of 3 questions, 5 or so subquestions + each, you can fill in your answers on the question sheet +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Interlock Protocol} + +The interlock protocol (``best bet'' against MITM): + +\begin{center} +\begin{tabular}{ll@{\hspace{2mm}}l} +1. & \bl{$A \to B :$} & \bl{$K^{pub}_A$}\\ +2. & \bl{$B \to A :$} & \bl{$K^{pub}_B$}\\ +3. & & \bl{$\{A,m\}_{K^{pub}_B} \;\mapsto\; H_1,H_2$}\\ + & & \bl{$\{B,m'\}_{K^{pub}_A} \;\mapsto\; M_1,M_2$}\\ +4. & \bl{$A \to B :$} & \bl{$H_1$}\\ +5. & \bl{$B \to A :$} & \bl{$\{H_1, M_1\}_{K^{pub}_A}$}\\ +6. & \bl{$A \to B :$} & \bl{$\{H_2, M_1\}_{K^{pub}_B}$}\\ +7. & \bl{$B \to A :$} & \bl{$M_2$} +\end{tabular} +\end{center}\pause + +\footnotesize +\bl{$m$} = How is your grandmother? \bl{$m'$} = How is the +weather today in London? + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + +\begin{center} +\begin{tabular}{l@{\hspace{9mm}}l} +\begin{tabular}[t]{@{}l@{}} +\bl{$A \to C : K^{pub}_A$}\\ +\bl{$C \to B : K^{pub}_C$}\\ +\bl{$B \to C : K^{pub}_B$}\\ +\bl{$C \to A : K^{pub}_C$}\medskip\\ +\bl{$\{A,m\}_{K^{pub}_C} \;\mapsto\; H_1,H_2$}\\ +\bl{$\{B,n\}_{K^{pub}_C} \;\mapsto\; M_1,M_2$}\bigskip\\ +\bl{$\{C,a\}_{K^{pub}_B} \;\mapsto\; C_1,C_2$}\\ +\bl{$\{C,b\}_{K^{pub}_A} \;\mapsto\; D_1,D_2$} +\end{tabular} & +\begin{tabular}[t]{@{}l@{}} +\bl{$A \to C : H_1$}\\ +\bl{$C \to B : C_1$}\\ +\bl{$B \to C : \{C_1, M_1\}_{K^{pub}_C}$}\\ +\bl{$C \to A : \{H_1, D_1\}_{K^{pub}_A}$}\\ +\bl{$A \to C : \{H_2, D_1\}_{K^{pub}_C}$}\\ +\bl{$C \to B : \{C_2, M_1\}_{K^{pub}_B}$}\\ +\bl{$B \to C : M_2$}\\ +\bl{$C \to A : D_2$} +\end{tabular} +\end{tabular} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + +\begin{itemize} +\item you have to ask something that cannot imitated + (requires \bl{$A$} and \bl{$B$} know each other) +\item what happens if \bl{$m$} and \bl{$n$} are voice + messages?\bigskip + +\item the moral: establishing a secure connection from ``zero'' is +almost impossible---you need to rely on some established +trust\medskip + +\item that is why we rely on certificates, which however are +badly, badly realised (just today a POODLE attack against SSL) + +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + + +\end{document} + + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: t +%%% End: +