diff -r 7dd5797a5ffa -r 470922b46a63 slides/slides10.tex --- a/slides/slides10.tex Fri Nov 28 13:47:32 2014 +0000 +++ b/slides/slides10.tex Wed Dec 03 00:00:36 2014 +0000 @@ -1,27 +1,9 @@ \documentclass[dvipsnames,14pt,t]{beamer} -\usepackage{beamerthemeplaincu} -\usepackage[absolute,overlay]{textpos} -\usepackage{ifthen} -\usepackage{tikz} -\usepackage{pgf} -\usepackage{calc} -\usepackage{ulem} -\usepackage{courier} -\usepackage{listings} -\renewcommand{\uline}[1]{#1} -\usetikzlibrary{arrows} -\usetikzlibrary{automata} -\usetikzlibrary{shapes} -\usetikzlibrary{shadows} -\usetikzlibrary{positioning} -\usetikzlibrary{calc} -\usetikzlibrary{plotmarks} -\usepackage{graphicx} -\usepackage{pgfplots} -\usepackage{soul} +\usepackage{../slides} \usepackage{../langs} \usepackage{../data} - +\usepackage{../graphics} +\usepackage{soul} \tikzset{onslide/.code args={<#1>#2}{% \only<#1>{\pgfkeysalso{#2}} % \pgfkeysalso doesn't change the path @@ -49,16 +31,15 @@ \makeatother -% beamer stuff -\renewcommand{\slidecaption}{AFL 10, King's College London, 4.~December 2013} +% beamer stuff +\renewcommand{\slidecaption}{AFL 10, King's College London} \newcommand{\bl}[1]{\textcolor{blue}{#1}} -\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions + \begin{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}<1>[t] +\begin{frame}[t] \frametitle{% \begin{tabular}{@ {}c@ {}} \\[-3mm] @@ -75,572 +56,31 @@ \end{tabular} \end{center} -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ \begin{frame}[c] -\Large\bf -There are more problems, than there are programs.\bigskip\bigskip\pause\\ - -There must be a problem for which there is no program. -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{Last Week} - -\begin{center} -if \bl{$\varnothing$} does not occur in \bl{$r$} \;\;then\;\;\bl{$L(r) \not= \{\}$} -\end{center} - -\noindent -holds, or equivalently - -\begin{center} -\bl{$L(r) = \{\}$} \;\;implies\;\; \bl{$\varnothing$} occurs in \bl{$r$}.\pause -\end{center} - -\begin{center} -\bl{\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} -$occurs(\varnothing)$ & $\dn$ & $true$\\ -$occurs(\epsilon)$ & $\dn$ & $f\!alse$\\ -$occurs (c)$ & $\dn$ & $f\!alse$\\ -$occurs (r_1 + r_2)$ & $\dn$ & $occurs(r_1) \vee occurs(r_2)$\\ -$occurs (r_1 \cdot r_2)$ & $\dn$ & $occurs(r_1) \vee occurs(r_2)$\\ -$occurs (r^*)$ & $\dn$ & $occurs(r)$ \\ -\end{tabular}} -\end{center} +\large\bf +Using a compiler, \\how can you mount the\\ perfect attack against a system? \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c,fragile] -\frametitle{Functional Programming} - -\footnotesize -\begin{textblock}{13}(0.9,3) -\lstset{emph={def,if,then,else},emphstyle=\color{javapurple}} -\begin{lstlisting}[basicstyle=\ttfamily, numbers=none] -def fib(n) = if n == 0 then 0 - else if n == 1 then 1 - else fib(n - 1) + fib(n - 2); - -def fact(n) = if n == 0 then 1 else n * fact(n - 1); - -def ack(m, n) = if m == 0 then n + 1 - else if n == 0 then ack(m - 1, 1) - else ack(m - 1, ack(m, n - 1)); - -def gcd(a, b) = if b == 0 then a else gcd(b, a % b); -\end{lstlisting} -\end{textblock} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ \begin{frame}[c] -\begin{center} -\bl{\begin{tabular}{@{}lcl@{}} -\textit{Exp} & $\rightarrow$ & \textit{Var} $|$ \textit{Num}\\ - & $|$ & \textit{Exp} \texttt{+} \textit{Exp} $|$ ... $|$ ( \textit{Exp} )\\ - & $|$ & \texttt{if}\; \textit{BExp} \;\texttt{then}\; \textit{Exp} \;\texttt{else}\; \textit{Exp}\\ - & $|$ & \texttt{write}\;\textit{Exp}\\ - & $|$ & \textit{Exp}\;\texttt{;}\;\textit{Exp}\\ - & $|$ & \textit{FunName} \texttt{(}\textit{Exp},...,\textit{Exp}\texttt{)}\medskip\\ -\textit{BExp} & $\rightarrow$ & \ldots\medskip\\ -\textit{Decl} & $\rightarrow$ & \textit{Def} \;\texttt{;}\; \textit{Decl}\\ - & $|$ & \textit{Exp}\medskip\\ -\textit{Def} & -$\rightarrow$ & \texttt{def} \textit{FunName}\texttt{(}\textit{x}$_1$,..., \textit{x}$_n$\texttt{)} \texttt{=} \textit{Exp}\\ -\end{tabular}} -\end{center} - - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c, fragile] -\frametitle{Abstract Syntax Tree} - -\footnotesize -\begin{textblock}{13}(0.3,2) -\begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none] -abstract class Exp -abstract class BExp -abstract class Decl - -case class - Def(name: String, args: List[String], body: Exp) - extends Decl -case class Main(e: Exp) extends Decl - -case class Call(name: String, args: List[Exp]) extends Exp -case class If(a: BExp, e1: Exp, e2: Exp) extends Exp -case class Write(e: Exp) extends Exp -case class Var(s: String) extends Exp -case class Num(i: Int) extends Exp -case class Aop(o: String, a1: Exp, a2: Exp) extends Exp -case class Sequ(e1: Exp, e2: Exp) extends Exp - -case class Bop(o: String, a1: Exp, a2: Exp) extends BExp -\end{lstlisting} -\end{textblock} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c, fragile] -\frametitle{Mathematical Functions} - -Compilation of some mathematical functions: - -\begin{center} -\begin{tabular}{lcl} -\texttt{Aop("+", a1, a2)} & $\Rightarrow$ & \texttt{...iadd}\\ -\texttt{Aop("-", a1, a2)} & $\Rightarrow$ & \texttt{...isub}\\ -\texttt{Aop("*", a1, a2)} & $\Rightarrow$ & \texttt{...imul}\\ -\texttt{Aop("/", a1, a2)} & $\Rightarrow$ & \texttt{...idiv}\\ -\texttt{Aop("\%", a1, a2)} & $\Rightarrow$ & \texttt{...irem}\\ -\end{tabular} -\end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c, fragile] -\frametitle{Boolean Expressions} - -Compilation of boolean expressions: - -\begin{center} -\begin{tikzpicture}[node distance=2mm and 4mm, - block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm}, - point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red}, - skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}] -\node (A1) [point] {}; -\node (b) [block, right=of A1] {code of \bl{$b$}}; -\node (A2) [point, right=of b] {}; -\node (cs1) [block, right=of A2] {code of \bl{$cs_1$}}; -\node (A3) [point, right=of cs1] {}; -\node (cs2) [block, right=of A3] {code of \bl{$cs_2$}}; -\node (A4) [point, right=of cs2] {}; - -\only<1>{ -\draw (A1) edge [->, red, line width=1mm] (b); -\draw (b) edge [->, red, line width=1mm] (A2); -\draw (A2) edge [skip loop] (A3); -\draw (A3) edge [->, red, line width=1mm] (cs2); -\draw (cs2) edge [->,red, line width=1mm] (A4); -\node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};} -\end{tikzpicture} -\end{center} - -\begin{center} -\begin{tabular}{lcl} -\texttt{Bop("==", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpne...}\\ -\texttt{Bop("!=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpeq...}\\ -\texttt{Bop("<", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpge...}\\ -\texttt{Bop("<=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpgt...}\\ -\end{tabular} -\end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t, fragile] -\frametitle{Sequences} - -Compiling \texttt{arg1 ; arg2}: - - -\begin{textblock}{7}(2,5)\footnotesize -\begin{minipage}{6cm} -\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] -...arg1... -pop -...arg1... -\end{lstlisting} -\end{minipage} -\end{textblock} - - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t, fragile] -\frametitle{Write} - -Compiling \texttt{write(arg)}: - - -\begin{textblock}{7}(2,4)\footnotesize -\begin{minipage}{6cm} -\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] -...arg... -dup -invokestatic XXX/XXX/write(I)V -\end{lstlisting} -\end{minipage} -\end{textblock} - - - -\begin{textblock}{7}(2,8)\footnotesize -\begin{minipage}{6cm} -\begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none] -case Write(a1) => { - compile_exp(a1, env) ++ - List("dup\n", - "invokestatic XXX/XXX/write(I)V\n") - } -\end{lstlisting} -\end{minipage} -\end{textblock} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c, fragile] -\frametitle{Functions} - -\begin{textblock}{7}(1,2)\footnotesize -\begin{minipage}{6cm} -\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] -.method public static write(I)V - .limit locals 5 - .limit stack 5 - iload 0 - getstatic java/lang/System/out Ljava/io/PrintStream; - swap - invokevirtual java/io/PrintStream/println(I)V - return -.end method -\end{lstlisting} -\end{minipage} -\end{textblock} - - -\begin{textblock}{10}(1,9.8) -\small We will need for definitions\\[-8mm]\mbox{}\footnotesize -\begin{center} -\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] -.method public static f (I...I)I - .limit locals ?? - .limit stack ?? - ?? -.end method -\end{lstlisting} -\end{center} -\end{textblock} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c, fragile] -\frametitle{Stack Estimation} -\footnotesize -\begin{center} -\begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none] -def max_stack_exp(e: Exp): Int = e match { - case Call(_, args) => args.map(max_stack_exp).sum - case If(a, e1, e2) => max_stack_bexp(a) + - (List(max_stack_exp(e1), max_stack_exp(e1)).max) - case Write(e) => max_stack_exp(e) + 1 - case Var(_) => 1 - case Num(_) => 1 - case Aop(_, a1, a2) => - max_stack_exp(a1) + max_stack_exp(a2) - case Sequ(e1, e2) => - List(max_stack_exp(e1), max_stack_exp(e2)).max -} - -def max_stack_bexp(e: BExp): Int = e match { - case Bop(_, a1, a2) => - max_stack_exp(a1) + max_stack_exp(a2) -} -\end{lstlisting} -\end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[fragile] -\frametitle{Successor} +{\large\bf +What is a \alert{perfect} attack?}\bigskip -\begin{textblock}{7}(1,2.5)\footnotesize -\begin{minipage}{6cm} -\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] -.method public static suc(I)I -.limit locals 1 -.limit stack - iload 0 - ldc 1 - iadd - ireturn -.end method -\end{lstlisting} -\end{minipage} -\end{textblock} - -\begin{textblock}{7}(6,8) -\begin{tikzpicture}\small -\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] -{\begin{minipage}{5cm} -\begin{lstlisting}[language=Lisp,basicstyle=\ttfamily, numbers=none] -def suc(x) = x + 1; -\end{lstlisting} -\end{minipage}}; -\end{tikzpicture} -\end{textblock} -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[fragile] -\frametitle{Addition} - -\begin{textblock}{7}(1,1.5)\footnotesize -\begin{minipage}{6cm} -\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] -.method public static add(II)I -.limit locals 2 -.limit stack 4 - iload 0 - ldc 0 - if_icmpne If_else_2 - iload 1 - goto If_end_3 -If_else_2: - iload 0 - ldc 1 - isub - iload 1 - invokestatic defs/defs/add(II)I - invokestatic defs/defs/suc(I)I -If_end_3: - ireturn -.end method -\end{lstlisting} -\end{minipage} -\end{textblock} - -\begin{textblock}{7}(6,6.2) -\begin{tikzpicture}\small -\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] -{\begin{minipage}{7cm} -\begin{lstlisting}[language=Lisp,basicstyle=\ttfamily, numbers=none] -def add(x, y) = - if x == 0 then y - else suc(add(x - 1, y)); -\end{lstlisting} -\end{minipage}}; -\end{tikzpicture} -\end{textblock} -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[fragile] -\frametitle{Factorial} - -\begin{textblock}{7}(1,1.5)\footnotesize -\begin{minipage}{6cm} -\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] -.method public static facT(II)I -.limit locals 2 -.limit stack 4 - iload 0 - ldc 0 - if_icmpne If_else_2 - iload 1 - goto If_end_3 -If_else_2: - iload 0 - ldc 1 - isub - iload 0 - iload 1 - imul - invokestatic fact/fact/facT(II)I -If_end_3: - ireturn -.end method -\end{lstlisting} -\end{minipage} -\end{textblock} - -\begin{textblock}{7}(6,7) -\begin{tikzpicture}\small -\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] -{\begin{minipage}{7cm} -\begin{lstlisting}[language=Lisp,basicstyle=\ttfamily, numbers=none] -def facT(n, acc) = - if n == 0 then acc - else facT(n - 1, n * acc); -\end{lstlisting} -\end{minipage}}; -\end{tikzpicture} -\end{textblock} -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[fragile] -%\frametitle{Factorial} - -\begin{textblock}{7}(1,-0.2)\footnotesize -\begin{minipage}{6cm} -\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none, escapeinside={(*@}{@*)}] -.method public static facT(II)I -.limit locals 2 -.limit stack 4 -(*@\hl{facT\_Start:} @*) - iload 0 - ldc 0 - if_icmpne If_else_2 - iload 1 - goto If_end_3 -If_else_2: - iload 0 - ldc 1 - isub - iload 0 - iload 1 - imul - (*@\hl{istore 1} @*) - (*@\hl{istore 0} @*) - (*@\hl{goto facT\_Start} @*) -If_end_3: - ireturn -.end method -\end{lstlisting} -\end{minipage} -\end{textblock} - -\begin{textblock}{7}(6,7) -\begin{tikzpicture}\small -\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] -{\begin{minipage}{7cm} -\begin{lstlisting}[language=Lisp,basicstyle=\ttfamily, numbers=none] -def facT(n, acc) = - if n == 0 then acc - else facT(n - 1, n * acc); -\end{lstlisting} -\end{minipage}}; -\end{tikzpicture} -\end{textblock} -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c, fragile] -\frametitle{Tail Recursion} - -A call to \texttt{f(args)} is usually compiled as\medskip - -{\small\begin{lstlisting}[basicstyle=\ttfamily, numbers=none] - args onto stack - invokestatic .../f -\end{lstlisting}}\pause - - -A call is in tail position provided:\medskip - -{\small\begin{itemize} -\item \texttt{if Bexp then \hl{Exp} else \hl{Exp}} -\item \texttt{Exp ; \hl{Exp}} -\item \texttt{Exp op Exp} -\end{itemize}}\medskip - -then a call \texttt{f(args)} can be compiled as\medskip\small - -\begin{lstlisting}[basicstyle=\ttfamily, numbers=none] - prepare environment - jump to start of function -\end{lstlisting} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c, fragile] -\frametitle{Tail Recursive Call} -\footnotesize -\begin{textblock}{13}(0.3,2) -\begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none] -def compile_expT(a: Exp, env: Mem, name: String): Instrs = - ... - case Call(n, args) => if (name == n) - { - val stores = args.zipWithIndex.map - { case (x, y) => "istore " + y.toString + "\n" } - args.flatMap(a => compile_expT(a, env, "")) ++ - stores.reverse ++ - List ("goto " + n + "_Start\n") - } - else - { - val is = "I" * args.length - args.flatMap(a => compile_expT(a, env, "")) ++ - List ("invokestatic XXX/XXX/" + n + "(" + is + ")I\n") - } -\end{lstlisting} -\end{textblock} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -\Large\bf -There are more problems, than there are programs.\bigskip\bigskip\\ -There must be a problem for which there is no program. -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{Subsets} - -\Large -\bl{$A \subseteq B$} and \bl{$B \subseteq A$}\bigskip - -then \bl{$A = B$} -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{Injective Function} - -\Large -\bl{f} is an injective function iff \bigskip - -\bl{$\forall x y.\; f(x) = f(y) \Rightarrow x = y$} +\begin{enumerate} +\item you can potentially completely take over a target system +\item your attack is (nearly) undetectable +\item the victim has (almost) no chance to recover +\end{enumerate} \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -648,144 +88,144 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ \begin{frame}[c] -\frametitle{Cardinality} + -\Large -\bl{$|A|$} $\dn$ ``how many elements''\bigskip\\ + \begin{center} + \begin{tikzpicture}[scale=1] + + \onslide<1->{ + \node (A) at (0,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=17mm] {}; + \node [below right] at (A.north west) {\footnotesize\begin{tabular}{@{}l@{}} + \only<1,2>{clean}\only<3->{\alert{hacked}}\\compiler\end{tabular}};} -\bl{$A \subseteq B \Rightarrow |A| \leq |B|$}\bigskip\\\pause - -if there is an injective function \bl{$f: A \rightarrow B$} then \bl{$|A| \leq |B|$}\ -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + \onslide<2->{ + \node (B) at (-2,2) [draw=black, rectangle, very thick, minimum height=10mm, minimum width=12mm] {}; + \node [below right] at (B.north west) {\footnotesize\begin{tabular}{@{}l@{}}login\\(src)\end{tabular}}; + + \node (C) at (2,2) [draw=black, rectangle, very thick, minimum height=10mm, minimum width=12mm] {}; + \node [below right] at (C.north west) {\footnotesize\begin{tabular}{@{}l@{}}login\\(bin)\end{tabular}}; -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{Natural Numbers} + \draw[->, line width=2mm] (B) -- (C); + } + + \onslide<3->{\node [above left=-1.5mm] at (C.south east) {\footnotesize \alert{$\blacksquare$}};} -\Large -\bl{$\mathbb{N}$} \bl{$\dn$} \bl{$\{0, 1, 2, 3, .......\}$}\bigskip\pause - -\bl{$A$} is \alert{countable} iff \bl{$|A| \leq |\mathbb{N}|$} + \end{tikzpicture} + \end{center} \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{First Question} - -\Large -\bl{$|\mathbb{N} - \{0\}| \;\;\;\alert{?}\;\;\; |\mathbb{N}| $}\bigskip\bigskip - -\normalsize -\bl{$\geq$} or \bl{$\leq$} or \bl{$=$} -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -\Large -\bl{$|\mathbb{N} - \{0, 1\}| \;\;\;\alert{?}\;\;\; |\mathbb{N}| $}\bigskip\pause - -\bl{$|\mathbb{N} - \mathbb{O}| \;\;\;\alert{?}\;\;\; |\mathbb{N}| $}\bigskip\bigskip - -\normalsize -\bl{$\mathbb{O}$} $\dn$ odd numbers\quad \bl{$\{1,3,5......\}$}\\ \pause -\bl{$\mathbb{E}$} $\dn$ even numbers\quad \bl{$\{0,2,4......\}$}\\ -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ \begin{frame}[c] -\Large -\bl{$|\mathbb{N} \cup \mathbb{-N}| \;\;\;\alert{?}\;\;\; |\mathbb{N}| $}\bigskip\bigskip - + \begin{center} + \begin{tikzpicture}[scale=1] + + \onslide<1->{ + \node (A) at (0,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {}; + \node [below right] at (A.north west) {\small V0.01}; + \node [below right] (A1) at (A.south west) {\small Scala}; + \node [below right] (A1) at (A1.south west) {\small\textcolor{gray}{host language}}; + \node [above right] at (A.north west) {my compiler (src)};} -\normalsize -\bl{$\mathbb{\phantom{-}N}$} $\dn$ positive numbers\quad \bl{$\{0,1,2,3,......\}$}\\ -\bl{$\mathbb{-N}$} $\dn$ negative numbers\quad \bl{$\{0,-1,-2,-3,......\}$}\\ -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + \onslide<2->{ + \node (B) at (1.8,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {}; + \node [below right] at (B.north west) {\small V0.02}; + \node [below right] at (B.south west) {\small Scala}; + \node at (3,0) {\ldots}; + + \node (C) at (5,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {}; + \node [below right] at (C.north west) {\small V1.00}; + \node [below right] at (C.south west) {\small Scala};} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -\Large -\bl{$A$} is \alert{countable} if there exists an injective \bl{$f : A \rightarrow \mathbb{N}$}\bigskip + \onslide<3->{ + \node (D) at (6.8,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {}; + \node [below right] at (D.north west) {\small V1.00}; -\bl{$A$} is \alert{uncountable} if there does not exist an injective \bl{$f : A \rightarrow \mathbb{N}$}\bigskip\bigskip - + \node (E) at (6.8,2) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {}; + \node [below right] at (E.north west) {\small V1.01};} + + \onslide<4->{ + \node (F) at (8.6,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {}; + \node [below right] at (F.north west) {\small V1.01}; -countable: \bl{$|A| \leq |\mathbb{N}|$}\\ -uncountable: \bl{$|A| > |\mathbb{N}|$}\pause\bigskip - - -Does there exist such an \bl{$A$} ? + \node (G) at (8.6,2) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {}; + \node [below right] at (G.north west) {\small V1.02}; + \node at (9.8,0) {\ldots}; + \node at (9.8,2) {\ldots}; + \node at (8,-2) {\textcolor{gray}{\begin{tabular}{@{}l@{}}no host language\\needed\end{tabular}}}; + } + + \end{tikzpicture} + \end{center} \end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{Halting Problem} - -\large -Assume a program \bl{$H$} that decides for all programs \bl{$A$} and all -input data \bl{$D$} whether\bigskip - -\begin{itemize} -\item \bl{$H(A, D) \dn 1$} iff \bl{$A(D)$} terminates -\item \bl{$H(A, D) \dn 0$} otherwise -\end{itemize} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{Halting Problem (2)} - -\large -Given such a program \bl{$H$} define the following program \bl{$C$}: -for all programs \bl{$A$}\bigskip - -\begin{itemize} -\item \bl{$C(A) \dn 0$} iff \bl{$H(A, A) = 0$} -\item \bl{$C(A) \dn$ loops} otherwise -\end{itemize} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{Contradiction} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\bl{$H(C, C)$} is either \bl{$0$} or \bl{$1$}. + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + \mode{ + \begin{frame}<1-3> + \frametitle{\LARGE\begin{tabular}{c}Hacking Compilers + \end{tabular}} + + %Why is it so paramount to have a small trusted code base (TCB)? + \bigskip\bigskip + + \begin{columns} + \begin{column}{2.7cm} + \begin{minipage}{2.5cm}% + \begin{tabular}{c@ {}} + \includegraphics[scale=0.2]{../pics/ken-thompson.jpg}\\[-1.8mm] + \footnotesize Ken Thompson\\[-1.8mm] + \footnotesize Turing Award, 1983\\ + \end{tabular} + \end{minipage} + \end{column} + \begin{column}{9cm} + \begin{tabular}{l@ {\hspace{1mm}}p{8cm}} + + & Ken Thompson showed how to hide a Trojan Horse in a + compiler \textcolor{red}{without} leaving any traces in the source code.\\[2mm] + + & No amount of source level verification will protect + you from such Thompson-hacks.\\[2mm] -\begin{itemize} -\item \bl{$H(C, C) = 1$} $\stackrel{\text{def}\,H}{\Rightarrow}$ \bl{$C(C)\downarrow$} $\stackrel{\text{def}\,C}{\Rightarrow}$ \bl{$H(C, C)=0$} -\item \bl{$H(C, C) = 0$} $\stackrel{\text{def}\,H}{\Rightarrow}$ \bl{$C(C)$} loops $\stackrel{\text{def}\,C}{\Rightarrow}$\\ -\hspace{7cm}\bl{$H(C, C)=1$} -\end{itemize} + & Therefore in safety-critical systems it is important to rely + on only a very small TCB. + \end{tabular} + \end{column} + \end{columns} -Contradiction in both cases. So \bl{$H$} cannot exist. + \only<2>{ + \begin{textblock}{6}(4,2) + \begin{tikzpicture} + \draw (0,0) node[inner sep=3mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] + {\normalsize + \begin{minipage}{8cm} + \begin{quote} + \includegraphics[scale=0.05]{../pics/evil.png} + \begin{enumerate} + \item[1)] Assume you ship the compiler as binary and also with sources. + \item[2)] Make the compiler aware when it compiles itself. + \item[3)] Add the Trojan horse. + \item[4)] Compile. + \item[5)] Delete Trojan horse from the sources of the compiler. + \item[6)] Go on holiday for the rest of your life. ;o)\\[-7mm]\mbox{} + \end{enumerate} + \end{quote} + \end{minipage}}; + \end{tikzpicture} + \end{textblock}} -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + \end{frame}} + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + \end{document}