\documentclass[dvipsnames,14pt,t]{beamer}

\usepackage{beamerthemeplaincu}

%\usepackage[T1]{fontenc}

%\usepackage[latin1]{inputenc}

\usepackage{mathpartir}

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

\setmonofont{Consolas}

\definecolor{javared}{rgb}{0.6,0,0} % for strings

\definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments

\definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords

\definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc

\lstset{language=Java,

	basicstyle=\ttfamily,

	keywordstyle=\color{javapurple}\bfseries,

	stringstyle=\color{javagreen},

	commentstyle=\color{javagreen},

	morecomment=[s][\color{javadocblue}]{/**}{*/},

	numbers=left,

	numberstyle=\tiny\color{black},

	stepnumber=1,

	numbersep=10pt,

	tabsize=2,

	showspaces=false,

	showstringspaces=false}

\lstdefinelanguage{scala}{

  morekeywords={abstract,case,catch,class,def,%

    do,else,extends,false,final,finally,%

    for,if,implicit,import,match,mixin,%

    new,null,object,override,package,%

    private,protected,requires,return,sealed,%

    super,this,throw,trait,true,try,%

    type,val,var,while,with,yield},

  otherkeywords={=>,<-,<\%,<:,>:,\#,@},

  sensitive=true,

  morecomment=[l]{//},

  morecomment=[n]{/*}{*/},

  morestring=[b]",

  morestring=[b]',

  morestring=[b]"""

}

\lstset{language=Scala,

	basicstyle=\ttfamily,

	keywordstyle=\color{javapurple}\bfseries,

	stringstyle=\color{javagreen},

	commentstyle=\color{javagreen},

	morecomment=[s][\color{javadocblue}]{/**}{*/},

	numbers=left,

	numberstyle=\tiny\color{black},

	stepnumber=1,

	numbersep=10pt,

	tabsize=2,

	showspaces=false,

	showstringspaces=false}

\lstdefinelanguage{while}{

  morekeywords={if,then,else,while,do,true,false,write},

  otherkeywords={=,!=,:=,<,>,;},

  sensitive=true,

  morecomment=[n]{/*}{*/},

}

\lstset{language=While,

	basicstyle=\ttfamily,

	keywordstyle=\color{javapurple}\bfseries,

	stringstyle=\color{javagreen},

	commentstyle=\color{javagreen},

	morecomment=[s][\color{javadocblue}]{/**}{*/},

	numbers=left,

	numberstyle=\tiny\color{black},

	stepnumber=1,

	numbersep=10pt,

	tabsize=2,

	showspaces=false,

	showstringspaces=false}

% beamer stuff 

\renewcommand{\slidecaption}{AFL 09, King's College London, 27.~November 2013}

\newcommand{\bl}[1]{\textcolor{blue}{#1}}       

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

 \pgfdeclareradialshading{smallbluesphere}{\pgfpoint{0.5mm}{0.5mm}}%

  {rgb(0mm)=(0,0,0.9);

  rgb(0.9mm)=(0,0,0.7);

  rgb(1.3mm)=(0,0,0.5);

  rgb(1.4mm)=(1,1,1)}

  \def\myitemi{\begin{pgfpicture}{-1ex}{-0.55ex}{1ex}{1ex}

    \usebeamercolor[fg]{subitem projected}

    {\pgftransformscale{0.8}\pgftext{\normalsize\pgfuseshading{bigsphere}}}

    \pgftext{%

      \usebeamerfont*{subitem projected}}

  \end{pgfpicture}}

% The data files, written on the first run.

\begin{filecontents}{compiled.data}

%1 0.234146

%5000 0.227539

%10000 0.280748

50000 1.087897

100000 3.713165

250000 21.6624545

500000 85.872613

750000 203.6408015

1000000 345.736574

\end{filecontents}

\begin{filecontents}{interpreted.data}

%1 0.00503

200 1.005863

400 7.8296765

500 15.43106

600 27.2321885

800 65.249271

1000 135.4493445

1200 232.134097

1400 382.527227

\end{filecontents}

\begin{filecontents}{interpreted2.data}

%1 0.00503

200 1.005863

400 7.8296765

600 27.2321885

800 65.249271

1000 135.4493445

1200 232.134097

1400 382.527227

\end{filecontents}

\begin{filecontents}{compiled2.data}

200 0.222058

400 0.215204

600 0.202031

800 0.21986

1000 0.205934

1200 0.1981615

1400 0.207116

\end{filecontents}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}<1>[t]

\frametitle{%

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

  \\[-3mm]

  \LARGE Automata and \\[-2mm] 

  \LARGE Formal Languages (9)\\[3mm] 

  \end{tabular}}

  \normalsize

  \begin{center}

  \begin{tabular}{ll}

  Email:  & christian.urban at kcl.ac.uk\\

  Office: & S1.27 (1st floor Strand Building)\\

  Slides: & KEATS (also home work is there)\\

  \end{tabular}

  \end{center}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\large\bf

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

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

{\large\bf

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

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

  \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}};}

  \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}};

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

  }

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

  \end{tikzpicture}

  \end{center}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

  \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)};}

  \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};}

  \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};

  \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};

  \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<presentation>{

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

  \myitemi

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

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

  \myitemi

  & No amount of source level verification will protect 

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

  \myitemi

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

  on only a very small TCB.

  \end{tabular}

  \end{column}

  \end{columns}

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

  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\frametitle{Our Compiler}

  \begin{center}

  \begin{tikzpicture}[scale=1]

  \node (0) at (-2.3,0) {}; 

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

  \node [below right] at (A.north west) {lexer};

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

  \node [below right=1mm] at (B.north west) {\mbox{}\hspace{-1mm}parser};

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

  \node [below right] at (C.north west) {\mbox{}\hspace{-1mm}code gen};

  \node (1) at (8.4,0) {}; 

  \draw [->,line width=4mm] (0) -- (A); 

  \draw [->,line width=4mm] (A) -- (B); 

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

  \draw [->,line width=4mm] (C) -- (1); 

  \end{tikzpicture}

  \end{center}

lexer input: string\medskip\\

lexer output: sequence of tokens\\ 

\mbox{}\hfill(white space and comments filtered out)\medskip\\

parser output: abstract syntax tree\medskip\\ 

code gen output: assembler byte code / \\

\mbox{}\hfill assembler machine code

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}For-Loops\end{tabular}}

\begin{center}\Large

\texttt{for} \;\textit{Id} \texttt{:=} \textit{AExp}\; \texttt{upto} \;\textit{AExp}\; \texttt{do} \textit{Block}

\end{center}\bigskip

\begin{center}

\begin{minipage}{8cm}

\begin{tabular}{l}

\texttt{for i := 2 upto 4 do \{}\\

\hspace{5mm}\texttt{write i}\\	

\texttt{\}}\

\end{tabular}

\end{minipage}

\end{center}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}While-Language\end{tabular}}

\begin{center}

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

$Stmt$ & $\rightarrow$ &  $\text{skip}$\\

              & $|$ & $Id := AExp$\\

              & $|$ & $\text{if}\; B\!Exp \;\text{then}\; Block \;\text{else}\; Block$\\

              & $|$ & $\text{while}\; B\!Exp \;\text{do}\; Block$\\

               & $|$ & $\alert{\text{write}\; Id}$\\

                & $|$ & $\alert{\text{read}\; Id}$\medskip\\

$Stmts$ & $\rightarrow$ &  $Stmt \;\text{;}\; Stmts$\\

              & $|$ & $Stmt$\medskip\\

$Block$ & $\rightarrow$ &  $\{ Stmts \}$\\

                & $|$ & $Stmt$\medskip\\

$AExp$ & $\rightarrow$ & \ldots\\

$BExp$ & $\rightarrow$ & \ldots\\

\end{tabular}}

\end{center}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Interpreter\end{tabular}}

\begin{center}

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

$\text{eval}(n, E)$ & $\dn$ & $n$\\

$\text{eval}(x, E)$ & $\dn$ & $E(x)$ \;\;\;\textcolor{black}{lookup \bl{$x$} in \bl{$E$}}\\

$\text{eval}(a_1 + a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) + \text{eval}(a_2, E)$\\

$\text{eval}(a_1 - a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) - \text{eval}(a_2, E)$\\

$\text{eval}(a_1 * a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) * \text{eval}(a_2, E)$\bigskip\\

$\text{eval}(a_1 = a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) = \text{eval}(a_2, E)$\\

$\text{eval}(a_1\,!\!= a_2, E)$ & $\dn$ & $\neg(\text{eval}(a_1, E) = \text{eval}(a_2, E))$\\

$\text{eval}(a_1 < a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) < \text{eval}(a_2, E)$\

\end{tabular}}

\end{center}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Interpreter (2)\end{tabular}}

\begin{center}

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

$\text{eval}(\text{skip}, E)$ & $\dn$ & $E$\\

$\text{eval}(x:=a, E)$ & $\dn$ & \bl{$E(x \mapsto \text{eval}(a, E))$}\\

\multicolumn{3}{@{}l@{}}{$\text{eval}(\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2 , E) \dn$}\\

\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)\;\text{then}\;

\text{eval}(cs_1,E)$}\\

\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\phantom{\text{if}\;\text{eval}(b,E)\;}\text{else}\;\text{eval}(cs_2,E)$}\\

\multicolumn{3}{@{}l@{}}{$\text{eval}(\text{while}\;b\;\text{do}\;cs, E) \dn$}\\

\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)$}\\

\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{then}\;

\text{eval}(\text{while}\;b\;\text{do}\;cs, \text{eval}(cs,E))$}\\

\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{else}\; E$}\\

$\text{eval}(\text{write}\; x, E)$ & $\dn$ & $\{\;\text{println}(E(x))\; ;\;E\;\}$\\

\end{tabular}}

\end{center}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[t]