introduction.tex

\section{Introduction}
\label{sec.introduction}

Despite the efforts of programmers to develop systems free of vulnerabilities,
researchers frequently uncover new flaws in operating system kernels that can be
triggered by untrusted programs. To reduce security flaws
a variety of techniques, including system call interposition, operating system
virtualization and library OSes,
have been proposed. However, evaluating the level of security
in such virtualization technologies through a quantitative approach is a challenging issue.
As security comparisons between diverse systems are often qualitative
or predictive in nature, it is hard
to discern which practices actually better protect the kernel.

%\yanyan{why we need comparisons?}

In this work, we devise a metric that provides a strong indication of where bugs
will arise in the Linux kernel. Namely, we demonstrate
that executing lines of kernel code that are not used by popular programs represent
a substantial security risk. We support this hypothesis with data from a quantitative
analysis of resilience to flaws in two versions of the Linux kernel, and using this data
to predict where within the kernel bugs will later be discovered. We found that only 2.5\% - 4.0\%
of flaws occur in commonly used code, despite accounting for only
32.2\% - 34.5\% of the reachable kernel code.

Guided by this metric, we propose the safely-reimplement design, a new
technique for building virtualization systems. In this design, the operating
system interface (i.e., POSIX) is reimplemented in a restricted environment
(i.e., a sandbox) that limits kernel access to only commonly-used paths.
Creating such a safe space requires building complex operating system functionality
(i.e., directories and permissions) utilizing only commonly-used primitives (i.e.,
read and writing to a file). However, it allows complex functionality to safely
run untrusted user programs on vulnerable code.
%since it only has access to parts of the kernel that are very unlikely
%to contain flaws.
This ensures that an attacker will be unable to trigger bugs in less
commonly-used kernel paths. As a result, bugs or failures
will be contained within the restricted environment.
%even if the (likely buggy) operating system interface code contains flaws.

Using this design, we develop a prototype virtualization system for
running untrusted user programs on vulnerable kernel code. Dubbed Lind, the
prototype adapts two existing technologies- Native Client (NaCl) \cite{NaCl-09} and
%Seattle's Repy
%an operating system interface
Restricted Python (Repy)~\cite{Repy-10}, to handle distinctly different tasks. NaCl serves as a computational
module that isolates binaries, providing memory safety for a legacy program like
Tor while passing the calls to the operating system interface.
%As described in the design above,
Repy is a sandbox technique we used to build our operating system interface called SafePOSIX. 
SafePOSIX is isolated within Repy to restrict the interface to invoke only common code paths.
It reimplements complex operating system functionality in an isolated
environment provided by a small (8K LOC) Repy sandbox kernel. This provides
straightforward access to the required common kernel paths while allowing more
complex functionality to be built.
As a result, Lind can offer enhanced security without sacrificing basic functionality.

To demonstrate the effectiveness of Lind, we replicated 35 kernel bugs in the Linux kernel
version 3.14.1. We exploited these kernel bugs %\yanyan{what are these programs? 35 kernel bugs?}
in eight different virtualized environments, including
commercial systems VirtualBox, VMWare Workstation, Docker, LXC,
KVM, QEMU, and research prototypes Graphene and Lind. Our results show
that applications run in Lind were the least likely to trigger kernel bugs,
with only one out of the 35 (2.9\%) kernel vulnerabilities being found.
Furthermore, our results show that virtualization systems that use commonly
executed kernel paths have better resilience to vulnerabilities
in the underlying kernel.

In summary, the main contributions of this paper are as follows:

\begin{itemize}\setlength\itemsep{0em}
\item
We propose and verify a novel metric for quantitatively measuring and evaluating
the security of privileged code, such as in an OS kernel.

\item
We validate the hypothesis that commonly-used kernel paths contain fewer bugs,
as predicted by our metric.

\item
We apply the metric to a secure design that accesses only commonly-used
kernel paths. System calls from uncommon paths are reimplemented in a
restricted environment.

\item
We develop a prototype secure virtualization system called Lind that encompasses
the reimplementation design and a strictly controlled access to the kernel
through a very small trusted computing base.

\item
We evaluate Lind and find it triggers only one (2.9\%) of the kernel vulnerabilities
we examined. This result is about an order of magnitude better than the seven other virtualization systems
that we tested.
\end{itemize}

