\documentclass{sig-alternate}

%------------------------------------------------------------------------------
%                                  Preamble. 
%------------------------------------------------------------------------------
%
%\usepackage[small,compact]{titlesec}
%\usepackage{times}
%\usepackage{pifont}
%\usepackage{txfonts}  % These save space
%\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{styles/fancyhdr}
\usepackage{fancyvrb}
\usepackage{listings}
%\usepackage[top=1in,right=1in,left=0.75in,bottom=0.75in]{geometry} 
\usepackage{xcolor}

% Note:  Supplying these parameters to the hyperref package
% generates corrupt postscript according to pdf2ps, and it doesn't
% work on Windows.  The ``black'' keyword causes these programs trouble.

%\usepackage[pdftex, colorlinks=true, citecolor=black, linkcolor=black,
%  citebordercolor=black, urlcolor=black]{hyperref}

% \usepackage{hyperref}

\usepackage[pdftex, colorlinks=true, citecolor=black, linkcolor=black,
  citebordercolor={0 0 0}, urlcolor=black]{hyperref}


%\pdfpageheight=11.25in
%\pdfpagewidth=8.5in

% Page layout. CFP says we need 1 inch margins.
%\setlength{\textheight}{9.25in}
%\setlength{\textwidth}{7in}
%\setlength{\columnsep}{0.33in}


\input{macros.tex}

%\usepackage{styles/tweaklist}
% this sets the spacings in the itemize environment
%\renewcommand{\itemhook}{\setlength{\topsep}{0pt}%
%  \setlength{\itemsep}{0pt}%
%  \setlength{\parsep}{0ex}%
%}

% this sets the spacings in the enumerate environment
%\renewcommand{\enumhook}{\setlength{\topsep}{0pt}%
%  \setlength{\itemsep}{0pt}%
%  \setlength{\parsep}{0ex}%
%}

% this sets the spacings in the description environment
%\renewcommand{\descripthook}{\setlength{\topsep}{0pt}%
%  \setlength{\itemsep}{0pt}%
%  \setlength{\parsep}{0ex}%
%}

%\pagestyle{plain}
%\pagestyle{fancyplain}
%\lhead{}
%\chead{}
%\rhead{}
%\lfoot{}
%\cfoot{}
%\rfoot{}
\renewcommand{\headrulewidth}{0pt}


%------------------------------------------------------------------------------
%                              Title and Authors.
%------------------------------------------------------------------------------
\begin{document}
\conferenceinfo{SOSP'09,} {October 11--14, 2009, Big Sky, Montana, USA.} 
\CopyrightYear{2009}
\crdata{978-1-60558-752-3/09/10} 

\title{Tolerating Hardware Device  Failures in Software
\numberofauthors{1}
\author{
\alignauthor
Asim Kadav, Matthew J. Renzelmann and Michael M. Swift\\
\affaddr{Computer Sciences Department, }  \\
\affaddr{University of Wisconsin-Madison} \\
  \small \textsf{\{kadav,mjr,swift\}@cs.wisc.edu}}
}
\date{}

\widowpenalty=5000
\clubpenalty=5000

\maketitle

\begin{abstract}
%   \small  -- Not short of space - yet.
\input{abstract}

\end{abstract}

\category{D.4.5}{Operating Systems}{Reliability}
\category{D.3.4}{Programming Languages}{Processors} 
\terms{Reliability, Design}
\keywords {Device Drivers, Reliability, Recovery, Debugging, Code Generation}
%------------------------------------------------------------------------------
%                                Main Contents. 
%------------------------------------------------------------------------------
%\pagestyle{fancyplain}
\vspace{0.5in}
%\begin{abstract}
%
%  \small 
%
%  Hardware devices can fail, but many drivers assume they do not.
%  When confronted with real devices that misbehave, these assumptions
%  can
%  lead to driver or system failures. While major operating system and
%  device
%  vendors recommend that drivers detect and recover from hardware
%  failures, we find that there are many
%  drivers that will crash or hang when a device
%  fails. Such bugs cannot easily be detected by regular stress testing
%  because the failures are induced by the device and not the software
%  load.

%  This paper describes \toolname, a code-manipulation tool and
%  associated runtime that improves
%  system reliability in the presence of faulty devices. \toolname\ 
%  analyzes driver source code to find locations where the
%  driver incorrectly trusts  the hardware to behave. \toolname\
%  identified almost 1000 such bugs in Linux drivers with a false
%  positive rate of only 8 percent.  With the help
%  of shadow drivers for recovery,
%  \toolname\ can automatically repair  840 of
%  these bugs with no
%  programmer involvement. To facilitate proactive management of device
%  failures, \toolname\
%  locates existing
%  driver code that detects device failures and inserts missing
%  failure-reporting code. Finally, the \toolname\ runtime can detect
%  and tolerate
%  interrupt-related bugs, such as stuck or missing interrupts.
%
%\end{abstract}

\section{Introduction}
\noindent Reliability remains a paramount problem for operating systems. As
computers are further embedded within our lives, we demand higher
reliability because there are fewer opportunities to compensate for
their failure. At the same time, computers are increasingly dependent on
attached devices for the services they provide.

Applications invoke devices through device drivers. The device and
driver interact through a protocol specified by the hardware. When the
device obeys the specification, a driver may trust any inputs it
receives. Unfortunately, devices do not always behave according to
their specification. Some failures are caused by wear-out or
electrical interference~\cite{li:error-propagation:asplos:2008}. In
addition, internal software failures can occur in devices that execute
embedded firmware, sometimes up to millions of lines of
code~\cite{yang:raid-patent:2007}.

Studies of Windows servers at Microsoft demonstrate the scope of the
problem~\cite{arthur04}. In one study of Windows servers, eight
percent of systems suffered from a storage or network adapter
failure~\cite{arthur04}. Many of these failures are transient:
hardware vendors repeatedly report that the majority of returned
devices operate correctly and retrying an operation often
succeeds~\cite{arpaci01,BairavasundaramEtAl07-Sigmetrics,pinheiro:disk-failure-trends:fast:2007}.
In total, 9\% of all unplanned reboots of servers at Microsoft during
a separate study were caused by adapter or hardware failures. Most
importantly, when running platforms with {\em
  the same adapters} and software that tolerates hardware
faults, reported device failures rates drop from 8 percent to 3
percent~\cite{arthur04}. This evidence suggests that (1) {\em device
  failure is a major cause of system crashes}, (2) {\em transient
  device failures are common}, and (3) {\em drivers that tolerate
  device failures can improve reliability}. Without addressing this
problem, the reliability of operating systems is limited by the
reliability of devices.

Device hardware failures cause system hangs or crashes when drivers
cannot detect or tolerate the failure. The Linux kernel mailing list
contains numerous reports of drivers waiting forever and reminders
from kernel experts to avoid infinite
waits~\cite{lkml:tulip-driver-wait:2006}. Nevertheless, this code
persists. For example, the code below from the 3c59x.c network driver
in the Linux 2.6.18.8 kernel will loop forever if the device never
returns the right value:

{\small
\begin{verbatim}
while (ioread16(ioaddr + Wn7_MasterStatus))
        & 0x8000)
   ;
\end{verbatim}
} To address this problem, major OS vendors have issued
recommendations on how to harden drivers to device
failures~\cite{graham:windows-ft-drivers:2004,sun:hardening:drivers:2007,intel:driver-hardening:spec:2002}.
These recommendations include validating all inputs from a device,
ensuring that all code waiting for a device will terminate, and
reporting all hardware failures. Despite these recommendations, we
found that a large number of Linux drivers do not properly tolerate
hardware failures. We see two reasons for this: (1) testing drivers
against hardware failures is difficult, and (2) hardening drivers by
hand is challenging. Common testing procedures, such as stress
testing, will not detect failures related to hardware. Instead,
fault-injection testing is
required~\cite{arthur04,hanson:driver-test-patent:2005,Zhuang:ols:2003}.
Unlike other software testing, device drivers require that an instance
of the device be present, which limits the number of machines that can
run tests.

Previous work on driver fault tolerance has concentrated on two major
approaches: static bug
finding~\cite{bbc+06,br02,engler00,post:linux-sdv:ifm:2007} and
run-time fault
tolerance~\cite{williams08,erlingsson:xfi:osdi:2006,herder:driver-resilience:dsn:2007,zhou:safedrive:osdi:2006,sbl05}.
Static approaches check for bugs in the interface between the driver
and the kernel to ensure that the driver does not violate
kernel-programming rules, such as by failing to release a lock. But,
these tools do not verify that the driver validates inputs received
from the device.

Systems that tolerate faults at run time, such as
Safe\-Drive~\cite{zhou:safedrive:osdi:2006} and Nooks~\cite{sbl05},
either instrument driver code or execute it in an isolated
environment. These systems detect faults, including hardware-induced
faults, dynamically and trigger a recovery mechanism. However, these
systems have had limited deployment, perhaps due to the heavyweight
nature of the solution.

This paper presents \toolname,\footnote{Carburizing is a process of
  hardening steel through heat treatment.} a code-manipulation tool
and associated runtime that automatically {\em hardens} drivers. A
hardened driver is one that can survive the failure of its device and
if possible, return the device to full function.
\toolname\ implements three major hardening recommendations: (1)
validate  inputs from the device, (2) verify device responsiveness,
and (3) report hardware failures so an administrator can
proactively manage failing
hardware~\cite{arthur04,graham:windows-ft-drivers:2004,intel:driver-hardening:spec:2002,sun:hardening:drivers:2007}.

\toolname\ analyzes driver code to find where it accepts input from
the device. If the driver uses device data without checking its correctness,
\toolname\ modifies the driver to insert validation code. If the
driver checks device data for correctness, \toolname\ inserts code to
report a failure if the data is incorrect. Finally, the \toolname\
runtime detects stuck interrupts and non-responsive devices and causes
the driver to poll the device. To automatically repair bugs,
\toolname\ invokes a generic recovery service that can reset the
device. We rely on shadow drivers~\cite{swift06} to provide this
service.

Despite the common application of static analysis tools to the Linux
kernel~\cite{coverity04}, \toolname\ uncovers a large number of
problems. \toolname\ identified 992 bugs in existing Linux drivers
where a hardware failure may cause the driver to crash or hang. With
manual inspection of a random subset, we determined that the false
positive rate is 7.4\%, for approximately 919 true bugs
found. Discounting for false positives, \toolname\ repairs
approximately 845 real bugs by inserting code to detect hardware
failures and recover at runtime.  When run with common I/O workloads,
drivers modified by \toolname\ perform similarly to native drivers.

In the remainder of this paper, we first discuss hardware failures and
OS vendor guidelines for hardening drivers. We then present the three
major functions of \toolname\ in Sections~\ref{sec:bug-finding},
\ref{sec:reporting} and \ref{sec:recovery}.
Section~\ref{sec:performance} presents the overhead of our code
changes, and we finish with related work in
Section~\ref{sec:related-work} and conclusions.


