\section{Design Overview}
\label{sec:design}

\noindent FGFT is a system to tolerate faults
in drivers using a {\em pay-as-you-go} model based on checkpoints for
recovery. This system protects code from faults at the granularity of
a single thread executing a single entry point.  \toolshort\ recovers
from any failures that occur during the function.  This can greatly
reduce the cost of isolating and tolerating faults because far less
code is affected.

We list four goals of providing fine-grained fault tolerance:

\begin{enumerate}
\item {\em Class independent.}  Isolation and recovery should be
  independent of the driver-kernel interface and should be able to recover
  driver actions from proprietary commands.
%
\item {\em Low infrastructure.} Little new code should be added to the
  kernel in support of \toolshort.
%
\item {\em Pay-as-you-go.} \toolshort\ should not have a fixed minimum
  overhead of isolation or monitoring driver behavior. Furthermore,
  programmer effort should only be required when fault tolerance
  is desired.
%
\item {\em Fast recovery.}  \toolshort\ should restore driver
  functions quickly after a failure without affecting other threads
  concurrently executing in the driver.
\end{enumerate}
The first goal enables \toolshort\ to apply to a broad range of
drivers, and the second reduces the adoption cost for an operating
system. Pay-as-you-go ensures that for high-performance drivers,
tolerating faults in code off the critical path has little cost.  Fast
recovery enables its use in latency-sensitive environments.

The two major components of \toolshort\ are an isolation mechanism to
prevent a faulty driver from corrupting the OS and to detect failures,
and a recovery mechanism to restore the driver to a functioning state
after a failure. We begin a discussion of our fault model to
motivate our design choices.

\subsection{Fault Model}

A driver entry point is a driver function invoked by the kernel or applications to access
specific driver functionality. Each driver registers a set of functions as entry points,
such as to initialize the device or transmit a packet. Driver entry points can be invoked by
applications multiple times in arbitrary order. Hence, drivers should not make assumptions
about the order or past history of these invocations. \toolshort\ provides fault tolerance
at the granularity of a single entry point into a driver. In contrast, past systems treat
the entire driver as a component with internal state. 

As the driver executes, the \toolshort\ isolation mechanism enforces fine-grained memory
safety. It ensures that the driver entry point is only allowed to access 
data passed to the driver and its stack; access to anything else will be treated as a fault. 
\toolshort\ detects faults in driver entry points in three ways. First, \toolshort\
detects memory failures (such as null pointer dereferences) and reading/writing unintended
kernel and driver structures. Second,  \toolshort\ uses marshaling to copy data in and out
of the driver. Type errors and malformed structures that cause the marshaling to fail will
be detected, although errors with compatible types (such as treating an array of bytes as
an array of longs), will not be. \toolshort\ on its own does not provide any semantic
checks to enforce driver invariants. Hence, driver faults must be detected within the
entry point where they occur. Otherwise, failures that that are triggered when one entry point
improperly sets a flag that another read and faults cannot be tolerated. Third, \toolshort\
catches processor exceptions such as  NULL pointer exception, general
protection fault, alignment fault, divide error (divide by zero), missing segments, and
stack faults. It triggers recovery if an exception arises within an isolated driver entry point.

%\fixme{
%I gather that you are assuming every driver invocation is state-less, i.e., one invocation does not affect the next. However, consider the following rather-common scenario where you have a server and muliple worker threads have been spwaned to handle multiple client requests.
%}

We design for an open-source environment, and therefore trust the
compiler to produce code that correctly accesses the stack. We also
assume that the driver is unable to hang or damage the device,
although it may misconfigure the device.

A key benefit of \toolshort\ is that by operating on specific entry
points it can be selective about what code should be hardened against
faults.  We call the entry points to be isolated {\em suspect}. The
suspect code can execute in isolation while the remainder of the
driver executes in the kernel at full speed. Hence, \toolshort\ is
useful when specific driver code is known to have problems, such as
just-patched code or code with known but un-patched vulnerabilities. 
We identify at least three cases where a fine-grained model is useful:

\begin{enumerate}
\item {\em Untested code}: Device drivers often contain untested code
 such as chipset-specific code or recovery code that can be invoked safely
 using \toolshort.
%
\item {\em Statically found bugs}: Often  static
  analysis tools identify hard to find/trigger driver bugs with
  substantial false positive rates. \toolshort\ can be integrated with
  existing static analysis tools until a fix is issued, which often
  takes considerable time. This approach  limits the
  overhead to just the buggy code, just when it contains known bugs.
%
\item {\em Runtime monitoring tools}: Runtime monitoring tools flag
  incoming requests based on their parameters, such as a specific {\tt
    ioctl} command code, or are enabled at run time through module
  parameters~\cite{liblit:2005} or
  security tools~\cite{paxson:1998}. \toolshort\ can dynamically
  decide whether to execute code in isolation or unsafely at full speed.

\end{enumerate}

In our evaluation we analyze a list of bugs and
find that they only affect 14\% of all driver entry points. Hence,
limiting the cost of fault tolerance to affected entry points can be useful.
We now describe the two major components of \toolshort: isolation and
recovery.

\subsection{Fine-Grained Isolation}
\toolshort\ provides isolation by forcing suspect code to operate on a
{\em copy} of driver and kernel data. This ensures that anything the
entry point does will not be seen by other threads or the kernel
until it successfully completes, and allows quick recovery after a
failure by deleting the copy.  Thus, \toolshort\ creates a clean copy of
data needed for a driver entry point on every invocation, which
consists of all data referenced by the entry point: parameters, global
driver variables, and global kernel variables.

