lexing: comparison text/proposal.tex

equal deleted inserted replaced

-:06aa99b54423
+:fedc16924b76
+% !TEX program = pfdlatex
 \documentclass{article}
 \usepackage{url}
 \usepackage{color}\definecolor{darkblue}{rgb}{0,0,0.5}
 \usepackage[a4paper,colorlinks=true,linkcolor=darkblue,citecolor=darkblue,filecolor=darkblue,pagecolor=darkblue,urlcolor=darkblue]{hyperref}
 \usepackage{style}
-\usepackage{langs}
+%\usepackage{langs}
 \usepackage{tikz}
 \usepackage{pgf}
 \usepackage{pgfplots}
 \usepackage{stackengine}
 \addtolength{\oddsidemargin}{-6mm}
 \addtolength{\evensidemargin}{-6mm}
 \addtolength{\textwidth}{12mm}
 %% \usepackage{accents}
-\newcommand\barbelow[1]{\stackunder[1.2pt]{#1}{\raisebox{-4mm}{\boldmath$\uparrow$}}}
+\newcommand\barbelow[1]{\stackunbder[1.2pt]{#1}{\raisebox{-4mm}{\boldmath$\uparrow$}}}
 \begin{filecontents}{re-python2.data}
 1 0.033
 5 0.036
 10 0.034
 \begin{document}
 \section*{PPProposal: \\
 Fast Regular Expression Matching\\
-with Brzozowski Derivatives}
+with Brzozowski bderivatives}
 \subsubsection*{Summary}
 If you want to connect a computer directly to the Internet, it must be
 immediately \mbox{hardened} against outside attacks. The current
 counter-actions. One possible action could be to slow down the traffic
 from sites where repeated password-guesses originate. Well-known
 network intrusion prevention systems that use regular expressions for
 traffic analysis are Snort and Bro.
-Given the large
+Given the large volume of Internet traffic even the smallest servers
-volume of Internet traffic even the smallest servers can handle
+can handle nowadays, the regular expressions for traffic analysis have
-nowadays, the regular expressions for traffic analysis have become a
+become a real bottleneck.  This is not just a nuisance, but actually a
-real bottleneck.  This is not just a nuisance, but actually a security
+security vulnerability in itself: it can lead to denial-of-service
-vulnerability in itself: it can lead to denial-of-service attacks.
+attacks.  The proposed project aims to remove this bottleneck by using
-The proposed project aims to remove this bottleneck by using a little-known
+a little-known technique of building bderivatives of regular
-technique of building derivatives of regular expressions. These
+expressions. These derivatives have not yet been used in the area of
-derivatives have not yet been used in the area of network traffic
+network traffic analysis, but have the potential to solve some
-analysis, but have the potential to solve some tenacious problems with
+tenacious problems with existing approaches. The project will require
-existing approaches. The project will require theoretical work, but
+theoretical work, but also a practical implementation (a
-also a practical implementation (a proof-of-concept at least).  The
+proof-of-concept at least).  The work will build on earlier work by
-work will build on earlier work by Ausaf and Urban from King's College
+Ausaf and Urban from King's College London
-London \cite{AusafDyckhoffUrban2016}.
+\cite{AusafDyckhoffUrban2016}.
 \subsubsection*{Background}
 If every 10 minutes a thief turned up at your car and rattled
 \cite{snort,bro}.  Clearly, there are also other kinds of
 vulnerabilities hackers try to take advantage of---mainly programming
 mistakes that can be abused to gain access to a computer. This means
 server administrators have a suite of sometimes thousands of regular
 expressions, all prescribing some suspicious pattern for when a
-computer is under attack.
+computer is unbder attack.
-The underlying algorithmic problem is to decide whether a string in
+The unbderlying algorithmic problem is to decide whether a string in
 the logs matches the patterns determined by the regular
 expressions. Such decisions need to be done as fast as possible,
 otherwise the scanning programs would not be useful as a hardening
 technique for servers. The quest for speed with these decisions is
 presently a rather big challenge for the amount of traffic typical
 following two graphs:
 \begin{center}
 \begin{tabular}{@{}cc@{}}
 %\multicolumn{2}{c}{Graph: $(a^*)^*\cdot b$ and strings
-%           $\underbrace{a\ldots a}_{n}$}\smallskip\\
+%           $\unbderbrace{a\ldots a}_{n}$}\smallskip\\
 \begin{tikzpicture}
 \begin{axis}[
 xlabel={$n$},
 x label style={at={(1.05,0.0)}},
 ylabel={time in secs},
 These graphs show how long strings can be when using the rather simple
 regular expression $(a^*)^* \,b$ and the built-in regular expression
 matchers in the popular programming languages Python and Java (Version
 8 and Version 9). There are many more regular expressions that show
 the same behaviour.  On the left-hand side the graphs show that for a
-string consisting of just 28 $a\,$'s, Python and the older Java (which
+string consisting of just 28 $a\,$'s, Python and the olbder Java (which
 was the latest version of Java until September 2017) already need 30
 seconds to decide whether this string is matched or not. This is an
 abysmal result given that Python and Java are very popular programming
 languages. We already know that this problem can be decided much, much
 faster.  If these slow regular expression matchers would be employed
 has to send to the server a large enough string of a's. The newer
 version of Java is better---it can match strings of around 50,000
 $a\,$'s in 30 seconds---however this would still not be good enough
 for being a useful tool for network traffic analysis. What is
 interesting is that even a relatively simple-minded regular expression
-matcher based on Brzozowski derivatives can out-compete the regular
+matcher based on Brzozowski bderivatives can out-compete the regular
 expressions matchers in Java and Python on such catastrophic
 backtracking examples. This gain in speed is the motivation and
 starting point for the proposed project. \smallskip
 \subsection*{Research Plan}
 \end{tabular}
 \end{center}
 \noindent
 For practical purposes, however, regular expressions have been
-extended in various ways in order to make them even more powerful and
+extended in various ways in orbder to make them even more powerful and
 even more useful for applications. Some of the problems to do with
 catastrophic backtracking stem, unfortunately, from these extensions.
 The crux in this project is to not use automata for regular expression
-matching (the traditional technique), but to use derivatives of
+matching (the traditional technique), but to use bderivatives of
-regular expressions instead.  These derivatives were introduced by
+regular expressions instead.  These bderivatives were introduced by
 Brzozowski in 1964 \cite{Brzozowski1964}, but somehow had been lost
 ``in the sands of time'' \cite{Owens2009}. However, they recently have
 become again a ``hot'' research topic with numerous research papers
 appearing in the last five years. One reason for this interest is that
-Brzozowski derivatives straightforwardly extend to more general
+Brzozowski bderivatives straightforwardly extend to more general
 regular expression constructors, which cannot be easily treated with
 standard techniques. They can also be implemented with ease in any
-functional programming language: the definition for derivatives
+functional programming language: the definition for bderivatives
 consists of just two simple recursive functions shown in
 Figure~\ref{f}. Moreover, it can be easily shown (by a mathematical
 proof) that the resulting regular matcher is in fact always producing
 a correct answer. This is an area where Urban can provide a lot of
 expertise for this project: he is one of the main developers of the
 $\textit{nullable}(c)$     & $\dn$ & $\textit{false}$\\
 $\textit{nullable}(r_1 + r_2)$ & $\dn$ & $\textit{nullable}(r_1) \vee \textit{nullable}(r_2)$\\
 $\textit{nullable}(r_1 \cdot r_2)$ & $\dn$ & $\textit{nullable}(r_1) \wedge \textit{nullable}(r_2)$\\
 $\textit{nullable}(r^*)$ & $\dn$ & $\textit{true}$\medskip\\
-$\textit{der}\;c\;(\ZERO)$ & $\dn$ & $\ZERO$\\
+$\textit{bder}\;c\;(\ZERO)$ & $\dn$ & $\ZERO$\\
-$\textit{der}\;c\;(\ONE)$  & $\dn$ & $\ZERO$\\
+$\textit{bder}\;c\;(\ONE)$  & $\dn$ & $\ZERO$\\
-$\textit{der}\;c\;(d)$     & $\dn$ & $\textit{if}\; c = d\;\textit{then} \;\ONE \; \textit{else} \;\ZERO$\\
+$\textit{bder}\;c\;(d)$     & $\dn$ & $\textit{if}\; c = d\;\textit{then} \;\ONE \; \textit{else} \;\ZERO$\\
-$\textit{der}\;c\;(r_1 + r_2)$ & $\dn$ & $(\textit{der}\;c\;r_1) + (\textit{der}\;c\;r_2)$\\
+$\textit{bder}\;c\;(r_1 + r_2)$ & $\dn$ & $(\textit{bder}\;c\;r_1) + (\textit{bder}\;c\;r_2)$\\
-$\textit{der}\;c\;(r_1 \cdot r_2)$ & $\dn$ & $\textit{if}\;\textit{nullable}(r_1)$\\
+$\textit{bder}\;c\;(r_1 \cdot r_2)$ & $\dn$ & $\textit{if}\;\textit{nullable}(r_1)$\\
-& & $\textit{then}\;((\textit{der}\;c\;r_1)\cdot r_2) + (\textit{der}\;c\;r_2)$\\
+& & $\textit{then}\;((\textit{bder}\;c\;r_1)\cdot r_2) + (\textit{bder}\;c\;r_2)$\\
-& & $\textit{else}\;(\textit{der}\;c\;r_1)\cdot r_2$\\
+& & $\textit{else}\;(\textit{bder}\;c\;r_1)\cdot r_2$\\
-$\textit{der}\;c\;(r^*)$ & $\dn$ & $(\textit{der}\;c\;r)\cdot (r^*)$\\[-5mm]
+$\textit{bder}\;c\;(r^*)$ & $\dn$ & $(\textit{bder}\;c\;r)\cdot (r^*)$\\[-5mm]
 \end{tabular}
 \end{center}
-\caption{The complete definition of derivatives of regular expressions
+\caption{The complete definition of bderivatives of regular expressions
 \cite{Brzozowski1964}.
 This definition can be implemented with ease in functional programming languages and can be easily extended to regular expressions used in practice.
 The are more flexible for applications and easier to manipulate in
 mathematical proofs, than traditional techniques for regular expression
 matching.\medskip\label{f}}
 \end{figure}
-There are a number of avenues for research on Brzozowski derivatives.
+There are a number of avenues for research on Brzozowski bderivatives.
 One problem I like to immediately tackle in this project is how to
 handle \emph{back-references} in regular expressions. It is known that
-the inclusion of back-references causes the underlying algorithmic
+the inclusion of back-references causes the unbderlying algorithmic
 problem to become NP-hard \cite{Aho}, and is the main reason why
 regular expression matchers suffer from the catastrophic backtracking
 problem. However, the full generality of back-references are not
 needed in practical applications. The goal therefore is to sufficiently
 restrict the problem so that an efficient algorithm can be
 designed. There seem to be good indications that Brzozowski
-derivatives are useful for that.
+bderivatives are useful for that.
 Another problem is \emph{how} regular expressions match a string
 \cite{Sulzmann2014}. In this case the algorithm does not just give a
 yes/no answer about whether the regular expression matches the string,
 but also generates a value that encodes which part of the string is
 Much research has already gone into regular expressions, and one might
 think they have been studied and implemented to death. But this is far
 from the truth. In fact regular expressions have become a ``hot''
 research topic in recent years because of problems with the
 traditional methods (in applications such as network traffic
-analysis), but also because the technique of derivatives of regular
+analysis), but also because the technique of bderivatives of regular
-expression has been re-discovered. These derivatives provide an
+expression has been re-discovered. These bderivatives provide an
 alternative approach to regular expression matching. Their potential
 lies in the fact that they are more flexible in implementations and
 much easier to manipulate in mathematical proofs. Therefore I like to
 research them in this project.\medskip
 \small
 \bibliographystyle{plain}
 \renewcommand{\refname}{References\\[-7mm]\mbox{}}
 \bibliography{proposal}
+\newpage
+\begin{center}\small
+\begin{tabular}{lcl}
+$\textit{bder}\;c\;_{[]}(\ZERO)$ & $\dn$ & $_{[]}\ZERO$\\
+$\textit{bder}\;c\;_{bs}(\ONE)$  & $\dn$ & $_{[]}\ZERO$\\
+$\textit{bder}\;c\;_{bs}(d)$     & $\dn$ & $\textit{if}\; c = d\;\textit{then} \;_{bs}\ONE \; \textit{else} \;_{[]}\ZERO$\\
+$\textit{bder}\;c\;_{bs}(r_1 + r_2)$ & $\dn$ & $_{bs}(\textit{bder}\;c\;r_1 + \textit{bder}\;c\;r_2)$\\
+$\textit{bder}\;c\;_{bs}(r_1 \cdot r_2)$ & $\dn$ & $\textit{if}\;\textit{nullable}(r_1)$\\
+& & $\textit{then}\;_{bs}(_{[]}(\textit{bder}\;c\;r_1)\cdot r_2) + (_{\textit{bmkeps}\,r_1\rightarrow}\textit{bder}\;c\;r_2)$\\
+& & $\textit{else}\;_{bs}(\textit{bder}\;c\;r_1)\cdot r_2$\\
+$\textit{bder}\;c\;_{bs}(r^*)$ & $\dn$ & $_{bs}(_{0\rightarrow}\textit{bder}\;c\;r)\cdot (r^*)$\\[-5mm]
+\end{tabular}
+\end{center}
 \end{document}
 %%% Local Variables:
 %%% mode: latex

changeset 359	fedc16924b76
parent 305	6e2cef17a9b3