\section{Device Hardware Failures}

\noindent In this section, we describe the problem of hardware device failures
and vendor recommendations on how to tolerate and manage device
failures.


\subsection{Failures Types}

\noindent Modern CMOS devices are prone to internal failures and without
significant design changes, this problem is expected to worsen as transistors
shrink. Prior studies indicate that these devices experience transient
{\em bit-flip} faults, where a single bit changes value; permanent
{\em stuck-at} faults, when a bit assumes a fixed value for an
extended period; and {\em bridging faults} when an adjacent pair of
bits are electrically mated, causing a logical-and or logical-or gate
between the
bits~\cite{walker:fault-lambda:icfp:2006,li:error-propagation:asplos:2008}.
Environmental conditions such as electromagnetic interference and
radiation can cause transient faults. Wear-out and insufficient
burn-in may result in stuck-at and bridging faults.

In addition, when a device contains embedded firmware, or even an
embedded operating system~\cite{yang:raid-patent:2007}, any
software-related failure is possible, such as out-of-resource errors
from memory leaks or concurrency bugs.

\paragraph {Failure manifestations}

\noindent Device drivers observe failures when they access data generated by the
device. For PCI drivers, which perform I/O through memory or I/O
ports, the driver reads incorrect values from the device. For USB
drivers, which use a request/response protocol, a device failure may
cause a response packet to contain incorrect
data~\cite{li:error-propagation:asplos:2008}. Sources at Microsoft
report that device hangs and interrupt storms are common
manifestations of faulty hardware~\cite{ganapathy:comm:2009}.

Many hardware failures are likely to manifest as corrupt values in
device registers. A single bit-flip internal to a device controller
may propagate to other internal registers before the device driver
reads a garbled value exposed through a device register. Similarly, an
internal stuck-at failure may result in a transient corruption in a
device register, a stuck value in a register, a stuck interrupt
request line, or unpredictable DMA accesses. Bugs in device firmware
may manifest as incorrect output values or timing failures, when a
device does not respond within the specified time period.

\subsection{Vendor Recommendations}

\input{figures/harden-table}

\noindent Major OS vendors provide recommendations to driver writers on how to
tolerate device
failures~\cite{arthur04,graham:windows-ft-drivers:2004,intel:driver-hardening:spec:2002,sun:hardening:drivers:2007}.
Table~\ref{table:driver-hardening} summarizes the recommendations of
Microsoft, IBM, Intel, and Sun on how to prevent faulty hardware from
causing system failures. The advice can be condensed to four major
actions:

\begin{enumerate}
\item {\em Validate.} All input from a device should be treated as
  suspicious and validated to make sure that values lie within range.
\item {\em Timeout.} All interaction with a device should be subject to
  timeouts to prevent waiting forever when the device is not responsive.
\item {\em Report.} All suspect behavior should be reported to an OS
  service, allowing centralized detection and management of  hardware failures.
\item {\em Recover.} The driver should recover from any device
  failure, if necessary by restarting the device.
\end{enumerate}


The goal of our work is to {\em automatically implement} these
recommendations. First, we seek to make drivers tolerate and recover
from device failures, so device failures do not lead to system
failures. For this aspect of our work, we focus on transient failures
that do not recur after the device is reset. Second, we seek to make
drivers report device failures so that administrators learn of transient
failures and can proactively replace faulty devices.

\toolname\ addresses {\em all} four aspects of vendor recommendations.
Section~\ref{sec:bug-finding} addresses bugs that can be found through
static analysis, including infinite polling and input validation.
Section~\ref{sec:reporting} addresses reporting hardware failures to a
centralized service. Section~\ref{sec:recovery} addresses runtime
support for tolerating device failures, including recovery, stuck
interrupts, and lost requests. The recommendations that \toolname\ can
apply automatically are marked in Table~\ref{table:driver-hardening}.
The remaining recommendations can be addressed with other techniques,
such as an IOMMU for DMA memory protection, or cannot be applied
without semantic information about the device.


\pagebreak[4]
\section{Hardening Drivers}
\label{sec:bug-finding}
\noindent This section describes how \toolname\ finds and fixes infinite polling
and input validation bugs from Table~\ref{table:driver-hardening}.
These are {\em hardware
  dependence} bugs that arise because the software depends on the
hardware's correctness for its own correctness. The goal of
our work is to (1) find places where driver code uses data originating
from a device, (2) verify that the driver checks the data for validity
before performing actions that could lead to a crash or hang, and if
not, (3) automatically insert validity or timing checks into the code.
These checks invoke a generic recovery mechanism, which we describe in
Section~\ref{sec:recovery}. When used without a recovery service,
\toolname\ identifies bugs for a programmer to fix.

\begin{figure}
\centering
\includegraphics[keepaspectratio=true,width=3in]{figures/arch.pdf}

\caption{\small \bf The \toolname\ architecture. Existing kernel
  drivers are converted to hardened drivers and execute with runtime
  support for failure detection and recovery.} 

\label{fig:architecture}
\vspace{-0.2in}
\end{figure}


Figure~\ref{fig:architecture} shows the overall architecture of our
system. \toolname\ takes unmodified drivers as input and with a set of
static analyses produces (1) a list of possible bugs and (2) a driver
with these bugs repaired, i.e. drivers that validate all input coming
from hardware before using it in critical control or data flow paths.
The \toolname\ runtime detects additional hardware failures at runtime
and can restore functionality after a hardware failure.

We implement \toolname\ with CIL~\cite{nmr+02}. CIL
reads in pre-processed C code and produces an internal representation
of the code suitable for static analysis. Tools built with CIL can
then modify the code and produce a new pre-processed source file as
output.

We next describe the analyses for hardening drivers in \toolname\ and
our strategies for automatically repairing these bugs. We experiment
with device drivers from the Linux 2.6.18.8 kernel. 

\subsection{Finding Sensitive Code}
\noindent \toolname\ locates code that is dependent on inputs from the device.
When a driver makes a control decision, such as a branch or function
call, based on data from the device, the control code is {\em sensitive}
because it is dependent on the correct functioning of the device. If
code uses a value originating from a device in an address calculation,
for example as an array index, use of the address is dependent on the
device. \toolname\ finds hardware-dependent code that is incorrect for
some device inputs.

\toolname's analyses are performed in two passes. The first pass is
common to all analyses and identifies variables that  are {\em
  tainted}, or dependent on input from the device. \toolname\ consults
a table of functions known to perform I/O, such as \codesm{readl} for
memory-mapped I/O or \codesm{inb} for port I/O. Initially, \toolname\
marks all heap and stack variables that receive results from these
functions as tainted. \toolname\ then propagates taint to variables
that are computed from or aliased to the tainted variables. \toolname\
considers the static visibility of variables but does not consider
possible calling contexts. For compound variables such as structures
and arrays, the analysis is field insensitive and assumes that the
entire structure is tainted if any field contains a value read from
the device. We find that in practice this occurs rarely, and therefore
yields a simpler analysis that is almost as precise as being sensitive
to fields.

The output of the first pass is a table containing all variables in
all functions indicating whether the variable is tainted.
\toolname\ also stores a list of tainted functions that return values
calculated from device inputs. The table from the first pass is used
by the second-pass analyses described below.


\begin{figure}[t!]
\fvset{numbers=left,numbersep=2pt,fontfamily=courier, fontsize=\footnotesize}
\LVerbatimInput{code/amd8111e.c}
%\includegraphics[keepaspectratio=true,width=3in]{figures/amd-orig.pdf}
\vspace{-0.1in}

\caption{\small \bf The AMD 8111e network driver (amd8111e.c)  can hang
  if the readl() call in line 6  always returns the same value.}

\label{fig:loop-fail}
\vspace{-0.1in}
\end{figure}

\subsubsection{Infinite Polling}
\noindent Drivers often wait for a device to enter a given state by polling a
device register. Commonly, the driver sits in a tight loop reading the
device register until a bit is set to the proper value, as shown in
Figure~\ref{fig:loop-fail}. If the device {\em never sets} the proper
value, this loop will cause the system to hang.  Driver developers
are expected to ensure these loops will timeout eventually. We find,
though, that in many cases device drivers omit the timeout code and
loops terminate only if the device functions correctly.

To identify these unbounded loops, we implement
an analysis to detect control paths that wait forever for a particular
input from the device. \toolname\ locates all loops where the
terminating conditions are tainted (\ie, dependent on the device). For
each loop, \toolname\ computes the set of conditions that cause the
loop to terminate through \codesm{while} clauses as well as
conditional \codesm{break}, \codesm{return} and \codesm{goto}
statements. If all the terminating conditions for a loop are hardware
dependent, the loop may iterate infinitely when the device misbehaves.
Figure~\ref{fig:loop-fail} shows a bug detected by our analysis. The
code in lines 5-6 can loop infinitely if \codesm{readl}, a function to
read a device register, never returns the correct value. While this is
a simple example, our analysis can detect complex cases, such as loops
that contain \codesm{case} statements or that call functions
performing I/O. 

\begin{figure}[t!]
\fvset{numbers=left,numbersep=2pt,fontfamily=courier, fontsize=\footnotesize}
\LVerbatimInput{code/pas2_card.c} 
%%\includegraphics[keepaspectratio=true,width=3in]{figures/pas-orig.pdf}
\vspace{-0.1in}
\caption{\small \bf The  Pro Audio Sound
  driver (pas2\_card.c) uses the \codesm{pas\_model} variable as an
  array index in line 9 without any checks.}

\label{fig:array-fail}
\vspace{-0.2in}
\end{figure}

                           
\subsubsection{Checking Array Accesses}

\noindent Many drivers use inputs from a device to index into an array. When the
range of the variable (\eg, 65536 for a short) is larger than the
array, an incorrect index can lead to reading an unmapped address (for
large indices) or corrupting adjacent data structures.
Figure~\ref{fig:array-fail} shows a loop in the Pro Audio sound driver
(pas2\_card.c) that does not check for bounds while accessing an
array. While many drivers always check array bounds, some drivers are
not as conscientious. Furthermore, a single driver may be inconsistent
in its checks.

We implement an analysis in \toolname\ to determine whether
tainted variables are used as array indices in static
arrays. If the array is accessed using a tainted variable, \toolname\
flags the access as a potential hardware dependence bug. The analysis can
detect when values returned by one function are used as array indices
in another. In addition, when an array index is computed from multiple
variables, \toolname\ checks whether all the input variables are untainted.

