% Chapter 1

\chapter{Introduction} % Main chapter title

\label{Introduction} % For referencing the chapter elsewhere, use \ref{Chapter1} 

%----------------------------------------------------------------------------------------

% Define some commands to keep the formatting separated from the content 

\newcommand{\keyword}[1]{\textbf{#1}}

\newcommand{\tabhead}[1]{\textbf{#1}}

\newcommand{\code}[1]{\texttt{#1}}

\newcommand{\file}[1]{\texttt{\bfseries#1}}

\newcommand{\option}[1]{\texttt{\itshape#1}}

%boxes

\newcommand*{\mybox}[1]{\framebox{\strut #1}}

%\newcommand{\sflataux}[1]{\textit{sflat}\_\textit{aux} \, #1}

\newcommand\sflat[1]{\llparenthesis #1 \rrparenthesis }

\newcommand{\ASEQ}[3]{\textit{ASEQ}_{#1} \, #2 \, #3}

\newcommand{\bderssimp}[2]{#1 \backslash_{bsimp} #2}

\newcommand{\rderssimp}[2]{#1 \backslash_{rsimp} #2}

\newcommand{\bders}[2]{#1 \backslash #2}

\newcommand{\bsimp}[1]{\textit{bsimp}(#1)}

\newcommand{\rsimp}[1]{\textit{rsimp}(#1)}

\newcommand{\sflataux}[1]{\llparenthesis #1 \rrparenthesis'}

\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}%

\newcommand{\denote}{\stackrel{\mbox{\scriptsize denote}}{=}}%

\newcommand{\ZERO}{\mbox{\bf 0}}

\newcommand{\ONE}{\mbox{\bf 1}}

\newcommand{\AALTS}[2]{\oplus {\scriptstyle #1}\, #2}

\newcommand{\rdistinct}[2]{\textit{distinct} \; \textit{#1} \; #2}

\newcommand\hflat[1]{\llparenthesis  #1 \rrparenthesis_*}

\newcommand\hflataux[1]{\llparenthesis #1 \rrparenthesis_*'}

\newcommand\createdByStar[1]{\textit{createdByStar}(#1)}

\newcommand\myequiv{\mathrel{\stackrel{\makebox[0pt]{\mbox{\normalfont\tiny equiv}}}{=}}}

\def\Some{\textit{Some}}

\def\None{\textit{None}}

\def\code{\textit{code}}

\def\decode{\textit{decode}}

\def\internalise{\textit{internalise}}

\def\lexer{\mathit{lexer}}

\def\mkeps{\textit{mkeps}}

\newcommand{\rder}[2]{#2 \backslash #1}

\def\AZERO{\textit{AZERO}}

\def\AONE{\textit{AONE}}

\def\ACHAR{\textit{ACHAR}}

\def\fuse{\textit{fuse}}

\def\bder{\textit{bder}}

\def\POSIX{\textit{POSIX}}

\def\ALTS{\textit{ALTS}}

\def\ASTAR{\textit{ASTAR}}

\def\DFA{\textit{DFA}}

\def\NFA{\textit{NFA}}

\def\bmkeps{\textit{bmkeps}}

\def\retrieve{\textit{retrieve}}

\def\blexer{\textit{blexer}}

\def\flex{\textit{flex}}

\def\inj{\mathit{inj}}

\def\Empty{\mathit{Empty}}

\def\Left{\mathit{Left}}

\def\Right{\mathit{Right}}

\def\Stars{\mathit{Stars}}

\def\Char{\mathit{Char}}

\def\Seq{\mathit{Seq}}

\def\Der{\textit{Der}}

\def\Ders{\textit{Ders}}

\def\nullable{\mathit{nullable}}

\def\Z{\mathit{Z}}

\def\S{\mathit{S}}

\def\rup{r^\uparrow}

%\def\bderssimp{\mathit{bders}\_\mathit{simp}}

\def\distinctWith{\textit{distinctWith}}

\def\lf{\textit{lf}}

\def\PD{\textit{PD}}

\def\suffix{\textit{Suffix}}

\def\size{\mathit{size}}

\def\rexp{\mathbf{rexp}}

\def\simp{\mathit{simp}}

\def\simpALTs{\mathit{simp}\_\mathit{ALTs}}

\def\map{\mathit{map}}

\def\distinct{\mathit{distinct}}

\def\blexersimp{\mathit{blexer}\_\mathit{simp}}

\def\map{\textit{map}}

%\def\vsuf{\textit{vsuf}}

%\def\sflataux{\textit{sflat}\_\textit{aux}}

\def\rrexp{\textit{rrexp}}

\newcommand\rnullable[1]{\textit{rnullable}(#1)}

\newcommand\rsize[1]{\llbracket #1 \rrbracket_r}

\newcommand\asize[1]{\llbracket #1 \rrbracket}

\newcommand\rerase[1]{ (#1)\downarrow_r}

\newcommand\ChristianComment[1]{\textcolor{blue}{#1}\\}

\def\erase{\textit{erase}}

\def\STAR{\textit{STAR}}

\def\flts{\textit{flts}}

\def\RZERO{\mathbf{0}_r }

\def\RONE{\mathbf{1}_r}

\newcommand\RCHAR[1]{\mathbf{#1}_r}

\newcommand\RSEQ[2]{#1 \cdot #2}

\newcommand\RALTS[1]{\oplus #1}

\newcommand\RSTAR[1]{#1^*}

\newcommand\vsuf[2]{\textit{vsuf} \;#1\;#2}

\pgfplotsset{

    myplotstyle/.style={

    legend style={draw=none, font=\small},

    legend cell align=left,

    legend pos=north east,

    ylabel style={align=center, font=\bfseries\boldmath},

    xlabel style={align=center, font=\bfseries\boldmath},

    x tick label style={font=\bfseries\boldmath},

    y tick label style={font=\bfseries\boldmath},

    scaled ticks=true,

    every axis plot/.append style={thick},

    },

}

%----------------------------------------------------------------------------------------

%This part is about regular expressions, Brzozowski derivatives,

%and a bit-coded lexing algorithm with proven correctness and time bounds.

%TODO: look up snort rules to use here--give readers idea of what regexes look like

\begin{figure}

\centering

\begin{tabular}{@{}c@{\hspace{0mm}}c@{\hspace{0mm}}c@{}}

\begin{tikzpicture}

\begin{axis}[

    xlabel={$n$},

    x label style={at={(1.05,-0.05)}},

    ylabel={time in secs},

    enlargelimits=false,

    xtick={0,5,...,30},

    xmax=33,

    ymax=35,

    ytick={0,5,...,30},

    scaled ticks=false,

    axis lines=left,

    width=5cm,

    height=4cm, 

    legend entries={JavaScript},  

    legend pos=north west,

    legend cell align=left]

\addplot[red,mark=*, mark options={fill=white}] table {re-js.data};

\end{axis}

\end{tikzpicture}

  &

\begin{tikzpicture}

\begin{axis}[

    xlabel={$n$},

    x label style={at={(1.05,-0.05)}},

    %ylabel={time in secs},

    enlargelimits=false,

    xtick={0,5,...,30},

    xmax=33,

    ymax=35,

    ytick={0,5,...,30},

    scaled ticks=false,

    axis lines=left,

    width=5cm,

    height=4cm, 

    legend entries={Python},  

    legend pos=north west,

    legend cell align=left]

\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};

\end{axis}

\end{tikzpicture}

  &

\begin{tikzpicture}

\begin{axis}[

    xlabel={$n$},

    x label style={at={(1.05,-0.05)}},

    %ylabel={time in secs},

    enlargelimits=false,

    xtick={0,5,...,30},

    xmax=33,

    ymax=35,

    ytick={0,5,...,30},

    scaled ticks=false,

    axis lines=left,

    width=5cm,

    height=4cm, 

    legend entries={Java 8},  

    legend pos=north west,

    legend cell align=left]

\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};

\end{axis}

\end{tikzpicture}\\

\multicolumn{3}{c}{Graphs: Runtime for matching $(a^*)^*\,b$ with strings 

           of the form $\underbrace{aa..a}_{n}$.}

\end{tabular}    

\caption{aStarStarb} \label{fig:aStarStarb}

\end{figure}

Regular expressions are widely used in computer science: 

be it in text-editors \parencite{atomEditor} with syntax highlighting and auto-completion;

command-line tools like $\mathit{grep}$ that facilitate easy 

text-processing; network intrusion

detection systems that reject suspicious traffic; or compiler

front ends--the majority of the solutions to these tasks 

involve lexing with regular 

expressions.

Given its usefulness and ubiquity, one would imagine that

modern regular expression matching implementations

are mature and fully studied.

Indeed, in a popular programming language' regex engine, 

supplying it with regular expressions and strings, one can

get rich matching information in a very short time.

Some network intrusion detection systems

use regex engines that are able to process 

megabytes or even gigabytes of data per second \parencite{Turo_ov__2020}.

Unfortunately, this is not the case for $\mathbf{all}$ inputs.

%TODO: get source for SNORT/BRO's regex matching engine/speed

Take $(a^*)^*\,b$ and ask whether

strings of the form $aa..a$ match this regular

expression. Obviously this is not the case---the expected $b$ in the last

position is missing. One would expect that modern regular expression

matching engines can find this out very quickly. Alas, if one tries

this example in JavaScript, Python or Java 8, even with strings of a small

length, say around 30 $a$'s, one discovers that 

this decision takes crazy time to finish given the simplicity of the problem.

This is clearly exponential behaviour, and 

is triggered by some relatively simple regex patterns, as the graphs

 in \ref{fig:aStarStarb} show.

\ChristianComment{Superlinear I just leave out the explanation 

which I find once used would distract the flow. Plus if i just say exponential

here the 2016 event in StackExchange was not exponential, but just quardratic so would be 

in accurate}

This superlinear blowup in regular expression engines

had repeatedly caused grief in real life.

For example, on 20 July 2016 one evil

regular expression brought the webpage

\href{http://stackexchange.com}{Stack Exchange} to its

knees.\footnote{\url{https://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016}(Last accessed in 2019)}

In this instance, a regular expression intended to just trim white

spaces from the beginning and the end of a line actually consumed

massive amounts of CPU resources---causing web servers to grind to a

halt. In this example, the time needed to process

the string was $O(n^2)$ with respect to the string length. This

quadratic overhead was enough for the homepage of Stack Exchange to

respond so slowly that the load balancer assumed a $\mathit{DoS}$ 

attack and therefore stopped the servers from responding to any

requests. This made the whole site become unavailable. 

A more recent example is a global outage of all Cloudflare servers on 2 July

2019. A poorly written regular expression exhibited exponential

behaviour and exhausted CPUs that serve HTTP traffic. Although the outage

had several causes, at the heart was a regular expression that

was used to monitor network

traffic.\footnote{\url{https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/}(Last accessed in 2022)}

%TODO: data points for some new versions of languages

These problems with regular expressions 

are not isolated events that happen

very occasionally, but actually widespread.

They occur so often that they get a 

name--Regular-Expression-Denial-Of-Service (ReDoS)

attack.

\citeauthor{Davis18} detected more

than 1000 super-linear (SL) regular expressions

in Node.js, Python core libraries, and npm and pypi. 

They therefore concluded that evil regular expressions

are problems "more than a parlour trick", but one that

requires

more research attention.

But the problems are not limited to slowness on certain 

cases. 

Another thing about these libraries is that there

is no correctness guarantee.

In some cases, they either fail to generate a lexing result when there exists a match,

or give results that are inconsistent with the $\POSIX$ standard.

A concrete example would be 

the regex

\begin{verbatim}

(aba|ab|a)*

\end{verbatim}

and the string

\begin{verbatim}

ababa

\end{verbatim}

The correct $\POSIX$ match for the above would be 

with the entire string $ababa$, 

split into two Kleene star iterations, $[ab] [aba]$ at positions

$[0, 2), [2, 5)$

respectively.

But trying this out in regex101\parencite{regex101}

with different language engines would yield 

the same two fragmented matches: $[aba]$ at $[0, 3)$

and $a$ at $[4, 5)$.

Kuklewicz\parencite{KuklewiczHaskell} commented that most regex libraries are not

correctly implementing the POSIX (maximum-munch)

rule of regular expression matching.

As Grathwohl\parencite{grathwohl2014crash} commented,

\begin{center}

	``The POSIX strategy is more complicated than the greedy because of the dependence on information about the length of matched strings in the various subexpressions.''

\end{center}

To summarise the above, regular expressions are important.

They are popular and programming languages' library functions

for them are very fast on non-catastrophic cases.

But there are problems with current practical implementations.

First thing is that the running time might blow up.

The second problem is that they might be error-prone on certain

cases that are very easily spotted by a human.

In the next part of the chapter, we will look into reasons why 

certain regex engines are running horribly slow on the "catastrophic"

cases and propose a solution that addresses both of these problems

based on Brzozowski and Sulzmann and Lu's work.

 \section{Why are current regex engines slow?}

%find literature/find out for yourself that REGEX->DFA on basic regexes

%does not blow up the size

Shouldn't regular expression matching be linear?

How can one explain the super-linear behaviour of the 

regex matching engines we have?

The time cost of regex matching algorithms in general

involve two different phases, and different things can go differently wrong on 

these phases.

$\DFA$s usually have problems in the first (construction) phase

, whereas $\NFA$s usually run into trouble

on the second phase.

\subsection{Different Phases of a Matching/Lexing Algorithm}

Most lexing algorithms can be roughly divided into 

two phases during its run.

The first phase is the "construction" phase,

in which the algorithm builds some  

suitable data structure from the input regex $r$, so that

it can be easily operated on later.

We denote

the time cost for such a phase by $P_1(r)$.

The second phase is the lexing phase, when the input string 

$s$ is read and the data structure

representing that regex $r$ is being operated on. 

We represent the time

it takes by $P_2(r, s)$.\\

For $\mathit{DFA}$,

we have $P_2(r, s) = O( |s| )$,

because we take at most $|s|$ steps, 

and each step takes

at most one transition--

a deterministic-finite-automata

by definition has at most one state active and at most one

transition upon receiving an input symbol.

But unfortunately in the  worst case

$P_1(r) = O(exp^{|r|})$. An example will be given later. 

For $\mathit{NFA}$s, we have $P_1(r) = O(|r|)$ if we do not unfold 

expressions like $r^n$ into $\underbrace{r \cdots r}_{\text{n copies of r}}$.

The $P_2(r, s)$ is bounded by $|r|\cdot|s|$, if we do not backtrack.

On the other hand, if backtracking is used, the worst-case time bound bloats

to $|r| * 2^|s|$.

%on the input

%And when calculating the time complexity of the matching algorithm,

%we are assuming that each input reading step requires constant time.

%which translates to that the number of 

%states active and transitions taken each time is bounded by a

%constant $C$.

%But modern  regex libraries in popular language engines

% often want to support much richer constructs than just

% sequences and Kleene stars,

%such as negation, intersection, 

%bounded repetitions and back-references.

%And de-sugaring these "extended" regular expressions 

%into basic ones might bloat the size exponentially.

%TODO: more reference for exponential size blowup on desugaring. 

\subsection{Why $\mathit{DFA}s$ can be slow in the first phase}

The good things about $\mathit{DFA}$s is that once

generated, they are fast and stable, unlike

backtracking algorithms. 

However, they do not scale well with bounded repetitions.

\subsubsection{Problems with Bounded Repetitions}

Bounded repetitions, usually written in the form

$r^{\{c\}}$ (where $c$ is a constant natural number),

denotes a regular expression accepting strings

that can be divided into $c$ substrings, where each 

substring is in $r$. 

For the regular expression $(a|b)^*a(a|b)^{\{2\}}$,

an $\mathit{NFA}$ describing it would look like:

\begin{center}

\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto] 

   \node[state,initial] (q_0)   {$q_0$}; 

   \node[state, red] (q_1) [right=of q_0] {$q_1$}; 

   \node[state, red] (q_2) [right=of q_1] {$q_2$}; 

   \node[state, accepting, red](q_3) [right=of q_2] {$q_3$};

    \path[->] 

    (q_0) edge  node {a} (q_1)

    	  edge [loop below] node {a,b} ()

    (q_1) edge  node  {a,b} (q_2)

    (q_2) edge  node  {a,b} (q_3);

\end{tikzpicture}

\end{center}

The red states are "countdown states" which counts down 

the number of characters needed in addition to the current

string to make a successful match.

For example, state $q_1$ indicates a match that has

gone past the $(a|b)^*$ part of $(a|b)^*a(a|b)^{\{2\}}$,

and just consumed the "delimiter" $a$ in the middle, and 

need to match 2 more iterations of $(a|b)$ to complete.

State $q_2$ on the other hand, can be viewed as a state

after $q_1$ has consumed 1 character, and just waits

for 1 more character to complete.

$q_3$ is the last state, requiring 0 more character and is accepting.

Depending on the suffix of the

input string up to the current read location,

the states $q_1$ and $q_2$, $q_3$

may or may

not be active, independent from each other.

A $\mathit{DFA}$ for such an $\mathit{NFA}$ would

contain at least $2^3$ non-equivalent states that cannot be merged, 

because the subset construction during determinisation will generate

all the elements in the power set $\mathit{Pow}\{q_1, q_2, q_3\}$.

Generalizing this to regular expressions with larger

bounded repetitions number, we have that

regexes shaped like $r^*ar^{\{n\}}$ when converted to $\mathit{DFA}$s

would require at least $2^{n+1}$ states, if $r$ contains

more than 1 string.

This is to represent all different 

scenarios which "countdown" states are active.

For those regexes, tools that uses $\DFA$s will get

out of memory errors.

\subsubsection{Tools that uses $\mathit{DFA}$s}

%TODO:more tools that use DFAs?

$\mathit{LEX}$ and $\mathit{JFLEX}$ are tools

in $C$ and $\mathit{JAVA}$ that generates $\mathit{DFA}$-based

lexers. The user provides a set of regular expressions

and configurations to such lexer generators, and then 

gets an output program encoding a minimized $\mathit{DFA}$

that can be compiled and run. 

When given the above countdown regular expression,

a small number $n$ would result in a determinised automata

with millions of states.

For this reason, regex libraries that support 

bounded repetitions often choose to use the $\mathit{NFA}$ 

approach.

\subsection{Why $\mathit{NFA}$s can be slow in the second phase}

When one constructs an $\NFA$ out of a regular expression

there is often very little to be done in the first phase, one simply 

construct the $\NFA$ states based on the structure of the input regular expression.

In the lexing phase, one can simulate the $\mathit{NFA}$ running in two ways:

one by keeping track of all active states after consuming 

a character, and update that set of states iteratively.

This can be viewed as a breadth-first-search of the $\mathit{NFA}$

for a path terminating

at an accepting state.

Languages like $\mathit{Go}$ and $\mathit{Rust}$ use this

type of $\mathit{NFA}$ simulation and guarantees a linear runtime

in terms of input string length.

%TODO:try out these lexers

The other way to use $\mathit{NFA}$ for matching is choosing  

a single transition each time, keeping all the other options in 

a queue or stack, and backtracking if that choice eventually 

fails. This method, often called a  "depth-first-search", 

is efficient in a lot of cases, but could end up

with exponential run time.\\

%TODO:COMPARE java python lexer speed with Rust and Go

The reason behind backtracking algorithms in languages like

Java and Python is that they support back-references.

\subsubsection{Back References}

If we have a regular expression like this (the sequence

operator is omitted for brevity):

\begin{center}