# HG changeset patch # User Christian Urban # Date 1385505906 0 # Node ID 85b961f1eee94016228a92dc5cd0e715a2c2f4c4 # Parent 0b59588d28d2132615fba88b9adac691d6ce2d95 added diff -r 0b59588d28d2 -r 85b961f1eee9 hws/hw08.pdf Binary file hws/hw08.pdf has changed diff -r 0b59588d28d2 -r 85b961f1eee9 hws/hw08.tex --- a/hws/hw08.tex Tue Nov 26 19:54:16 2013 +0000 +++ b/hws/hw08.tex Tue Nov 26 22:45:06 2013 +0000 @@ -13,35 +13,15 @@ \section*{Homework 8} \begin{enumerate} -\item Suppose the following grammar for the WHILE-language: - -\begin{center} -\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$\medskip\\ -$Stmts$ & $\rightarrow$ & $Stmt \;\text{;}\; Stmts$\\ - & $|$ & $Stmt$\medskip\\ -$Block$ & $\rightarrow$ & $\{ Stmts \}$\\ - & $|$ & $Stmt$\medskip\\ -$AExp$ & $\rightarrow$ & $AExp + AExp$\\ - & $|$ & $AExp * AExp$\\ - & $|$ & $( AExp )$\\ - & $|$ & $Num$\\ - & $|$ & $Id$\medskip\\ -$BExp$ & $\rightarrow$ & $AExp = AExp$\\ - & $|$ & $AExp \not= AExp$\\ - & $|$ & $\text{false}$\\ - & $|$ & $\text{true}$\\ - -\end{tabular} -\end{center} - -Transform this grammar into Chomsky normalform. - \item Write a program in the WHILE-language that calculates the factorial function. +\item What optimisations could a compiler perform when compiling a WHILE-program? + +\item What is the main difference between the Java assembler (as processed by Jasmin) and +Java Byte Code? + +\item Parser combinators can directly be given a string as input, without the need of a lexer. What are +the advantages to first lex a string and then feed a sequence of tokens as input to the parser? \end{enumerate} \end{document} diff -r 0b59588d28d2 -r 85b961f1eee9 slides/slides09.pdf Binary file slides/slides09.pdf has changed diff -r 0b59588d28d2 -r 85b961f1eee9 slides/slides09.tex --- a/slides/slides09.tex Tue Nov 26 19:54:16 2013 +0000 +++ b/slides/slides09.tex Tue Nov 26 22:45:06 2013 +0000 @@ -1,7 +1,7 @@ \documentclass[dvipsnames,14pt,t]{beamer} -\usepackage{beamerthemeplainculight} -\usepackage[T1]{fontenc} -\usepackage[latin1]{inputenc} +\usepackage{beamerthemeplaincu} +%\usepackage[T1]{fontenc} +%\usepackage[latin1]{inputenc} \usepackage{mathpartir} \usepackage[absolute,overlay]{textpos} \usepackage{ifthen} @@ -98,11 +98,23 @@ % beamer stuff -\renewcommand{\slidecaption}{AFL 09, King's College London, 28.~November 2012} +\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 @@ -165,7 +177,7 @@ \begin{center} \begin{tabular}{ll} Email: & christian.urban at kcl.ac.uk\\ - Of$\!$fice: & S1.27 (1st floor Strand Building)\\ + Office: & S1.27 (1st floor Strand Building)\\ Slides: & KEATS (also home work is there)\\ \end{tabular} \end{center} @@ -177,22 +189,169 @@ \mode{ \begin{frame}[c] -Imagine the following situation: You talk to somebody -and you find out that she/he has implemented a compiler.\smallskip +\large\bf +Using a compiler, \\how can you mount the\\ perfect attack against a system? + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] -What is your reaction? Check all that apply.\bigskip\pause +{\large\bf +What is a perfect attack?} + +\begin{enumerate} +\item you can potentially completely take over a target system +\item your attack is (nearly) undetectable +\end{enumerate} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - \begin{itemize} - \item[$\Box$] You think she/he is God - \item[$\Box$] \"Uberhacker - \item[$\Box$] superhuman - \item[$\Box$] wizard - \item[$\Box$] supremo - \end{itemize} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\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@{}}clean\\compiler\end{tabular}};} + + + \onslide<2->{ + \node (B) at (0,3) [draw=black, rectangle, very thick, minimum height=8mm, minimum width=12mm] {}; + \node [below right] at (B.north west) {\footnotesize login}; + \node [above right] at (B.south west) {\footnotesize \alert{infected}}; + \node [right] at (B.east) {\ldots}; + } + + + + + \end{tikzpicture} + \end{center} + + \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\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};} + + \end{tikzpicture} + \end{center} + + + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + \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}} + \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{ \begin{frame}[c] @@ -227,7 +386,7 @@ \mbox{}\\[-18mm]\mbox{} {\lstset{language=While}\fontsize{10}{12}\selectfont -\texttt{\lstinputlisting{fib.while}}} +\texttt{\lstinputlisting{../progs/fib.while}}} \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -286,7 +445,7 @@ \mbox{}\\[-18mm]\mbox{} {\lstset{language=While}\fontsize{10}{12}\selectfont -\texttt{\lstinputlisting{loops.while}}} +\texttt{\lstinputlisting{../progs/loops.while}}} \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%