\toolname\ also detects dynamic (variable-sized) array dereferencing
with tainted variables. CIL converts all dynamic array accesses into
pointer arithmetic and memory dereferencing, so it requires a separate
analysis from static arrays (those declared as arrays with a fixed
size). In the second analysis pass, \toolname\ detects whether a
tainted variable is used for pointer arithmetic or as the address of a
memory dereference. In both cases, \toolname\ detects a potentially
unsafe memory reference. We report a bug where the pointer arithmetic
is performed rather than where a dereference occurs; this is the
location where a bounds check is required, as the offset may not be
available when memory is actually dereferenced. If the pointer is
never used, this may result in a false positive.

\begin{figure}[t!]
\fvset{numbers=left,numbersep=2pt,fontfamily=courier, fontsize=\footnotesize}
\LVerbatimInput{code/a100u2w.c}
%%\includegraphics[keepaspectratio=true,width=3in]{figures/a100-orig.pdf}
\vspace{-0.1in}

\caption{\small \bf  The \codesm{pScbIdx} variable is used in pointer
  arithmetic in line 11 without any check in the a100 SCSI driver (a100u2w.c).}

\label{fig:deref-fail}
\vspace{-0.1in}
\end{figure}

Figure~\ref{fig:deref-fail} shows driver code where unsafe data from
device is used for pointer arithmetic. At line 3, \codesm{bScbIdx} is
assigned value from the \codesm{ORC\_RD} macro, which reads a 32-bit
value from the device. At line 9, this value is used as an offset for
pointer \codesm{pScb}. If a single bit of the incoming data is
flipped, the pointer dereference in line 11 could cause memory
corruption or, if the address is unmapped, a system crash.


\begin{figure}[t!]
\fvset{numbers=left,numbersep=2pt,fontfamily=courier, fontsize=\footnotesize}
\LVerbatimInput{code/hptiop.c}
%%\includegraphics[keepaspectratio=true,width=3in]{figures/hpt-orig.pdf}
\vspace{-0.1in}

\caption{\small \bf The HighPoint RR3xxx SCSI  driver
  (hptiop.c) reads  \codesm{arg}  from the controller in line 5 and dereferences it 
  as a pointer in line 9.}

\label{fig:pointer-deref-fail}
\vspace{-0.1in}
\end{figure}

While rare, drivers may also read a pointer directly from a device.
Figure~\ref{fig:pointer-deref-fail} shows an example from a SCSI
driver where the driver reads a 64-bit pointer in lines 5 and 6 and
dereferences it in line 9. \toolname\ also flags this use of pointers
as a bug.

\subsubsection{Removing False Positives}

\noindent False positives may arise when the driver has a timeout in a loop or
validates input that our analysis does not detect. From the suspect
loops, \toolname\ determines whether the programmer has already
implemented a timeout mechanism by looking for the use of a {\em
  timeout counter}. A timeout counter is a variable that is (1) either
incremented or decremented in the loop, (2) not used as an array index
or in pointer arithmetic, and (3) used in a terminating condition for
the loop, such as a \codesm{while} clause or in an \codesm{if} before
a \codesm{break}, \codesm{goto}, or \codesm{return} statement.  If a
loop contains a counter, \toolname\ determines that it will not loop
infinitely.  We also detect the use of the kernel \codesm{jiffies}
clock as a counter.

False positives for unsafe pointer dereferencing and array indexing may
occur if the driver already validates the pointer or index with a
comparison to NULL or a shift/mask operation on the incoming pointer 
data from the device. \toolname\ does not flag
a bug when these operations occur between the I/O operation and the
pointer arithmetic or pointer dereference.

\toolname\ removes false positives that occur when a tainted variable
is used multiple times without an intervening I/O operation and when a
tainted variable is re-assigned with an  untainted value. We keep track of
where in the code a variable becomes tainted, and only detect a bug if
the pointer dereference or array index occurs after the taint.

We find that the false positive techniques have been helpful.
Identifying validity checks and repeated use of a variable reduced the
number of detected dynamic-array access bugs from 650 to 150, and the
other techniques further reduced it by almost half. For infinite
polling, these techniques identified half the results as false
positives where the driver correctly broke out of the loop.
 

\subsection{Repairing Sensitive Code}

\noindent Finding driver bugs alone is valuable, but reliability does not
improve until the bug is fixed. After finding a bug, \toolname\ in
many cases can generate a fix. Repairing sensitive code consists of
inserting a test to detect whether a failure occurred and code to
handle the failure. To recover, \toolname\ inserts code that
invokes a generic recovery function capable of resetting the hardware.
While repeating a device read operation may fix the bug, this is not
safe in general because device-register reads can have side effects.
As recovery affects performance, we ensure it will not be invoked
unless an unhandled failure occurs and the driver could otherwise
crash or hang. 

\toolname\ relies on a generic recovery function common to all
drivers. However, some drivers already implement recovery
functionality. For example, the E1000 gigabit Ethernet driver provides
a function to shutdown and resume the driver when it detects an error.
For such drivers, it may be helpful to modify \toolname\ to generate
code invoking a driver-specific function instead.

