102 In the handouts is a similar graph with \bl{$(a^*)^* \cdot b$} for Java. |
102 In the handouts is a similar graph with \bl{$(a^*)^* \cdot b$} for Java. |
103 |
103 |
104 \end{frame} |
104 \end{frame} |
105 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
105 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
106 |
106 |
|
107 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
108 \begin{frame}[c] |
|
109 \frametitle{Evil Regular Expressions} |
|
110 |
|
111 \begin{itemize} |
|
112 \item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\bigskip |
|
113 \item Evil regular expressions\medskip |
|
114 \begin{itemize} |
|
115 \item \bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$} |
|
116 \item \bl{$(a^*)^*$} |
|
117 \item \bl{$([a$\,-\,$z]^+)^*$} |
|
118 \item \bl{$(a + a \cdot a)^*$} |
|
119 \item \bl{$(a + a?)^*$} |
|
120 \end{itemize} |
|
121 |
|
122 \item sometimes also called \alert{catastrophic backtracking} |
|
123 \end{itemize} |
|
124 |
|
125 \end{frame} |
|
126 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
107 |
127 |
108 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
128 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
109 \begin{frame}[c] |
129 \begin{frame}[c] |
110 \frametitle{Languages} |
130 \frametitle{Languages} |
111 |
131 |
141 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
161 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
142 \begin{frame}[c] |
162 \begin{frame}[c] |
143 \frametitle{The Power Operation} |
163 \frametitle{The Power Operation} |
144 |
164 |
145 \begin{itemize} |
165 \begin{itemize} |
146 \item The \alert{\bf Power} of a language: |
166 \item The \alert{\textbf{\boldmath$n$th Power}} of a language: |
147 |
167 |
148 \begin{center} |
168 \begin{center} |
149 \begin{tabular}{lcl} |
169 \begin{tabular}{lcl} |
150 \bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ |
170 \bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ |
151 \bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$} |
171 \bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$} |
153 \end{center}\bigskip |
173 \end{center}\bigskip |
154 |
174 |
155 \item[] For example |
175 \item[] For example |
156 |
176 |
157 \begin{center} |
177 \begin{center} |
158 \begin{tabular}{lcl} |
178 \begin{tabular}{lcll} |
159 \bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$}\\ |
179 \bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(\{[]\})$}\\ |
160 \bl{$A^1$} & \bl{$=$} & \bl{$A$}\\ |
180 \bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(\{[]\})$}\\ |
161 \bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\ |
181 \bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\ |
162 \end{tabular} |
182 \end{tabular} |
163 \end{center} |
183 \end{center} |
164 |
184 |
165 \end{itemize} |
185 \end{itemize} |
242 sets of strings\\ |
262 sets of strings\\ |
243 \bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$} |
263 \bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$} |
244 \end{textblock} |
264 \end{textblock} |
245 |
265 |
246 \end{frame} |
266 \end{frame} |
247 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
267 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
248 |
|
249 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
250 \begin{frame}[c] |
|
251 \frametitle{\begin{tabular}{c}The Specification\\ of Matching\end{tabular}} |
|
252 |
|
253 \begin{bubble}[10cm] |
|
254 \large |
|
255 A regular expression \bl{$r$} matches a string~\bl{$s$} |
|
256 provided |
|
257 |
|
258 \begin{center} |
|
259 \bl{$s \in L(r)$}\\ |
|
260 \end{center} |
|
261 \end{bubble}\bigskip\bigskip |
|
262 |
|
263 \ldots and the point of the this lecture is |
|
264 to decide this problem as fast as possible |
|
265 (unlike Python, Ruby, Java etc) |
|
266 |
|
267 \end{frame} |
|
268 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
269 |
268 |
270 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
269 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
271 \begin{frame}[c] |
270 \begin{frame}[c] |
272 \frametitle{Semantic Derivative} |
271 \frametitle{Semantic Derivative} |
273 |
272 |
298 |
297 |
299 \end{itemize} |
298 \end{itemize} |
300 |
299 |
301 \end{frame} |
300 \end{frame} |
302 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
301 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
302 |
|
303 |
|
304 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
305 \begin{frame}[c] |
|
306 \frametitle{\begin{tabular}{c}The Specification\\ of Matching\end{tabular}} |
|
307 |
|
308 \begin{bubble}[10cm] |
|
309 \large |
|
310 A regular expression \bl{$r$} matches a string~\bl{$s$} |
|
311 provided |
|
312 |
|
313 \begin{center} |
|
314 \bl{$s \in L(r)$}\\ |
|
315 \end{center} |
|
316 \end{bubble}\bigskip\bigskip |
|
317 |
|
318 \ldots and the point of the this lecture is |
|
319 to decide this problem as fast as possible |
|
320 (unlike Python, Ruby, Java etc) |
|
321 |
|
322 \end{frame} |
|
323 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
324 |
303 |
325 |
304 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
326 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
305 \begin{frame}[t] |
327 \begin{frame}[t] |
306 \frametitle{Regular Expressions} |
328 \frametitle{Regular Expressions} |
307 |
329 |
395 \end{center} |
417 \end{center} |
396 |
418 |
397 \end{frame} |
419 \end{frame} |
398 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
420 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
399 |
421 |
400 %\newcommand{\YES}{\textcolor{gray}{yes}} |
|
401 %\newcommand{\NO}{\textcolor{gray}{no}} |
|
402 %\newcommand{\FORALLR}{\textcolor{gray}{$\forall$ r.}} |
|
403 |
|
404 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
405 \begin{frame}[c] |
|
406 \frametitle{\begin{tabular}{c}The Specification\\[-1mm] for Matching\end{tabular}} |
|
407 |
|
408 \large |
|
409 A regular expression \bl{$r$} matches a string \bl{$s$}\\ if and only if |
|
410 |
|
411 \begin{center} |
|
412 \bl{$s \in L(r)$}\\ |
|
413 \end{center} |
|
414 |
|
415 \end{frame} |
|
416 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
417 |
|
418 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
419 \begin{frame}[c] |
|
420 \frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$} and \bl{$(a^*)^* \cdot b$}} |
|
421 |
|
422 \begin{center}\footnotesize |
|
423 \begin{tabular}{@{}c@{\hspace{-2mm}}c@{}} |
|
424 \begin{tikzpicture} |
|
425 \begin{axis}[ |
|
426 xlabel={$n$}, |
|
427 x label style={at={(1.05,0.0)}}, |
|
428 ylabel={time in secs}, |
|
429 enlargelimits=false, |
|
430 xtick={0,5,...,30}, |
|
431 xmax=33, |
|
432 ymax=35, |
|
433 ytick={0,5,...,30}, |
|
434 scaled ticks=false, |
|
435 axis lines=left, |
|
436 width=5.5cm, |
|
437 height=4.5cm, |
|
438 legend entries={Python,Ruby}, |
|
439 legend pos=north west, |
|
440 legend cell align=left |
|
441 ] |
|
442 \addplot[blue,mark=*, mark options={fill=white}] |
|
443 table {re-python.data}; |
|
444 \addplot[brown,mark=pentagon*, mark options={fill=white}] |
|
445 table {re-ruby.data}; |
|
446 \end{axis} |
|
447 \end{tikzpicture} |
|
448 & |
|
449 \begin{tikzpicture} |
|
450 \begin{axis}[ |
|
451 xlabel={$n$}, |
|
452 x label style={at={(1.05,0.0)}}, |
|
453 ylabel={time in secs}, |
|
454 enlargelimits=false, |
|
455 xtick={0,5,...,30}, |
|
456 xmax=33, |
|
457 ymax=35, |
|
458 ytick={0,5,...,30}, |
|
459 scaled ticks=false, |
|
460 axis lines=left, |
|
461 width=5.5cm, |
|
462 height=4.5cm, |
|
463 legend entries={Java}, |
|
464 legend pos=north west, |
|
465 legend cell align=left] |
|
466 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; |
|
467 \end{axis} |
|
468 \end{tikzpicture} |
|
469 \end{tabular} |
|
470 \end{center} |
|
471 |
|
472 \end{frame} |
|
473 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
474 |
|
475 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
476 \begin{frame}[c] |
|
477 \frametitle{Evil Regular Expressions} |
|
478 |
|
479 \begin{itemize} |
|
480 \item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\bigskip |
|
481 \item Evil regular expressions\medskip |
|
482 \begin{itemize} |
|
483 \item \bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$} |
|
484 \item \bl{$(a^*)^*$} |
|
485 \item \bl{$([a$\,-\,$z]^+)^*$} |
|
486 \item \bl{$(a + a \cdot a)^*$} |
|
487 \item \bl{$(a + a?)^*$} |
|
488 \end{itemize} |
|
489 |
|
490 \item sometimes also called \alert{catastrophic backtracking} |
|
491 \end{itemize} |
|
492 |
|
493 \end{frame} |
|
494 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
495 |
422 |
496 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
423 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
497 \begin{frame}[t] |
424 \begin{frame}[t] |
498 \frametitle{A Matching Algorithm} |
425 \frametitle{A Matching Algorithm} |
499 |
426 |