# HG changeset patch # User Christian Urban # Date 1543883606 0 # Node ID 24bbe4e4b37b7bb72baae1474cbc8f7712e4c0d9 # Parent e722f4ba54dea311ec6d4a516c4a70cf2043ac0f updated diff -r e722f4ba54de -r 24bbe4e4b37b progs/catastrophic.java --- a/progs/catastrophic.java Thu Nov 29 02:38:24 2018 +0000 +++ b/progs/catastrophic.java Tue Dec 04 00:33:26 2018 +0000 @@ -16,7 +16,7 @@ public class catastrophic { public static void main(String[] args) { - + //we always run all the tests twice -> to warmup of the JVM for (int runs = 0; runs < 2; runs++) { diff -r e722f4ba54de -r 24bbe4e4b37b progs/compile_arr.scala --- a/progs/compile_arr.scala Thu Nov 29 02:38:24 2018 +0000 +++ b/progs/compile_arr.scala Tue Dec 04 00:33:26 2018 +0000 @@ -45,7 +45,8 @@ .limit stack 2 getstatic java/lang/System/out Ljava/io/PrintStream; iload 0 - invokevirtual java/io/PrintStream/println(I)V + i2c + invokevirtual java/io/PrintStream/print(C)V return .end method @@ -88,6 +89,8 @@ compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("isub\n") case Aop("*", a1, a2) => compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("imul\n") + case Ref(s, a1) => + List("aload " + env(s) + "\n") ++ compile_aexp(a1, env) ++ List("iaload \n") } // boolean expression compilation @@ -149,13 +152,10 @@ case AssignA(s, a1, a2) => { val index = if (env.isDefinedAt(s)) env(s) else throw new Exception("Array not yet defined") - (List("aload " + index) ++ + (List("aload " + index + "\n") ++ compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ - List("iastore"), env) - - compile_aexp(a, env) ++ - List("istore " + index + "\n"), env + (x -> index)) + List("iastore \n"), env) } } @@ -238,22 +238,236 @@ compile_run(fib_test, "fib") -val arr_test = - List(Assign("x", Num(0)), - Array("a", 10)) - -compile_block(arr_test, Map())._1.mkString -compile_run(arr_test, "arr") - val arr_test = - List(Array("a", 10), - Array("b", 2), - AssignA("a", Num(0), Num(10)), - Assign("x", Ref("a", Num(0))), - Write("x"), - AssignA("b", Num(1), Num(5)), - Assign("x", Ref("b", Num(1))), - Write("x")) + List(Array("a", 10), // a[10] + Array("b", 2), // b[2] + AssignA("a", Num(0), Num(10)), // a[0] := 10 + Assign("x", Ref("a", Num(0))), // x := a[0] + Write("x"), // write x + AssignA("b", Num(1), Num(5)), // b[1] := 5 + Assign("x", Ref("b", Num(1))), // x := b[1] + Write("x")) // write x + +compile_run(arr_test, "a") + + +//==================== +// Parser Combinators +//==================== + +import scala.language.implicitConversions +import scala.language.reflectiveCalls + + +abstract class Parser[I <% Seq[_], T] { + def parse(ts: I): Set[(T, I)] + + def parse_all(ts: I) : Set[T] = + for ((head, tail) <- parse(ts); if (tail.isEmpty)) yield head +} + +class SeqParser[I <% Seq[_], T, S](p: => Parser[I, T], q: => Parser[I, S]) extends Parser[I, (T, S)] { + def parse(sb: I) = + for ((head1, tail1) <- p.parse(sb); + (head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2) +} + +class AltParser[I <% Seq[_], T](p: => Parser[I, T], q: => Parser[I, T]) extends Parser[I, T] { + def parse(sb: I) = p.parse(sb) ++ q.parse(sb) +} + +class FunParser[I <% Seq[_], T, S](p: => Parser[I, T], f: T => S) extends Parser[I, S] { + def parse(sb: I) = + for ((head, tail) <- p.parse(sb)) yield (f(head), tail) +} + + +import scala.util.matching.Regex +case class RegexParser(reg: Regex) extends Parser[String, String] { + def parse(sb: String) = reg.findPrefixMatchOf(sb) match { + case None => Set() + case Some(m) => Set((m.matched, m.after.toString)) + } +} + +def StringParser(s: String) = RegexParser(Regex.quote(s).r) + + +implicit def string2parser(s : String) = StringParser(s) + +implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new { + def | (q : => Parser[I, T]) = new AltParser[I, T](p, q) + def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f) + def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q) +} + +implicit def StringOps(s: String) = new { + def | (q : => Parser[String, String]) = new AltParser[String, String](s, q) + def | (r: String) = new AltParser[String, String](s, r) + def ==>[S] (f: => String => S) = new FunParser[String, String, S](s, f) + def ~[S](q : => Parser[String, S]) = + new SeqParser[String, String, S](s, q) + def ~ (r: String) = + new SeqParser[String, String, String](s, r) +} + + +val NumParser = RegexParser("[0-9]+".r) ==> (s => s.toInt : Int) +val IdParser = RegexParser("[a-z][a-z,0-9]*".r) + + + +// Grammar Rules + +lazy val AExp: Parser[String, AExp] = + (Te ~ "+" ~ AExp) ==> { case ((x, _), z) => Aop("+", x, z):AExp } | + (Te ~ "-" ~ AExp) ==> { case ((x, _), z) => Aop("-", x, z):AExp } | Te +lazy val Te: Parser[String, AExp] = + (Fa ~ "*" ~ Te) ==> { case ((x, _), z) => Aop("*", x, z):AExp } | Fa +lazy val Fa: Parser[String, AExp] = + ("(" ~ AExp ~ ")") ==> { case ((_, y), _) => y } | + (IdParser ~ "[" ~ AExp ~ "]") ==> { case (((x, _), y), _) => Ref(x, y) } | + IdParser ==> Var | + NumParser ==> Num + +// boolean expressions +lazy val BExp: Parser[String, BExp] = + (AExp ~ "=" ~ AExp) ==> { case ((x, y), z) => Bop("=", x, z):BExp } | + (AExp ~ "!=" ~ AExp) ==> { case ((x, y), z) => Bop("!=", x, z):BExp } | + (AExp ~ "<" ~ AExp) ==> { case ((x, y), z) => Bop("<", x, z):BExp } | + (AExp ~ ">" ~ AExp) ==> { case ((x, y), z) => Bop("<", z, x):BExp } | + ("true" ==> ((_) => True:BExp )) | + ("false" ==> ((_) => False:BExp )) | + ("(" ~ BExp ~ ")") ==> { case ((x, y), z) => y} + +lazy val Stmt: Parser[String, Stmt] = + ("skip" ==> (_ => Skip: Stmt)) | + (IdParser ~ ":=" ~ AExp) ==> { case ((x, y), z) => Assign(x, z): Stmt } | + (IdParser ~ "[" ~ AExp ~ "]" ~ ":=" ~ AExp) ==> { + case (((((x, y), z), v), w), u) => AssignA(x, z, u): Stmt } | + ("if" ~ BExp ~ "then" ~ Block ~ "else" ~ Block) ==> + { case (((((x,y),z),u),v),w) => If(y, u, w): Stmt } | + ("while" ~ BExp ~ "do" ~ Block) ==> { case (((x, y), z), w) => While(y, w) } | + ("new" ~ IdParser ~ "[" ~ NumParser ~ "]") ==> { case ((((x, y), z), u), v) => Array(y, u) } | + ("write" ~ IdParser) ==> { case (_, y) => Write(y) } + +lazy val Stmts: Parser[String, Block] = + (Stmt ~ ";" ~ Stmts) ==> { case ((x, y), z) => x :: z : Block } | + (Stmt ==> ((s) => List(s) : Block)) -//compile_run(arr_test, "a") \ No newline at end of file + +lazy val Block: Parser[String, Block] = + ("{" ~ Stmts ~ "}") ==> { case ((x, y), z) => y} | + (Stmt ==> (s => List(s))) + +Stmts.parse_all("x2:=5+a") +Stmts.parse_all("x2:=5+a[3+a]") +Stmts.parse_all("a[x2+3]:=5+a[3+a]") +Block.parse_all("{x:=5;y:=8}") +Block.parse_all("if(false)then{x:=5}else{x:=10}") + + + +val fib = """ + n := 10; + minus1 := 0; + minus2 := 1; + temp:=0; + while (n > 0) do { + temp := minus2; + minus2 := minus1 + minus2; + minus1 := temp; + n := n - 1}; + result := minus2; + write result + """.replaceAll("\\s+", "") + +val fib_prog = Stmts.parse_all(fib).toList +//compile_run(fib_prog.head, "fib") + + +// BF + +// simple instructions +def instr(c: Char) : String = c match { + case '>' => "ptr := ptr + 1;" + case '<' => "ptr := ptr - 1;" + case '+' => "field[ptr] := field[ptr] + 1;" + case '-' => "field[ptr] := field[ptr] - 1;" + case '.' => "x := field[ptr]; write x;" + //case ',' => "XXX" // "ptr = getchar();\n" + case '[' => "while (field[ptr] != 0) do {" + case ']' => "skip};" + case _ => "" +} + +def instrs(prog: String) : String = + prog.toList.map(instr).mkString + + +def splice(cs: List[Char], acc: List[(Char, Int)]) : List[(Char, Int)] = (cs, acc) match { + case (Nil, acc) => acc + case (c :: cs, Nil) => splice(cs, List((c, 1))) + case (c :: cs, (d, n) :: acc) => + if (c == d) splice(cs, (c, n + 1) :: acc) + else splice(cs, (c, 1) :: (d, n) :: acc) +} + +def spl(s: String) = splice(s.toList, Nil).reverse + +def instr2(c: Char, n: Int) : String = c match { + case '>' => "ptr := ptr + " + n.toString + ";" + case '<' => "ptr := ptr - " + n.toString + ";" + case '+' => "field[ptr] := field[ptr] + " + n.toString + ";" + case '-' => "field[ptr] := field[ptr] - " + n.toString + ";" + case '.' => "x := field[ptr]; write x;" //* n + //case ',' => "*ptr = getchar();\n" * n + case '[' => "while (field[ptr] != 0) do {" * n + case ']' => "skip};" * n + case _ => "" +} + +def instrs2(prog: String) : String = + spl(prog).map{ case (c, n) => instr2(c, n) }.mkString + + +def bf_str(prog: String) : String = { + "\n" ++ + //"new field[30000];\n" ++ + "ptr := 15000;" ++ + instrs2(prog) ++ + "skip" +} + +def bf_run(prog: String, name: String) = { + println("BF processing start") + val bf_string = bf_str(prog).replaceAll("\\s", "") + println(s"BF parsing start (string length ${bf_string.length})") + val bf_prog = Stmts.parse_all(bf_string).toList.head + println("BF Compile start") + compile_run(Array("field", 30000) :: bf_prog, name) +} + + + +val bf1 = """++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[ + ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<< + ]>.>+[>>]>+]""" + +bf_run(bf1, "sier") + +bf_run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ + ..+++.>>.<-.<.+++.------.--------.>>+.>++.""", "hello") + +bf_run("""+++++++++++ + >+>>>>++++++++++++++++++++++++++++++++++++++++++++ + >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+> + +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[- + <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<< + -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]] + >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++ + +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++ + ++++++++++++++++++++++++++++++++++++++++++++.[-]<< + <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<< + [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""", "fibs") diff -r e722f4ba54de -r 24bbe4e4b37b slides/slides10.pdf Binary file slides/slides10.pdf has changed diff -r e722f4ba54de -r 24bbe4e4b37b slides/slides10.tex --- a/slides/slides10.tex Thu Nov 29 02:38:24 2018 +0000 +++ b/slides/slides10.tex Tue Dec 04 00:33:26 2018 +0000 @@ -59,205 +59,12 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -\large\bf -Using a compiler, \\how can you mount the\\ perfect attack against a system? - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\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{ -\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{ -\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{ - \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] - - \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}} - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Compilers \& Boeings 777} - -First flight in 1994. They want to achieve triple redundancy in hardware -faults.\bigskip - -They compile 1 Ada program to\medskip - -\begin{itemize} -\item Intel 80486 -\item Motorola 68040 (old Macintosh's) -\item AMD 29050 (RISC chips used often in laser printers) -\end{itemize}\medskip - -using 3 independent compilers.\bigskip\pause - -\small Airbus uses C and static analysers. Recently started using CompCert. - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -{\Large\bf -How many strings are in \bl{$L(a^*)$}?}\bigskip\pause - -\normalsize -\begin{center} -\begin{tabular}{llllll} - \bl{$[]$} & \bl{$a$} & \bl{$aa$} & \bl{$aaa$} & \bl{$aaaa$} & \ldots\\ - \bl{0} & \bl{1} & \bl{2} & \bl{3} & \bl{4} & \ldots -\end{tabular} -\end{center} + \Large\bf Are there more strings in \bf{$L(a^*)$} or + \bf{$L((a + b)^*)$}? \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%