text:
\section{Approach}
\label{sec:approach}

\iffalse
For example, consider the insertion sort algorithm in Listing~\ref{lst:insertionsort}.
The condition on line~5 continues the loop as long as two successive numbers are in the wrong order.
The chance of randomly testing all possibilities of this loop in relatively low, i.e. fuzzing for sure can find inputs for all paths, but it will take a long time.
For harder (more narrow) conditions, e.g. like \prog{a[j] == x}, it will take even longer.

\begin{lstlisting}[caption=Insertion Sort, label=lst:insertionsort, numbers=left,  stepnumber=1, xleftmargin=1em]
public static void sort(int[] a) {
    final int N = a.length;
    for (int i = 1; i < N; i++) {
        int j = i - 1;
        int x = a[i];
        while ((j >= 0) && (a[j] > x)) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = x;
    }
}
\end{lstlisting}

Now note that finding inputs that execute the previously unexplored program behavior is exactly the type of problem that symbolic execution is good at.
For a fixed N it will easily find and solve the constraints for the loop iterations.

Therefore, we came up with an approach that combines the scalability of fuzzing with the precision of symbolic execution for worst case analysis, called \tool{Badger}.
In our experiments we analyzed exactly this function and observed that the combination performs significantly faster (cf. Section \ref{sec:evaluation}).
\fi

\input{overview-figure}

Figure \ref{fig:badger-overview} shows an overview of the \tool{Badger} workflow.
The fuzzer block is hatched because the detailed workflow in the fuzzer is omitted in this figure. As discussed, \tool{Badger} has two main components: fuzzing and symbolic execution (\symexe for short).
Inputs are generated in an iterative manner, on both fuzzing and \symexe sides, and are transferred between the two components, to trigger generation of new inputs, as guided by heuristics for worst-case analysis. Specifically,
the fuzzer generates and exports inputs that are shown to increase either coverage or cost on the fuzzer side; the specific costs will be discussed in detail below.
These inputs are imported by \symexe (cf. label 1 in Figure \ref{fig:badger-overview}).
\symexe uses concolic execution over the imported inputs to build a partial symbolic execution tree, similar to the trie-based data structure by Yang et al. \cite{Yang2012} (cf. label 2 in Figure \ref{fig:badger-overview}).
This trie captures the so-far explored portion of the symbolic execution paths, in which each node represents a decision in the program that includes symbolic variables.
The trie is saved in memory and gets extended incrementally, whenever new inputs are imported by \symexe.
While the trie is constructed and updated, it is also analyzed on-the-fly to compute the cost and coverage achieved for each node. This information is used by heuristics for worst-case analysis on the \symexe side to choose a node for further exploration in order to produce new inputs that increase coverage and/or cost.

In order to explore the chosen node, we first use a guided symbolic execution until we reach the node of interest (cf. label 3 in Figure \ref{fig:badger-overview}).
This can be done very efficiently, guided by the path in the trie that leads to that node, and with constraint solving turned off.
After reaching the node of interest, we start a bounded symbolic execution (BSE) with a specified depth to explore new paths and generate corresponding new path conditions.

The collected path conditions are then solved to generate new input files (cf. label 4 in Figure \ref{fig:badger-overview}).
Since the exploration is performed on heuristically chosen nodes, and the newly generated inputs follow new paths, which were not explored before,
we need to assess them, to measure their actual cost and the coverage achieved. This is done by running again concolic execution over these newly generated inputs, and updating/extending the trie in the process (cf. label 2 in Figure \ref{fig:badger-overview}).
Only the inputs that are found to lead to new interesting behavior (better cost or new coverage) are exported to the fuzzer, which will use them for its own analysis (cf. label 5 in Figure \ref{fig:badger-overview}). The fuzzer will generate more inputs of interest, which will be imported again by \symexe.

We group the steps labeled with 2 to 4 in the \symexe box, which represents the symbolic execution component, and does not include the interaction with the fuzzer.
We note that in practice, we let \tool{Badger} stay in \symexe for a specified number of iterations, i.e. it only imports new input files from the fuzzer in intervals. The intuition is to let \symexe work on its own, exploring {\em several} promising nodes, rather than spending all its time importing information from the fuzzer. Note that similarly, the fuzzer imports new files in intervals (i.e. the havoc cycle in \tool{AFL}).

\tool{Badger} uses  \tool{Kelinci} for fuzzing and \tool{SPF} for symbolic execution, which are executed in parallel.
Both tools have been extended to search specifically for worst-case behavior w.r.t. a variety of cost metrics.
In the following, we explain both components in detail.

\subsection{Fuzzing with KelinciWCA}
\tool{KelinciWCA} extends \tool{Kelinci} with prioritization of costly paths. Costs are collected on the \textsc{Java}\xspace side, then sent to \tool{AFL}, which we also modified to take into account the path costs (in addition to coverage). The fuzzer maintains the current \emph{highscore} with respect to the used cost model.
When creating the next generation of inputs, the fuzzer selects ancestors from the set of inputs from the previous generation that either lead to the execution of previously unexplored program branches or to a new highscore. The chance that an input is selected from this set depends on its cost, as recorded on the \textsc{Java}\xspace side.

There are three cost models available:
\begin{itemize}
  \item \textbf{Timing} is measured by counting jumps (branches) in the program. This is more precise than measuring wall clock time, as in the latter case, there are often outliers and other inconsistencies due to, e.g., other activities on the machine. It is efficiently measured by adding the statement \prog{Mem.jumps++} to the instrumentation trampoline, adding 4 bytecode instructions and bringing the total number to 16.
  \item \textbf{Memory} usage is measured by intermittent polling using a timer. The maximum consumption at any point during execution of the program on the given input is collected. Though measuring allocations using program instrumentation could in some cases be more precise, it does not take into account garbage collection, and it requires the program to determine the sizes of individual objects which is expensive and can also be inaccurate.
  \item \textbf{User-defined} costs can also be used. In this case, the user instruments their program with calls to the special method \method{Kelinci.addCost(int)}, enabling the use of arbitrary metrics like the values of variables. Moreover, it allows a relationship between input and cost about which a machine can reason. This will be used later by the symbolic execution engine to directly generate inputs with maximal costs as an optimization.
\end{itemize}

\tool{KelinciWCA} inherits the ability of \tool{AFL} to run in a parallel mode, which enables the synchronization with other \tool{AFL} instances.
After a configurable number of cycles with its own mutation operations (i.e. havoc cycles), \tool{AFL} checks the other instances for interesting inputs.
Since this synchronization procedure is merely based on a specific folder structure, we can pass files from our symbolic execution part to \tool{KelinciWCA} easily.

\subsection{Example}
Before describing the \symexe component of \tool{Badger}, we introduce an example to illustrate how the various steps work.
The example is an implementation of Insertion Sort and is given in
Listing~\ref{lst:insertionsort}.

\begin{lstlisting}[caption=Insertion Sort, label=lst:insertionsort, numbers=left,  stepnumber=1, xleftmargin=1em]
public static void sort(int[] a) {
    final int N = a.length;
    for (int i = 1; i < N; i++) {
        int j = i - 1;
        int x = a[i];
        while ((j >= 0) && (a[j] > x)) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = x;
    }
}
\end{lstlisting}

\subsection{SymExe: Symbolic Execution with Symbolic PathFinder}
The \symexe component consists of three steps: trie extension and input assessment (cf. label 2 in Figure \ref{fig:badger-overview}), exploration (cf. label 3 in Figure \ref{fig:badger-overview}) and input generation (cf. label 4 in Figure \ref{fig:badger-overview}).
The following sub sections will cover all parts.

Figure~\ref{fig:example} shows snapshots of the trie while running \symexe on Insertion Sort for three numbers (N=3).
Note that trie nodes correspond to decisions rather than conditions in the program; multiple trie nodes may correspond to a single program condition. Since $N$ has the concrete value 3, the only symbolic decision in our program is \prog{a[j] > x} on line~5. Therefore, all nodes in Figure~\ref{fig:example} except the root nodes correspond to that decision.

\input{approach-example-figure}

\subsubsection{Trie extension / input assessment}
In this step, \symexe performs a concolic execution over a set of concrete inputs (which are generated either by the fuzzer or by \symexe itself) and updates the trie data structure that maintains a view of all the explored symbolic execution paths. This is done by adding a concolic mode to SPF that simply collects the constraints along the concrete paths (without any constraint solving) and using a listener to monitor the execution and update the trie with newly explored nodes.

\iffalse
To enable the concolic execution with \tool{SPF}, we modified each symbolic handler of a branching bytecode instruction to not explore all possible branches, but to only follow the path that would have been taken by the concrete values.
\tool{SPF} uses, inherited by \tool{JPF}, so called choice generators to model all branches at a symbolic branching instruction: each branch is represented by a choice that can be made.
For example a choice generator would introduce two choices for an if condition, one for the true branch and one for the false branch.
Using concrete values to make the decisions, does only leave one possible choice.
Instead of let the choice generator generate \emph{n} choices at a branching instruction, we let it generate only one choice and set the path condition accordingly.
This enables us to use \tool{SPF} in the usual way, but actually it follows only the path of the concrete values and collect the path constraints.
During the concolic execution we extend our trie data structure for each choice we made, i.e., we create a new node for this choice.
Building, and extending, the trie data structure is implemented as a listener in \tool{SPF}, which is a simply way to make an extension to the \tool{JPF} framework.
\fi

Figure \ref{fig:example:a} shows the trie for the initial input of the Insertion Sort example.
There are three nodes: the root node of the trie, and two decisions for \prog{a[j] > x} on line 5, which is the only condition that depends on symbolic input.
The last node (id=2) is a leaf, the last decision on the execution trace for the initial input.

During concolic execution we perform a worst-case analysis (WCA), to compute cost and coverage information for each node in the trie.
The default cost metric is timing, measured in number of jumps (branches).
Alternatively, WCA can collect user-defined costs
specified in the code with \method{Observations.addCost(int)}. A novelty of our approach is that we can handle symbolic (input-dependent) costs as described in detail below.

Each trie node gets an associated \emph{score}, indicating how promising this node is with respect to the cost.
A score reflects an estimation of total costs that may be achieved rather than costs accumulated so far along a path. The score of a leaf node is defined as the cost associated with the path that ends in that leaf node; for example, it could be the total number of branches executed to reach that node.  The scores for the internal nodes
are propagated up in the trie, by taking the average of children scores as the score for a parent node.
For our simple example in Figure \ref{fig:example:a} all nodes get the value 7 (after importing one input) as the graph corresponds to a single path with cost 7.
Furthermore, coverage information for each node is updated.

The next step is to select the most promising node for further exploration. Every node that has unexplored children is a candidate for further exploration. We choose the most promising one based on three criteria. First, nodes with unexplored choices leading to new \textbf{branch} coverage are given priority; this means that if exploring a node can potentially lead to new coverage, we consider it as a good candidate for exploration. Second, nodes are ranked based on their \textbf{score}; nodes with higher score will again be given priority. Third, nodes are ranked based on their \textbf{position} in the trie. For the latter, the tool is parametric with respect to two different heuristics:
\begin{enumerate}
\item Prefer nodes \textbf{higher} in the trie.
  This follows the intuition of exploring a wider region of the execution tree, covering a wider input space, analogous to a breadth-first search.
\item Prefer \textbf{lower} nodes. This follows the intuition to drill deeper in a promising direction, where high costs have been observed, analogous to depth-first search.
\end{enumerate}

For the example in Figure \ref{fig:example:a} we apply the second heuristic, i.e. to prefer nodes lower in the trie.
Hence, the node with id=1 is chosen as the most promising node
instead of the root node.
For the situation in Figure \ref{fig:example:c} (which reflects the case when the import generated by \symexe itself is evaluated) it is clearly the node with id=3 because it is the only node with score=10.0 that can be explored.

