2 \usepackage{beamerthemeplaincu}

     2 \usepackage{../slides}

     3 \usepackage[absolute,overlay]{textpos}

     4 \usepackage{ifthen}

     5 \usepackage{tikz}

     6 \usepackage{pgf}

     7 \usepackage{calc} 

     8 \usepackage{ulem}

     9 \usepackage{courier}

    10 \usepackage{listings}

    11 \renewcommand{\uline}[1]{#1}

    12 \usetikzlibrary{arrows}

    13 \usetikzlibrary{automata}

    14 \usetikzlibrary{shapes}

    15 \usetikzlibrary{shadows}

    16 \usetikzlibrary{positioning}

    17 \usetikzlibrary{calc}

    18 \usetikzlibrary{plotmarks}

    19 \usepackage{graphicx} 

    20 \usepackage{pgfplots}

    21 \usepackage{soul}

    24 

     5 \usepackage{../graphics}

     6 \usepackage{soul}

    52 % beamer stuff 

    34 % beamer stuff

    53 \renewcommand{\slidecaption}{AFL 10, King's College London, 4.~December 2013}

    35 \renewcommand{\slidecaption}{AFL 10, King's College London}

    55 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions

    37 

    60 \mode<presentation>{

    42 \begin{frame}[t]

    61 \begin{frame}<1>[t]

    78 \end{frame}}

    59 \end{frame}

    85 \Large\bf

    66 \large\bf

    86 There are more problems, than there are programs.\bigskip\bigskip\pause\\

    67 Using a compiler, \\how can you mount the\\ perfect attack against a system?

    87 

    68 

    88 There must be a problem for which there is no program.

    69 \end{frame}}

    89 \end{frame}}

    70 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

    90 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

    71 

    91 

    72 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    92 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    73 \mode<presentation>{

    93 \mode<presentation>{

    74 \begin{frame}[c]

    94 \begin{frame}[t]

    75 

    95 \frametitle{Last Week}

    76 {\large\bf

    96 

    77 What is a \alert{perfect} attack?}\bigskip

    97 \begin{center}

    78 

    98 if \bl{$\varnothing$} does not occur in \bl{$r$} \;\;then\;\;\bl{$L(r) \not= \{\}$}

    79 \begin{enumerate}

    99 \end{center}

    80 \item you can potentially completely take over a target system

   100 

    81 \item your attack is (nearly) undetectable

   101 \noindent

    82 \item the victim has (almost) no chance to recover

   102 holds, or equivalently

    83 \end{enumerate}

   103 

    84 

   104 \begin{center}

    85 \end{frame}}

   105 \bl{$L(r) = \{\}$} \;\;implies\;\; \bl{$\varnothing$} occurs in \bl{$r$}.\pause

    86 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   106 \end{center}

    87 

   107 

    88 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   108 \begin{center}

    89 \mode<presentation>{

   109 \bl{\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}

    90 \begin{frame}[c]

   110 $occurs(\varnothing)$      & $\dn$ & $true$\\

    91 

   111 $occurs(\epsilon)$           & $\dn$ &  $f\!alse$\\

    92 

   112 $occurs (c)$                    & $\dn$ &  $f\!alse$\\

    93   \begin{center}

   113 $occurs (r_1 + r_2)$       & $\dn$ &  $occurs(r_1) \vee occurs(r_2)$\\ 

    94   \begin{tikzpicture}[scale=1]

   114 $occurs (r_1 \cdot r_2)$ & $\dn$ &  $occurs(r_1) \vee occurs(r_2)$\\

    95   

   115 $occurs (r^*)$                & $\dn$ & $occurs(r)$ \\

    96   \onslide<1->{

   116 \end{tabular}}

    97   \node (A) at (0,0)  [draw=black, rectangle, very thick, minimum height=18mm, minimum width=17mm] {};

   117 \end{center}

    98   \node [below right] at (A.north west) {\footnotesize\begin{tabular}{@{}l@{}}

   118 

    99   \only<1,2>{clean}\only<3->{\alert{hacked}}\\compiler\end{tabular}};}

   119 \end{frame}}

   100 

   120 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   101 

   121 

   102   \onslide<2->{

   122 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   103   \node (B) at (-2,2)  [draw=black, rectangle, very thick, minimum height=10mm, minimum width=12mm] {};

   123 \begin{frame}[c,fragile]

   104   \node [below right] at (B.north west) {\footnotesize\begin{tabular}{@{}l@{}}login\\(src)\end{tabular}};

   124 \frametitle{Functional Programming}

   105   

   125 

   106   \node (C) at (2,2)  [draw=black, rectangle, very thick, minimum height=10mm, minimum width=12mm] {};

   126 \footnotesize

   107   \node [below right] at (C.north west) {\footnotesize\begin{tabular}{@{}l@{}}login\\(bin)\end{tabular}};

   127 \begin{textblock}{13}(0.9,3)

   108 

   128 \lstset{emph={def,if,then,else},emphstyle=\color{javapurple}}

   109   \draw[->, line width=2mm] (B) -- (C);

   129 \begin{lstlisting}[basicstyle=\ttfamily, numbers=none]

   130 def fib(n) = if n == 0 then 0 

   131              else if n == 1 then 1 

   132              else fib(n - 1) + fib(n - 2);

   133 

   134 def fact(n) = if n == 0 then 1 else n * fact(n - 1);

   135 

   136 def ack(m, n) = if m == 0 then n + 1

   137                 else if n == 0 then ack(m - 1, 1)

   138                 else ack(m - 1, ack(m, n - 1));

   139                 

   140 def gcd(a, b) = if b == 0 then a else gcd(b, a % b);                

   141 \end{lstlisting}

   142 \end{textblock}

   143 

   144 \end{frame}

   145 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   146 

   147 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   148 \mode<presentation>{

   149 \begin{frame}[c]

   150 

   151 \begin{center}

   152 \bl{\begin{tabular}{@{}lcl@{}}

   153 \textit{Exp} & $\rightarrow$ &  \textit{Var} $|$ \textit{Num}\\

   154               & $|$ & \textit{Exp} \texttt{+} \textit{Exp} $|$ ... $|$ ( \textit{Exp} )\\

   155               & $|$ & \texttt{if}\; \textit{BExp} \;\texttt{then}\; \textit{Exp} \;\texttt{else}\; \textit{Exp}\\

   156               & $|$ & \texttt{write}\;\textit{Exp}\\

   157               & $|$ & \textit{Exp}\;\texttt{;}\;\textit{Exp}\\

   158               & $|$ & \textit{FunName} \texttt{(}\textit{Exp},...,\textit{Exp}\texttt{)}\medskip\\

   159 \textit{BExp} & $\rightarrow$ & \ldots\medskip\\

   160 \textit{Decl} & $\rightarrow$ &  \textit{Def} \;\texttt{;}\; \textit{Decl}\\

   161               & $|$ & \textit{Exp}\medskip\\

   162 \textit{Def} & 

   163 $\rightarrow$ &  \texttt{def} \textit{FunName}\texttt{(}\textit{x}$_1$,..., \textit{x}$_n$\texttt{)} \texttt{=} \textit{Exp}\\

   164 \end{tabular}}

   165 \end{center}

   166 

   167 

   168 \end{frame}}

   169 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   170 

   171 

   172 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   173 \begin{frame}[c, fragile]

   174 \frametitle{Abstract Syntax Tree}

   175 

   176 \footnotesize

   177 \begin{textblock}{13}(0.3,2)

   178 \begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none]

   179 abstract class Exp

   180 abstract class BExp 

   181 abstract class Decl

   182 

   183 case class 

   184   Def(name: String, args: List[String], body: Exp) 

   185                                           extends Decl

   186 case class Main(e: Exp) extends Decl

   187 

   188 case class Call(name: String, args: List[Exp]) extends Exp

   189 case class If(a: BExp, e1: Exp, e2: Exp) extends Exp

   190 case class Write(e: Exp) extends Exp

   191 case class Var(s: String) extends Exp

   192 case class Num(i: Int) extends Exp

   193 case class Aop(o: String, a1: Exp, a2: Exp) extends Exp

   194 case class Sequ(e1: Exp, e2: Exp) extends Exp

   195 

   196 case class Bop(o: String, a1: Exp, a2: Exp) extends BExp

   197 \end{lstlisting}

   198 \end{textblock}

   199 

   200 \end{frame}

   201 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   202 

   203 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   204 \begin{frame}[c, fragile]

   205 \frametitle{Mathematical Functions}

   206 

   207 Compilation of some mathematical functions:

   208 

   209 \begin{center}

   210 \begin{tabular}{lcl}

   211 \texttt{Aop("+", a1, a2)} & $\Rightarrow$ & \texttt{...iadd}\\

   212 \texttt{Aop("-", a1, a2)} & $\Rightarrow$ & \texttt{...isub}\\

   213 \texttt{Aop("*", a1, a2)} & $\Rightarrow$ & \texttt{...imul}\\

   214 \texttt{Aop("/", a1, a2)} & $\Rightarrow$ & \texttt{...idiv}\\

   215 \texttt{Aop("\%", a1, a2)} & $\Rightarrow$ & \texttt{...irem}\\

   216 \end{tabular}

   217 \end{center}

   218 

   219 \end{frame}

   220 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   221 

   222 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   223 \begin{frame}[c, fragile]

   224 \frametitle{Boolean Expressions}

   225 

   226 Compilation of boolean expressions:

   227 

   228 \begin{center}

   229 \begin{tikzpicture}[node distance=2mm and 4mm,

   230  block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm},

   231  point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red},

   232  skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}]

   233 \node (A1) [point] {};

   234 \node (b) [block, right=of A1] {code of \bl{$b$}};

   235 \node (A2) [point, right=of b] {};

   236 \node (cs1) [block, right=of A2] {code of \bl{$cs_1$}};

   237 \node (A3) [point, right=of cs1] {};

   238 \node (cs2) [block, right=of A3] {code of \bl{$cs_2$}};

   239 \node (A4) [point, right=of cs2] {};

   240 

   241 \only<1>{

   242 \draw (A1) edge [->, red, line width=1mm] (b);

   243 \draw (b) edge [->, red, line width=1mm] (A2);

   244 \draw (A2) edge [skip loop] (A3);

   245 \draw (A3) edge [->, red, line width=1mm] (cs2);

   246 \draw (cs2) edge [->,red, line width=1mm] (A4);

   247 \node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};}

   248 \end{tikzpicture}

   249 \end{center}

   250 

   251 \begin{center}

   252 \begin{tabular}{lcl}

   253 \texttt{Bop("==", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpne...}\\

   254 \texttt{Bop("!=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpeq...}\\

   255 \texttt{Bop("<", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpge...}\\

   256 \texttt{Bop("<=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpgt...}\\

   257 \end{tabular}

   258 \end{center}

   259 

   260 \end{frame}

   261 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   262 

   263 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   264 \begin{frame}[t, fragile]

   265 \frametitle{Sequences}

   266 

   267 Compiling \texttt{arg1 ; arg2}:

   268 

   269 

   270 \begin{textblock}{7}(2,5)\footnotesize

   271 \begin{minipage}{6cm}

   272 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none]

   273 ...arg1...

   274 pop

   275 ...arg1...

   276 \end{lstlisting}

   277 \end{minipage}

   278 \end{textblock}

   279 

   280   

   281 \end{frame}

   282 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   283 

   284 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   285 \begin{frame}[t, fragile]

   286 \frametitle{Write}

   287 

   288 Compiling \texttt{write(arg)}:

   289 

   290 

   291 \begin{textblock}{7}(2,4)\footnotesize

   292 \begin{minipage}{6cm}

   293 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none]

   294 ...arg...

   295 dup

   296 invokestatic XXX/XXX/write(I)V

   297 \end{lstlisting}

   298 \end{minipage}

   299 \end{textblock}

   300 

   301 

   302 

   303 \begin{textblock}{7}(2,8)\footnotesize

   304 \begin{minipage}{6cm}

   305 \begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none]

   306 case Write(a1) => {

   307     compile_exp(a1, env) ++

   308     List("dup\n",

   309          "invokestatic XXX/XXX/write(I)V\n")

   311 \end{lstlisting}

   111   

   312 \end{minipage}

   112  \onslide<3->{\node [above left=-1.5mm] at (C.south east) {\footnotesize \alert{$\blacksquare$}};}

   313 \end{textblock}

   113 

   314   

   114   \end{tikzpicture}

   315 \end{frame}

   115   \end{center}

   316 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   116 

   317 

   117 \end{frame}}

   318 

   118 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   319 

   119 

   320 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   120 

   321 \begin{frame}[c, fragile]

   121 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   322 \frametitle{Functions}

   122 \mode<presentation>{

   323 

   123 \begin{frame}[c]

   324 \begin{textblock}{7}(1,2)\footnotesize

   124 

   325 \begin{minipage}{6cm}

   125   \begin{center}

   326 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none]

   126   \begin{tikzpicture}[scale=1]

   327 .method public static write(I)V 

   127   

   328    .limit locals 5 

   128   \onslide<1->{

   329    .limit stack 5 

   129   \node (A) at (0,0)  [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {};

   330    iload 0 

   130   \node [below right] at (A.north west) {\small V0.01};

   331    getstatic java/lang/System/out Ljava/io/PrintStream; 

   131   \node [below right] (A1) at (A.south west) {\small Scala};

   332    swap 

   132   \node [below right] (A1) at (A1.south west) {\small\textcolor{gray}{host language}};

   333    invokevirtual java/io/PrintStream/println(I)V 

   133   \node [above right] at (A.north west) {my compiler (src)};}

   334    return 

   134 

   335 .end method

   135   \onslide<2->{

   336 \end{lstlisting}

   136   \node (B) at (1.8,0)  [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {};

   337 \end{minipage}

   137   \node [below right] at (B.north west) {\small V0.02};

   338 \end{textblock}

   138   \node [below right] at (B.south west) {\small Scala};

   339 

   139   \node at (3,0) {\ldots};

   340 

   140 

   341 \begin{textblock}{10}(1,9.8)

   141   \node (C) at (5,0)  [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {};

   342 \small We will need for definitions\\[-8mm]\mbox{}\footnotesize

   142   \node [below right] at (C.north west) {\small V1.00};

   343 \begin{center}

   143   \node [below right] at (C.south west) {\small Scala};}

   344 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none]

   144 

   345 .method public static f (I...I)I

   145   \onslide<3->{

   346   .limit locals ??

   146   \node (D) at (6.8,0)  [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {};

   347   .limit stack ?? 

   147   \node [below right] at (D.north west) {\small V1.00};

   348   ??

   148 

   349 .end method

   149   \node (E) at (6.8,2)  [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {};

   350 \end{lstlisting}

   150   \node [below right] at (E.north west) {\small V1.01};}

   351 \end{center}

   151   

   352 \end{textblock}

   152   \onslide<4->{

   353 

   153   \node (F) at (8.6,0)  [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {};

   354 \end{frame}

   154   \node [below right] at (F.north west) {\small V1.01};

   355 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   155 

   356 

   156   \node (G) at (8.6,2)  [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {};

   357 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   157   \node [below right] at (G.north west) {\small V1.02};

   358 \begin{frame}[c, fragile]

   158   \node at (9.8,0) {\ldots};

   359 \frametitle{Stack Estimation}

   159   \node at (9.8,2) {\ldots};

   360 \footnotesize

   160   \node at (8,-2) {\textcolor{gray}{\begin{tabular}{@{}l@{}}no host language\\needed\end{tabular}}};

   361 \begin{center}

   362 \begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none]

   363 def max_stack_exp(e: Exp): Int = e match {

   364   case Call(_, args) => args.map(max_stack_exp).sum

   365   case If(a, e1, e2) => max_stack_bexp(a) + 

   366   	(List(max_stack_exp(e1), max_stack_exp(e1)).max)

   367   case Write(e) => max_stack_exp(e) + 1

   368   case Var(_) => 1

   369   case Num(_) => 1

   370   case Aop(_, a1, a2) => 

   371   	max_stack_exp(a1) + max_stack_exp(a2)

   372   case Sequ(e1, e2) => 

   373   	List(max_stack_exp(e1), max_stack_exp(e2)).max

   374 }

   375 

   376 def max_stack_bexp(e: BExp): Int = e match {

   377   case Bop(_, a1, a2) => 

   378   	max_stack_exp(a1) + max_stack_exp(a2)

   379 }

   380 \end{lstlisting}

   381 \end{center}

   382 

   383 \end{frame}

   384 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   385 

   386 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   387 \begin{frame}[fragile]

   388 \frametitle{Successor}

   389 

   390 \begin{textblock}{7}(1,2.5)\footnotesize

   391 \begin{minipage}{6cm}

   392 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none]

   393 .method public static suc(I)I 

   394 .limit locals 1

   395 .limit stack

   396   iload 0

   397   ldc 1

   398   iadd

   399   ireturn

   400 .end method 

   401 \end{lstlisting}

   402 \end{minipage}

   403 \end{textblock}

   404 

   405 \begin{textblock}{7}(6,8)

   406 \begin{tikzpicture}\small

   407 \draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] 

   408 {\begin{minipage}{5cm}

   409 \begin{lstlisting}[language=Lisp,basicstyle=\ttfamily, numbers=none]

   410 def suc(x) = x + 1;

   411 \end{lstlisting}

   412 \end{minipage}};

   413 \end{tikzpicture}

   414 \end{textblock}

   415 \end{frame}

   416 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   417 

   418 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   419 \begin{frame}[fragile]

   420 \frametitle{Addition}

   421 

   422 \begin{textblock}{7}(1,1.5)\footnotesize

   423 \begin{minipage}{6cm}

   424 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none]

   425 .method public static add(II)I 

   426 .limit locals 2

   427 .limit stack 4

   428   iload 0

   429   ldc 0

   430   if_icmpne If_else_2

   431   iload 1

   432   goto If_end_3

   433 If_else_2:

   434   iload 0

   435   ldc 1

   436   isub

   437   iload 1

   438   invokestatic defs/defs/add(II)I

   439   invokestatic defs/defs/suc(I)I

   440 If_end_3:

   441   ireturn

   442 .end method

   443 \end{lstlisting}

   444 \end{minipage}

   445 \end{textblock}

   446 

   447 \begin{textblock}{7}(6,6.2)

   448 \begin{tikzpicture}\small

   449 \draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] 

   450 {\begin{minipage}{7cm}

   451 \begin{lstlisting}[language=Lisp,basicstyle=\ttfamily, numbers=none]

   452 def add(x, y) = 

   453     if x == 0 then y 

   454     else suc(add(x - 1, y));

   455 \end{lstlisting}

   456 \end{minipage}};

   457 \end{tikzpicture}

   458 \end{textblock}

   459 \end{frame}

   460 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   461 

   462 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   463 \begin{frame}[fragile]

   464 \frametitle{Factorial}

   465 

   466 \begin{textblock}{7}(1,1.5)\footnotesize

   467 \begin{minipage}{6cm}

   468 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none]

   469 .method public static facT(II)I 

   470 .limit locals 2

   471 .limit stack 4

   472   iload 0

   473   ldc 0	

   474   if_icmpne If_else_2

   475   iload 1

   476   goto If_end_3

   477 If_else_2:

   478   iload 0

   479   ldc 1

   480   isub

   481   iload 0

   482   iload 1

   483   imul

   484   invokestatic fact/fact/facT(II)I

   485 If_end_3:

   486   ireturn

   487 .end method 

   488 \end{lstlisting}

   489 \end{minipage}

   490 \end{textblock}

   491 

   492 \begin{textblock}{7}(6,7)

   493 \begin{tikzpicture}\small

   494 \draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] 

   495 {\begin{minipage}{7cm}

   496 \begin{lstlisting}[language=Lisp,basicstyle=\ttfamily, numbers=none]

   497 def facT(n, acc) = 

   498   if n == 0 then acc 

   499   else facT(n - 1, n * acc);

   500 \end{lstlisting}

   501 \end{minipage}};

   502 \end{tikzpicture}

   503 \end{textblock}

   504 \end{frame}

   505 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   506 

   507 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   508 \begin{frame}[fragile]

   509 %\frametitle{Factorial}

   510 

   511 \begin{textblock}{7}(1,-0.2)\footnotesize

   512 \begin{minipage}{6cm}

   513 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none, escapeinside={(*@}{@*)}]

   514 .method public static facT(II)I 

   515 .limit locals 2

   516 .limit stack 4

   517 (*@\hl{facT\_Start:} @*)

   518   iload 0

   519   ldc 0

   520   if_icmpne If_else_2

   521   iload 1

   522   goto If_end_3

   523 If_else_2:

   524   iload 0

   525   ldc 1

   526   isub

   527   iload 0

   528   iload 1

   529   imul

   530   (*@\hl{istore 1} @*)

   531   (*@\hl{istore 0} @*)

   532   (*@\hl{goto facT\_Start} @*)

   533 If_end_3:

   534   ireturn

   535 .end method 

   536 \end{lstlisting}

   537 \end{minipage}

   538 \end{textblock}

   539 

   540 \begin{textblock}{7}(6,7)

   541 \begin{tikzpicture}\small

   542 \draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] 

   543 {\begin{minipage}{7cm}

   544 \begin{lstlisting}[language=Lisp,basicstyle=\ttfamily, numbers=none]

   545 def facT(n, acc) = 

   546   if n == 0 then acc 

   547   else facT(n - 1, n * acc);

   548 \end{lstlisting}

   549 \end{minipage}};

   550 \end{tikzpicture}

   551 \end{textblock}

   552 \end{frame}

   553 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   554 

   555 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   556 \begin{frame}[c, fragile]

   557 \frametitle{Tail Recursion}

   558 

   559 A call to \texttt{f(args)} is usually compiled as\medskip

   560 

   561 {\small\begin{lstlisting}[basicstyle=\ttfamily, numbers=none]

   562   args onto stack

   563   invokestatic  .../f 

   564 \end{lstlisting}}\pause

   565 

   566 

   567 A call is in tail position provided:\medskip

   568 

   569 {\small\begin{itemize}

   570 \item \texttt{if Bexp then \hl{Exp} else \hl{Exp}}

   571 \item \texttt{Exp ; \hl{Exp}}

   572 \item \texttt{Exp  op Exp}

   573 \end{itemize}}\medskip

   574 

   575 then a call \texttt{f(args)} can be compiled as\medskip\small

   576 

   577 \begin{lstlisting}[basicstyle=\ttfamily, numbers=none]

   578   prepare environment

   579   jump to start of function

   580 \end{lstlisting}

   581 

   582 \end{frame}

   583 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   584 

   585 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   586 \begin{frame}[c, fragile]

   587 \frametitle{Tail Recursive Call}

   588 \footnotesize

   589 \begin{textblock}{13}(0.3,2)

   590 \begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none]

   591 def compile_expT(a: Exp, env: Mem, name: String): Instrs = 

   592   ...

   593   case Call(n, args) => if (name == n) 

   594   { 

   595     val stores = args.zipWithIndex.map 

   596        { case (x, y) => "istore " + y.toString + "\n" } 

   597     args.flatMap(a => compile_expT(a, env, "")) ++

   598     stores.reverse ++ 

   599     List ("goto " + n + "_Start\n") 

   600   } 

   601   else 

   602   {

   603     val is = "I" * args.length

   604     args.flatMap(a => compile_expT(a, env, "")) ++

   605     List ("invokestatic XXX/XXX/" + n + "(" + is + ")I\n")

   607 \end{lstlisting}

   162   

   608 \end{textblock}

   163   \end{tikzpicture}

   609 

   164   \end{center}

   610 \end{frame}

   165 

   611 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   166 \end{frame}}

   612 

   167 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   613 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   168 

   614 \mode<presentation>{

   169 

   615 \begin{frame}[c]

   170   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   616 

   171   \mode<presentation>{

   617 \Large\bf

   172   \begin{frame}<1-3>

   618 There are more problems, than there are programs.\bigskip\bigskip\\

   173   \frametitle{\LARGE\begin{tabular}{c}Hacking Compilers 

   619 There must be a problem for which there is no program.

   174   \end{tabular}}

   620 \end{frame}}

   175   

   621 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   176   %Why is it so paramount to have a small trusted code base (TCB)?

   622 

   177   \bigskip\bigskip

   623 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   178 

   624 \mode<presentation>{

   179   \begin{columns}

   625 \begin{frame}[c]

   180   \begin{column}{2.7cm}

   626 \frametitle{Subsets}

   181   \begin{minipage}{2.5cm}%

   627 

   182   \begin{tabular}{c@ {}}

   628 \Large

   183   \includegraphics[scale=0.2]{../pics/ken-thompson.jpg}\\[-1.8mm]

   629 \bl{$A \subseteq B$} and \bl{$B \subseteq A$}\bigskip

   184   \footnotesize Ken Thompson\\[-1.8mm]

   630 

   185   \footnotesize Turing Award, 1983\\

   631 then \bl{$A = B$}

   186   \end{tabular}

   632 \end{frame}}

   187   \end{minipage}

   633 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   188   \end{column}

   634 

   189   \begin{column}{9cm}

   635 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   190   \begin{tabular}{l@ {\hspace{1mm}}p{8cm}}

   636 \mode<presentation>{

   191  

   637 \begin{frame}[c]

   192   & Ken Thompson showed how to hide a Trojan Horse in a 

   638 \frametitle{Injective Function}

   193   compiler \textcolor{red}{without} leaving any traces in the source code.\\[2mm]

   639 

   194   

   640 \Large

   195   & No amount of source level verification will protect 

   641 \bl{f} is an injective function iff \bigskip

   196   you from such Thompson-hacks.\\[2mm]

   642 

   197 

   643 \bl{$\forall x y.\; f(x) = f(y) \Rightarrow x = y$}

   198   & Therefore in safety-critical systems it is important to rely 

   644 

   199   on only a very small TCB.

   645 \end{frame}}

   200   \end{tabular}

   646 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   201   \end{column}

   647 

   202   \end{columns}

   648 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   203 

   649 \mode<presentation>{

   204   \only<2>{

   650 \begin{frame}[c]

   205   \begin{textblock}{6}(4,2)

   651 \frametitle{Cardinality}

   206   \begin{tikzpicture}

   652 

   207   \draw (0,0) node[inner sep=3mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] 

   653 \Large

   208   {\normalsize

   654 \bl{$|A|$} $\dn$ ``how many elements''\bigskip\\

   209   \begin{minipage}{8cm}

   655 

   210   \begin{quote}

   656 \bl{$A \subseteq B  \Rightarrow |A| \leq |B|$}\bigskip\\\pause

   211   \includegraphics[scale=0.05]{../pics/evil.png}

   657 

   212   \begin{enumerate}

   658 if there is an injective function \bl{$f: A \rightarrow B$} then \bl{$|A| \leq |B|$}\

   213   \item[1)] Assume you ship the compiler as binary and also with sources.

   659 

   214   \item[2)] Make the compiler aware when it compiles itself.

   660 \end{frame}}

   215   \item[3)] Add the Trojan horse.

   661 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   216   \item[4)] Compile.

   662 

   217   \item[5)] Delete Trojan horse from the sources of the compiler.

   663 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   218   \item[6)] Go on holiday for the rest of your life. ;o)\\[-7mm]\mbox{}

   664 \mode<presentation>{

   219   \end{enumerate}

   665 \begin{frame}[c]

   220   \end{quote}

   666 \frametitle{Natural Numbers}

   221   \end{minipage}};

   667 

   222   \end{tikzpicture}

   668 \Large

   223   \end{textblock}}

   669 \bl{$\mathbb{N}$} \bl{$\dn$} \bl{$\{0, 1, 2, 3, .......\}$}\bigskip\pause 

   224 

   670 

   225   \end{frame}}

   671 \bl{$A$} is \alert{countable} iff \bl{$|A| \leq |\mathbb{N}|$}

   226   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

   672 

   227 

   673 \end{frame}}

   228 

   674 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   675 

   676 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   677 \mode<presentation>{

   678 \begin{frame}[c]

   679 \frametitle{First Question}

   680 

   681 \Large

   682 \bl{$|\mathbb{N} - \{0\}|   \;\;\;\alert{?}\;\;\;  |\mathbb{N}| $}\bigskip\bigskip 

   683 

   684 \normalsize

   685 \bl{$\geq$} or \bl{$\leq$} or \bl{$=$} 

   686 \end{frame}}

   687 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   688 

   689 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   690 \mode<presentation>{

   691 \begin{frame}[c]

   692 

   693 \Large

   694 \bl{$|\mathbb{N} - \{0, 1\}|   \;\;\;\alert{?}\;\;\;  |\mathbb{N}| $}\bigskip\pause 

   695 

   696 \bl{$|\mathbb{N} - \mathbb{O}|   \;\;\;\alert{?}\;\;\;  |\mathbb{N}| $}\bigskip\bigskip

   697 

   698 \normalsize

   699 \bl{$\mathbb{O}$} $\dn$ odd numbers\quad   \bl{$\{1,3,5......\}$}\\ \pause

   700 \bl{$\mathbb{E}$} $\dn$ even numbers\quad   \bl{$\{0,2,4......\}$}\\

   701 \end{frame}}

   702 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   703 

   704 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   705 \mode<presentation>{

   706 \begin{frame}[c]

   707 

   708 \Large

   709 \bl{$|\mathbb{N} \cup \mathbb{-N}|   \;\;\;\alert{?}\;\;\;  |\mathbb{N}| $}\bigskip\bigskip

   710 

   711 

   712 \normalsize

   713 \bl{$\mathbb{\phantom{-}N}$} $\dn$ positive numbers\quad   \bl{$\{0,1,2,3,......\}$}\\

   714 \bl{$\mathbb{-N}$} $\dn$ negative numbers\quad   \bl{$\{0,-1,-2,-3,......\}$}\\

   715 \end{frame}}

   716 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   717 

   718 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   719 \mode<presentation>{

   720 \begin{frame}[c]

   721 

   722 \Large

   723 \bl{$A$} is \alert{countable} if there exists an injective \bl{$f : A \rightarrow \mathbb{N}$}\bigskip

   724 

   725 \bl{$A$} is \alert{uncountable} if there does not exist an injective \bl{$f : A \rightarrow \mathbb{N}$}\bigskip\bigskip 

   726 

   727 

   728 countable:  \bl{$|A| \leq |\mathbb{N}|$}\\

   729 uncountable:  \bl{$|A| > |\mathbb{N}|$}\pause\bigskip

   730 

   731 

   732 Does there exist such an \bl{$A$} ?

   733 

   734 \end{frame}}

   735 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   736 

   737 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   738 \mode<presentation>{

   739 \begin{frame}[c]

   740 \frametitle{Halting Problem}

   741 

   742 \large

   743 Assume a program \bl{$H$} that decides for all programs \bl{$A$} and all 

   744 input data \bl{$D$} whether\bigskip

   745 

   746 \begin{itemize}

   747 \item \bl{$H(A, D) \dn 1$} iff \bl{$A(D)$} terminates

   748 \item \bl{$H(A, D) \dn 0$} otherwise

   749 \end{itemize}

   750 

   751 \end{frame}}

   752 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   753 

   754 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   755 \mode<presentation>{

   756 \begin{frame}[c]

   757 \frametitle{Halting Problem (2)}

   758 

   759 \large

   760 Given such a program \bl{$H$} define the following program \bl{$C$}:

   761 for all programs \bl{$A$}\bigskip

   762 

   763 \begin{itemize}

   764 \item \bl{$C(A) \dn 0$} iff \bl{$H(A, A) = 0$} 

   765 \item \bl{$C(A) \dn$ loops} otherwise

   766 \end{itemize}

   767 

   768 \end{frame}}

   769 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   770 

   771 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   772 \mode<presentation>{

   773 \begin{frame}[c]

   774 \frametitle{Contradiction}

   775 

   776 

   777 \bl{$H(C, C)$} is either \bl{$0$} or \bl{$1$}.

   778 

   779 \begin{itemize}

   780 \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$} 

   781 \item \bl{$H(C, C) = 0$} $\stackrel{\text{def}\,H}{\Rightarrow}$ \bl{$C(C)$} loops $\stackrel{\text{def}\,C}{\Rightarrow}$\\ 

   782 \hspace{7cm}\bl{$H(C, C)=1$} 

   783 \end{itemize}

   784 

   785 Contradiction in both cases. So \bl{$H$} cannot exist.

   786 

   787 \end{frame}}

   788 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%