The remainder of this paper is organized as follows.
Section \ref{sec.metric} describes our key hypothesis and
how we tested our metric.
Section \ref{sec.motivation-and-background} presents our goals for using the metric to guide the design
of effective security systems.
%and models the threat of an attacker conducting a kernel exploit.
A study of kernel protection strategies, including our newly proposed design
is discussed in Section \ref{sec.design}. Section \ref{sec.implementation}
describes the implementation of Lind. In Section \ref{sec.evaluation} the security and
efficiency of Lind is tested against other virtualization systems.
Section \ref{sec.limitation} outlines the
limitations of Lind and possible future initiatives.
Finally, Section \ref{sec.related_work} reviews existing techniques that share
Lind's security techniques and goals, and we share some concluding thoughts in
Section \ref{sec.conclusion}.



% old text
%To run multiple applications on a computer, it is critical to securely
%manage access to the machine's underlying hardware.
%In modern computer systems, either a hypervisor - a virtual machine monitor (VMM), or an
%operating system (OS) kernel performs this important function. Unfortunately, code within an OS kernel
%may contain flaws and vulnerabilities that can be triggered in an attack by a malicious adversary.
%If this occurs, an attacker could have unrestricted access to the system.

%One critical flaw, discovered in the Linux kernel in the \texttt{futex} subsystem call can allow an attacker to
%gain ring 0 control via the \texttt{futex} syscall, and potentially execute arbitrary code
%with kernel mode privileges~\cite{CVE-2014-3153}. \cappos{Possibly omit this sentence.}

%Numerous defensive technologies have emerged in recent years as options for protecting
%protecting OS kernels, including OS virtualization (i.e., Xen,
%KVM, VirtualBox), system call filtering \cite{Janus:99},\cite{SCI-04},
%and library OSes \cite{Bascule},\cite{Drawbridge-11}.
%Common security wisdom holds that running software in a
%virtual machinecan prevent an attacker from exploiting flaws in the underlying
%kernel. However, exactly how secure is virtualization? \cite{Tal}. As we will
%demonstrate in this paper, even with virtualization techniques employed, one
%third of the vulnerabilities in the Linux kernel are still vulnerable to exploitation.

%However,
%Limiting access to kernel code by itself is insufficent to build a secure virtualization system because of two issues.
%First, if a complex program can not access a part of the kernel, its functionality must exist somewhere else or the program will not work.
%Second, it is typical for virtualization systems to add new privileged code as their TCB.
%As a result, a vulnerability in the privileged codebase is as much of a security risk as a flaw in the kernel.
%CVE-2008-2100 and CVE-2011-1751 are two examples of weaknesses in the virtualized system, where exploits from guest to host OS have been possible.
%In CVE-2008-2100, a vulnerability in VMWare's codebase was caused by buffer overflows in the VIX API.
%This could allow local users to bypass the guest VM and gain privilege escalation to execute arbitrary code in the host OS,
%even shellcode to access the kernel of the host OS. In CVE-2011-1751, missing check in KVM's QEMU emulation of PCI-ISA bridge
%could allow an attacker for root exploit in the host OS being triggered from a guest \cite{Virtunoid}.

%\cappos{Revise this paragraph further}\lois{as we discussed, replace these two vague examples with one example described in more detail}

%\lois{transition is needed here. There is no connection made between virtualization techniques and where kernel vulnerabilities exist}

%For this purpose, we examined 40 kernel patches designed to fix severe Linux kernel security bugs and analyzed the lines where those bugs occurred.
%The results show that kernel paths used by popular applications contain fewer security bugs, and therefore, can be exposed with less risk.
% \gholami {I think this is excessive info in the introduction}

