# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1537860637 -3600
# Node ID 99d2bb1f145cbd34461c7469f3a672675b1d198c
# Parent  db5cb071644deaf85d1a5c06a418436a3d0df689
updated

diff -r db5cb071644d -r 99d2bb1f145c slides/slides01.pdf
Binary file slides/slides01.pdf has changed
diff -r db5cb071644d -r 99d2bb1f145c slides/slides01.tex
--- a/slides/slides01.tex	Tue Sep 25 00:27:06 2018 +0100
+++ b/slides/slides01.tex	Tue Sep 25 08:30:37 2018 +0100
@@ -51,7 +51,7 @@
 \begin{frame}[t]
 \frametitle{Why Study Compilers?}
 
-John Regehr {\small(LLVM compiler hacker)}\smallskip\\
+John Regehr {\small(Univ.~Utah, LLVM compiler hacker)}\smallskip\\
 
 \begin{bubble}[10.5cm]
   \bf ``\ldots{}It’s effectively a perpetual
@@ -187,6 +187,29 @@
 \end{frame} 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Evil Regular Expressions}
+
+\begin{itemize}
+\item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\medskip
+\item Evil regular expressions\medskip
+\begin{itemize}
+\item \bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}
+\item \bl{$(a^*)^*\cdot b$}
+\item \bl{$([a$\,-\,$z]^+)^*$}
+\item \bl{$(a + a \cdot a)^*$}
+\item \bl{$(a + a^?)^*$}
+\end{itemize}
+
+\item sometimes also called \alert{catastrophic backtracking}
+\item this is a problem for \alert{N}etwork \alert{I}ntrusion
+  \alert{D}etection systems, StackExchange, Atom editor
+\item \url{https://vimeo.com/112065252}  
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
@@ -199,9 +222,12 @@
                       very thick,draw=black!50,minimum height=18mm, minimum width=20mm,
                       top color=white,bottom color=black!20}]
 
-  \node at (3.05, 1.8) {\Large\bf Write a compiler};
+  \node at (3.05, 1.8) {\Large\bf write a compiler};
 
-  \node (0) at (-2.3,0) {}; 
+  \node (0) at (-2.3,0) {};  
+  \node [above=5mm of 0]
+  {\makebox[0mm]{\footnotesize
+      \begin{tabular}{@{}l@{}}input\\[-1mm]program\end{tabular}}}; 
   
   \node (A) at (0,0)  [node] {};
   \node [below right] at (A.north west) {lexer};
@@ -212,7 +238,10 @@
   \node (C) at (6,0)  [node] {};
   \node [below right] at (C.north west) {\mbox{}\hspace{-1mm}code gen};
 
-  \node (1) at (8.4,0) {}; 
+  \node (1) at (8.4,0) {};
+  \node [above=5mm of 1]
+  {\makebox[0mm]{\footnotesize
+      \begin{tabular}{@{}r@{}}binary\\[-1mm]code\end{tabular}}};
 
   \draw [->,line width=4mm] (0) -- (A); 
   \draw [->,line width=4mm] (A) -- (B); 
@@ -357,7 +386,7 @@
 \frametitle{Familiar Regular Expr.}
 \small
 \begin{center}
-\texttt{[a-z0-9\_.-]+ @ [a-z0-9.-]+ . [a-z.]\{2,6\}}
+\texttt{[a-z0-9\_$\backslash{}$.-]+ @ [a-z0-9$\backslash{}$.-]+ . [a-z$\backslash{}$.]\{2,6\}}
 \end{center}\smallskip
 
 \begin{center}
@@ -370,7 +399,7 @@
 \pcode{[...]} & matches any single character inside the brackets\\
 \pcode{[^...]} & matches any single character not inside the 
 brackets\\
-\pcode{a-zA-Z} & character ranges\\
+\pcode{a-z A-Z} & character ranges\\
 \pcode{\\d} & matches digits; equivalent to \pcode{[0-9]}\\
 \pcode{.} & matches every character except newline\\
 \pcode{(re)}	& groups regular expressions and remembers 
@@ -387,8 +416,8 @@
 \frametitle{Today}
 
 \begin{itemize}
-\item While the ultimate goal is to implement a small compiler 
-(a really small one for the JVM)\ldots\bigskip
+\item While the ultimate goal is to implement a small compiler for the JVM
+  \ldots\bigskip
 \end{itemize}
 
 Let's start with: