% 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_{bsimps} #2}

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

\def\derssimp{\textit{ders}\_\textit{simp}}

\def\rders{\textit{rders}}

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

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

\def\bsimps{\textit{bsimp}}

\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{rdistinct} \;\; #1 \;\; #2}

\def\rdistincts{\textit{rdistinct}}

\def\rDistinct{\textit{rdistinct}}

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

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

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

\def\cbn{\textit{createdByNtimes}}

\def\hpa{\textit{highestPowerAux}}

\def\hpower{\textit{highestPower}}

\def\ntset{\textit{ntset}}

\def\optermsimp{\textit{optermsimp}}

\def\optermOsimp{\textit{optermOsimp}}

\def\optermosimp{\textit{optermosimp}}

\def\opterm{\textit{opterm}}

\def\nString{\textit{nonemptyString}}

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

\def\SEQ{\textit{SEQ}}

\def\SEQs{\textit{SEQs}}

\def\case{\textit{case}}

\def\sequal{\stackrel{\mbox{\scriptsize rsimp}}{=}}

\def\rsimpalts{\textit{rsimp}_{ALTS}}

\def\good{\textit{good}}

\def\btrue{\textit{true}}

\def\bfalse{\textit{false}}

\def\bnullable{\textit{bnullable}}

\def\bnullables{\textit{bnullables}}

\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_r #1}

\def\rerases{\textit{rerase}}

\def\nonnested{\textit{nonnested}}

\def\AZERO{\textit{AZERO}}

\def\sizeNregex{\textit{sizeNregex}}

\def\AONE{\textit{AONE}}

\def\ACHAR{\textit{ACHAR}}

\def\simpsulz{\textit{simp}_{Sulz}}

\def\scfrewrites{\stackrel{*}{\rightsquigarrow_{scf}}}

\def\frewrite{\rightsquigarrow_f}

\def\hrewrite{\rightsquigarrow_h}

\def\grewrite{\rightsquigarrow_g}

\def\frewrites{\stackrel{*}{\rightsquigarrow_f}}

\def\hrewrites{\stackrel{*}{\rightsquigarrow_h}}

\def\grewrites{\stackrel{*}{\rightsquigarrow_g}}

\def\fuse{\textit{fuse}}

\def\bder{\textit{bder}}

\def\der{\textit{der}}

\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\bmkepss{\textit{bmkepss}}

\def\retrieve{\textit{retrieve}}

\def\blexer{\textit{blexer}}

\def\flex{\textit{flex}}

\def\inj{\textit{inj}}

\def\Empty{\textit{Empty}}

\def\Left{\textit{Left}}

\def\Right{\textit{Right}}

\def\Stars{\textit{Stars}}

\def\Char{\textit{Char}}