%This paper presents a new approach for shielding privileged code from untrusted
%programs through controlled kernel access.
%A metric was developed that helps to identify likely locations
%within the kernel where vulnerabilities may exist, based on examination of
%40 kernel bug fixing patches. We validated the proposed metric and built a new
%``safely-reimplement'' design %for virtualizationsystems
%called ` that restricts access to only the
%kernel paths that are mostly used by common applications.

%\lois{for all vrtualization systems?}
%To restrict the privileged code, we first build a minimal, sandboxed environment that also only uses common kernel paths.
%We then implement a POSIX interface inside of this safe sandbox. For complex and dangerous system functions,
%which may access the risky portion of the kernel, input to POSIX is reimplemented by our own code within a sandbox.
%Any bugs or failures within the implementation of those complex system functions will be contained by the sandbox,
%and will not have the chance to reach and trigger risky portions of the kernel. Because of this added security,
%we dub this as a "safe-reimplementation" design. Therefore, even if the code is vulnerable to an attack,
%it is unable to trigger kernel paths that are less commonly used or tested.\lois{I think this paragraph needs to be simplified.
%I think the level of detail is too high for an introduction paragraph}
%This new design helped us to understand which kernel paths are hardest to safely-reimplement and
%provided key insights about what kernel paths system designers should give the highest degree of scrutiny.
%In turn, we then use this design paradigm to develop a virtualization system called Lind.
%\lois{and Lind is developed to do what? Is it just another virtualization system?}

%The new design paradigm ``safely-reimplemented'' within a minimal sandbox based
%on Repy ~\cite{Repy-10} - the POSIX implementation
%to limit access to the kernel - and  integrated it with the Google Native client
%for software fault isolation through memory safety of the application.
%Finally, we evaluate the efficiency of our solution by running applications
%within Lind and other virtualization systems
%and comparing the kernel traces produced by each application.
%The results show that applications run in Lind were the least likely to trigger
%kernel bugs,
%with only one out of the 35 kernel vulnerabilities tested being found for an
%effectiveness rate of 2.9\%.
%In contrast, the virtualization systems built without our metric triggered
%more vulnerabilities (14-40\%).

%To evaluate the effectiveness of Lind, we first captured the kernel traces from user programs run in Lind and four other virtualization systems.
%These traces were then compared against historical kernel bug reports to verify which trace was more likely to trigger bugs.
%Results showed that applications run in Lind were the least likely to trigger kernel bugs, with only one out of the 35 kernel vulnerabilities
%tested being found for an effectiveness rate of 2.9\%. In contrast, the virtualization systems built without our metric triggered more vulnerabilities (23-40\%).
%This suggests that our metric can help effectively design and build more secure virtualization systems.

%In summary,
%\lois{I inserted "in summary," but I don't think this is quite enough. A transition is needed}
%the main contributions of this paper are as follows. %\cappos{revise}
%\begin{itemize}
%\item
%We propose and validate a novel metric for quantitatively measuring and
%evaluating the security of privileged code, such as in an OS kernel.
%The proposed metric is used to examines the safety of the kernel trace at the lines-of-code level.
%\yanyan{what is "generated by producing design recommendations"?}

%\item Validating the key hypothesis that commonly used kernel paths contain fewer bugs, as predicted by our metric.

%\item
%We use the metric to build a secure ``safely-reimplement'' design that
%involves reimplementation of risky system calls inside a
%sandbox that only uses safe kernel paths.
%that commonly used kernel paths contain fewer bugs.

%\item
%With this new design, we implement a sandbox security system called Lind
%that provides a isolated environment for applications and strong protection for the kernel.

%\item
%We conducted empirical evaluation of the Lind system to confirm its architectural
%goals, such as strong security and usability.
%Through a quantitative analysis for sandboxes, we show that only 2.9\% of
%vulnerabilities in the Linux kernel were triggered in Lind.

%We implement Lind and find \gholami{I think this is not a contribution rather
%it is more results of evaulations} it triggers
%only one (2.9\%) of the kernel vulnerabilities we examined. This suggests that our metric can help design and
%build virtualization systems with greater security.

%\end{itemize}
%\cappos{Quantitative analysis for sandboxes}

%The remainder of this paper is organized as follows.
%Section \ref{sec.motivation-and-background} describes the motivation that drove our work and key background material.
%Section \ref{sec.metric}, introduces the proposed kernel security metric. The
%``safely-reimplement'' design pattern derived from this metric is then discussed in Section \ref{sec.design}. Section \ref{sec.implementation},
%explains the significant features of Lind, the kernel security system developed
%from the design pattern explained in the previous section. In Section \ref{sec.evaluation} the security and
%efficiency of Lind is tested against other virtualization systems.
%Section \ref{sec.limitation} outlines the current
%limitations of the Lind prototype and possible future initiatives.
%Finally, Section \ref{sec.related_work} reviews existing tools and techniques that share
%Lind's security techniques and goals, and we conclude our remarks in
%Section \ref{sec.conclusion}.