78 

   218 

   219 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   220 \mode<presentation>{

   221 \begin{frame}[c]

   222 

   223 ``I hate coding. I do not want to look at code.''

   224 

   225 \end{frame}}

   226 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   227 

   228 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   229 \mode<presentation>{

   230 \begin{frame}[c]

   231 

   232 ``I am appalled. You do not show code anymore.''

   233 

   234 \end{frame}}

   235 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   236 

   237 

   238 

   239 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   240 \mode<presentation>{

   241 \begin{frame}[c]

   242 \frametitle{\begin{tabular}{c}ReDoS\end{tabular}}

   243 

   244 \begin{itemize}

   245 \item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice\bigskip

   246 \item ``Regular Expressions Will Stab You in the Back''\bigskip

   247 \item Evil regular expressions\medskip

   248 \begin{itemize}

   249 \item \bl{$(a?\{n\})a\{n\}$}

   250 \item \bl{$(a^+)^+$}

   251 \item \bl{$([a-zA-Z]^+)^*$}

   252 \item \bl{$(a + aa)^+$}

   253 \item \bl{$(a + a?)^+$}

   254 \end{itemize}

   255 \end{itemize}

   256 

   257 \end{frame}}

   258 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   259 

   260 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   261 \mode<presentation>{

   262 \begin{frame}[c]

   263 \frametitle{\begin{tabular}{c}Regexp Matching\end{tabular}}

   264 

   265 Given a regular expression

   266 

   267 \begin{enumerate}

   268 \item you might convert it into a DFA (subset construction)

   269 \item you might try all possible paths in an NFA via backtracking

   270 \item you might try all paths in an NFA in parallel

   271 \item you might try to convert the DFA ``lazily''

   272 \end{enumerate}\bigskip

   273 

   274 Often No~2 is implemented (sometimes there are even good reasons for doing this).

   275 

   276 \end{frame}}

   277 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   278 

   279 

   280 

   281 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   282 \mode<presentation>{

   283 \begin{frame}[c]

   284 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\})a\{n\}$} in Python\end{tabular}}

   285 

   286 \begin{tikzpicture}[y=.2cm, x=.3cm]

   287  	%axis

   288 	\draw (0,0) -- coordinate (x axis mid) (30,0);

   289     	\draw (0,0) -- coordinate (y axis mid) (0,30);

   290     	%ticks

   291     	\foreach \x in {0,5,...,30}

   292      		\draw (\x,1pt) -- (\x,-3pt)

   293 			node[anchor=north] {\x};

   294     	\foreach \y in {0,5,...,30}

   295      		\draw (1pt,\y) -- (-3pt,\y) 

   296      			node[anchor=east] {\y}; 

   297 	%labels      

   298 	\node[below=0.6cm] at (x axis mid) {\bl{a}s};

   299 	\node[rotate=90, left=1.2cm] at (y axis mid) {secs};

   300 

   301 	%plots

   302 	\draw[color=blue] plot[mark=*, mark options={fill=white}] 

   303 		file {re-python.data};

   304 	\only<2->{

   305 	\draw[color=red] plot[mark=triangle*, mark options={fill=white} ] 

   306 		file {re1.data};}

   307 	\only<3->{	 

   308          \draw[color=green] plot[mark=square*, mark options={fill=white} ] 

   309 		file {re2.data};}

   310     

   311 	%legend

   312 	\begin{scope}[shift={(4,20)}] 

   313 	\draw[color=blue] (0,0) -- 

   314 		plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) 

   315 		node[right]{\small Python};

   316 	\only<2->{\draw[yshift=\baselineskip, color=red] (0,0) -- 

   317 		plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0)

   318 		node[right]{\small Scala V1};}

   319 	\only<3->{	

   320 	 \draw[yshift=2\baselineskip, color=green] (0,0) -- 

   321 		plot[mark=square*, mark options={fill=white}] (0.25,0) -- (0.5,0)

   322 		node[right]{\small Scala V2 with simplifications};}

   323 	\end{scope}

   324 \end{tikzpicture}

   325 

   326 \end{frame}}

   327 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   328 

   329 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   330 \mode<presentation>{

   331 \begin{frame}[c]

   332 

   333 

   334 \begin{tikzpicture}[y=.7cm, x=.0009cm]

   335  	%axis

   336 	\draw (0,0) -- coordinate (x axis mid) (10000,0);

   337     	\draw (0,0) -- coordinate (y axis mid) (0,6);

   338     	%ticks

   339     	\foreach \x in {0,2000,...,10000}

   340      		\draw (\x,1pt) -- (\x,-3pt)

   341 			node[anchor=north] {\x};

   342     	\foreach \y in {0,1,...,6}

   343      		\draw (1pt,\y) -- (-3pt,\y) 

   344      			node[anchor=east] {\y}; 

   345 	%labels      

   346 	\node[below=0.6cm] at (x axis mid) {\bl{a}s};

   347 	\node[rotate=90, left=1.2cm] at (y axis mid) {secs};

   348 

   349 	%plots

   350 	\draw[color=blue] plot[mark=*, mark options={fill=white}] 

   351 		file {re-internal.data};

   352 	\only<2->{	 

   353          \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] 

   354 		file {re3.data};}

   355     

   356 	%legend

   357 	\begin{scope}[shift={(2000,4)}] 

   358 	\draw[color=blue] (0,0) -- 

   359 		plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) 

   360 		node[right]{\small Scala Internal};

   361         \only<2->{

   362 	\draw[yshift=\baselineskip, color=red] (0,0) -- 

   363 		plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0)

   364 		node[right]{\small Scala V3 with explicit $\_\{\_\}$};}

   365 	\end{scope}

   366 \end{tikzpicture}

   367 

   368 \end{frame}}

   369 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   370