\begin{figure}[t!]
\fvset{firstnumber=1,frame=none,numbers=left,numbersep=2pt,fontfamily=courier,fontsize=\footnotesize}
\begin{Verbatim}
static int amd8111e_read_phy(.......)
{
  .
\end{Verbatim}
\vspace{-0.2in}
\fvset{firstnumber=last,frame=single,framesep=0mm}
\begin{Verbatim}
  unsigned long long delta = (cpu/khz/HZ)*2;
  unsigned long long _start = 0;
  unsigned long long _cur = 0;  
  timeout = rdstcll(start) + delta ;
\end{Verbatim}
\vspace{-0.2in}
\fvset{firstnumber=last,frame=none}
\begin{Verbatim}  
  reg_val = readl(mmio + PHY_ACCESS);
  while (reg_val & PHY_CMD_ACTIVE)  {
    reg_val = readl( mmio + PHY_ACCESS );

\end{Verbatim}
\vspace{-0.2in}
\fvset{firstnumber=last,frame=single}
\begin{Verbatim}
    if (_cur < timeout) {
        rdstcll(_cur);
    } else {
      __shadow_recover();
    }
\end{Verbatim}
\vspace{-0.3in}
\fvset{firstnumber=last,frame=none}
\begin{Verbatim}  
  .
}
\end{Verbatim}

%\fvset{numbers=left,numbersep=2pt,fontfamily=courier, fontsize=\footnotesize}
%\LVerbatimInput{code/amd8111e-fix.c}
%%\includegraphics[keepaspectratio=true,width=3in]{figures/amd-fix.pdf}
\vspace{-0.1in}

\caption{\small \bf The code from Figure~\ref{fig:loop-fail} fixed by
  \toolname\ with a timeout counter.}
\label{fig:loop-pass}
\vspace{-0.1in}
\end{figure}


\paragraph{Fixing infinite polling}
\noindent When \toolname\ identifies a loop where a driver may wait infinitely,
it generates code to break out of the loop after a fixed delay. We
selected maximum delays based on the delays used in other drivers.
For loops that do not sleep, we found that most drivers wait for two
timer ticks before timing out; we chose five ticks, a slightly longer
delay, to avoid incorrectly breaking out of loops. For loops that
invoke a sleep function such as \codesm{msleep}, we insert code that
breaks out of loops after five seconds, because the delay does not
impact the rest of the system.  This is far longer than most devices
require and ensures that if our analysis does raise false positives,
the repair will not break the driver. As shown in
Figure~\ref{fig:loop-pass}, for tight loops \toolname\ generates code
to read the processor timestamp counter before the loop and breaks out
of the loop after the specified delay. When the loop times out, the
driver invokes a generic recovery function. This repair will only be
invoked after a previously infinite loop times out, ensuring that
there will be no falsely detected failures.

\paragraph{Fixing invalid array indices}

\begin{figure}[t!]
\fvset{firstnumber=1,frame=none,numbers=left,numbersep=2pt,fontfamily=courier,fontsize=\footnotesize}
\begin{Verbatim}
static void __init attach_pas_card(...)
{
  .  
  if ((pas_model = pas_read(0xFF88)))
  {
    char  temp[100];

\end{Verbatim}
\vspace{-0.3in}
\fvset{firstnumber=last,frame=single,framesep=0mm}
\begin{Verbatim}
  if ((int )pas_model < 0 || 
      (int )pas_model >= 5) {
      __shadow_recover();
  }
\end{Verbatim}
\vspace{-0.3in}
\fvset{firstnumber=last,frame=none}
\begin{Verbatim}  
    sprintf(temp,
      "%s rev %d", 
       pas_model_names[(int) pas_model],
       pas_read(0x2789));
    .
}
\end{Verbatim}
%\fvset{numbers=left,numbersep=2pt,fontfamily=courier, fontsize=\footnotesize}
%\LVerbatimInput{code/pas2_card-fix.c}
%%\includegraphics[keepaspectratio=true,width=3in]{figures/pas-fix.pdf}
\vspace{-0.1in}

\caption{\small \bf The code from Figure~\ref{fig:array-fail} fixed by
  \toolname\ with a bounds check.}
\label{fig:array-pass}
%%vspace{-0.1in}
\end{figure}

\noindent When array bounds are known, \toolname\ can insert code to detect
invalid array indices with a simple bounds check before the array is
accessed. \toolname\ computes the size of static arrays and inserts
bounds checks on array indices when the index comes from the device.
When an array index is used repeatedly, \toolname\ only inserts a
check before the first use.

For dynamically sized arrays, the bound is not available. 
\toolname\ reports the bug but does not generate a repair. With
programmer annotations indicating where array bounds are
stored~\cite{grb08,zhou:safedrive:osdi:2006}, \toolname\ could also
generate code for dynamic bounds checking.

Figure~\ref{fig:array-pass} shows the code from
Figure~\ref{fig:array-fail} after repair. In this code, the array size is
declared statically and \toolname\ automatically generates the
appropriate range check. This check will only trigger a recovery if
the index is outside the array bounds, so it never falsely detects a
failure.



\begin{figure}[t!]
\fvset{firstnumber=1,frame=none,numbers=left,numbersep=2pt,fontfamily=courier,fontsize=\footnotesize}
\begin{Verbatim}
void hptiop_iop_request_callback( ... ) {
  .
  p = (struct hpt_iop_cmd __iomem *)req;
  arg = (struct hi_k *)
           (readl(&req->context) |
    ((u64) readl(&req->context_hi32)<<32));

  if (readl(&req->result) == IOP_SUCCESS) {
\end{Verbatim}
\vspace{-0.2in}
\fvset{firstnumber=last,frame=single,framesep=0mm}
\begin{Verbatim}
    if (arg == NULL)
      __shadow_recover();
\end{Verbatim}
\vspace{-0.3in}
\fvset{firstnumber=last,frame=none}
\begin{Verbatim}  
    arg->result = HPT_IOCTL_OK;
  }
  .
}
\end{Verbatim}

%\fvset{numbers=left,numbersep=2pt,fontfamily=courier, fontsize=\footnotesize}
%\LVerbatimInput{code/hptiop-fix.c}

%%\includegraphics[keepaspectratio=true,width=3in]{figures/hpt-fix.pdf}
\vspace{-0.1in}

\caption{\small \bf The code from Figure~\ref{fig:pointer-deref-fail}
  after repair. \toolname\ inserts a null-pointer check in line 9.}
\label{fig:pointer-deref-pass}
\vspace{-0.1in}
\end{figure}


When repairing code that reads a pointer directly from a device,
\toolname\ does not know legal values for the pointer. As result,
\toolname\ only ensures that the pointer is non-NULL. Unlike other
fixes, this only prevents a subset of crashes, because legal values of
the pointer are not known. Figure~\ref{fig:pointer-deref-pass} shows
repaired code where data from device is dereferenced.

\paragraph{Fixing driver panics} 
\noindent \toolname\ can also fix driver code
that intentionally crashes the system when hardware fails. Many
drivers invoke \codesm{panic} when they encounter abnormal hardware
situations. While OS vendors discourage this practice, it is used when
driver developers do not know how to recover and ensures that errors do
not propagate and corrupt the system. If a recovery facility is
available then crashing the system is not necessary. \toolname\
incorporates a simple analysis to identify calls to \codesm{panic},
\codesm{BUG}, \codesm{ASSERT} and other system halting functions and
replace them with calls to the recovery function.

\pagebreak[4]
\subsection{Summary}
\noindent The static analysis performed by \toolname\ finds many bugs but is
neither sound nor complete: it may produce false positives, and
identify code as needing a fix when it is in fact correct, and false
negatives by missing some bugs. Nonetheless, we find that it
identifies many true bugs.

False positives may occur when the driver already contains a validity
check that \toolname\ does not recognize. For example, if the timeout
mechanism for a loop is implemented in a separate function, \toolname\
will not find it and will falsely mark the loop as a bug. \toolname\
only detects counters implemented as standard integer types. When
drivers use custom data-types, \toolname\ does not detect the counter
and again falsely marks the loop as an error. For array indexing,
\toolname\ does not consider shift operations as a validity check
because, if the array is not a power of two in size, some index values
will cause accesses past the end of the array. 

False negatives can occur because our interprocedural analysis only
passes taint through return values. When a tainted variable is passed
as an argument, \toolname\ does not detect its use as sensitive code.
\toolname\ also cannot detect silent failures that occur when the
hardware produces a legal but wrong value, such as in incorrect index
that lies within the bounds of the array.

\subsection{Analysis Results}
\noindent We ran our code across all drivers in the Linux 2.6.18.8 kernel
distribution. In total, we analyzed 6359 source files across the
\codesm{drivers} and \codesm{sound} directories. For major driver
classes, Table~\ref{table:driver-bug-table} shows the number of bugs
found of each type. Despite analyzing over 2.8 million lines of code,
on a 2.4 GHz Core 2 processor the analysis only takes 37 minutes to
run, output repaired source files and compile the driver files.



\begin{table*}[tbp]
\centering

\begin{small}
\begin{tabular}{|l|r|r|r|r|r|}
\hline
{\bf Driver } & \multicolumn{1}{c|}{\bf Infinite Polling} &
\multicolumn{1}{c|}{\bf Static Array} &  \multicolumn{1}{c|}{\bf
  Dynamic Array} & {\bf Panic}\\ 
{\bf  Class} &  {\bf Found} &  {\bf Found}   
& {\bf Found} & {\bf Fixed} \\ 
\hline
\hline
net   & 117   & 2    &21     & 2 \\ \hline
scsi  & 298   &31    &22     & 121\\ \hline
sound & 64    & 1    &0      & 2\\ \hline
video & 174   & 0    &22     & 22\\ \hline 
other & 381   & 9   & 57    & 32\\ \hline
\hline
Total & 860   &43    & 89    & 179 \\ \hline
\end{tabular}
\end{small}
\caption{\small \bf Instances of hardware dependencies by modern Linux device
 drivers.(2.6.18.8 kernel) }
\label{table:driver-bug-table}
\vspace{-0.1in}
\end{table*}


The results show that hardware dependence bugs are wide\-spread, with
992 bugs found across a wide variety of driver classes. Of these,
\toolname\ can automatically repair the 903 infinite loop and static
array index bugs. Only the 89 dynamic-array dereferences require
programmer involvement.

We estimate the false positive rate by randomly sampling bugs and
inspecting the code. With weighted sampling across all classes of
bugs, we compute that \toolname\ is able to detect bugs at a false
positive rate of 7.4\% $\pm$ 4.3\% with 95\% confidence.For the
infinite loop bugs, we inspected 140 cases and found only 5 false
positives. In these cases, the timeout mechanism was implemented in a
function separate from the loop, which \toolname\ does not detect.
However, \toolname's timeout was {\em
    more relaxed than the driver's, and as a result did not harm the driver.}
This low false positive rate demonstrates that a fairly simple and fast
analysis can detect infinite loops with high accuracy.

For the static arrays, we randomly sampled 15 identified bugs and
found 6 true bugs that could cause a system crash if the hardware
experienced a transient failure, such as a single bit flip in a device
register. Most of the remaining false positives occurred because the
array was exactly the size of the index's range, for example 256
entries for an unsigned byte index. However, even in the case of false
positives, the code added by \toolname\ correctly checked array bounds
and does not falsely detect a failure. The only harm done to the
driver is the slight overhead of an unnecessary bounds check. More
sophisticated analysis could remove these false positives.

For dynamic arrays and memory dereferencing, we sampled 35 bugs and
found 25 real bugs for a programmer to fix. Most false positives
manifested in drivers that use mechanisms other than a mask or
comparison for verifying an index. For example, the Intel i810\_audio
driver uses the modulo operation on a dynamic array offset. The SIS
graphic driver calls a function to validate all inputs, and
\toolname's analysis cannot detect validation done in a separate
function. Better interprocedural analysis is needed to prevent these
false positives. 

Overall, we found that 498 driver modules out of the 1950 analyzed
contained bugs. The bugs followed two distributions. Many
drivers had only one or two hardware dependence bugs. The developers
of these drivers were typically vigilant about validating device input
but forgot in a few places. A small number of drivers performed very
little validation and had a large number of bugs. For example,
\toolname\ detected 24 infinite loops in the telespci ISDN driver and
80 in the ATP 870 SCSI driver.

These bugs demonstrate that language or library constructs can improve
the quality of driver code. For example, constructs to wait for a
device condition safely, with internally implemented timeouts, can
reduce the problem of hung systems due to devices. Past work on
language support for concurrency in drivers has investigated providing
similar language features to avoid correctness
violations~\cite{chandrashekaran:clarity:fse:2007} .

\subsection{Experimental Results}
\noindent We verify that the \toolname's repair transformation works by testing
it on three Ethernet drivers. Testing every driver repair is not
practical because it would require obtaining hundreds of devices. We
focus on network drivers because we have only implemented the recovery
mechanism for this driver class. We test whether \toolified\ drivers,
those modified by \toolname, can detect and recovery from hardware
faults.

Of the devices at our disposal, through physical hardware or emulation
in a virtual machine, only two 100Mbps network interface cards use
drivers that had bugs according to our analysis: a DEC DC21x4x card
using the de4x5 driver, and a 3Com 3C905 card using the 3c59x driver.
We also tested the forcedeth driver for NVIDIA MCP55 Pro gigabit
devices because it places high performance demands on the system (see
Section~\ref{sec:performance}). In the case of forcedeth, since there
are no bugs in the driver, we emulate problematic code by manually
inserting bugs, running \toolname\ on the driver, and testing the
resulting code.

We inject hardware faults with a simple fault injection tool that
modifies the return values of the \codesm{read(b,w,l)} and
\codesm{in(b,w,l)} I/O functions. We modified the forcedeth driver by
inserting code that returns incorrect output for a specific device
read operation on a device register. We then simulated a series of
transient faults in the register of interest. We injected hardware
read faults at three locations in the de4x5 driver to induce an
infinite-loop in interrupt context. The loop continued even if the
hardware returned 0xffffffff, a code used to indicate that the
hardware is no longer present in the system. We injected a similar set
of faults into the 3c59x driver to create an infinite loop in the
interrupt handler and trigger recovery. We did not test all the bugs
in each driver, because a single driver may support many devices, and
some bugs only occur for a specific device. As a result, we could not
force the driver through all buggy code paths with a single device.

In each test, we found that the driver quickly detected the failure
with the generated code and triggered the recovery mechanism. After a
short delay while the driver recovered, it returned to normal function
without interfering with applications. We stopped injecting faults in
the de4x5 and 3c59x drivers after they each recovered four times. The
forcedeth driver successfully recovered from more than ten of these
transient faults. These tests demonstrate that automatic recovery can
restart drivers after hardware failures.
\section{Reporting Hardware Failures}
\label{sec:reporting}

\noindent A transient hardware failure, even while recoverable, reduces
performance and may portend future
failures~\cite{pinheiro:disk-failure-trends:fast:2007}. As a result,
OS and hardware vendors recommend monitoring hardware failures to
allow proactive device repair or replacement. For example, the
Solaris Fault Management Architecture~\cite{solaris:fma:website} feeds
 errors reported by device drivers and other system components into
a diagnosis engine. The engine correlates failures from different
components and can recommend a high-level action, such as disabling or
replacing a device. In reading driver code, we found Linux drivers
only report a subset of errors and often omit the failure details.

When \toolname\ repairs a hardware dependence bug, it also inserts
error-reporting code. Thus, a centralized fault management system can
track hardware errors and correlate hardware failures to other system
reliability or performance problems. Currently, we use \codesm{printk}
to write to the system log, as Linux does not have a failure monitoring
service.

\begin{figure}[t!]
\fvset{numbers=left,numbersep=2pt,fontfamily=courier, fontsize=\footnotesize}
\LVerbatimInput{code/forcedeth.c}
%%\includegraphics[keepaspectratio=true,width=3in]{figures/hpt-orig.pdf}

\caption{\small \bf The forcedeth network driver polls the
  BMCR\_RESET device register until it changes state or until a
  timeout occurs.  The driver reports only a generic error message at
  a higher level and not the specific failure where it occurred.}
\label{fig:loop-terminate}
\vspace{-0.1in}
\end{figure}

To support administrative management of hardware failures, \toolname\
will also insert monitoring code into existing drivers where the
driver itself detects a failure. \toolname\ in this case relies on the
driver to detect hardware failures, through the timeouts and sanity
checks. Figure~\ref{fig:loop-terminate} shows code where the driver
detects a failure with a timeout and returns an error, but does not
report any failure. In this case, \toolname\ will insert logging code
where the error is returned and include standard information, such as
the driver name, location in the code, and error type (timeout or
corruption). If the driver already reports an error, then we assume
its report is sufficient and \toolname\ does not introduce additional
reporting.

We implement analyses in \toolname\ to detect when the driver either
detects a failure of the hardware or returns an error specifically
because of a value read from the hardware. These analyses
depend on the bug-finding capabilities from the preceding section to
find sensitive code. In this case, what would have been a false
positive, because the failure {\em is} handled by the driver, becomes
the condition for which to search. 

\subsection{Reporting Device Timeouts }
\noindent \toolname\ detects locations where a driver correctly times out of a
polling loop. This code indicates that a device failure has occurred
because the device did not output the correct value within the
specified time. This analysis is the same as the false-positive
analysis used for pruning results for infinite loops, except that the
false positives are now the code we seek.
Figure~\ref{fig:loop-terminate} shows an example of code that loops
until either a timeout is reached or the device produces the necessary
value. \toolname\ detects whether a logging statement, which we
consider a function taking a string as a parameter, occurs either
before breaking out of the loop or just after breaking out. If so,
\toolname\ determines that the driver already reports the failure.

Once loops that timeout are detected, \toolname\ identifies the
predicate that holds when the loop breaks because of a timeout.
\toolname\ identifies any return statements based on such predicates
and places a reporting statement just before the return. The resulting
code is shown in Figure~\ref{fig:loop-reporting}. If the test is
incorporated into \codesm{while} or \codesm{for} loop predicate then
\toolname\ inserts code into the loop to report a failure if the
expression holds. CIL converts \codesm{for} loops into
\codesm{while(1)} loops with \codesm{break} statements so that code can
be inserted between the variable update and the condition evaluation.
Thus, the driver will test the expression, report a failure, test the
expression again, and break out of the loop.


\begin{figure}[t!]
\fvset{firstnumber=1,frame=none,numbers=left,numbersep=2pt,fontfamily=courier,fontsize=\footnotesize}
\begin{Verbatim}
static int phy_reset(...) {
  .
  while (miicontrol & BMCR_RESET) {
    msleep(10);
    miicontrol = mii_rw(...);
     if (tries++ > 100) {
\end{Verbatim}
\vspace{-0.2in}
\fvset{firstnumber=last,frame=single,framesep=0mm}
\begin{Verbatim}
      printk("...");
 \end{Verbatim} 
\vspace{-0.3in}
\fvset{firstnumber=last,frame=none}
\begin{Verbatim}   
      return -1;
  }
 }
  .
}
\end{Verbatim}
%\fvset{numbers=left,numbersep=2pt,fontfamily=courier, fontsize=\footnotesize}
%\LVerbatimInput{code/forcedeth-fix.c}
%%\includegraphics[keepaspectratio=true,width=3in]{figures/hpt-orig.pdf}

\caption{\small \bf \toolname\ inserts a reporting statement automatically in the
  case of a timeout, which indicates the device is not operating according to
  specification.}

\label{fig:loop-reporting}

\end{figure}

\subsection{Reporting Incorrect Device Outputs}
\noindent \toolname\ analyzes driver code to find driver functions that return
errors due to hardware failures. This covers range tests on array
indices and explicit comparisons of status or state values. \toolname\
identifies that a hardware failure has occurred when the driver
returns an error as a result of reading data from a
device. Specifically, it identifies code where three conditions hold:
(a) a driver function returns a negative integer constant; (b) the
error return value is only returned based on the evaluation of a
conditional expression, and (c), the expression references variables
that were read from the device. We further expand the analysis to
detect sites where an error variable is set, such as when the driver
sets the return value and jumps to common cleanup code. If these 
conditions hold, \toolname\ inserts a call to the reporting function
just before the return statement to signify a hardware failure.

\subsection{Results}

\noindent Table~\ref{table:reporting-fixes} shows the result of our analysis. In
total, \toolname\ identified 1555 locations where drivers detect a
timeout. Of these, drivers reported errors only 420 times, and
\toolname\ inserted error-reporting code 1135 times. \toolname\
detected 828 locations where the driver detected a failure with
comparisons or range tests. Of these, the driver reported a failure
361 times and \toolname\ inserted an error report 467 times.

\begin{table}[tp]
\centering
\small
\begin{tabular}{|l|r|r|}
\hline
{\bf Driver } & \multicolumn{1}{c|}{\bf Device Timeout} &
\multicolumn{1}{c|}{\bf Incorrect Output} \\
{\bf  Class} &  {\bf found/fixed} & {\bf found/fixed}  \\
\hline
\hline
net  & 483/321 & 249/97  \\ \hline
scsi & 302/249 & 137/110\\ \hline
sound & 359/297 & 81/53\\ \hline
other & 411/268 & 361/207 \\ \hline
\hline
Total & 1555/1135 & 828/467 \\ \hline
\end{tabular}

\caption{\small \bf Instances of device-reporting code inserted by
  \toolname. Each entry shows the number of device failures detected
  by the driver, followed by the number where the driver did not
  report failures  and \toolname\ inserted reporting code.}

\label{table:reporting-fixes}
\vspace{-0.1in}
\end{table}


\begin{table}[tp]
\centering
\small
\begin{tabular}{|l|l|r|r|}
\hline
{\bf Driver } & {\bf Class}  &{\bf Actual errors} & {\bf Reported Errors} \\
\hline
\hline
bnx2      & net &24 & 17 \\ \hline
mptbase   & scsi & 28 & 17 \\ \hline
ens1371   & sound & 10 & 9  \\ \hline
\end{tabular}

\caption{\small \bf Instances of fault-reporting code inserted by
  \toolname\ compared against all errors detected in the driver.
  Each entry shows the actual number of errors detected in the driver followed
  by the number of errors reported using \toolname.}
\label{table:reporting-errors}
\vspace{-0.1in}
\end{table}


We evaluate the effectiveness of \toolname\ at introducing
error-reporting code by performing the same analysis by hand to see
whether it finds all the locations where drivers detect a hardware
failure. For the drivers listed in Table~\ref{table:reporting-errors},
we identified every location where the original driver detects a
failure and whether it reports the failure through logging.

We manually examined the three drivers, one from each major class, and
counted as an error any code that clearly indicated the hardware was
operating outside of specification. This code performs any of the
following actions on the basis of a value read from the device: (1)
returning a negative value, (2) printing an error message indicating a
hardware failure, or (3) detecting a failed self-test. We did not
count errors found in any code removed during preprocessing, such as
\codesm{ASSERT} statements.

Table~\ref{table:reporting-errors} shows the number of failures the
driver detects (according to our manual analysis), whether reported or
not, compared with the number of errors reported by \toolname. In
these three drivers, \toolname\ did not produce any false positives:
all of the errors reported did indicate a device malfunction. However,
\toolname\ missed  several places where the driver detected a failure.
Out of 62 locations where the driver detected a failure, \toolname\
identified 43. 

We found three reasons for these false negatives. First, some drivers,
such as the bnx2 network driver, wrap several low-level read
operations in a single function, and return the tainted data via an
out parameter. \toolname\ does not propagate taint through out
parameters. Second, \toolname's analysis is not sophisticated enough
to track tainted structure members across procedure boundaries. The
mptbase SCSI driver reads data into a member variable in one procedure
and returns an error based on its value in another, and we do not
detect the member as tainted where the failure is returned. Finally,
some drivers detect a hardware failure and print a message but do not
subsequently return an error. Thus, \toolname\ does not identify that
a hardware failure was detected.

To verify the operation of the reporting statements, we injected
targeted faults designed to cause the \toolified\ driver to report a
failure. We tested four drivers with fault injection to ensure they
reported failures. We injected synthetic faults into the ens1371 sound
driver and the de4x5, 8139cp, and 8139too network drivers using the
tool from Section~\ref{sec:bug-finding}. We verified that targeted
fault injection triggered every reporting statement that applies
to the hardware devices we had. 

The only false positive we found occurred in the 8139too network driver
during during device initialization. This driver executes a loop
that is expected to time out, and \toolname\
falsely considers this a hardware fault. The other carburized drivers
do not report any false positives. We injected faults with a fixed
probability every time the driver invoked a port or I/O memory read
operation, both during driver initialization and while running a
workload. The drivers did not report any additional errors compared to
unmodified drivers under these conditions, largely because none of the
injected faults would lead to a system crash. As future work, we plan
to examine the problem of reporting whether a device is malfunctioning
even if the malfunction does not lead to a crash.


Overall, we found that \toolname\ was effective at introducing
additional error logging to drivers where logging did not previously
exist. While it does not detect every hardware failure, \toolname\
increases the number of failures logged and can therefore improve an
administrator's ability to detect when hardware is failing, as
compared to driver failures caused by software.
\section{Runtime Fault Tolerance}
\label{sec:recovery}

\noindent The \toolname\ runtime provides two key services. First, it provides
an automatic recovery service to restore drivers and devices to a
functioning state when a failure occurs. Second, it detects classes of
failures that cannot be addressed by static analysis and modification
of driver code, such as tolerating stuck interrupts.

\subsection{Automatic Recovery}
\noindent Static analysis tools have proved useful as bug finding tools. But,
programmers must still write code to repair the bugs that are found.
\toolname\ circumvents this limitation by relying on {\em automatic
  recovery} to restore drivers and devices to a functioning state when
a failure is detected. The driver may invoke a recovery function at
any time, which will reset the driver to a known-good state. For
stuck-at hardware failures, resetting the device can often correct the
problem. We rely on the same mechanism to recover from
transient failures, although a full reset may not be required in every
case.

We leverage shadow drivers~\cite{swift06} to provide automatic
recovery because they conceal failures from applications and the OS. A
shadow driver is a kernel agent that monitors and stores the state of
a driver by intercepting function calls between the driver and the
kernel. During normal operation, the shadow driver {\em
  taps} all function calls between the driver and the
kernel. In this {\em passive
  mode}, the shadow driver records operations that change the state of
the driver, such as configuration operations and requests currently
being processed by the driver.

Shadow drivers are class drivers, in that they are customized to the
driver interface but not to its implementation. Thus, a separate
shadow driver is needed to recover from failures in each unique class,
such as network, sound, or SCSI. We have only implemented recovery for
network drivers so far, although other work shows that they work
effectively for sound, storage~\cite{swift06} and video
drivers~\cite{lagar-cavilla:vmm-graphs:vee:2007} .

When the driver invokes the recovery function, the shadow driver
transitions into {\em active mode}, where it performs two
functions. First, it proxies for the device driver, fielding requests
from the kernel until the driver recovers. This process ensures that the
kernel and application software is unaware that the device
failed. Second, shadow drivers unload and release the state of the
driver and then restart the driver, causing it to reinitialize the
device. When starting this driver, the shadow driver uses its log to
configure the driver to its state prior to recovery, including
resubmitting pending requests. Once this is complete, the shadow
driver transitions back to passive mode, and the driver is available
for use.

The shadow driver recovery model works when resetting the device
clears a device failure. For devices that fail permanently or require
a full power cycle to recover, shadow drivers will detect that the
failure is not transient when recovery fails and can notify a
management agent.

We obtained the shadow driver implementation used for virtual machine
migration~\cite{kadav08} and ported the recovery functions for network
device drivers to the 2.6.18.8 kernel. However, we did not port the
entire Nooks driver isolation subsystem~\cite{sbl05}. Nooks prevents
memory corruption and detects failures through hardware traps, which
are unnecessary for tolerating hardware failures. Nooks' isolation
also causes a performance drop from switching protection domains,
which \toolname\ avoids. The remaining code consists of wrappers
around the kernel/driver interface, code to log driver requests, and
code to restart and restore driver state after a failure. In addition,
we export the \codesm{\_\_shadow\_recover} function from the kernel,
which a driver may call to initiate recovery after a hardware failure.

\subsection{Tolerating Missing Interrupts}

\noindent In addition to providing a recovery service, the \toolname\ runtime
also detects failures that cannot be detected through static
modifications of driver code. Devices may fail by generating
too many interrupts or by not generating any. The first case causes a
system hang, because no useful work can occur while the interrupt
handler is running, while the second case can result in an inoperable
device. 

To address the scenario in which the device stops generating
interrupts, \toolname\ monitors the driver and invokes the interrupt
handler automatically if necessary. With monitoring, an otherwise
operative device need not generate interrupts to provide service. Unlike
other hardware errors, we do not force the driver to recover in this
case because we cannot detect precisely whether an interrupt is
missing. Instead, the \toolname\ runtime pro-actively calls the
driver's interrupt handler to process any pending requests

The \toolname\ runtime increments a counter each time a driver's
interrupt handler is called. Periodically, a low priority kernel
thread checks this counter. If the counter value has changed,
\toolname\ does nothing since the device appears to be working
normally. If, however, the interrupt handler has not been executed,
the device may not be delivering interrupts.

The \toolname\ runtime detects whether there has been recent driver activity
that should have caused an interrupt by testing whether driver code has been
executed. Rather than recording every driver invocation, \toolname\ polls the
reference bits on the driver's code pages. If any of the code pages have been
referenced, \toolname\ assumes that a request may have been made and that the
interrupt handler should be called soon.

Because every driver is different, \toolname\ implements a dynamic
approach to increase or decrease the polling interval exponentially,
depending on whether previous calls were productive or not. By
default, \toolname\ checks the referenced bits every 16ms. We chose
this value because it provides a relatively good response time in the
event of a single missing interrupt. If \toolname's call to the
interrupt handler returns \codesm{IRQ\_NONE}, indicating the interrupt
was spurious, then \toolname\ doubles the polling interval, up to a
maximum of one second. Conversely, if the interrupt handler returns
\codesm{IRQ\_HANDLED}, indicating that there was work for the driver,
then \toolname\ decreases the polling interval to a minimum of 4ms.
Thus, \toolname\ calls the interrupt handler repeatedly only if it
detects that the driver is doing useful work during the handler.

Relying on the handler return value to detect whether the handler was
productive works for devices that support shared interrupts. Spurious
interrupt handler invocations can occur with shared interrupts because
the kernel cannot detect which of the devices sharing the interrupt
line needs service. However, some drivers report \codesm{IRQ\_HANDLED}
even if the device does not require service, leading \toolname\ to
falsely detect that it has missed an interrupt. We are examining
alternate mechanisms to distinguish productive and unproductive calls
to interrupt handlers to improve performance and reduce unnecessary
polling, such as timing the duration of the handler or detecting which
code pages are accessed during the handler.

\toolname's polling mechanism adds some overhead when the kernel
invokes a driver but does not cause the device to generate an
interrupt. For network drivers, this occurs when the kernel invokes an
ethtool management function. The \toolname\ runtime will call the
interrupt handler even though it is not necessary for correct
operation. The driver treats this call to its interrupt
handler as spurious. Because \toolname\ decreases the
polling interval in these cases, there is little unnecessary polling
even when many  requests are made of a driver that do not generate
interrupts.

Some Linux network drivers, through the \codesm{napi} interface,
already support polling. In addition, many network drivers implement a
watchdog function to detect when the device stops working. For these
drivers, it may be sufficient to direct the kernel to poll rather than
relying on a separate mechanism. However, this approach only works for
network drivers, while the \toolname\ runtime approach works across
all driver classes.

\subsection{Tolerating Stuck Interrupts}

\noindent The \toolname\ runtime detects stuck interrupts and recovers by
converting the device from interrupts to polling by periodically
calling the driver's exported interrupt function. A stuck interrupt
occurs when the device does not lower the interrupt request line even
when directed to do so by the driver. The \toolname\ runtime detects
this failure when a driver's interrupt handler has been called many
times without intervening progress of other system functions, such as
the regular timer interrupt. The Linux kernel can detect unhandled
interrupts~\cite{lkml:spurious-interrupts:2007}, but it recovers by
disabling the device rather than enabling it to make progress.

Similar to missing interrupts, the \toolname\ runtime does not trigger
full recovery in this case (although that is possible), but instead
disables the interrupt request line with \codesm{disable\_IRQ}. It
then relies on the polling mechanism previously described to
periodically call the driver's interrupt handler.


\subsection{Results}

\noindent We experiment with stuck and missing interrupts using fault injection on the
E1000 gigabit Ethernet driver, the ens1371 sound driver, and a collection of
interdependent storage driv\-ers: ide-core, ide-generic, and ide-disk.  On all
three devices, we simulate missing interrupts by disabling the device's
interrupt request line.  We simulate stuck interrupts with the E1000 by
inserting a command to generate an interrupt from inside the interrupt handler.
For E1000, we compare throughput and CPU utilization between an unmodified
driver, a driver undergoing monitoring for stuck/disabled interrupts, and a
driver whose interrupt line has been disabled.

In the case of E1000, we found that the \toolname\ runtime was able to
detect both failures promptly, and that the driver continued running
in polling mode. Because interrupts occur only once every 4ms in the
steady state, receive throughput drops from 750 Mb/s to 130 Mb/s. With
more frequent polling, the throughput would be higher. Similarly,
\toolname\ detected both failures for the IDE driver. The IDE disk
operated correctly in polling mode but throughput decreased by 50\%.
The ens1371 driver in polling mode played back sound with a little
distortion, but otherwise operated normally. These tests
demonstrate that \toolname's stuck and missing interrupt detection
mechanism works and can keep devices functioning in the presence of a
failure.
\section{Overhead Evaluation}
\label{sec:performance}
\noindent The primary cost of using \toolname\ is the time spent running the
tool and fixing bugs that cannot be automatically repaired. However,
the code transformations introduced by \toolname, shadow driver
recovery, and interrupt monitoring introduce a small runtime cost. In
this section we measure the overhead of running \toolified\ drivers.

We measure the performance overhead on gigabit Ethernet drivers, as
they are the most performance-intensive of our devices: a driver may
receive more than 75,000 packets to deliver per second.  Thus, any
overhead of \toolname's mechanisms will show up more clearly than on
lower-bandwidth devices. Past work on Nooks and shadow storage drivers
showed a greater difference in performance than for the network, but
the CPU utilization differences were far greater for network
drivers~\cite{swift06}.

We measure performance with netperf~\cite{jones95} between two Sun
Ultra 20 workstation with 2.2Ghz AMD Opteron processors and 1GB of
RAM connected via a crossover cable. We configure netperf to run
enough experiments to report results accurate to 2.5\% with 99\%
confidence.

\begin{table}[tbp]
\center
\small


{\bf NVIDIA MCP55 Pro gigabit NIC (forcedeth)}\\
\begin{tabular}{|c|c|c|} \hline
{\bf System } & {\bf Throughput} & {\bf CPU Utilization} \\  \hline
Linux 2.6.18.8 Kernel & 940  Mb/s & 31\% \\ \hline
\toolname\ Kernel  & 935 Mb/s & 36\% \\ 
(with shadow driver) & & \\ \hline
\end{tabular}
\\
\vspace{0.2cm}
{\bf Intel Pro/1000 gigabit NIC (E1000)}\\ 
\begin{tabular}{|c|c|c|} \hline
{\bf System} & {\bf Throughput} & {\bf CPU Utilization} \\  \hline
Native Kernel & 721 Mb/s & 16\% \\ \hline
\toolname\ Kernel & 720 Mb/s & 16\% \\ 
(with shadow driver) & & \\ \hline
\end{tabular}
\caption{\small \bf TCP streaming send performance with netperf for regular and \toolified\ drivers 
  with automatic recovery mechanism for the E1000 and forcedeth drivers.}
\label{table:overhead}
\end{table}

Table~\ref{table:overhead} shows the throughput and CPU utilization
for sending TCP data with a native Linux kernel and one with the
\toolname\ runtime with shadow driver recovery enabled and a
\toolified\ network driver. The network throughput with \toolname\ is
within one-half percent of native performance, and CPU utilization
increases only 5 percentage points for forcedeth and not at all for
the E1000 driver. These results demonstrate that supporting generic
recovery, even for high-throughput devices, has very little runtime cost.

\begin{table}[tp]
\centering
\small
{\bf Intel Pro/1000 gigabit NIC (E1000)}\\ 
\begin{tabular}{|c|r|c|}
\hline
{\bf System } &  {\bf Throughput} & {\bf CPU \%}  \\
\hline
Native Kernel - TCP           & 750 Mb/s & 19\% \\ \hline
\toolname\ Monitored - TCP    & 751 Mb/s & 19\% \\ \hline
Native Kernel - UDP-RR        & 7328 Tx/s & 6\% \\ \hline
\toolname\ Monitored - UDP-RR & 7310 Tx/s & 6\% \\ \hline
\end{tabular}

\caption{\small \bf TCP streaming and UDP request-response receive performance comparison
  of the E1000 between the native Linux kernel and a kernel with the \toolname\
  runtime monitoring the driver's interrupts.}
\label{table:recovery-interrupts}
\vspace{-0.2in}
\end{table}

Table~\ref{table:recovery-interrupts} shows performance overhead of
interrupt monitoring but with no shadow driver recovery. The table
shows the TCP receive throughput and CPU utilization for the E1000
driver on the native Linux kernel, and on a kernel with \toolname\
interrupt monitoring enabled. The TCP receive and transmit socket
buffers were left at their default sizes of 87,380 and 655,360 bytes,
respectively. The table also shows UDP request-response performance
with 1-byte packets, a test designed to highlight driver latency.
While these results are for receiving packets, we also compared
performance with TCP and UDP-RR transmit benchmarks and found similar
results: the performance of the native kernel and the kernel with
monitoring are identical.

These two sets of experiments demonstrate that the cost of tolerating
hardware failures in software, either through explicit invocation of a generic
recovery service or through run-time interrupt monitoring, is
low. Given this low overhead,   \toolname\ is a practical approach to
tolerate even infrequent hardware failures. 
\section{Related work}
\label{sec:related-work}
\noindent \toolname\ draws inspiration from past projects on
driver reliability, bug finding, automatic patch generation, device
interface specification, and recovery.


\paragraph{Driver reliability}
\noindent Past work on driver reliability has focused on preventing driver bugs
from crashing the system. Much of this work can apply to hardware
failures, as they manifest as a bug causing the driver to access
invalid memory or consume too much CPU. In contrast to \toolname,
these tools are all heavyweight: they require new operating systems
(Singularity~\cite{spear:singularity-drivers:eurosys:2006},
Minix~\cite{herder:driver-resilience:dsn:2007},
Nexus~\cite{williams08}), new driver models (Windows
UMDF~\cite{microsoft:umdf:2006}, Linux user-mode
drivers~\cite{leslie:user-driver:jcst:2005}), runtime instrumentation
of large amounts of code (XFI~\cite{erlingsson:xfi:osdi:2006} and
SafeDrive~\cite{zhou:safedrive:osdi:2006}), adoption of a hypervisor
(Xen~\cite{fhn+04} and iKernel~\cite{tan:ikernel:dasc:2007}), or a
new subsystem in the kernel (Nooks~\cite{sbl05}). \toolname\
instead fixes specific bugs, which reduces the code needed in the
kernel to just recovery and not fault detection or isolation. Thus,
\toolname\ may be easier to integrate into existing kernel development
processes. Furthermore, \toolname\ detects hardware failures before
they cause corruption, while driver reliability systems using memory
detection may not detect it until much later, after corruption
propagates.

\paragraph{Bug finding}
\noindent Tools for finding bugs in OS code through static
analysis~\cite{ball06:sdv:eurosys:2006,br02,engler00} have focused on
enforcing kernel-programming rules, such as proper memory allocation,
locking and error handling. However, these tools enforce kernel API
protocols, but do not address the hardware protocol. Furthermore,
these tools only find bugs but do not automatically repair them. 

Hardware dependence errors are commonly found through synthetic fault
injection~\cite{arthur04,hanson:driver-test-patent:2005,sun:hardening:drivers:2007,Zhuang:ols:2003}.
This approach requires a machine with the device installed, while
\toolname\ operates only on source code. Furthermore, fault injection is
time consuming, as it requires injection of many possible faults into
each I/O operation made by a driver.

\paragraph{Automatic patch generation}
\noindent \toolname\ is complementary to prior work on repairing broken error
handling code found through fault
injection~\cite{suesskraut:error-fixing:edcc:2006}. Error handling
repair is an alternate means of recovering when a hardware failure
occurs by re-using existing error handling code instead of invoking a
generic recovery function. Other work on automatically patching bugs
has focused on security
exploits~\cite{cui:data-patch:oakland:2007,sidiroglou:worm-patch:oakland:2005,smirnov:batch-buffer:ias:2007}.
These systems also address how to generate repair code automatically, but
focus on bugs used for attacks, such as buffer overruns, and not the
infinite loop problems caused by devices.

\paragraph{Hardware Interface specification}
\noindent Several projects, such as Devil~\cite{merillon00},
Dingo~\cite{ryzhyk:dingo:eurosys:2009},
HAIL~\cite{sun:hail:emsoft:2005}, Nexus~\cite{williams08},
Laddie~\cite{wittie:check-driver-io:apges:2007} and others, have
focused on reducing faults on the driver/device interface by
specifying the hardware interface through a domain specific language.
These languages improve driver reliability by ensuring that the driver
follows the correct protocol for the device. However, these systems
all assume that the hardware is perfect and never misbehaves. Without
runtime checking they cannot verify that the device produces correct
output.

\paragraph{Recovery}
\noindent \toolname\ relies on shadow drivers~\cite{swift06} for recovery. 
However, since our implementation of shadow drivers does not 
integrate any isolation mechanism, the overhead of recovery 
support is very low. Other
systems that recover from driver failure, including
SafeDrive~\cite{zhou:safedrive:osdi:2006}, and
Minix~\cite{herder:driver-resilience:dsn:2007}, rely on similar
mechanisms to restore the kernel to a consistent state and release
resources acquired by the driver could be used as well. CuriOS
provides transparent recovery and further ensures that client session
state can be recovered~\cite{david08curios}. However, CuriOS is a new
operating system and requires specially written code to take advantage
of its recovery system, while \toolname\ works with existing driver
code in existing operating systems.

To achieve high reliability in the presence of hardware failures,
fault tolerant systems often use multiple instances of a hardware
device and switch to a new device when one
fails~\cite{bartlett81,hp:parallel-tcp:2002,su:fault-tolerant-arch:jcc:1977}.
These systems provide an alternate recovery mechanism to shadow
drivers. However, this approach still relies on drivers to detect
failures, and \toolname\ improves that ability.

\section{Conclusions}

\noindent System reliability is limited by the reliability of devices. Evidence
suggests that device failures cause a measurable fraction of system
failures, and that most hardware failures are transient and can be
tolerated in software. \toolname\ improves reliability by {\em
  automatically hardening} drivers against device failures without new
programming languages, programming models, operating systems, or
execution environments. \toolname\ finds and repairs hardware
dependence bugs in drivers, where the driver will hang or crash if the
hardware fails. In addition, \toolname\ inserts logging code so
that system administrators can proactively repair or replace hardware
that fails.

In an analysis of the Linux kernel, \toolname\ identified over 992
hardware dependence bugs with fewer than 8\% false postives. Discounting
for false positives, \toolname\ could automatically repair
approximately 845 real bugs by inserting code to detect when a failure
occurs and invoke a recovery service. Repairs made to false positives
have no correctness impact. In performance tests, hardening drivers
had almost no visible performance overhead.

There are still more opportunities to improve device drivers.
\toolname\ assumes that if a driver detects a hardware failure, it
correctly responds to that failure.  In practice, we find this is
often not the case. In addition, \toolname\ does not  assist drivers in
handling unexpected events; we have seen code that crashes when the
device returns a flag before the driver is prepared. Thus, there are
yet more opportunities to improve driver quality.

\section*{Acknowledgements}
\noindent This work is supported in part by the National Science Foundation
(NSF) grants CCF 0621487 and CNS 0745517, and by the Wisconsin Alumni
Research Foundation.  We would also like to thank Ben Liblit for
helpful discussions during the initial stages of the project and our
shepherd Miguel Castro for his useful advice.


 %------------------------------------------------------------------------------
 %                                  References.
 %------------------------------------------------------------------------------
%{\small
%    \bibliographystyle{abbrvurl3}
%    \bibliography{references,my-big,test}
%} % small

\begin{thebibliography}{10}

\bibitem{arpaci01}
R.~H. Arpaci-Dusseau and A.~C. Arpaci-Dusseau.
\newblock Fail-stutter fault tolerance.
\newblock In {\em Proc. of the Eighth {IEEE} {HOTOS}}, May 2001.

\bibitem{arthur04}
S.~Arthur.
\newblock Fault resilient drivers for {Longhorn} server, May 2004.
\newblock Microsoft Corporation, WinHec 2004 Presentation DW04012.

\bibitem{BairavasundaramEtAl07-Sigmetrics}
L.~N. Bairavasundaram, G.~R. Goodson, S.~Pasupathy, and J.~Schindler.
\newblock {An Analysis of Latent Sector Errors in Disk Drives}.
\newblock In {\em Proc. of the 7th SIGMETRICS}, June 2007.

\bibitem{bbc+06}
T.~Ball, E.~Bounimova, B.~Cook, V.~Levin, J.~Lichtenberg, C.~McGarvey,
  B.~Ondrusek, S.~K. Rajamani, and A.~Ustuner.
\newblock Thorough static analysis of device drivers.
\newblock In {\em Proc. of the 2006 EuroSys Conference}, 2006.

\bibitem{ball06:sdv:eurosys:2006}
T.~Ball, E.~Bounimova, B.~Cook, V.~Levin, J.~Lichtenberg, C.~McGarvey,
  B.~Ondrusek, S.~K. Rajamani, and A.~Ustuner.
\newblock Thorough static analysis of device drivers.
\newblock In {\em Proc. of the 2006 EuroSys Conference}, Apr. 2006.

\bibitem{br02}
T.~Ball and S.~K. Rajamani.
\newblock The {SLAM} project: {Debugging} system software via static analysis.
\newblock In {\em Proc. of the 29th {POPL}}, 2002.

\bibitem{bartlett81}
J.~F. Bartlett.
\newblock A {NonStop} kernel.
\newblock In {\em Proc. of the 8th {ACM} SOSP}, Dec. 1981.

\bibitem{chandrashekaran:clarity:fse:2007}
P.~Chandrashekaran, C.~Conway, J.~M. Joy, and S.~K. Rajamani.
\newblock Programming asynchronous layers with {CLARITY}.
\newblock In {\em Proc. of the 15th Annual Symposium on Foundations of Software
  Engineering}, Sept. 2007.

\bibitem{coverity04}
Coverity.
\newblock Anaylsis of the {Linux} kernel, 2004.
\newblock Available at \url{http://www.coverity.com}.

\bibitem{cui:data-patch:oakland:2007}
W.~Cui, M.~Peinado, H.~J. Wang, and M.~E. Locasto.
\newblock Shieldgen: Automatic data patch generation for unknown
  vulnerabilities with informed probing.
\newblock In {\em Proc. of the IEEE Symposium on Security and Privacy}, 2007.

\bibitem{david08curios}
F.~M. David, E.~M. Chan, J.~C. Carlyle, and R.~H. Campbell.
\newblock {CuriOS}: Improving reliability through operating system structure.
\newblock In {\em Proc. of the 8th {USENIX} OSDI}, December 2008.

\bibitem{engler00}
D.~Engler, B.~Chelf, A.~Chou, and S.~Hallem.
\newblock Checking system rules using system-specific, programmer-written
  compiler extensions.
\newblock In {\em Proc. of the 4th {USENIX} OSDI}, Oct. 2000.

\bibitem{fhn+04}
K.~Fraser, S.~Hand, R.~Neugebauer, I.~Pratt, A.~Warfield, and M.~Williamson.
\newblock Safe hardware access with the {Xen} virtual machine monitor.
\newblock In {\em OASIS Workhop}, 2004.

\bibitem{ganapathy:comm:2009}
N.~Ganapathy, 2009.
\newblock Architect, Microsoft Windows Driver Experience team, personal
  communication.

\bibitem{grb08}
V.~Ganapathy, M.~J. Renzelmann, A.~Balakrishnan, M.~M. Swift, and S.~Jha.
\newblock The design and implementation of microdrivers.
\newblock In {\em Proc. of the 13th {ACM} ASPLOS}, Mar. 2008.

\bibitem{graham:windows-ft-drivers:2004}
S.~Graham.
\newblock Writing drivers for reliability, robustness and fault tolerant
  systems.
\newblock \url{http://www.microsoft.com/whdc/archive/FTdrv.mspx}, Apr. 2004.

\bibitem{hanson:driver-test-patent:2005}
S.~R. Hanson and E.~J. Radley.
\newblock Testing device driver hardening, May 2005.
\newblock US Patent 6,971,048.

\bibitem{herder:driver-resilience:dsn:2007}
J.~N. Herder, H.~Bos, B.~Gras, P.~Homburg, and A.~S. Tanenbaum.
\newblock Failure resilience for device drivers.
\newblock In {\em Proc. of the 2007 {IEEE} DSN}, June 2007.

\bibitem{hp:parallel-tcp:2002}
{Hewlett Packard Corp.}
\newblock Parallel processing of {TCP/IP} with ethernet adapter failover.
\newblock
  \url{http://h20223.www2.hp.com/NonStopComputing/downloads/EAFailoverTCP-IP-PL.pdf}, 2002.

\bibitem{intel:driver-hardening:spec:2002}
{Intel Corporation} and {IBM Corporation}.
\newblock Device driver hardening design specification draft release 0.5h.
\newblock
  \url{http://hardeneddrivers.sourceforge.net/downloads/DDH-Spec-0.5h.pdf},
  Aug. 2002.

\bibitem{jones95}
R.~Jones.
\newblock \href{http://www.netperf.org}{Netperf: A network performance
  benchmark, version 2.1}, 1995.
\newblock Available at \url{http://www.netperf.org}.

\bibitem{kadav08}
A.~Kadav and M.~M. Swift.
\newblock Live migration of direct-access devices.
\newblock In {\em First Workshop on I/O Virtualization (WIOV '08)}, Dec. 2008.

\bibitem{lagar-cavilla:vmm-graphs:vee:2007}
H.~A. Lagar-Cavilla, N.~Tolia, M.~Satyanarayanan, and E.~de~Lara.
\newblock {VMM}-independent graphics acceleration.
\newblock In {\em Proc. of the 3rd VEE}, June 2007.

\bibitem{leslie:user-driver:jcst:2005}
B.~Leslie, P.~Chubb, N.~Fitzroy-Dale, S.~Gotz, C.~Gray, L.~Macpherson,
  D.~Potts, Y.~Shen, K.~Elphinstone, and G.~Heiser.
\newblock User-level device drivers: {Achieved} performance.
\newblock {\em Journal Computer Science and Technology}, 20(5), Sept. 2005.

\bibitem{li:error-propagation:asplos:2008}
M.-L. Li, P.~Ramachandran, S.~Sahoo, S.~Adve, V.~Adve, and Y.~Zhou.
\newblock Understanding the propagation of hard errors to software and
  implications for resilient system design.
\newblock In {\em Proc. of the 13th {ACM} ASPLOS}, Mar. 2008.

\bibitem{lkml:tulip-driver-wait:2006}
{Linux Kernel Mailing List}.
\newblock Fixes for uli5261 (tulip driver).
\newblock \url{http://lkml.org/lkml/2006/8/19/59}, Aug. 2006.

\bibitem{lkml:spurious-interrupts:2007}
{Linux Kernel Mailing List}.
\newblock Improve behaviour of spurious irq detect.
\newblock \url{http://lkml.org/lkml/2007/6/7/211}, June 2007.

\bibitem{merillon00}
F.~M{\'{e}}rillon, L.~R{\'{e}}veill{\`{e}}re, C.~Consel, R.~Marlet, and
  G.~Muller.
\newblock Devil: An {IDL} for hardware programming.
\newblock In {\em Proc. of the 4th {USENIX} OSDI}, Oct. 2000.

\bibitem{microsoft:umdf:2006}
{Microsoft Corporation}.
\newblock Introduction to the {WDF} user-mode driver framework.
\newblock \url{http://www.microsoft.com/whdc/driver/wdf/umdf_intro.mspx}, May
  2006.

\bibitem{nmr+02}
G.~C. Necula, S.~Mcpeak, S.~P. Rahul, and W.~Weimer.
\newblock {CIL:} {Intermediate} language and tools for analysis and
  transformation of {C} programs.
\newblock In {\em Proc. of the 11th International Conference on Compiler
  Construction}, 2002.

\bibitem{pinheiro:disk-failure-trends:fast:2007}
E.~Pinheiro, W.-D. Weber, and L.~A. Barroso.
\newblock Failure trends in a large disk drive population.
\newblock In {\em Proc. of the 5th FAST}, 2007.

\bibitem{post:linux-sdv:ifm:2007}
H.~Post and W.~Kuchlin.
\newblock Integrated static analysis for {Linux} device driver verification.
\newblock In {\em Proc. of the 6th International Conference on Integrated
  Formal Methods}, July 2007.

\bibitem{ryzhyk:dingo:eurosys:2009}
L.~Ryzhyk, P.~Chubb, I.~Kuz, and G.~Heiser.
\newblock Dingo: Taming device drivers.
\newblock In {\em Proc. of the 200 EuroSys Conference}, Apr. 2009.

\bibitem{linux:driver-dos-donts:2004}
T.~Shureih.
\newblock {HOWTO}: Linux device driver dos and don'ts.
\newblock \url{http://janitor.kernelnewbies.org/docs/driver-howto.html}, Mar.
  2004.

\bibitem{sidiroglou:worm-patch:oakland:2005}
S.~Sidiroglou and A.~D. Keromytis.
\newblock Countering network worms through automatic patch generation.
\newblock {\em IEEE Security and Privacy}, 3(6):41--49, 2005.

\bibitem{smirnov:batch-buffer:ias:2007}
A.~Smirnov and {Tzi-cker}Chiueh.
\newblock Automatic patch generation for buffer overflow attacks.
\newblock In {\em Proc. of the 3rd Symposium on Information Assurance and
  Security}, 2007.

\bibitem{spear:singularity-drivers:eurosys:2006}
M.~Spear, T.~Roeder, O.~Hodson, G.~Hunt, and S.~Levi.
\newblock Solving the starting problem: Device drivers as self-describing
  artifacts.
\newblock In {\em Proc. of the 2006 EuroSys Conference}, Apr. 2006.

\bibitem{su:fault-tolerant-arch:jcc:1977}
S.~Y.~H. Su and R.~J. Spillman.
\newblock An overview of fault-tolerant digital system architecture.
\newblock In {\em Proc. of the National Computer Conference (AFIPS)}, 1977.

\bibitem{sun:hail:emsoft:2005}
J.~Sun, W.~Yuan, M.~Kallahalla, and N.~Islam.
\newblock {HAIL}: A language for easy and correct device access.
\newblock In {\em Proc. of the 5th ACM International Conference on Embedded
  Software}, Sept. 2005.

\bibitem{solaris:fma:website}
{Sun Microsystems}.
\newblock Opensolaris community: Fault management.
\newblock \url{http://opensolaris.org/os/community/fm/}.

\bibitem{sun:hardening:drivers:2007}
{Sun Microsystems}.
\newblock {\em {Solaris Express} Software Developer Collection: Writing Device
  Drivers}, chapter 13: Hardening Solaris Drivers.
\newblock {Sun Microsystems}, 2007.

\bibitem{suesskraut:error-fixing:edcc:2006}
M.~S{\"u}{\ss}kraut and C.~Fetzer.
\newblock Automatically finding and patching bad error handling.
\newblock In {\em Proc. of the 6th EDCC}, Oct. 2006.

\bibitem{swift06}
M.~Swift, M.~Annamalau, B.~N. Bershad, and H.~M. Levy.
\newblock Recovering device drivers.
\newblock {\em {ACM} Transactions on Computer Systems}, 24(4), Nov. 2006.

\bibitem{sbl05}
M.~M. Swift, B.~N. Bershad, and H.~M. Levy.
\newblock Improving the reliability of commodity operating systems.
\newblock {\em {ACM} Transactions on Computer Systems}, 23(1), Feb. 2005.

\bibitem{tan:ikernel:dasc:2007}
L.~Tan, E.~M. Chan, R.~Farivar, N.~Mallick, J.~C. Carlyle, F.~M. David, and
  R.~H. Campbell.
\newblock {iKernel}: Isolating buggy and malicious device drivers using
  hardware virtualization support.
\newblock In {\em Proc. of the 3rd DASC}, 2007.

\bibitem{erlingsson:xfi:osdi:2006}
\'{U}lfar Erlingsson, M.~Abadi, M.~Vrable, M.~Budiu, and G.~C. Necula.
\newblock Xfi: software guards for system address spaces.
\newblock In {\em Proc. of the 7th {USENIX} OSDI}, 2006.

\bibitem{walker:fault-lambda:icfp:2006}
D.~Walker, L.~Mackey, J.~Ligatti, G.~A. Reis, and D.~I. August.
\newblock Static typing for a faulty lambda calculus.
\newblock In {\em Proc. of the ICFP Conference}, Sept. 2006.

\bibitem{williams08}
D.~Williams, P.~Reynolds, K.~Walsh, E.~G. Sirer, and F.~B. Schneider.
\newblock Device driver safety through a reference validation mechanism.
\newblock In {\em Proc. of the 8th {USENIX} OSDI}, 2008.

\bibitem{wittie:check-driver-io:apges:2007}
L.~Wittie, C.~Hawblitzel, and D.~Pierret.
\newblock Generating a statically-checkable device driver {I/O} interface.
\newblock In {\em Workshop on Automatic Program Generation for Embedded
  Systems}, Oct. 2007.

\bibitem{yang:raid-patent:2007}
J.~Yang.
\newblock Zero-penalty {RAID} controller memory leak detection and isolation
  method and system utilizing sequence numbers, 2007.
\newblock Patent application 11715680.

\bibitem{zhou:safedrive:osdi:2006}
F.~Zhou, J.~Condit, Z.~Anderson, I.~Bagrak, R.~Ennals, M.~Harren, G.~Necula,
  and E.~Brewer.
\newblock {SafeDrive}: {Safe} and recoverable extensions using language-based
  techniques.
\newblock In {\em Proc. of the 7th {USENIX} OSDI}, Nov. 2006.

\bibitem{Zhuang:ols:2003}
L.~Zhuang, S.~Wang, and K.~Gao.
\newblock Fault injection test harness.
\newblock In {\em Proc. of the Ottawa Linux Symposium}, June 2003.

\end{thebibliography}
\end{document}
