\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]
\frametitle{\begin{tabular}{c}Compiling Writes\end{tabular}}

{\Large\bl{write $x$}}

\begin{center}
\small\bl{\begin{tabular}{l}
.method public static write(I)V\hspace{1cm}\textcolor{black}{(library function)}\\ 
\;\;    .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\bigskip\bigskip\\
%
\normalsize
iload $E(x)$\\
invokestatic write(I)V\\
\end{tabular}}
\end{center}

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]

\begin{center}
\small\bl{\begin{tabular}{l}
.class public XXX.XXX\\
.super java/lang/Object\\
\\
.method public <init>()V\\
\;\;     aload\_0\\
\;\;     invokenonvirtual java/lang/Object/<init>()V\\
 \;\;    return\\
.end method\\
\\
.method public static main([Ljava/lang/String;)V\\
\;\;   .limit locals 200\\
\;\;     .limit stack 200\\
\\
   \textcolor{black}{(here comes the compiled code)}\\
\\
\;\;     return\\
.end method\\
\end{tabular}}
\end{center}

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

\end{document}

%%% Local Variables:  
%%% mode: latex
%%% TeX-master: t
%%% End: