\chapter{Related Work}
%TODO: kurze einleitung

\section{Overview}
Because replaying application runs is important in order to be able to debug or test applications, there exist many techniques that implement capture and replay. One of the basic steps in order to be able to capture and replay an application is to distinct between the applications deterministic core (the \emph{observed part}) and the non-deterministic environment like user input, network or external storage (the \emph{unobserved part}). Capture and replay techniques capture the interactions between observed and unobserved part during the \emph{capture phase} so that they can replay these interactions on the observed part during the \emph{replay phase}.

% -------
% Dieser Teil koennte sonst noch irgendwo untergebracht werden.
%--------
% In general, capture and replay can be divided into two phases: The \emph{capture phase}, where the application is run and the information that is needed for replaying the application is captured and the \emph{replay phase} where the application is replayed based on this information.
% 
% During \emph{capture phase}, the capture and replay implementation needs to record the information that will later be needed to replay the observed part. In general this is at least all information that is passed from the unobserved part to the observed part. The information is captured by some management code that was introduced by the capture and replay framework (\figref{fig:GenericCrStructure_capture}).

% 
% During \emph{replay phase} the management code needs to replace the unobserved part ( 
% \figref{fig:GenericCrStructure_replay}) in order to replay the run of the observed part. Depending on the part of the application that was defined to be unobserved, the management part can act both as a driver (e.g. in the case of mouse events) and stub (e.g. in the case of a network socket). 
% %Schema dazu: Capture phase & Replay phase , observed & unobserved part && log
% \begin{figure}[h]
%   \centering
%   \includegraphics[width=0.4\textwidth]{illustrations/capture_and_replay_generic_structure_replay}
%   \caption{Generic structure of a capture and replay technique - replay phase}
%   \label{fig:GenericCrStructure_replay}
% %\includegraphics{illustrations/capture_and_replay_generic_structure}
% \end{figure}

Different implementations make different assumptions about what is deterministic and what changes its behaviour throughout different runs of the application. Therefore they define different portions of the program as observed and unobserved part. In the following we will categorize the different implementations based on which part is defined to be unobserved.

\section {Capturing User Input}
The best known capture and replay technique is the capturing of user input, which is most often used for GUI testing. Here, keyboard and mouse events are considered to come from the unobserved part. The exact location where these events are captured may vary (inside the application or through the operating system), but the advantages and limitations mostly stay the same. Usually, capture and replay of user input is used for regression testing. In that setup, the tester executes a sequence of actions on the application's GUI, while capturing is enabled. These recorded actions can be replayed on the application in order to check if there were regressions. Abbot \cite{abbot} is an example of such a tool, although it offers more features than only capture and replay of user interactions. %TODO: wie funktioniert Abbot?

Compared to our implementation, the capturing of user inputs has many drawbacks due to its simplicity. Because only the user input is considered to belong to the unobserved part, it can only replay programs that interact with other parts of the environment (like file system and network) as long as these interactions are deterministic. One strategy is to restore the environment before every run of the application, but this is not always easy (e.g. if a random generator is used). If the assumption, that the observed part behaves deterministically does not hold, this results in an incorrect replay of the application. Because our implementation makes it possible to individually define the applications observed and unobserved part, it can also replay programs that depend on other parts of the non-deterministic environment than only the user input.

\section {Capturing Interactions with Libraries}
JRapture \cite{jrapture} uses an approach that has the potential of replaying more complex applications. JRapture is a tool for capturing and replaying Java applications in the field. In addition to capturing and replaying, it also offers a profiling interface that permits the program to be instrumented for profiling in the replay phase. JRapture uses the whole Java API as the unobserved part of the application. The technique is able to capture interaction between the Java API and the rest of the program by manual instrumentation of the Java API classes. JRapture supports multithreaded applications, but it can not guarantee a deterministic replay of concurrent applications.

Unlike our technique, JRapture relies on a manually modified version of the core libraries. Programs that need to be captured and replayed need to use a special version of the Java API.  Therefore programs which interact with the environment through other mechanisms than the Java API (for example through the Java Native Interface JNI) can not be supported without additional manual instrumentations.

%genauer veranschaulichen, was complete und incomplete ist.
JRapture captures the complete information that is passed between the observed and unobserved part, in contrast to our approach that only captures necessary information.

\section {Capturing Interactions with the Scheduler}
The techniques presented so far did not consider thread scheduling as another source of non-determinism. DejaVu \cite{dejavu}, a capture and replay tool for Java, considers thread scheduling as its only source of non-determinism, thus thread scheduling belongs to its unobserved part.\\
It is not easy to instrument the scheduler in order to detect thread switches, because threads are often scheduled by the operating system. DejaVu therefore introduces the concept of \emph{logical thread schedule} which is a simplified version of the real thread schedule (the \emph{physical thread schedule}). The \emph{logical thread schedule} contains enough thread schedule information to reproduce the execution behaviour of the program under the assumption that the thread schedule is the only source of non-determinism. By detecting some critical events during capture phase such as accesses to shared variables, and synchronization events, DejaVu is able to deduce the logical thread schedule.

DejaVu concentrates on enabling a determistic replay of multi-threaded programs that do not have any other source of non-determinism than the thread scheduler. Our technique does not take the non-determinism of the thread scheduler into account, it concentrates on all other interactions with the environment instead. DejaVu and selective capture and replay, as described by Joshi and Orso \cite{orso05may, orso06}, are othogonal and could be combined in order to allow replays of general multi-threaded programs. 

\section{Selective Capture Replay}
In contrast to other techniques, \emph{selective capture and replay} \cite{orso05may} implemented for Java, offers the possibility to make an own definition of observed and unobserved part of the system. Observed and unobserved part are both defined as a set of classes. The technique captures interactions between observed and unobserved part using automated code instrumentation.

There are two implementations of selective capture and replay: SCARPE, the original work of Joshi and Orso \cite{orso05may} and JINSI by Orso, Joshi, Burger and Zeller \cite{JINSI}, which minimizes failure inducing component interactions, that were captured using selective capture and replay.

We transfer the concept from the original paper \cite{orso05may} to Eiffel; our implementation instruments code in a different way and adds some Eiffel specific modifications.