-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathintro.tex
65 lines (55 loc) · 7.18 KB
/
intro.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
\section{Introduction}
\label{sec:intro}
%Regular expressions are frequently used in software development and are also responsible for many errors. For example, a simple search for ``regex OR regular expression'' in GitHub yields 227,474 issues (and growing), with 25\% of those still being open.
%When a regular expression is responsible for a software bug, the impact can be severe, possibly resulting in corrupted data, security vulnerabilities, or denial of service attacks.
%Despite this, regular expressions remain under-studied in software engineering. %, lacking even foundational studies of common errors and how to prevent them. % A regular expression is a language describing the pattern of strings to match.
%Regular expressions can lead to software performance issues, impacting software response time and even triggering system crashes~\cite{browser}.
% There is a type of DOS attack called regular expression denial of service (ReDos)~\cite{kirrage2013static}, which uses a regular expression to slow down the software.
%A single regular expression was responsible for the StackOverflow Outage~\cite{stackoverflow} that occurred in July 2016. %A simple regular expression for space trimming triggered endlessly computing in its regular expression engine. As a result, StackOverflow website had not been responsive fast for about an hour before the problem was fixed.
%We found out that evil, inefficient, or not-well-tested regular expressions are one of the causes of many program bugs
%and even system failures.
A survey of professional developers reveals that they test their regular expressions {\em less} than the rest of their code~\cite{chapman2016}. In this work, we explore how thoroughly tested regular expressions are by examining open source projects.
%For example, buggy regular expressions can enable SQL injection attacks~\cite{halfond2006classification}.
%As evidence, a search for ``regex OR regular expression'' in GitHub yields over 555,000 issues, with 22\% of those still being open.
%Despite the issues associated with regular expressions,
Traditional code coverage criteria, are rather coarse-grained when it comes to regular expressions.
Statement coverage requires the regular expression to be invoked at least once.
If the regular expression call site appears in a predicate, branch coverage requires that the regular expression is tested with at minimum two strings, one in the language of the regular expression and one not.
However, these metrics ignore the complex structure represented by a regular expression.
We propose to use test metrics for graph-based coverage~\cite{ammann2016introduction} over the DFA representation of regular expressions. % and consider the underlying structure of the regular expression itself.
Regular expression tools can help support developers in their creation and testing of regular expressions. These tools either automatically generate strings according to the given regular expressions~\cite{hampi, kiezun2009hampi, rex, brics} or automatically generate regular expressions according to the given list of strings~\cite{Babbar:2010:CBA:1871840.1871848, Li:2008:REL:1613715.1613719}.
Rex~\cite{rex} is a tool for analyzing regular expressions through symbolic analysis.
%In this work, we use it to generate strings for testing. % the regular expressions.
Given a regular expression $R$, Rex uses the Z3~\cite{de2008z3} SMT solver to generate members of the language by treating it as a satisfiability problem. % By design, non-members are not generated by Rex.
Like automatic test case generation tools, integrating these generated results into software testing can help automate the process, but it is not clear how well covered the regular expressions would be compared to developer-written tests.
In this work, we focus on empirically measuring how well tested regular expressions are and further explore the potential for using existing tools, specifically Rex, to improve the test coverage.
%First, we look at the impact of problematic regular expressions and analyze the causal relationship between under-tested regular expressions and software bugs.
First, we measure the test coverage of regular expressions in the wild based on a set of 1,225 Java projects on GitHub containing 15,096 tested regular expressions. Second, we measure the test coverage of strings generated by Rex and compare the coverage achieved against the strings generated by developers in the GitHub projects. % as well after applying automatically generated strings to a large corpus of regular expressions.
%, we extracted 26 regular expressions and measured their coverage. In order to understand the impact of the coverage of regular expressions, we carry out a study on the related bug reports. Finally, we apply the strings generated by regular expression tools to measure the test coverage of regular expressions on a large corpus of regular expressions.
Our contributions are:
\vspace{-3pt}
\begin{itemize}
\item Application of graph-based metrics for test coverage of regular expressions: node coverage, edge coverage, and edge-pair coverage (Section~\ref{sec:coverage}).
%\item An case study on the importance of testing regular expressions (RQ1).
\item Test coverage evaluation of 15,096 regular expressions based on nearly 900,000 input strings from 1,225 Java projects from GitHub (RQ1).
\item Evaluation of test coverage achieved by the Rex symbolic analysis tool for regular expressions (RQ2).
%\item A discussion on integrating current regular expression tools with automatic software testing of regular expressions.
%Comparison of regular expression test coverage w/o strings generated from regular expression tools.
\end{itemize}
\vspace{-3pt}
Our main findings are:
\vspace{-3pt}
\begin{itemize}
\item Of 18,426 call sites for three pattern matching API methods identified statically in 1,225 GitHub projects, only 3,093 (16.8\%) are ever executed by test suites (RQ1).
\item Of 15,096 regular expressions captured during test suite execution of 1,225 GitHub projects, 10,970 (72.7\%) use only failing inputs (4,941) or only matching inputs (6,029) (RQ1).
\item The Rex-generated test inputs achieve similar coverage levels to the developer-written tests (RQ2).
%lower coverage than the repository test inputs when the number of test inputs is the same. Considering only the passing inputs from the test suites, Rex achieves similar coverage (RQ2).
\end{itemize}
%To our knowledge, this is the first work to explore the test coverage of regular expressions.
%The rest of this paper is structured as follows:
%Section~\ref{sec:motive} describes the background and motivation and
%Section~\ref{sec:coverage} describes the coverage metrics.
%Section~\ref{sec:rq} presents the research questions and
%Section~\ref{sec:method} presents our instrumentation and artifact collection.
%Section~\ref{sec:results} describes our results for each research question. %Namely, the importance of testing regular expressions, regular expression coverage in current community source code, and the effectiveness of regular expression tools on regular expression coverage.
%Section~\ref{sec:discussion} discusses the limitations and future work, followed by related work in Section~\ref{sec:related} and the conclusion in Section~\ref{sec:conclusion}.