\def\Seq{\textit{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\distinctBy{\textit{distinctBy}}

\def\starupdate{\textit{starUpdate}}

\def\starupdates{\textit{starUpdates}}

\def\nupdate{\textit{nupdate}}

\def\nupdates{\textit{nupdates}}

\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\blexerStrong{\textit{blexerStrong}}

\def\bsimpStrong{\textit{bsimpStrong}}

\def\bdersStrongs{\textit{bdersStrong}}

\newcommand{\bdersStrong}[2]{#1 \backslash_{bsimpStrongs} #2}

\def\map{\textit{map}}

\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\rflts{\textit{rflts}}

\def\rrewrite{\textit{rrewrite}}

\def\bsimpalts{\textit{bsimp}_{ALTS}}

\def\bsimpaseq{\textit{bsimp}_{ASEQ}}

\def\rsimlalts{\textit{rsimp}_{ALTs}}

\def\rsimpseq{\textit{rsimp}_{SEQ}}

\def\erase{\textit{erase}}

\def\STAR{\textit{STAR}}

\def\flts{\textit{flts}}

\def\zeroable{\textit{zeroable}}

\def\nub{\textit{nub}}

\def\filter{\textit{filter}}

%\def\not{\textit{not}}

\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]{\sum #1}

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

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

\lstdefinestyle{myScalastyle}{

  frame=tb,

  language=scala,

  aboveskip=3mm,

  belowskip=3mm,

  showstringspaces=false,

  columns=flexible,

  basicstyle={\small\ttfamily},

  numbers=none,

  numberstyle=\tiny\color{gray},

  keywordstyle=\color{blue},

  commentstyle=\color{dkgreen},

  stringstyle=\color{mauve},

  frame=single,

  breaklines=true,

  breakatwhitespace=true,

  tabsize=3,

}

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

%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

Regular expressions, since their inception in the 1940s, 

have been subject to extensive study and implementation. 

Their primary application lies in lexing, 

a process whereby an unstructured input string is disassembled into a tree of tokens

with their guidance.

This is often used to match strings that comprises of numerous fields, 

where certain fields may recur or be omitted. 

For example, the regular expression for recognising email addresses is

\begin{center}

\verb|^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$|.

\end{center}

Using this, regular expression matchers and lexers are able to extract 

of software systems such as compilers, IDEs, and firewalls.

The study of regular expressions is ongoing due to an

issue known as catastrophic backtracking. 

This phenomenon refers to scenarios in which the regular expression 

matching or lexing engine exhibits a disproportionately long 

runtime despite the simplicity of the input and expression.

The origin of catastrophic backtracking is rooted in the 

ambiguities of lexing. 

In the process of matching a multi-character string with 

a regular expression that encompasses several sub-expressions, 

different positions can be designated to mark 

the boundaries of corresponding substrings of the sub-expressions. 

For instance, in matching the string $aaa$ with the 

regular expression $(a+aa)^*$, the divide between 

the initial match and the subsequent iteration could either be 

set between the first and second characters ($a | aa$) or between the second and third characters ($aa | a$). As both the length of the input string and the structural complexity of the regular expression increase, the number of potential delimiter combinations can grow exponentially, leading to a corresponding increase in complexity for algorithms that do not optimally navigate these possibilities.

Catastrophic backtracking facilitates a category of computationally inexpensive attacks known as Regular Expression Denial of Service (ReDoS) attacks. Here, an attacker merely dispatches a small attack string to a server, provoking high-complexity behaviours in the server's regular expression engine. Such attacks, whether intentional or accidental, have led to the failure of real-world systems (additional details can be found in the practical overview section in chapter \ref{Introduction}).

Various disambiguation strategies are employed to select sub-matches, notably including Greedy and POSIX strategies. POSIX, the strategy most widely adopted in practice, invariably opts for the longest possible sub-match. Kuklewicz \cite{KuklewiczHaskell}, for instance, offers a descriptive definition of the POSIX rule in section 1, last paragraph:

%Regular expressions 

%have been extensively studied and

%implemented since their invention in 1940s.

%It is primarily used in lexing, where an unstructured input string is broken

%down into a tree of tokens.

%That tree's construction is guided by the shape of the regular expression.

%This is particularly useful in expressing the shape of a string

%with many fields, where certain fields might repeat or be omitted.

%Regular expression matchers and Lexers allow us to 

%identify and delimit different subsections of a string and potentially 

%extract information from inputs, making them

%an indispensible component in modern software systems' text processing tasks

%such as compilers, IDEs, and firewalls.

%Research on them is far from over due to the well-known issue called catastrophic-backtracking,

%which means the regular expression matching or lexing engine takes an unproportional time to run 

%despite the input and the expression being relatively simple.

%

%Catastrophic backtracking stems from the ambiguities of lexing: 

%when matching a multiple-character string with a regular 

%exression that includes serveral sub-expressions, there might be different positions to set 

%the border between sub-expressions' corresponding sub-strings.

%For example, matching the string $aaa$ against the regular expression

%$(a+aa)^*$, the border between the initial match and the second iteration

%could be between the first and second character ($a | aa$) 

%or between the second and third character ($aa | a$).

%As the size of the input string and the structural complexity 

%of the regular expression increase,

%the number of different combinations of delimiters can grow exponentially, and

%algorithms that explore these possibilities unwisely will also see an exponential complexity.

%

%Catastrophic backtracking allow a class of computationally inexpensive attacks called

%Regular expression Denial of Service attacks (ReDoS), in which the hacker 

%simply sends out a small attack string to a server, 

%triggering high-complexity behaviours in its regular expression engine. 

%These attacks, be it deliberate or not, have caused real-world systems to go down (see more 

%details of this in the practical overview section in chapter \ref{Introduction}).

%There are different disambiguation strategies to select sub-matches, most notably Greedy and POSIX.

%The widely adopted strategy in practice is POSIX, which always go for the longest sub-match possible.

%There have been prose definitions like the following

%by Kuklewicz \cite{KuklewiczHaskell}: 

%described the POSIX rule as (section 1, last paragraph):

\begin{quote}

	\begin{itemize}

		\item

regular expressions (REs) take the leftmost starting match, and the longest match starting there

earlier subpatterns have leftmost-longest priority over later subpatterns\\

\item

higher-level subpatterns have leftmost-longest priority over their component subpatterns\\

\item

REs have right associative concatenation which can be changed with parenthesis\\

\item

parenthesized subexpressions return the match from their last usage\\

\item

text of component subexpressions must be contained in the text of the 

higher-level subexpressions\\

\item

if "p" and "q" can never match the same text then "p|q" and "q|p" are equivalent, up to trivial renumbering of captured subexpressions\\

\item

if "p" in "p*" is used to capture non-empty text then additional repetitions of "p" will not capture an empty string\\

\end{itemize}

\end{quote}