We note that the input assessment and the trie extension can be executed in two modes: (1) import, and (2) export.
The import mode is used when importing input files from \tool{KelinciWCA}.
There is a special case when the user-defined cost metric is used: after importing an input, \symexe tries to maximize the costs along the concrete path by leveraging the maximizing procedures described in Section \ref{subsubsec:inputgeneration}.
If successful, \symexe will immediately export the maximizing input to the fuzzer.
The export mode is used when it is necessary to assess input files generated by \symexe.
Executing them with concolic execution (and on-the-fly WCA) reveals cost values and extends the trie with new nodes.
We use a conservative approach to exporting input files to \tool{KelinciWCA}, because we do not want to flood the fuzzer with irrelevant inputs.
Only inputs leading to new branch coverage or a new high score are exported.

\subsubsection{Exploration}
This step performs the actual exploration of new parts of the trie. The goal is to explore {\em new} branches starting from the node that was deemed most promising in the previous step (this means that the new branches will likely increase coverage or cost).
This step involves a quick symbolic execution along the trie path that reaches the node, as guided by the choices encoded in the trie.
There is no constraint solving needed.
As soon as the node of interest is reached, we switch to bounded symbolic execution (BSE) to explore new decisions.
When BSE reaches its bound we extract the path condition(s) and pass them to the next step, which will solve them to obtain new inputs.

In our example in Figure~\ref{fig:example:b} the trie-guided symbolic execution phase is very short, since only one choice is made to get to the node with id=1.
Next, we perform BSE with depth=1, i.e. only one step, and reach the node with id=3.
The score for this new node is unknown because it is not the end of the execution trace. The extracted path condition $pc$ makes it possible to generate an input value that reaches this new node. We will then need to run concolic execution again, to assess this new input, to compute the scores and update the trie (see Figure~\ref{fig:example:c}).

\subsubsection{Input Generation and Input-dependent Costs}
\label{subsubsec:inputgeneration}
In this step we generate concrete inputs by solving the path conditions from the previous step. This is done by using an off-the-shelve constraint solver. For the example, the path condition $sym\_0 \leq sym\_1  \wedge  sym\_1 > sym\_2$ may be solved to generate the input \prog{[1,1,0]}.
The solution(s) are used to generate a new input file (cf. step 5 in Figure~\ref{fig:badger-overview}), which is application-dependent. Note that it could happen that some path conditions are unsatisfiable, in which case no input is generated for them.

The path condition from Figure~\ref{fig:example:b} makes it possible to generate an input value that follows a path along the node with id=3. As shown in Figure~\ref{fig:example:c}, this input leads to a leaf node with id=4, and to a new high score, which is back-propagated to the precedent nodes.

As mentioned, the usage of heuristics makes it necessary to assess the actual cost value of each input because it is not guaranteed that the most promising nodes actually lead to worse costs.
This is done by passing the generated input back to the trie extension phase and executing in export mode as described above.

A key novelty of our approach is the incorporation of symbolic (input-dependent) costs, which require specialized techniques for input generation. The user-specified costs allow to use arbitrary variables in the program when specifying the cost, including input-dependent ones. Thus, a symbolic path may have a symbolic cost, i.e. a symbolic expression that is passed as a parameter to method \method{Observations.addCost(int)}. We are then interested in computing inputs that {\em maximize} this cost. To achieve this, we propose to use an optimization procedure in the constraint solver.
In our set-up, we use \tool{Z3}~\cite{DeMoura:2008:ZES:1792734.1792766}, which allows to specify {\em optimization objectives}, i.e. we can ask \tool{Z3} to generate a model that maximizes a given expression. We illustrate the approach on a simple example, shown in Listing~\ref{lst:ex-maximization}.

\begin{lstlisting}[caption={User-Defined Cost Maximization Example}, label={lst:ex-maximization}, numbers=left,  stepnumber=1, xleftmargin=1em]
int sumArg(int[] a) {
	int sum = 0;
	for (int i=0; i < a.length; i++) {
		if (a[i] > 0)
			sum += a[i];
		else
 			sum -= a[i];
	}
	Observations.addCost(sum);
	return sum;
}
\end{lstlisting}

If the user is interested in maximizing the value of a variable (here \prog{sum}), then simply counting jumps or measuring resource consumption will not be sufficient for the generation of worst-case inputs.
To address this situation, we instrument the code with a special cost specification (line~8).
When performing concolic execution over \prog{sumArg} for concrete input values \prog{a=\{1,2\}},
variable \prog{sum} at line~8 has the value \prog{sum=$s_1$+$s_2$}  and the path condition is $s_1>0 \wedge s_2>0$,
where $s_1$ and $s_2$ are the corresponding symbolic inputs.

We can pass an optimization term to \tool{Z3} for the specified cost expression.
For example for two positive inputs the query to the solver (in SMT 2 syntax) will look like:
{\small
\begin{center}
\prog{(assert (> $s_1$ 0))} \\
\prog{(assert (> $s_2$ 0))} \\
\prog{(maximize (+ $s_1$ $s_2$))}
\end{center}
}
The retrieved model for the path condition
will contain values that maximize the given expression. Assume for simplicity that the allowed range for the inputs is $[-100,100]$.
Then the maximization procedure will return $s_1=100, s_2=100$ which indicate the worst-case inputs for this path.

\section{Background}

\label{sec:background}
\input{kelinci.tex}
\input{spf.tex}

\section{Conclusions and Future Work}
\label{sec:conclusions}
We have proposed \tool{Badger}, a hybrid testing approach for complexity analysis.
It extends the \tool{Kelinci} fuzzer with a worst-case analysis, and uses a modified version of \tool{Symbolic PathFinder} to import inputs from the fuzzer, analyze them and generate new inputs that increase both coverage and execution cost. \tool{Badger} can use various cost models, such as time and memory consumption, and also supports the specification of input-dependent costs.
\tool{Badger} was evaluated against a large set of benchmarks, demonstrating the performance and quality benefits over fuzzing and symbolic execution by themselves.