We use entry points as the granularity of isolation because it closely
matches internal driver structure: they provide a natural boundary for
returning errors after a fault, and drivers already synchronize
concurrent invocation of entry points. If two driver threads cannot
run concurrently in the driver, then driver synchronization ensures
that one of them blocks until the other successfully completes.  Thus,
\toolshort\ reuses existing synchronization mechanisms to ensure that
when suspect code runs, no other threads are active in the
driver. This ensures that any changes to device state will not be seen until the
entry point completes successfully or it fails and recovery completes.

\toolshort\ provides entry-point isolation with a copy-in/out model of
driver and kernel state when suspicious entry-points are
invoked. \toolshort\ uses static analysis and code-generation to
generate another kernel module that contains suspect entry points
instrumented for memory safety. \toolshort\ also generates
communication code containing marshaling routines to copy driver and
kernel state necessary for executing these entry points in
isolation. Since the static analysis to marshal the data structures
required by the isolated copy can be imprecise, \toolshort\ requires a
programmer to annotate ambiguous data types in the driver code.  In
order to provide even finer control over when to provide fault
tolerance, \toolshort\ automatically inserts taps, which are
predicates that can decide at runtime whether to invoke the normal or
fault-tolerant version of an entry point.

\toolshort\ detects faults through run-time memory safety checks that
detect access to unreachable addresses -- memory not passed as a
parameter or allocated by the entry point. Since, \toolshort\
generates the code for copy-in/out, it is able to provide fine-grained
memory safety (base and bound
validation~\cite{nagarakatte:softbound:pldi:2009}). Furthermore, for
failure detection, \toolshort\ interposes on kernel trap handlers
and detects if the faults originate from the suspicious entry-points
and accordingly triggers recovery.

\begin{figure}
\centering
\includegraphics[keepaspectratio=true,width=3in]{figures/pdf/devicestartup.pdf}
\caption{\small \bf Modern devices perform many operations during initialization such as setting up
kernel and device structures based on chipset and device features, checksumming device ROM data,
various device tests followed by driver initialization and configuration.}
\label{fig:devicestartup}
\vspace{-0.2in} 
\end{figure}


\subsection{Checkpoint based Recovery}
\toolshort\ relies on checkpoints prior to a driver entry point for
recovery. Unlike log-based recovery, which requires knowing how to
replay requests, checkpoints can restore state independent of how a
function modifies driver state. For example, a checkpoint of a device
prior to an \codesm{ioctl} call allows its state to be recovered no
matter what the call does.

Log-based recovery is also slow
enough that the technique may not be useful in latency-sensitive
environments. The primary delay comes from probing the device all over
again which cold boots the device and performs the initialization
steps as shown in Figure~\ref{fig:devicestartup}.
For example, during initialization a network driver probes for
the device, verifies EEPROM contents, tests the device, and registers
the device with the kernel.

The checkpoint of the driver's state in memory is captured
automatically through the copy-in/out model of
invocation. Suspect code always executes on a copy of the driver
state, so the original data is unmodified and need not be
restored. The major challenge, though, is the {\em device state},
which may be modified unpredictably by the driver. We therefore
require that drivers provide a facility for capturing and restoring
device state. Prior to invoking suspect code, \toolshort\ can take a
checkpoint, and following a failure, it can restore the checkpoint.

An appealing approach is to treat devices like memory and copy
memory-mapped I/O regions. However, reading registers may have side
effects such as clearing counters. In addition, some devices overlay two
logical registers, one for read and one for write, at the same
address.  Instead, we take inspiration from code {\em already present}
in many drivers that must perform {\em nearly the same} task as
checkpoint/restore: power management.

The functionality provided by power management, to suspend a device
before entering a low power mode and restoring it when transitioning
to high power mode is similar to what is required to support device
checkpoints. We reuse the suspend/resume code by separating code
that supports saving state to memory from the code that actually
suspends the device. Similarly, we identify code required for
restoring this state. In Section~\ref{sec:device}, we describe in detail how power
management code can be re-factored to support checkpoint/restore in
device drivers and how existing driver synchronization can be used to
arbitrate device access.

\subsection{Design Summary}
\toolshort\ improves the state of art in driver recovery and meets its
goals. \toolshort\ provides class-independent driver recovery
with checkpoints as opposed to restarting the driver. Hence,
\toolshort\ discards failed requests and retains proprietary driver
state such as {\em ioctls} that were issued before the
failure. 

\toolshort\ requires very little kernel code, as the code for
isolation is generated automatically and the recovery code requires
only small modifications to existing driver code. The annotation cost for
isolation and recovery is only required when a driver needs fault
tolerance. Only when a suspicious request executes does FGFT execute 
it in isolation, thus limiting isolation overhead to these requests.
Compared to \toolshort, Nooks~\cite{swift03} and SUD~\cite{Boyd-Wickizer:2010} require a new kernel
subsystem and writing and maintaining wrappers around the
driver-kernel interface.

There is also no recovery overhead of monitoring correctly
executing requests at  {\em all} times since driver recovery is based on checkpoints.
Finally, \toolshort\ provides fast recovery since it does not restart
the driver and re-execute the complicated device probe
routines. The device state is restored from a checkpoint, so  recovery
is an order of magnitude faster as we demonstrate in our
evaluation in Section~\ref{sec:evaluation}.