In the future, we plan to explore more heuristics for worst-case analysis on both the fuzzing and the symbolic execution side. We also plan to focus more on the symbolic execution part of \tool{Badger} and conduct experiments using multiple depths during bounded symbolic execution.
Additionally, we plan to explore techniques to increase scalability of the symbolic execution part by, e.g., limiting the size of the trie, which would lead to a faster exploration of the upper symbolic execution tree.
Furthermore, we plan to extend our approach not only for complexity analysis, but also for a {\em differential} side-channel analysis of security-relevant applications.
\section{Evaluation}
\label{sec:evaluation}
In this section we present an evaluation of our implementation for \tool{Badger}.
In order to enable the replication of our experiments and to make our tool publicly available, we have released \tool{Badger} and all evaluation artifacts on GitHub: \url{https://github.com/isstac/badger}.
We evaluate our approach to answer these research questions:

\begin{itemize}
\item[\textbf{RQ1:}] Since \tool{Badger} combines fuzzing and symbolic execution, is it better than each part on their own in terms of:
	\begin{enumerate}[label=(\alph*)]
		\item Quality of the worst-case, and
		\item Speed ?
	\end{enumerate}
\item[\textbf{RQ2:}] Is \tool{KelinciWCA} better than \tool{Kelinci} in terms of:
		\begin{enumerate}[label=(\alph*)]
		\item Quality of the worst-case, and
		\item Speed ?
	\end{enumerate}
\item[\textbf{RQ3:}] Can \tool{Badger} reveal worst-case vulnerabilities?
\end{itemize}

\subsection{Experimental Setup}
\label{subsec:experimental-setup}

\paragraph{Subjects}
\label{par:subjects}

Table~\ref{tbl:subjects} gives an overview of our evaluation subjects.
Subject 1 to 5 are similar to the benchmarks used in \tool{SlowFuzz}.
Subject 6 represents an image processing application provided by DARPA, as part of STAC engagements~\cite{Darpa}.
Subject 7 represents an implementation of a smart contract for crypto-currency, translated into \textsc{Java}\xspace from \tool{Ethereum}, where the goal is to estimate the worst-case {\em gas}
consumption.
For subject 1 to 6 we use the number of jumps as cost metric.
For subject 7 we use user-defined costs that are specified directly in the code.

\begin{table}[h]
\begin{center}
\caption{Overview of the evaluation subjects.}
\begin{tabular}{ l | l || l | l }
\textbf{ID} & \textbf{Subject} & \textbf{ID} & \textbf{Subject} \\ \hline
  1 & Insertion Sort & 4 & Hash Table \\
  2 & Quicksort & 5 & Compression \\
  3a & RegEx (fixed input) & 6 & Image Processor \\
  3b & RegEx (fixed regex) & 7 & Smart Contract \\
\end{tabular}
\label{tbl:subjects}
\end{center}
\end{table}

\paragraph{Experiment Execution}
\label{par:experiment-execution}

For all subjects we ran four variations: (1) \tool{Badger}, (2) \tool{KelinciWCA}, (3) \tool{Kelinci} and (4) \symexe.
Success of an evolutionary fuzzing tool can depend greatly on the corpus of input files provided by the user as the first generation. For all experiments, we chose a single file with meaningless values (e.g. ``Hello World'') to leave the heavy lifting to the tools.
Running option (1) means to execute \tool{KelinciWCA} and \symexe in parallel.
\tool{KelinciWCA} starts with the initial input and \symexe imports the inputs from \tool{KelinciWCA} like shown in Figure \ref{fig:badger-overview}.
Running option (2) and (3) means simply to execute the tools, and option (4) means to execute only \symexe on the initial input.
We have observed in pre-experiment executions that, for our subjects, after 5 hours the compared tools reach a plateau.
We therefore ran our experiments for 5 hours, 5 times (deviations from this paradigm for particular experiments are explained in the corresponding sections).
We also used these pre-experiment executions to determine the best fitting heuristic for each application.
Similar to Petsios et al.~\cite{Petsios2017}, we report slowdown in the subjects, i.e. the ratio between the costs of the observed worst case input and the initial input.

\paragraph{Infrastructure}
\label{par:infrastructure}
All experiments were conducted on a machine running \tool{openSUSE Leap 42.3} featuring 8 Quad-Core-AMD 8384 2.7 GHz and 64 GB of memory.
We used \textsc{OpenJDK}\xspace 1.8.0\_151 and \tool{GCC 4.8.5}.
We configured the \tool{Java VM} to use at most 10 GB of memory.

\subsection{Sorting}
We first evaluate our approach on two textbook examples: Insertion Sort and Quicksort.
We use the implementations from \textsc{JDK}\xspace 1.5.
Results for Insertion Sort are the averages of 5 runs. For quicksort we deviated from the usual paradigm of 5 runs and performed 10 runs, because we observed a lot of variation in the first 5 runs.
For both subjects we used N=64, i.e. the input is an array of 64 integers.

\input{01_insertionsort}

Results for Insertion Sort are shown in Figure~\ref{fig:insertionsort}. The score for the initial input is 509.
The tools reach the following averaged final scores: \tool{Badger} 9850, \tool{KelinciWCA} 9533, \tool{Kelinci} 6701, and \symexe 3025.
\tool{KelinciWCA} produces a slowdown of 18.73x.
\tool{Badger} reaches the final score of \tool{KelinciWCA} already after 61 minutes (\tool{KelinciWCA} needs 219 minutes) and continues to improve to a slowdown of 19.35x after 5 hours.
It is thus better in terms of both quality of the result, and speed.
The symbolic execution component \symexe by itself performs poorly, since it is only executed on the initial input and cannot use intermediate results by \tool{KelinciWCA}.

\input{02_quicksort}

Results for Quicksort are shown in Figure~\ref{fig:quicksort}. The score for the initial input is 2829.
The tools reach the following averaged final scores: \tool{Badger} 3683, \tool{KelinciWCA} 3719, \tool{Kelinci} 3161, and \symexe 2970.
There is no significant difference between the results for \tool{Badger} and \tool{KelinciWCA}.
\tool{Badger} tends to be faster in generating a highscore between 20 and 150 minutes, but the final score after 300 minutes for \tool{KelinciWCA} is slightly better.
\tool{Badger} produces a slowdown of 1.30x and \tool{KelinciWCA} of 1.31x.
This minor difference at the end can be explained by the randomness inherent in fuzzing; since \tool{Badger} includes \tool{KelinciWCA}, its results for a particular run are always at least as good.
In fact for the best run of the 10 performed, we observed that \tool{Badger} produced the score 4219 (1.49x), while \tool{KelinciWCA} produced the score 4013 (1.42x).

\subsection{Regular Expressions}
The second evaluation considers regular expression matching, which can be vulnerable to so called ReDoS (Regular expression DoS) attacks.
Specifically, we used the \prog{java.util.regex} \textsc{JDK}\xspace package.

\input{03_regex_lorem}

We performed two experiments. In the first, we fixed the matching text and mutated the regular expression.
We used the lorem ipsum filler text, and limited mutated regular expressions to 10 characters.
As initial input we used the regular expression $\left[\symbol{92}s\symbol{92}S\right]^{*}$.
We increased the number of experiments to 10 because we observed too much variation in the first 5 runs.

\input{03_regex_01_username}
\input{03_regex_02_password}
\input{03_regex_03_hexcolor}

Results are shown in Figure~\ref{fig:regex-text}. The initial input score is 68101.
The tools reach the following average scores: \tool{Badger} 125616, \tool{KelinciWCA} 124641, \tool{Kelinci} 119393, and \symexe 1388.
\tool{Badger} produces a slowdown of 1.84x and \tool{KelinciWCA} of 1.83x.
This insignificant difference can be explained by the poor result for \symexe, which was not able to improve the score of the initial input.

In the second experiment, we fix the regex and mutate the text.
We use the lorem ipsum as initial input again.
For the regular expressions we use ten popular examples~\cite{regular_expressions}.
Due to space limitations, we include only the first three here, respectively matching a username, password, and hexadecimal color code:

\vspace{-5pt}
{\Small
\begin{equation}
\hat{}\left[a\!-\!z0\!-\!9\_\!-\!\right]\{3,15\}\$
\end{equation}
\begin{equation}
((?\!=\!.\!^{*}\!\symbol{92}d)(?\!=\!.\!^{*}\!\left[a-z\right])(?\!=\!.\!^{*}\!\left[A-Z\right])(?\!=\!.\!^{*}\!\left[@\#\$\%\right]).\{6,20\})
\end{equation}
\begin{equation}
\hat{}\,\#(\left[A\!-\!Fa\!-\!f0\!-\!9\right]\!\{6\}\,|\,\left[A\!-\!Fa\!-\!f0\!-\!9\right]\!\{3\})\$
\end{equation}
}

Results are shown in Figures~\ref{fig:regex-username}, \ref{fig:regex-password} and \ref{fig:regex-hexcolor}, respectively.
Remarkably, for the username regex, \symexe is faster than \tool{Badger}.
This can be explained by the fact that the initial input already leads to relatively high costs; in general this is not the case.
Additionally, \symexe starts working right away, while \tool{Badger} needs some time to import input files generated by \tool{KelinciWCA} (it is started with a slight delay).

Results for the password regex show that \symexe is not able to generate any comparable highscore, which explains why \tool{Badger} is not performing significantly better than \tool{KelinciWCA}.

For the color code regex, \tool{Badger} and \tool{KelinciWCA} both produce a slowdown of 1.27x, but \tool{Badger} finds it significantly faster.
By leveraging the inputs generated by \symexe, \tool{Badger} reaches a cost of 2800 after 25 minutes, for which \tool{KelinciWCA} needs 133 minutes.
Interestingly, \tool{Kelinci} is also faster than \tool{KelinciWCA}.
While statistically unlikely, this can happen due to the inherent randomness in the fuzzer.

\subsection{Hash Table}
The fourth evaluation subject is a hash table implementation taken from a recent \textsc{DARPA}\xspace engagement \cite{Darpa} and modified to match the hash function by \tool{SlowFuzz}\cite{Petsios2017}, which was taken from a vulnerable \tool{PHP} implementation~\cite{phpvuln}.
The size of the hash table is 64, each key in the hash table has a length of 8 characters, and we fill it by reading the first $64 \cdot 8$ characters from an input file.
The worst-case of a hash table implementation can be triggered by generating hash collisions. Therefore, besides the normal costs, we also report the number of hash collisions.
We executed the experiments 10 times because we observed too much variation in the first 5 runs.

\input{04_hashtable}

The graph in Figure \ref{fig:hashtable} shows that \tool{Badger} first performs slightly better and faster, but is passed by \tool{KelinciWCA} after 103 minutes.
This is based on \symexe, which quickly generates a very good score, but is not able to further improve.
Since we cannot report the number of collisions for the averaged plot, we looked at the best performing run for each experiment.
The results correspond to 31 collisions found by \tool{Badger}, and 39 found by \tool{KelinciWCA} (the theoretical upper bound is 63).
This subject shows very evidently the advantage of \tool{KelinciWCA} over \tool{Kelinci}, which plateaus after 66 minutes and only finds 22 collisions.

\subsection{Compression}
Our fifth evaluation subject is taken from \tool{Apache Commons Compress}.
In the experiment, we \tool{BZip2} compress files up to 250 bytes.

\input{05_compress}

Results are shown in Figure~\ref{fig:compress}.
The score for the initial input is 1,505,039.
The tools reach the following average scores: \tool{Badger} 1,800,831, \tool{KelinciWCA} 1,779,457, \tool{Kelinci} 1,775,438, and \symexe 1,509,880.
\tool{Badger} produces a slowdown of 1.20x and \tool{KelinciWCA} of 1.18x.
\tool{Badger} is significantly faster.
The worst case found by \tool{KelinciWCA} after 100 minutes is found by \tool{Badger} within 50 minutes.

\subsection{Image Processor}
\label{subsec:imageprocessor}

Our sixth evaluation subject is an image processing application taken from a recent \textsc{DARPA}\xspace engagement \cite{Darpa}.
Our analysis revealed a vulnerability related to particular pixel values in the input image causing a significantly increased runtime for the program.
These pixel values trigger a particular value from a static array, which is used to determine the number of iterations in a processing loop.
\tool{Badger} was able to automatically generate a JPEG image that exposes the vulnerability.
For the sake of simplicity, we limited the size of images to 2x2 pixels.

\input{06_imageprocessor}

Results are shown in Figure~\ref{fig:imageprocessor}. Here we see that \tool{Badger} clearly outperforms both its components. It produces a slowdown of 40.11x, corresponding to theoretical worst-case, where all pixels have a value triggering the highest possible number of iterations in the processing loop.

\iffalse
We observed 8712 as score for our initial input.
The compared tools reach the following averaged final scores: \tool{Badger}:  349438, \tool{KelinciWCA}:  193730, \tool{Kelinci}: 188719, and \symexe: 291384.
\tool{Badger} produces a slowdown of 40.11x and \tool{KelinciWCA} of 22.24x.
The graph in Figure \ref{fig:imageprocessor} shows that \tool{Badger} outperforms \tool{KelinciWCA} for this subject.
\tool{Badger} produces a far higher slowdown and is much faster.
The worst case identified by \tool{KelinciWCA} of 188719 is found after 283 minutes.
\tool{Badger} finds this score already after 25 minutes.
For this subject \symexe plays a crucial role because it can an extremely high score, right after some minutes, which pushes \tool{Badger}.
The worst score produced with \tool{KelinciWCA} was in our experiments: 221940, which triggers the worst case array value only in 6 of 12 cases.
In contrast, the worst score produced with \tool{Badger} was in our experiments: 434088, which triggers the worst case array value in all of the 12 cases.
\fi

\subsection{Smart Contract}

Our last subject is an implementation of a smart contract for cryptocurrency, where the goal is to analyse the usage of a resource called {\em gas} of \tool{Ethereum} software.
Exceeding the allocated budget could result in loss of cryptocurrency.
Therefore we consider gas as the user-defined cost in our analysis.
We manually instrument the code with calls to the special methods \method{Kelinci.addCost(int)}, and \method{Observations.addCost(int)}.
We executed the experiments 10 times because we observed too much variation in the first 5 runs.
For our experiments we used an input array size of $N=50$ items.

\input{07_smartcontract}

Results are shown in Figure \ref{fig:smartcontract}.
We observed a cost of 3 for the initial input.
The tools reach the following average scores: \tool{Badger} 16,218,905, \tool{KelinciWCA} 11,934,664, \tool{Kelinci} 1,000,107, and \symexe 1,000,107.
The increase in the cost is 5,406,301.67x for \tool{Badger} and 3,978,221.33x for \tool{KelinciWCA}.
The cost depends on a concrete value in the input and can thus be very large (even for a short path the cost can be large if the input value is large).
The initial input does not contain these large values, and hence, the cost increase is so dramatic.
\tool{Badger} is significantly faster than \tool{KelinciWCA}, and also produces a much higher worst case cost.

\subsection{Discussion}

\subsubsection*{RQ1.a}
Our evaluation shows that, in terms of quality of the worst case, \tool{Badger} is always better than \symexe because eventually \tool{Badger} will use the insights of its symbolic execution part.
But, as mentioned earlier, \tool{Badger} does not consider inputs from \symexe until they are imported by \tool{KelinciWCA}.
Additionally, the randomness from the fuzzer can cause \symexe to explore other paths that turn out to be less costly than those closer to the initial input.
In most of our subjects, \tool{Badger} also produces a better worst case than \tool{KelinciWCA}.
There are two cases in which \tool{KelinciWCA} is slightly better than \tool{Badger}: Quicksort and Hash Table. These differences are based on the randomness in the fuzzing component of our approach.
Therefore, we conclude question RQ1.a with the positive answer: yes.
Note that in practice, a slightly lower worst case is often more useful if it can be obtained significantly faster.

\paragraph{RQ1.b}
Our evaluation demonstrates that \tool{Badger} is significantly faster than \tool{KelinciWCA} and \symexe, attesting a clear positive answer to RQ1.b.
In most cases, \symexe by itself performs poorly compared to \tool{Badger}.
Nevertheless, there is one case where \symexe is able to generate a high score very fast, and \tool{Badger} is not able to follow immediately: Regular Expression (username).
We explain this by the random initial input, along which path \symexe finds a high score very quickly, whereas \tool{Badger} experiences some delay in importing \tool{KelinciWCA} results that also sidetrack the analysis.
Note that, similar to \tool{KelinciWCA}, \tool{Badger} can achieve better performance through parallelization by, e.g., running multiple fuzzing instances in parallel.

\paragraph{RQ2.a}
The evaluation shows that \tool{KelinciWCA} is always better than \tool{Kelinci} in terms of quality of the worst case.
Although there are cases, in which \tool{Kelinci} performs not bad, the single focus on coverage limits \tool{Kelinci} for worst case analysis.
This limitation of \tool{Kelinci} was eliminated with \tool{KelinciWCA}.

\paragraph{RQ2.b}
Regarding the speed comparison between \tool{KelinciWCA} and \tool{Kelinci}, our evaluation illustrates that in almost all subjects \tool{KelinciWCA} does not only retrieves a better worst case, but it also achieves this in shorter time.
The only exception is the subject Regular Expression (hexcolor).
In general, \tool{KelinciWCA} is faster, but in cases where for a particular application higher coverage implies a better worst case, then \tool{Kelinci} might be more efficient.

\paragraph{RQ3}
We have shown that Badger performed well in our experiments, finding slowdowns on the subjects. Notably, \tool{Badger} identified a vulnerability in Image Processor, a complex application that processes non-trivial inputs (i.e. JPEG images).
\tool{Badger} was able to reveal the actual worst-case by building a JPEG image, demonstrating
its ability in exposing vulnerabilities in complex applications.

\iffalse
\paragraph{Limitations}
The evaluation shows that the randomness of \tool{KelinciWCA} affects \tool{Badger} as well.
This can be positive in terms of a surprising peak in the worst case, but it also can be negative when the fuzzing part is not able to generate something reasonable for a long time.
This requires the application of \tool{Badger} in multiple iterations.
Depending on the characteristics of the application, \symexe might not be able to contribute a lot, since symbolic exploration with constraint solving might take to much resources.
Nevertheless, we tried to mitigate this problem by applying hybrid concolic approaches.
Our developed heuristics for the worst case analysis show positive results in our evaluation, however, they also seem to thwart \tool{Badger} in cases where the \symexe performs faster than \tool{KelinciWCA}.
\fi

\subsection{Threats to Validity}

\paragraph{Internal Validity.}
The main threat to internal validity is the correctness of collection and analysis of experimental results.
Therefore, we fully automated the process of collecting data, aggregating values and plotting graphs.
Another threat to internal validity is the selection of experiment parameters, such as the heuristic worst case analysis.
In order to verify this we conduced pre-experimental tests that showed the effectiveness of our selection.
Additionally, in our experiments with \tool{Badger}, we used one process for \tool{KelinciWCA} and one for \symexe. In the experiments with the individual tools, each ran on a single core. This could give the combination of the tools an advantage. In future work, we plan to parallelize \symexe, which is expected to further improve the effectiveness of \tool{Badger}, and also will enable a more fair comparison.

\paragraph{External Validity.}
The main threat to external validity is that evaluation subjects may not generalize.
In order to mitigate this threat we have selected benchmarks that match existing work in the field, and added a real-world (complex) example.

\paragraph{Construct Validity.}
The main threat to construct validity is the correctness of our actual implementation.
We based our implementation on \tool{SPF} and \tool{Kelinci}, and hence, our adaptions inherit potential incorrectness of these tools.
However, face-validity shows that our evaluation results match the expected outcome.

\section{Introduction}
\label{sec:intro}

In recent years, fuzz testing has emerged as one of the most promising testing techniques for finding correctness bugs and security vulnerabilities in software. It is used routinely by major software companies such as Microsoft~\cite{MicrosoftSecurity,Godefroid:2012:SWF:2090147.2094081} and Google~\cite{Google}. While a large fraction of the inputs generated with fuzzing may be invalid, it can be more effective in practice than more sophisticated testing techniques --~such as the ones based on symbolic execution~\cite{Godefroid:2005:DDA:1065010.1065036,Sen2005}~--
due to the low computation overhead involved in fuzzing.

Fuzz testing tools, such as \tool{AFL}~\cite{afl} and \tool{LibFuzzer}~\cite{libfuzzer}, have proven very successful by finding bugs and vulnerabilities in a variety of applications, ranging from image processors and web browsers to system libraries and various language interpreters. For example, \tool{AFL} was instrumental in finding several of the Stagefright vulnerabilities in Android, the Shellshock related
vulnerabilities in \tool{BIND}
as well as numerous bugs in
popular applications and libraries such as \tool{OpenSSL}, \tool{OpenSSH}, \tool{GnuTLS}, \tool{GnuPG}, \tool{PHP}, \tool{Apache}, and \tool{IJG jpeg}.
In a nutshell, \tool{AFL} uses genetic algorithms to {\em mutate} user-provided inputs using byte-level operations. These mutations are guided by coverage information obtained from running the analyzed program on the generated inputs. The interesting mutants (that are shown to increase coverage) are saved and mutated again. The process continues with the newly generated inputs, with the goal of generating a diverse set of inputs that increase the coverage of the program.

Motivated by the success of fuzz testing, we explore here the application of the technique to algorithmic complexity analysis. Characterizing the algorithmic complexity of a program has many practical applications as it enables developers to reason about their programs, understand performance bottlenecks and find opportunities for compiler optimizations. Algorithmic complexity analysis can also reveal worst-case complexity vulnerabilities, which occur when the worst-case time or space complexity of an application is significantly higher than the average case. In such situations, an attacker can mount Denial-of-Service attacks by providing inputs that trigger the worst-case behavior, thus preventing benign users to use the application.

There are several challenges in adapting fuzz testing to algorithmic complexity analysis.
First, fuzz testers like \tool{AFL} are designed to generate inputs that increase code coverage, while for complexity analysis one is interested in generating inputs that trigger worst case execution behavior of the programs. Furthermore, fuzzers are known to be good at finding so called {\em shallow} bugs but they may fail to execute deep program paths \cite{DBLP:conf/ndss/StephensGSDWCSK16}, i.e. paths that are guarded by specific conditions in the code.  This is due to the fact that the fuzzers have little knowledge about which inputs affect which condition in the code. On the other hand, symbolic execution techniques are particularly well suited to find such cases, but usually are much more expensive in terms of computational resources required.

We therefore propose an analysis tool that uses fuzzing and symbolic execution in tandem, to enable them to find worst case program behaviors, while addressing their limitations. Specifically, we present \tool{Badger}: a framework that combines fuzzing and symbolic execution for automatically finding algorithmic complexity vulnerabilities in Java applications.

Our hybrid approach works as follows. We first run a fuzzer to generate a diverse set of inputs.
For fuzzing, we build on \tool{Kelinci}~\cite{ccs2017}, an \tool{AFL}-based fuzzer for \textsc{Java}\xspace programs. We modify \tool{Kelinci} and \tool{AFL} to add a new heuristic
to account for resource-usage {\em costs} of program executions, meaning that the inputs generated by the fuzzer are marked as important if they obtain either an increased execution cost or new coverage. We call this tool \tool{KelinciWCA}. The cost is defined in terms of
number of conditions executed, actual execution time as well as user-defined costs that allow us to keep track of memory and disk usage as well as other resources of interest particular to an application

The inputs generated by the fuzzer may cover a large set of executions but may fail to exercise deep program behavior.
This can happen because of some hard-to-solve conditions that guard deep executions, as discussed above.
At some user-defined point in time, the inputs are transferred to the symbolic execution side which analyzes them with the goal of
producing new inputs that increase the cost and/or the coverage. These inputs are passed back to the fuzzer and
the process continues until a vulnerability is found or a user-defined threshold is met.

For symbolic execution we use \tool{Symbolic PathFinder}~(\tool{SPF}), a symbolic execution tool for \textsc{Java}\xspace bytecode~\cite{Pasareanu:2013:ASE}. We modified \tool{SPF} by adding a mixed concrete-symbolic execution mode, similar to concolic execution~\cite{Sen2005} which allows us to {\em import} the inputs generated on the fuzzing side and quickly reconstruct the symbolic paths along the executions triggered by the concrete inputs. These symbolic paths are then organized in a {\em tree} which is analyzed with the goal of generating new inputs that expand the tree. The analysis is guided by novel {\em heuristics} on the SPF side that favor new branches that increase resource-costs.
The newly generated inputs are passed back to the fuzzing side.

A novelty of our approach is the handling of user-dependent costs, which get translated into symbolic costs on the symbolic execution side and are handled by running a symbolic maximization procedure, to generate the worst-case inputs. This broadens the application of \tool{Badger} over previous symbolic execution techniques~\cite{wise,Luckow2017}, which could only handle  simple, concrete costs.

Scalability is achieved in two ways. First, constraint solving is turned off during concolic execution, and is used only for generating new inputs, when expanding the tree. This is done selectively, guided by the heuristics. Furthermore, the tree is saved in memory, and expanded incrementally, only when new inputs are generated.

We demonstrate how \tool{Badger} is able to find a large number of inputs that trigger worst-case complexity in complex applications, and we show that it performs better than its parts (i.e. fuzzing and symbolic execution separately).

We note that we are not the first to use fuzzing and symbolic execution in a complementary manner. Tools such as \tool{Mayhem}~\cite{Cha:2012:UMB:2310656.2310692} and \tool{Driller}~\cite{DBLP:conf/ndss/StephensGSDWCSK16} are prominent examples. \tool{Mayhem} won first place at the recent DARPA Cyber Challenge~\cite{darpa_cgc_archive}, and \tool{Driller} later matched those results. There are many other similar hybrid approaches, which we discuss in Section~\ref{sec:relwork}. However, all these previous hybrid approaches aim to increase code coverage and we believe that we are the first to explore this combination for complexity analysis. The recent work on \tool{SlowFuzz}~\cite{Petsios2017} explores fuzzing for worst-case analysis (WCA). Although that work addresses binaries (and not \textsc{Java}\xspace) and uses a different fuzzer~\cite{libfuzzer}, it is similar in spirit to our \tool{KelinciWCA} tool. For this reason, we include in our experiments \textsc{Java}\xspace versions of the same (or similar) examples as in \cite{Petsios2017}. While we can not compare \tool{Badger} to \tool{SlowFuzz} directly, we compare \tool{Badger} with \tool{KelinciWCA}, which should give an indication whether a combination of \tool{SlowFuzz} with symbolic execution could achieve similar benefits.

\subsection{Fuzz Testing Java Programs with Kelinci}
\label{sec:kelinci}

\tool{Kelinci}
is an interface to execute \tool{AFL} on \textsc{Java}\xspace programs~\cite{ccs2017}.  It adds \tool{AFL}-style instrumentation to Java programs and communicates results back to a simple C program that interfaces with the \tool{AFL} fuzzer.
This in turn behaves as a C program that was instrumented by one of \tool{AFL}'s compilers.

The first step when applying \tool{Kelinci} is to add \tool{AFL}-style instrumentation to a Java program. \tool{AFL} uses a 64 kB region of shared memory for communication with the target application. Each basic block is instrumented with code that increments a location in the shared memory bitmap corresponding to the branch made into this basic block.
The Java version of this instrumentation is the following, which amounts to 12 bytecode instructions after compilation:

\begin{verbatim}
Mem.mem[id^Mem.prev_location]++;
Mem.prev_location = id >> 1;
\end{verbatim}

In this example, the \clazz{Mem} class is the Java representation of the shared memory and also holds the (shifted) \prog{id} of the last program location. The \prog{id} of a basic block is a compile-time random integer, where $0 \leq id < 65536$ (the size of the shared memory bitmap). The idea is that each jump from a block $id1$ to a block $id2$ is represented by a location in the bitmap $id1 \oplus id2$. While obviously there may be multiple jumps mapping to the same bitmap location, or even multiple basic blocks which have the same \prog{id}, such loss of precision is considered rare enough to be an acceptable trade-off for efficiency. The reason that the \prog{id} of the previous location is shifted is that, otherwise, it would be impossible to distinguish a jump $id1 \rightarrow id2$ from a jump $id2 \rightarrow id1$. Also, tight loops would all map to the location 0, as $id \oplus id = 0$ for any $id$.
Instrumentation is added to the program at compile time using the \tool{ASM} bytecode manipulation framework~\cite{asm}.

Based on this lightweight instrumentation, \tool{AFL} will prioritize input files that lead to newly covered branches as ancestors for the next generation of input files. \tool{Kelinci} was used to find bugs in various Java applications, including \tool{Apache Commons Imaging} and \tool{OpenJDK 9}~\cite{ccs2017}.

\iffalse
\begin{figure}
	\centering \includegraphics[width=.95\columnwidth,trim={25pt 35pt 205pt 250pt},clip]{KelinciDesign.pdf}
\caption{Overview of the design of \tool{Kelinci}.}
\label{fig:kelinci}
\end{figure}

The overall design of \tool{Kelinci} is depicted in Fig.~\ref{fig:kelinci}. The first step when applying the tool is to add \tool{AFL}-style instrumentation to a Java program. \tool{AFL} uses a 64 kB region of shared memory for communication with the target application. Each basic block is instrumented with code that increments a location in the shared memory bitmap corresponding to the branch made into this basic block.

The Java version of this instrumentation is the following, which amounts to 12 bytecode instructions after compilation:

\begin{verbatim}
Mem.mem[id^Mem.prev_location]++;
Mem.prev_location = id >> 1;
\end{verbatim}

In this example, the \clazz{Mem} class is the Java representation of the shared memory and also holds the (shifted) \prog{id} of the last program location. The \prog{id} of a basic block is a compile-time random integer, where $0 \leq id < 65536$ (the size of the shared memory bitmap). The idea is that each jump from a block $id1$ to a block $id2$ is represented by a location in the bitmap $id1 \oplus id2$. While obviously there may be multiple jumps mapping to the same bitmap location, or even multiple basic blocks which have the same \prog{id}, such loss of precision is considered rare enough to be an acceptable trade-off for efficiency. The reason that the \prog{id} of the previous location is shifted is that, otherwise, it would be impossible to distinguish a jump $id1 \rightarrow id2$ from a jump $id2 \rightarrow id1$. Also, tight loops would all map to the location 0, as $id \oplus id = 0$ for any $id$.

Instrumentation is added to the program using the \tool{ASM} bytecode manipulation framework~\cite{asm}. Basic blocks are instrumented as described, the \clazz{Mem} class is added, as well as a TCP server component, which handles communication with the C side and execution of the target application on incoming files.

\tool{AFL} expects two pieces of information from an instrumented application. First, the application should be running a fork server, which responds to requests from the fuzzer to fork the process and run the forked process on the provided input file. Second, the application is expected to connect to the shared memory and write to locations corresponding to branches in the program. The \prog{interface.c} component implements a fork server that is identical to the one in programs instrumented by an \tool{AFL} compiler. When a request to fork comes in, it creates a fork of itself that sends the provided file over to the Java side, receives the result (shared memory plus error status) once the run is done, writes results to shared memory and crashes if the Java program resulted in an exception escaping the \method{main} method.

For a given input file generated by the fuzzer, the interaction between the C and Java sides is as follows:
\begin{enumerate}
	\item \prog{interface.c} receives a fork request from \tool{AFL}.
	\item One of the forked \prog{interface.c} processes loads the provided input file, the other keeps running the fork server.
	\item The former \prog{interface.c} process sends the provided input file over a TCP connection to the \tool{Kelinci} server.
	\item The \tool{Kelinci} server receives the incoming request and enqueues it.
	\item The \tool{Kelinci} server processes the request by writing the incoming input file to disk, starting a new thread in which the \method{main} method of the target application is called on the provided input and monitoring it. If the thread throws an exception that escapes \method{main}, it is considered a bug. If the thread does not terminate within a given time-out, it is considered a hang.
	\item The \tool{Kelinci} server communicates the results back to the C side. The shared memory bitmap is sent over the TCP connection, as well as the status (\prog{OK}, \prog{ERROR} or \prog{TIMEOUT}).
	\item On the C side, the received bitmap is written to shared memory. Depending on the received status, the program exits normally, aborts or keeps looping until \tool{AFL} hits its time-out.
\end{enumerate}

To use the tool, the user first runs the \clazz{Instrumentor} on the target
application. Next, the user starts the \tool{Kelinci} server in the instrumented
program. Finally, the user executes \tool{AFL} on \prog{interface.c}. The fuzzer is unaware that it is actually analyzing a Java program.
\fi

\section{Related Work}
\label{sec:relwork}

\tool{SlowFuzz}~\cite{Petsios2017} is a fuzzer based on \tool{LibFuzzer}~\cite{libfuzzer} that prioritizes inputs that lead to increased execution times. The tool is similar to our \tool{KelinciWCA} component, although it addresses a different programing language. Our evaluation is partially based on the \tool{SlowFuzz} evaluation and not surprisingly results obtained with \tool{KelinciWCA} are similar to those for \tool{SlowFuzz}. Furthermore, our experiments with \tool{Badger} indicate that a combination of \tool{SlowFuzz} with symbolic execution would achieve similar benefits.

Several tools explore the combination of symbolic execution with fuzzing. All these tools aim to increase coverage while our goal is to generate inputs that excersise behaviors that increase resource consumption, leading to significant technical differences.

\tool{EvoSuite}~\cite{evosuite} is a test-case generation tool for \textsc{Java}\xspace, based on evolutionary algorithms and dynamic symbolic execution. Unit tests are generated via random mutation, recombination and selection and are evaluated with respect to a given fitness function (typically a coverage metric). When a change in fitness is observed after mutation of a certain primitive value, the variable this value is assigned to is deemed important and dynamic symbolic execution is invoked with this variable as a symbol.

\tool{SAGE} (Scalable Automated Guided Execution)~\cite{Godefroid:2012:SWF:2090147.2094081} extends dynamic symbolic execution
with a \emph{generational search} that, instead of negating only the final condition of a complete symbolic execution, negates all conditions on the path. Solving the resulting path conditions results in a large number of new test inputs.
\tool{SAGE} is used extensively at Microsoft where it has been successful at finding many security-related bugs.

\tool{Mayhem}~\cite{Cha:2012:UMB:2310656.2310692} is a symbolic execution engine that aims to find security vulnerabilities in binaries.
A \emph{Concrete Executor Client} (CEC) explores paths concretely and performs a dynamic taint analysis. When a basic block is reached that contains tainted instructions, it is passed to the \emph{Symbolic Executor Server} (SES) that is running in parallel. After symbolic execution, the SES instructs the CEC on a particular path to execute.
\tool{Mayhem} was combined with the \tool{Murphy} fuzzer and won the 2016 DARPA Cyber Grand Challenge~\cite{darpa_cgc}.

\tool{Driller}~\cite{DBLP:conf/ndss/StephensGSDWCSK16} is another promising tool that combines the \tool{AFL} fuzzer with the \tool{angr} symbolic execution engine and that has achieved similar results to Mayhem.
It is very similar to our approach, in that it executes a fuzzer and symbolic execution engine in parallel, combining their strengths and overcoming their weaknesses. However, while \tool{Driller} is optimized for uncovering new branches, we focus on worst-case analysis.

Symbolic execution was used before for worst-case analysis~\cite{wise,Luckow2017}. \tool{WISE}~\cite{wise} analyzes programs for small input configurations using concolic execution and attempts to {\em learn} a path policy that likely leads to worst-case executions at any size. This policy is then applied to programs that have larger input configurations, to {\em guide} the symbolic execution of the program. \tool{SPF-WCA}~\cite{Luckow2017} uses \tool{SPF} to perform a similar analysis with more sophisticated path policies, which take into account the {\em history} of executions and the calling context of the analyzed procedures. In addition, \tool{SPF-WCA} also uses function fitting to obtain estimates of the asymptotic complexity. Both WISE and SPF-WCA require to perform exhaustive symbolic execution for large enough input sizes to obtain good policies, which may not be feasible in practice. Furthermore, both techniques only consider one input parameter for size and usually require some manual fine tuning (e.g. for \tool{SPF-WCA} manually decide the size of the history).
In contrast, our technique uses a combination with fuzzing to avoid a full exhaustive symbolic execution and is fully automatic (except for the creation of drivers that are necessary for all of these approaches). Furthermore, \tool{Badger} enables analysis with input-dependent costs, using a novel maximization technique. This significantly broadens the application scope of \tool{Badger} w.r.t. previous techniques, which only support simple, fixed costs associated with each program path.

Load testing~\cite{LoadTesting} employs symbolic execution to perform an {\em iterative} analysis for increasing exploration depth,
with pruning of paths with low resource consumption.
That work could not be used directly for finding the worst-case algorithmic behavior,
since all the paths are explored up to the same depth, and therefore have the same number of steps.

Probabilistic symbolic execution is used in~\cite{ICSE16}
to infer the performance distribution of a program according to given usage profiles.
Although promising, the technique does not yet scale for large programs, due to
the more involved probabilistic computation.

Static analysis is used in~\cite{Gulwani09,GulavaniGulwani08,AlbertAGP11a,ShkaravskaKerstenVanEekelen2010}
to compute conservative bounds on looping programs. In contrast to this work, our tool produces actual inputs that expose vulnerabilities, but can not provide guarantees on worst-case bounds. There is also a large body of work on worst-case execution time (WCET) analysis---in particular for real-time systems~\cite{malikbook,reinhardbook,automaticloopboundwcet,automaticloopbound2}. Unlike our work, these techniques typically assume that loops have finite bounds and are independent of input, and estimate worst-case execution for specific platforms.

{\it Profilers}~\cite{gprof,SevitskyPK01, AmmonsCGS04} are typically used for performance analysis of programs, but are inherently limited by the quality of tests used. In our work we aim to automatically generate input data triggering a diverse set of executions, including the worst-case ones.

\subsection{Symbolic Execution and Symbolic PathFinder}
\label{sec:spf}

Symbolic execution~\cite{King:1976:SEP:360248.360252,Clarke:1976:SGT:1313320.1313532}
is a program analysis technique which executes programs on symbols in place of concrete inputs. When a decision is encountered, all branches are explored. Branch conditions are aggregated into a \emph{path condition}, a constraint over the symbolic program inputs. Solving the path condition using an off-the-shelf solver (e.g. \tool{Z3}~\cite{DeMoura:2008:ZES:1792734.1792766}) can detect infeasible paths as well as generate actual inputs (solutions of the constraint) that lead execution down the corresponding path. A typical use-case for symbolic execution is test-case generation~\cite{Clarke:1976:SGT:1313320.1313532,Cadar2008,Braione:ISSTA:2017}. In many cases, it can also detect faults directly~\cite{Godefroid:2012:SWF:2090147.2094081,Chipounov:2011:SPI:1950365.1950396}. There are many other use-cases, including security testing~\cite{Cha:2012:UMB:2310656.2310692,DBLP:conf/ndss/StephensGSDWCSK16,Pasareanu:2016:MSC} and complexity analysis~\cite{wise,Luckow2017}.

The research presented in this paper is based on \tool{Symbolic PathFinder} (\tool{SPF}), which extends the \tool{Java PathFinder} framework with a symbolic execution mode \cite{Pasareanu:2013:ASE}. This mature symbolic execution tool works on \tool{Java ByteCode} and has support for most language features such as all primitive data types, strings, complex data structures, library calls, etc. It interfaces with a variety of solvers to solve constraints generated by symbolic execution.

redpajama_set_name: RedPajamaArXiv


text:
export default = {
    getDefaultProps: function () {
        return {
            bsStyle: 'warning'
        };
    }
};

redpajama_set_name: RedPajamaGithub


Do not discard bad diffracting crystals! They can be very useful, too. Try to improve diffraction by crystal annealing, varying the solvent content or use your initial crystals for seeding.
Crystal dehydration - the most effective method to improve the diffraction properties once you have crystals. Try our Dehydration Salts & Crystal Dehydration and Salvage Kit!


text:
Los Angeles Celebrity Homes
Los Angeles Filming Locations
Seven Psychopaths Makers Talk About Shooting LA For LA
By Adrian Glick Kudler Oct 5, 2012, 3:12pm PDT
Can we make this mandatory for every film that comes out, please? (Just spitballing: maybe as a condition of film tax credits?) The people behind Seven Psychopaths have released a little video about the locations used in the movie--they shot all over LA, from the beach to the tar pits to Echo Park, and in and around Joshua Tree (apparently you cannot blow up a car in a national park). The movie tells a classic LA story: it "follows a struggling screenwriter (Colin Farrell) who inadvertently becomes entangled in the Los Angeles criminal underworld after his oddball friends (Christopher Walken and Sam Rockwell) kidnap a gangster's (Woody Harrelson) beloved Shih Tzu." It was directed by In Bruges's Martin McDonagh.
· Seven Psychopaths [Facebook]
Next Up In Los Angeles Celebrity Homes
Jason Segel is selling his Los Feliz house for $2.8M
Hollywood Hills home previously owned by Mark Ruffalo, Zooey Deschanel asking $3M
Peep Dita Von Teese's decadent Los Feliz home
Topanga retreat once owned by Neil Young seeks $1.45M
'Hunger Games' actress selling tranquil two-bedroom in Mount Washington for $1.1M
Dr. Phil's house with gun-filled dining room for sale for $5.75M

redpajama_set_name: RedPajamaCommonCrawl


text:
Suspect barricaded with child in Lancaster mobile home park
by The AV Times Staff • December 21, 2022 7 Comments
Fernando Fierro barricaded himself and his year-old child inside the Lido Estates mobile home park in Lancaster on Wednesday, Dec. 21, CHP officials said. [Image by BRYAN HALL]
LANCASTER – An armed man who led authorities on a high-speed pursuit, during which he allegedly fired shots at pursuing officers, was barricaded in a Lancaster mobile home park all day Wednesday with a year-old infant.
The incident began around 11:45 p.m. Tuesday, Dec. 20, when California Highway Patrol officers attempted a traffic stop on a white 2022 Kia SUV that was traveling at 132 mph on SR-14, according to a California Highway Patrol report.
"The suspect driver failed to yield to officers and a pursuit ensued, traversing several county roads and freeways into the Antelope Valley area," the CHP report states.
"During the pursuit, the suspect called the Los Angeles County Sheriff's Department and informed them that he had an infant child and a weapon in the vehicle. The suspect also said he would shoot at the CHP officers if they continued engaging in the pursuit," the CHP report states.
At about 12:42 a.m. Wednesday, the suspect, identified as Fernando Fierro, fired shots at pursuing officers, but no officers or vehicles were struck by the gunfire, according to the CHP report.
The suspect eventually came to a stop outside the Lido Estates mobile home park in the 2500 block of East Avenue I and exited the SUV while holding a gun to the infant's head, CHP officials said. The suspect then backed slowly into a mobile home, beginning the standoff, which was continued until late Wednesday afternoon.
The CHP contacted the Los Angeles County Sheriff's Department, which dispatched a SWAT team to the scene.
Elijandra Rosas, who identified herself as the suspect's aunt, told reporters at the scene that Fernando Fierro had his year-old son with him inside the mobile home. She issued a plea for him to surrender.
"Fernando, please get out of the house, please. I want to see you. I want to see the baby. … Please think of your mom and your dad and your sister and your brother, Fernando, please," she said.
As of late Wednesday afternoon, Fierro was still barricaded in the mobile home park and negotiators were trying to find a way to talk to him since he left his phone in his vehicle.
Editor's note: We will update this story when more information becomes available.
Filed Under: Crime/ Safety, Lancaster
7 comments for "Suspect barricaded with child in Lancaster mobile home park"
CarGuy says
That's amazing. Unbelievable even.
A Kia SUV went 132 mph…
Tim Scott says
There are some steep downhill sections on the 14.
Dalaran says
Yep, was going downhill, pushed by wind and it was previously owned by Chuck Norris.
Darwin says
I know unbelievable! I'm going to complain to Chevrolet why my brand new 2022 Sierra taps out at 108!!
Lancaster Man says
Fernando is just misunderstood.
PhukTimScott says
Hey Tim Scott, I suppose this is an imaginary incident of violence and these supposed victims are paid actors right? Because according to you, crime is not so bad…
LOL…Sonya, no matter how many times you try the "paid actors" bit you are never going to get people to confuse me with Alex Jones.
Crime rates are vastly exaggerated by people with a vested interest in scaring the public. Stating that fact doesn't equate to wing nut Alex and your favorite "news sources" making absurd claims that a crime didn't happen.


text:
Q: Encountered this error while trying to code a thread: Not an enclosing class I have this class called AnnouncementsActivity and I run a thread in its onCreate function this way:
 new GetAnnouncements().execute();

But, when I try to compile the code I get this error:
 Error:(42, 59) error: not an enclosing class: AnnouncementsActivity

Double clicking the error takes me to the doInBackground function of class GetAnnouncements:
  Toast toast = Toast.makeText(AnnouncementsActivity.this, announcementsList.get(1).get("baslik"), 5);

I execute the thread from AnnouncementsActivity, why does it say AnnouncementsActivity is not an enclosing class?

A: An enclosing class is an outer class that contains an inner class. In other words both classes are defined in the same java file and the 'inner' one is defined inside the 'outer' one.
Whether you call/create it from another doesn't make it an enclosing clsas.
You don't show enough code to show what you are trying to do but AnnouncementsActivity.this looks very wrong.

A: Are u change Toast inside to runonUIthread then solve ur problem.
runOnUiThread(new Runnable() {
                 public void run() {
                     Toast.makeText(AnnouncementsActivity.this, announcementsList.get(1).get("baslik"), 5).show();
                }
            });

try after say response .

redpajama_set_name: RedPajamaStackExchange


text:
FIGHT SEVEN SPRINGS WATER GRAB
ACTION ALERT: IT'S TIME TO FIGHT
Wise Water Words
Our Fundraising
Friends & Resource Links
Education & Activism
Education Through Art
OSFR Supports These Organizations
Our Favorite Blogs
River Businesses
Alachua County Environmental Protection Department
Our Elected State Officials
Our County Commissioners
Find Your Florida House Representative
Find Your Florida Senator
Find Your U.S. House Representative
Find Your U.S. Senator
Support OSFR
I'd like to volunteer!
I'd like to be on the board!
Make Our River Smile with Amazon Smile :)
About Our Santa Fe River, Inc.
WARNING ON SAFETY OF OUR DRINKING WATER
The Florida Springs Institute has sent out the following press release regarding the quality of our drinking water.
FLORIDA SPRINGS INSTITUTE: ELEVATED NITRATE NITROGEN LEVELS FOUND IN FLORIDA'S DRINKING WATER SUPPLY
Contact: Dr. Robert Knight
GAINESVILLE, FL – The Howard T. Odum Florida Springs Institute (FSI) is concerned about elevated levels of nitrate nitrogen in much of the Floridan Aquifer (see attached maps). This same Floridan Aquifer is the source of water feeding our 1,000+ artesian springs in North Florida and is the principal supply of potable water for the region.
A substantial portion of the water in the Floridan Aquifer has been contaminated with nitrate by human activities, including the use of fertilizers and the disposal of wastewater in areas where the aquifer is most vulnerable. Resulting nitrate concentrations are well above harmful thresholds (numeric nitrate standard of 0.35 mg/L) in most of Florida's natural springs.
Elevated groundwater nitrate concentrations are also acutely toxic to humans. In some areas of North Florida, nitrate concentrations in drinking water wells are already above the safe drinking water standard of 10 mg/L.
While groundwater nitrate concentrations are rising throughout the region, most areas are still below this acute threshold. However, a growing body of medical literature is indicating that there may be chronic effects of nitrate at levels at or below those found in community drinking water supplies, including municipalities and in bottled drinking water. Human health issues that have been found to be exacerbated by sub-lethal nitrate concentrations in drinking water include various forms of human cancer and birth defects.
For these reasons the Florida Springs Institute is collecting, analyzing, and publishing nitrate data from a variety of potable groundwater suppliers.
For the health of our springs and our human population, we believe it is critical that the public is aware of this growing threat. If you are concerned about the health of our springs and the availability of clean water for drinking and bathing, let your local and state leaders know.
Click Here to Become a Member!
IS THE SANTA FE RIVER WORTH $10 TO YOU?
Update Thermometer
Eye of the Aquifer • photo by John Moran and David Moynahan


Do you have a business and want to build a more personal relationship with your customers? Telling your story visually can help create a meaningful connection to your audience.
Your family's story told through photos of your everyday life. No posing, no fancy outfits, you be you and I capture what makes your family special.
You are art, and your talent deserves to be captured by a photographer who knows how to share the story of your passion with the world.
Going beyond just photos, a visual storyteller can capture the virtue of a person or moment without words. Whether for social media, your website, or even your portfolio, storytelling images can help you better connect to your audience.
Documenting the every-day is what I do, and I want to tell your story.
Because I offer a variety of services, please check out the individual services pages or send me a short message below to receive information on pricing.
Hi, I'm Morgan. I was photojournalist and editor for newspapers for over a decade, telling daily stories about my community and the people who make it unique. I'm also a mom, a life-longer dancer, and a dog lover. The best moments are captured when people can be themselves, so I want everyone to feel comfortable in front of my lens. Your story is important to me, and I look forward to helping you tell it.
Below you'll find my personal documentary work. I'm currently working on a 365 project documenting my family's everyday life. You can follow along on Instagram at @morgpet.


Fed's January meeting pushed benchmark U.S. Treasury yields to a four-year high. US stocks closed lower yesterday in a rocky session. Asian equities follow the footsteps today.
The dollar index traded near a one-week high today near the 90 mark, rising after minutes of the Federal Reserve's January meeting showed policymakers were more confident of the need to keep raising interest rates..
The Indian Unit is seen opening at 65.05 and expected to trade bullish between 64.80-65.20 for the day.
Wall Street surged on tech lift for the fifth straight session which lifted Asian equities on the last day of the week, but trading in the region subdued with many markets shut for the Lunar New Year holiday. Dow and S&P 500 break above their 50-day moving averages as bond yields hit fresh multiyear highs.
BOJ's Kuroda says powerful easing still required for now & BOJ will communicate its intentions on easing clearly when the time comes, to avoid market turbulence. Yen is constantly strengthening.
Oil prices edged higher today as the dollar stood near a three-year low in subdued Asian trade.
The dollar index grew weak near a three-year low today, headed for its biggest weekly loss in nine months, as a slew of bearish factors offset support for the U.S. currency from rising Treasury yields amid firming inflation.
The Indian Unit is seen an opening around 63.85 and is expected to play the 63.75-64.00 range for the day.
Wallstreet rally after the stronger than expected US inflation data last trading day while Asian markets rose following the footprint of global markets, the yield on the 10-year US Treasury note jumped to 2.92 percent on Wednesday, its highest levels in four years.
U.S equities edged up overnight for a third straight session with all the three major indices closing in the green.
Investors remain on edge ahead of U.S inflation report that could soothe, or inflame fears of faster rate hikes globally.
Asian equities turned mixed in early morning session as investors remain cautious ahead of U.S inflation data.
US equities ended a wild week where there was a bit of buying seen towards the end that pushed the indices up, but still recorded their worst week in two years with investors looking forward for markets to continue being volatile.
Asian markets were mixed early on Monday while oil prices edged up after recording six straight days of declines.
The Dollar index recorded its strongest week in almost 15 months. Inflation readings from the U.S., UK, and Germany along with world's leading central banks' actions on easy policies will be driving the index this week.
The Indian unit is seen opening around 64.35 with expectations to play the 64.20-64.50 range for the day.
US equities closed lower after an early surge as a spike in yields spooked investors of aggressive monetary tightening by Federal Reserve while Asian shares mostly climbed on Thursday after last session's rally faltered late in the day.
The dollar index closed above psychologically mark of 90 while U.S 10Y treasuries quote at 2.81%, the dollar gained against Euro and Japanese Yen in early Asian trade and remained flat against Pound.
Wall Street plunges on Monday with indices slumping more than four percent as Dow Jones notched its biggest intraday decline in history with a nearly 1,600-point drop, single-day percentage drops since August 2011, a period of stock-market volatility marked by the downgrade of the United States' credit rating and the eurozone debt crisis.
Asian market crash more than 3 percent with Nikkei falling above 5% after the global sell-off and rise in yields.
Wallstreet fell notably as markets to add to the large losses set last week after the Bureau of Labour Statistics said the US economy added 200,000 jobs in January. That number was higher than the 180,000 jobs expected by economists in a Reuter's poll while Asian markets traded lower on today's morning following the footprint of US markets.
The dollar index against a basket of major currencies traded marginally higher after U.S. payrolls report showed wages growing at their fastest pace in more than 8-1/2 years and fuelling inflation expectations.
Asian market trading lower early Friday after Wall Street closed mixed and yields on US government debt rose in the last session.
US Treasury yields continued to climb after economic indicators seemed to confirm the Fed's inflation views.
The Indian Rupee expected to open above 64.05 against previous closing of 64.01 and likely to trade volatile in the range of 63.85-64.25 with equities market & bond yield giving further direction in the pair.


text:
Achieving glycemic control in elderly patients with type 2 diabetes: A critical comparison of current options
Du, Y. F., Ou, H. Y., Beverly, E. A. & Chiu, C. J., 2014 Nov 18, In: Clinical Interventions in Aging. 9, p. 1963-1980 18 p.
Achieving customer satisfaction through product-service systems
Pan, J. N. & Nguyen, H. T. N., 2015 Nov 16, In: European Journal of Operational Research. 247, 1, p. 179-190 12 p.
Product-service Systems
Achieving a firm's competitive advantage through dynamic capability
Lin, C. & Tsai, H. L., 2016 Jul 4, In: Baltic Journal of Management. 11, 3, p. 260-285 26 p.
Dynamic Capabilities
Organizational Performance
Achieve white light by utilizing interface defects on simplified ultraviolet organic light emitting diodes
Wenq, H. L., Chu, S-Y., Kao, P. C. & Chen, Y. C., 2012 Dec 1, Society for Information Display - 19th International Display Workshops 2012, IDW/AD 2012. p. 1042-1043 2 p. (Proceedings of the International Display Workshops; vol. 2).
Organic light emitting diodes (OLED)
rubrene
Ultraviolet Rays
Ultrathin films
Achievement of high CO2 concentration in the flue gas at slightly positive pressure during oxy-coal combustion in a 300 kWth furnace
Chi, C. C., Lin, T. H., Huang, W. C., Hou, S. S. & Wang, P. Y., 2015 Aug 17, In: Fuel. 160, p. 434-439 6 p., 9515.
Coal combustion
Flue gases
Achievement goals and achievement emotions: (Poster)
Chang, Y. F., Cherng, B-L. & Peng, S-L., 2014, the 2014 Meeting of the American Psychological Association. Washington, DC, USA
A chemical engineering perspective on the origins of life
Grover, M. A., He, C. Y., Hsieh, M. C. & Yu, S. S., 2015 Jun 1, In: Processes. 3, 2, p. 309-338 30 p.
Biological materials
A check-in shielding scheme against acquaintance inference in location-based social networks
Chen, B. H., Li, C. T. & Chuang, K. T., 2019 Nov 1, In: World Wide Web. 22, 6, p. 2321-2354 34 p.
A chatbot using LSTM-based multi-layer embedding for elderly care
Su, M. H., Wu, C. H., Huang, K. Y., Hong, Q. B. & Wang, H. M., 2018 Apr 10, Proceedings of the 2017 International Conference on Orange Technologies, ICOT 2017. Wang, L., Dong, M., Lu, Y. & Li, H. (eds.). Institute of Electrical and Electronics Engineers Inc., p. 70-74 5 p. (Proceedings of the 2017 International Conference on Orange Technologies, ICOT 2017; vol. 2018-January).
A charge-pump-based current feedback method for amoled displays
Lin, C-L., Chang, F. C., Lai, P. C., Chen, P. S. & Chang, W. Y., 2013 Oct 21, In: IEEE/OSA Journal of Display Technology. 9, 10, p. 783-786 4 p., 6588572.
A characteristic and kinetic study on photo-degradation of dimethyl disulfide by S/ZN Co-doped TiO2 under visible light
Lin, Y. H., Chang, C. W., Lin, C. Y. & Chu, H., 2014 Jan 1, p. 612-617. 6 p.
dimethyl disulfide
Photodegradation
A channel selection method for device to device (D2D) communication using the mobile edge computing (MEC) paradigm
Huang, C-M., Cheng, R. S. & Chen, H. H., 2019 Jan 1, Wireless Internet - 11th EAI International Conference, WiCON 2018, Proceedings. Pang, A-C., Deng, D-J., Lin, C-C. & Chen, J-L. (eds.). Springer Verlag, p. 173-182 10 p. (Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST; vol. 264).
Long Term Evolution (LTE)
A channel busy rate-aware congestion avoidance mechanism for the wireless ad hoc network
Huang, C-M., Lin, C. Y. & Lin, S. Y., 2012 Nov 27, PE-WASUN'12 - Proceedings of the 9th ACM Symposium on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks. p. 113-116 4 p. (PE-WASUN'12 - Proceedings of the 9th ACM Symposium on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks).
A CFD study on the performance of a passive ocean plastic collector under rough sea conditions
Shaw, H. J., Chen, W. L. & Li, Y. H., 2019 Sep 15, In: Ocean Engineering. 188, 106243.
A CFD parametric study on the performance of a low-temperature-differential γ-type Stirling engine
Chen, W. L., Yang, Y. C. & Salazar, J. L., 2015 Dec 1, In: Energy Conversion and Management. 106, p. 635-643 9 p.
Stirling engines
A CFD model for simulating wave run-ups and wave loads in case of different wind turbine foundations influenced by nonlinear waves
Lin, Y. H., Chen, J. F. & Lu, P. Y., 2017 Jan 1, In: Ocean Engineering. 129, p. 428-440 13 p.
Acetylcorynoline attenuates dopaminergic neuron degeneration and α-synuclein aggregation in animal models of Parkinson's disease
Fu, R. H., Wang, Y. C., Chen, C. S., Tsai, R. T., Liu, S. P., Chang, W. L., Lin, H. L., Lu, C. H., Wei, J. R., Wang, Z. W., Shyu, W. C. & Lin, S. Z., 2014 Jul, In: Neuropharmacology. 82, p. 108-120 13 p.
acetylcorynoline
Synucleins
Nerve Degeneration
Dopaminergic Neurons
Acetylcholinesterase inhibitors and memantine in bipolar disorder: A systematic review and best evidence synthesis of the efficacy and safety for multiple disease dimensions
Veronese, N., Solmi, M., Luchini, C., Lu, R. B., Stubbs, B., Zaninotto, L. & Correll, C. U., 2016 Jun 1, In: Journal of Affective Disorders. 197, p. 268-280 13 p.
Memantine
Cholinesterase Inhibitors
Acetylation of retinal histones in diabetes increases inflammatory proteins: Effects of minocycline and manipulation of histone acetyltransferase (HAT) and histone deacetylase (HDAC)
Kadiyala, C. S. R., Zheng, L., Du, Y., Yohannes, E., Kao, H. Y., Miyagi, M. & Kern, T. S., 2012 Jul 27, In: Journal of Biological Chemistry. 287, 31, p. 25869-25880 12 p.
Acetylation
Acetophenones isolated from acronychia pedunculata and their anti-proliferative activities
Ito, C., Matsui, T., Ban, Y., Wu, T. S. & Itoigawa, M., 2016 Jan 23, In: Natural Product Communications. 11, 1, p. 83-86 4 p.
Acronychia pedunculata
Acetophenones
Acetophenones from acronychia pedunculata and their cancer chemopreventive activity
Ito, C., Hosono, M., Tokuda, H., Wu, T. S. & Itoigawa, M., 2016, In: Natural Product Communications. 11, 9, p. 1299-1302 4 p.
Acetaminophen and/or antibiotic use in early life and the development of childhood allergic diseases
Wang, J. Y., Liu, L. F., Chen, C. Y., Huang, Y. W., Hsiung, C. A. & Tsai, H. J., 2013 Aug 1, In: International Journal of Epidemiology. 42, 4, p. 1087-1099 13 p., dyt121.
A cell wall protein (YqgA) is genetically related to the cell wall-degrading DL-endopeptidases in Bacillus subtilis
Hashimoto, M., Fujikura, K., Miyake, Y., Higashitsuji, Y., Kiriyama, Y., Tanaka, T., Yamamoto, H. & Sekiguchi, J., 2014, In: Bioscience, Biotechnology and Biochemistry. 78, 8, p. 1428-1434 7 p.
N-Acetylmuramoyl-L-alanine Amidase
Bacilli
Endopeptidases
A cell-based systems biology assessment of human blood to monitor immune responses after influenza vaccination
Hoek, K. L., Samir, P., Howard, L. M., Niu, X., Prasad, N., Galassie, A., Liu, Q., Allos, T. M., Floyd, K. A., Guo, Y., Shyr, Y., Levy, S. E., Joyce, S., Edwards, K. M. & Link, A. J., 2015 Feb 23, In: PloS one. 10, 2, e0118528.
influenza vaccination
Accurate gradient approximation for complex interface problems in 3D by an improved coupling interface method
Shu, Y. C., Chern, I. L. & Chang, C. C., 2014 Oct 15, In: Journal of Computational Physics. 275, p. 642-661 20 p.
Interface Problems
Accurate Forecasting of the satellite-derived seasonal caspian sea level anomaly using polynomial interpolation and holt-winters exponential smoothing
Imani, M., You, R-J. & Kuo, C-Y., 2013 Aug 1, In: Terrestrial, Atmospheric and Oceanic Sciences. 24, 4 PART1, p. 521-530 10 p.
Accurate audio-to-score alignment for expressive violin recordings
Syue, J. L., Su, L., Lin, Y. J., Li, P. C., Lu, Y. K., Wang, Y. L. & Su, A. W. Y., 2017 Jan 1, Proceedings of the 18th International Society for Music Information Retrieval Conference, ISMIR 2017. Cunningham, S. J., Duan, Z., Hu, X. & Turnbull, D. (eds.). International Society for Music Information Retrieval, p. 250-256 7 p. (Proceedings of the 18th International Society for Music Information Retrieval Conference, ISMIR 2017).
Distance Function
Musical Terms
Accuracy validation of adjuvant! online in Taiwanese breast cancer patients - A 10-year analysis
Yao-Lung, K., Dar-Ren, C. & Tsai-Wang, C., 2012, In: BMC Medical Informatics and Decision Making. 12, 1, 108.
antineoplaston A10
Neoplasm Grading
Accuracy of ultrasonography and magnetic resonance imaging in diagnosing carpal tunnel syndrome using rest and grasp positions of the hands
Horng, Y. S., Chang, H. C., Lin, K. E., Guo, Y. L., Liu, D. H. & Wang, J. D., 2012 Aug, In: Journal of Hand Surgery. 37, 8, p. 1591-1598 8 p.
Hand Strength
Accuracy of source localization for eccentric inspiraling binary mergers using a ground-based detector network
Pan, H. P., Lin, C. Y., Cao, Z. & Yo, H. J., 2019 Dec 2, In: Physical Review D. 100, 12, 124003.
Fisher information
Accuracy assessment of digital surface model and orthophoto derived from UAV photogrammetry
Qoyimah, S. & Tseng, Y. H., 2017 Jan 1.
Accuracy and Safety of Using Customized Guiding Templates for Cervical Pedicle Screw Insertion in Severe Cervical Deformity, Fracture, and Subluxation: A Retrospective Study of 9 Cases
Wu, H. H., Su, I., Hsieh, C., Fang, J. & Chang, C., 2018 Aug 1, In: World Neurosurgery. 116, p. e1144-e1152
Accuracy analysis of a multi-camera imaging system mounted on a UAS after image mosaicking
Li, Y. T., Jhan, J. P. & Rau, J-Y., 2015 Jan 1.
Systematic errors
Accuracy analyses of a fixed-wing UAV equipped with SPAN CPT for direct georeferencing and DSM generation
Rau, J-Y., Chen, C. Y., Jhan, J. P., Liu, K. & Lee, W., 2013 Jan 1, 34th Asian Conference on Remote Sensing 2013, ACRS 2013. Asian Association on Remote Sensing, p. 512-519 8 p. (34th Asian Conference on Remote Sensing 2013, ACRS 2013; vol. 1).
Fixed wings
Accumulator-based output selection for test response compaction
Lien, W. C., Lee, K-J., Hsieh, T. Y., Chien, S. S. & Chakrabarty, K., 2012 Sep 28, p. 2313-2316. 4 p.
Accumulated mental stress study using the meridians of traditional chinese medicine with photoplethysmography
Chen, C. C., Lin, S. C., Young, M. S. & Yang, C. L., 2014 Nov 1, In: Journal of Alternative and Complementary Medicine. 20, 11, p. 860-867 8 p.
Photoplethysmography
Spectrum Analysis
Accounting for time dependence in large-scale multiple testing of event-related potential data1
Sheu, C. F., Perthame, É., Lee, Y. S. & Causeur, D., 2016 Mar, In: Annals of Applied Statistics. 10, 1, p. 219-245 27 p.
Multiple Testing
Accounting for site-selection bias in before-after studies for continuous distributions: Characteristics and application using speed data
Kuo, P. & Lord, D., 2013 Mar 1, In: Transportation Research Part A: Policy and Practice. 49, p. 256-269 14 p.
Accounting disclosure quality, capital market intensity and national productivity
Lin, Y-C., Chang, H., Chen, J. & Wu, G. S., 2014 Sep 1, In: Annals of Operations Research. 221, 1, p. 239-254 16 p.
Disclosure Quality
Physical Capital
Accounting and finance theory and practice: Future development
Huang, H. W., 2018 Jun, In: Asia Pacific Management Review. 23, 2, 1 p.
Accountability and Relational Governance: The case of Brainport Eindhoven, the Netherlands
Huang, W-J., 2015 Jul, AESOP Annual Congress 2015 . Prague, Czech Republic
Accommodation Strategies Employed by Non-native English-Mediated Instruction (EMI) Teachers
Tsai, Y. R. & Tsou, W., 2015 Jun 15, In: Asia-Pacific Education Researcher. 24, 2, p. 399-407 9 p.
Access to the Public Home Health Care and the Use of Health Care Services among the Elderly: Are They Substitutes or Complements
Liu, Y., 2014 Jun, 5th Biennial Conference of the American Society of Health Economists.
Access to Books Matters: Cultural Ambassadors and the Editorial Task Force
Wu, A. M. Y., 2019 May 1, In: Reading Teacher. 72, 6, p. 683-688 6 p.
Cultural Ambassador
Access control mechanism using flexible multi-layer structure for mesh-based P2P live streaming systems
Sue, C. C., Chuang, K. C. & Hsu, C. Y., 2016 Jul 25, In: International Journal of Communication Systems. 29, 11, p. 1740-1760 21 p.
Analytical models
Multilayers
Accelerometer-based energy expenditure estimation methods and performance comparison
Chuang, F. C., Yang, Y-T. C. & Wang, J-S., 2013 Jul, Proceedings of 2nd International Conference on Advances in Computer Science and Engineering (CSE 2013) . Los Angeles, USA
Accelerative expansion and DDT of stoichiometric ethylene/oxygen flame rings in micro-gaps
Wu, M. H. & Kuo, W. C., 2013 Jan 11, In: Proceedings of the Combustion Institute. 34, 2, p. 2017-2024 8 p.
Acceleration of Monte-Carlo simulation on high performance computing platforms
Wang, P. J., Liu, C. Y., Tu, C. H., Lee, C. P. & Hung, S. H., 2018 Oct 9, Proceedings of the 2018 Research in Adaptive and Convergent Systems, RACS 2018. Association for Computing Machinery, Inc, p. 225-230 6 p. (Proceedings of the 2018 Research in Adaptive and Convergent Systems, RACS 2018).
Acceleration of modern acidification in the South China Sea driven by anthropogenic CO2
Liu, Y., Peng, Z., Zhou, R., Song, S., Liu, W., You, C. F., Lin, Y. P., Yu, K., Wu, C. C., Wei, G., Xie, L., Burr, G. S. & Shen, C. C., 2014 Jun 3, In: Scientific reports. 4, 5148.
Acceleration of MAP-EM algorithm via over-relaxation
Tsai, Y. J., Huang, H. M., Fang, Y. H. D., Chang, S. I. & Hsiao, I. T., 2015 Mar 1, In: Computerized Medical Imaging and Graphics. 40, p. 100-107 8 p.
2-aminoethylmethacrylate
Computer-Assisted Image Processing
Image reconstruction


BBC 'All Together Now' finalists, The Sundaes, are quite simply the 'biggest' girl group in town!
This unique act combines stunning vocals, sensational choreography with superb comedy timing, not to mention the flamboyant costumes.
We're starting 2019 off as we mean to go on with unique, fresh and exciting events!
Why not stay the night? £85.00 bed and breakfast for a double room.


text:
Q: finding nearest occurrence of timestamp in a column based on conditions I have a dataframe in R which is similar to this :
time                value
13-07-2019 02:34:28 9.07
13-07-2019 02:34:57 8.87
13-07-2019 02:35:27 9.34
13-07-2019 02:46:08 X
13-07-2019 02:46:38 4.5
13-07-2019 02:47:08 6.66
13-07-2019 02:47:37 8.7
13-07-2019 02:48:08 4.7
13-07-2019 02:48:39 X
13-07-2019 02:49:08 7.8
13-07-2019 02:49:39 9.8
13-07-2019 02:50:38 X
13-07-2019 02:51:08 2.34
13-07-2019 02:51:39 5.67
13-07-2019 02:52:08 X
13-07-2019 02:52:38 8.766
13-07-2019 02:53:08 5.456
13-07-2019 02:53:38 X
13-07-2019 02:54:08 6.544
13-07-2019 02:54:39 9.877
13-07-2019 02:55:08 X

What I want is to find out the nearest time when I have x. For example:
13-07-2019 02:35:27 9.34
13-07-2019 02:46:08 X
13-07-2019 02:46:38 4.5

Here nearest time is for X is 13-07-2019 02:46:38
13-07-2019 02:53:08 5.456
13-07-2019 02:53:38 X
13-07-2019 02:54:08 6.544

Here it is 13-07-2019 02:53:08
I need to consider only the time within 30 seconds. If it is exceeding 30 sec, I will assume that the time is previous 30 sec
13-07-2019 01:53:08 5.456
13-07-2019 02:53:38 X
13-07-2019 04:54:08 6.544

Here I need to limit the time to : 13-07-2019 02:53:08 which is the lower 30 second because it difference exceeds 30sec.
Finally I need to get a dataframe with n number of values where n is the number of times I have x in my dataframe value column

A: Since you tagged your question with data.table,
here's one option assuming you have one
(named dt here)
and your times are strings
(if already POSIXct, skip the first line):
dt[, time := as.POSIXct(time, format = "%d-%m-%Y %H:%M:%S")]

max_difftime <- as.difftime(30L, units = "mins")
lambda <- function(rolled_time, x_time) {
    invalid <- abs(rolled_time - x_time) > max_difftime
    if (any(invalid)) {
        rolled_time[invalid] <- x_time[invalid] - max_difftime
    }
    rolled_time
}

dt[value != "X"
   ][dt[value == "X"],
     .(x_time = i.time, time = lambda(x.time, i.time)),
     on = "time",
     roll = "nearest"]
                x_time                time
1: 2019-07-13 02:46:08 2019-07-13 02:46:38
2: 2019-07-13 02:48:39 2019-07-13 02:49:08
3: 2019-07-13 02:50:38 2019-07-13 02:51:08
4: 2019-07-13 02:52:08 2019-07-13 02:51:39
5: 2019-07-13 02:53:38 2019-07-13 02:53:08
6: 2019-07-13 03:24:40 2019-07-13 02:54:40

I modified your sample data a bit so that the last row would have 03:24:40.
The code performs a rolling join between the rows where value is X and the rest of the rows,
looking for the nearest time.
The lambda function compares the nearest time found
(exposed as x.time by data.table)
with the time where X is found
(exposed as i.time by data.table),
and adjusts values where the time difference is greater than 30 minutes.
I added the x_time column just to show the comparison,
you can remove it if you don't need it.

A: If you are just counting the number of X without non-NA values within +-30 seconds, you can do
1) Using non-equi join:
DT[!is.na(value)][
    DT[is.na(value), .(now=time, start=time-30, end=time+30)],
    on=.(time>=start, time<=end), .(time=now, .N>0), by=.EACHI][,
        sum(V2)]

2) Using between:
start <- DT2[!is.na(value), time-30]
end <- DT2[!is.na(value), time+30]
DT2[is.na(value), sum(sapply(time, function(x) !any(between(x, start, end))))]

data:
library(data.table)
DT <- fread("time,value
13-07-2019 02:34:28,9.07
13-07-2019 02:34:57,8.87
13-07-2019 02:35:27,9.34
13-07-2019 02:46:08,NA
13-07-2019 02:46:38,4.5
13-07-2019 02:47:08,6.66
13-07-2019 02:47:37,8.7
13-07-2019 02:48:08,4.7
13-07-2019 02:48:39,NA
13-07-2019 02:49:08,7.8
13-07-2019 02:49:39,9.8
13-07-2019 02:50:38,NA
13-07-2019 02:51:08,2.34
13-07-2019 02:51:39,5.67
13-07-2019 02:52:08,NA
13-07-2019 02:52:38,8.766
13-07-2019 02:53:08,5.456
13-07-2019 02:53:38,NA
13-07-2019 02:54:08,6.544
13-07-2019 02:54:39,9.877
13-07-2019 02:55:08,NA
14-07-2019 01:53:08,5.456
14-07-2019 02:53:38,NA
14-07-2019 04:54:08,6.544")
DT[, time := as.POSIXct(time, format = "%d-%m-%Y %H:%M:%S")]
DT2 <- copy(DT)


beginning of works for Thessaloniki's metro.
more kilometers (16 more stations) by 2012.
in city center and 2,000 for motorcycles.
in a 9.5 kilometer line serving 14 stations.
The cost of this project is about €1bn.
ago and has been postponed in 2003.
are expected to last six years.