#  Yuga: Automatically Detecting Lifetime Annotation Bugs
in the Rust Language

Vikram Nitin<EMAIL_ADDRESS>Columbia UniversityNew YorkUSA ,  Anne
Mulhern<EMAIL_ADDRESS>RedHat ResearchUSA ,  Sanjay Arora
<EMAIL_ADDRESS>RedHat ResearchUSA and  Baishakhi Ray<EMAIL_ADDRESS>Columbia UniversityNew YorkUSA

###### Abstract.

The Rust programming language is becoming increasingly popular among systems
programmers due to its efficient performance and robust memory safety
guarantees. Rust employs an ownership model to ensure this guarantee by
allowing each value to be owned by only one identifier at a time.
Additionally, it introduces the concept of borrowing and lifetimes to enable
other variables to borrow the values under certain conditions temporarily.

Despite its benefits, security vulnerabilities have been reported in Rust
projects, often attributed to the use of ”unsafe” Rust code. These
vulnerabilities, in part, arise from incorrect lifetime annotations on
function signatures. However, existing tools fail to detect these bugs,
primarily because such bugs are rare, challenging to detect through dynamic
analysis, and require explicit memory models.

To overcome these limitations, first, we characterize incorrect lifetime
annotations as a source of memory safety bugs and leverage this understanding
to devise a novel static analysis tool, Yuga, to detect potential lifetime
annotation bugs. Yuga uses a multi-phase analysis approach, starting with a
quick pattern-matching algorithm to identify potential buggy components and
then conducting a flow and field-sensitive alias analysis to confirm the bugs.
We also curate new datasets of lifetime annotation bugs. Yuga successfully
detects bugs with good precision on these datasets, and we make the code and
datasets publicly available for review.

Rust, Lifetimes, Static analysis, Memory safety

††ccs: Software and its engineering Software maintenance tools††ccs: Software
and its engineering Software libraries and repositories††ccs: Software and its
engineering Software testing and debugging††ccs: Software and its engineering
Maintaining software

##  1\. Introduction

The Rust programming language is gaining increasing popularity among systems
programmers for its efficient performance while providing strong memory
safety, thread safety, and type checking. It uses a C-like syntax that allows
low-level access, enabling it to be used on embedded devices, to write kernel
code, to build performance-critical systems, and so on. At the same time, it
ameliorates many of the pitfalls of C, like pointer errors and concurrency
errors. For these reasons, Google recently extended support for developing the
Android OS in Rust (google-2021a, 10), and Rust is officially supported in the
Linux kernel as of Linux 6.1 (vaughan-nichols-2022, 32).

Rust memory safety model. While working within the secure confines of Rust, we
enjoy robust safety guarantees. Central to these assurances is Rust’s
Ownership model—a set of rules dictating memory management within a Rust
program. Ownership guarantees that each value and its associated memory are
owned by exactly one identifier at any point in the program. Modern
programming languages handle memory usage during execution in different
ways—some rely on garbage collection (e.g., Java) and others on manual
allocation and deallocation (e.g., C). Rust takes an alternative approach with
the concept of ownership, reinforced by a specific set of compiler-verified
rules. Any violation of these rules results in a compilation failure. Yet,
none of these rules significantly slow down the run-time of Rust programs.

(a) Ownership. The read of a at Line 3 causes the program to not compile
because b has taken ownership of the String value and so a is not live.

(b) Borrowing. When the String is borrowed by b (Line 2), a still retains
ownership of the String and so of the heap region XXXX which the String owns.

Figure 1. Ownership and Borrowing. The color of an identifier indicates the
color of the heap region it owns.

However, the strict ownership policy—each value owned by only one identifier
at any given time, is often overly limiting. Thus, Rust allows
Borrowing—another identifier may temporarily borrow a value under certain
conditions by creating a reference to that value. Consider the statement a =
&b, here a is borrowing the value b. Rust further introduces the concept of
Lifetimes to restrict a borrow’s scope—a lifetime is a region of the source
code in which the borrowing identifier is live; the borrowing identifier must
not outlive the borrowed value (_e.g.,_ a cannot outlive b in the above
example).

The Rust compiler, specifically its Borrow Checker, ensures the validity of
all borrows by tracking variable lifetimes. Often the checker can infer the
lifetime of a variable without assistance. However, for certain cases related
to inter-procedural reasoning, the compiler requires explicit lifetime
annotations on function signatures to guide the Borrow Checker. For example,
the type &’a i32 denotes a borrow to an integer value, where the lifetime of
the borrow is parameterized by the lifetime annotation ’a. These annotations
on the function signature provide valuable information to the compiler,
enabling it to verify certain memory safety properties without even looking at
the function body.

Violation of memory safety guarantees. Despite the strong safety guarantees
promised by Rust, an increasing number of security vulnerabilities have been
reported in Rust projects. The number of vulnerabilities reported to the
RUSTSEC Database (rustsec, 25) during 2018 was only 22; in 2022, there were
91. The majority of these vulnerabilities arise from the use of a language
feature called unsafe Rust (xu2020memory, 35)—Rust’s memory safety guarantees
can be too restrictive for some applications, so Rust provides an “escape
hatch” in the form of unsafe Rust, which allows writing code that bypasses
some memory safety checks. The added flexibility comes at the cost of
potential memory safety-related bugs.

Thus, while using unsafe Rust, it is the developer’s responsibility to ensure
the code is correct—a single mistake may jeopardize the whole program’s safety
guarantees and inadvertently introduce vulnerability. One of the causes of
such vulnerabilities is incorrect lifetime annotations (LAs) on function
signatures. Deciding the correct LAs for a variable is non-trivial—it requires
expert knowledge of how the value will propagate to subsequent borrows and
pointers, often through deeply nested structures and function calls. Further,
lifetimes in Rust are a non-intuitive concept even for experienced
programmers, as there is no analogous concept in any other popular programming
language (to the best of our knowledge). A one-token mistake in specifying
correct LAs can lead to security vulnerabilities(futures_rs, 28), as we see
from a manual inspection of reported Rust security vulnerabilities.

Limitation of Existing Approaches. Checking the safety of unsafe Rust is an
active area of research (baranowski2018verifying, 5, 19, 18, 31, 1, 24), with
multiple reported vulnerabilities (rustsec, 25, 35), and automated tools that
perform static (bae2021rudra, 4, 14, 8, 6), and dynamic (miri, 20, 26)
analysis to check for vulnerabilities. However, none of these existing tools
can detect memory-safety bugs due to incorrect LAs. First of all, LA-related
bugs are rare and typically only surface during execution in specific edge
cases. Thus, detecting them through dynamic analysis is non-trivial.
Additionally, they tend to be deeply embedded within a program, and analyzing
them requires accurate modeling of program memory. Thus, it becomes
challenging to study using standard static analyzers or symbolic execution
tools. Even, more mature hybrid vulnerability detection tools designed for
other languages like C/C++ cannot be applied here as LA is a new concept
introduced in Rust.

To this end, we propose a novel static analysis tool to check correct memory
usage in unsafe Rust code. In particular, we focus on detecting incorrect
lifetime annotations (LAs) as they often lead to security vulnerabilities.

Our approach: We have developed and implemented a novel static analysis tool
called Yuga, capable of detecting incorrect LA bugs. We employ a multi-phase
analysis approach that starts with a pattern-matching algorithm to quickly
identify the potential buggy components. Subsequently, we perform a flow and
field-sensitive alias analysis, focusing only on the potential buggy
components to confirm the bugs. By adopting this multi-phase analysis, we
effectively address the well-known scalability challenges associated with
alias analysis, while still achieving reasonably high precision.

In particular, Yuga operates in four stages. First, it propagates the LAs from
a function parameter to internal references, pointers, and fields, using an
AST-like representation. In the second stage, it identifies any potential
mismatches in LAs between the function arguments and return values. These
first two steps are challenging since they involve analyzing relationships
between program variables through nested pointers and structures. When a
mismatch is found, Yuga flags the corresponding pairs of values as potentially
buggy. In the third stage, Yuga conducts a flow and field-sensitive alias
analysis to confirm the interactions between the source and target, further
validating the presence of bugs. Up to this point, the analysis is intra-
procedural. In the final stage, Yuga employs specific shallow filters based on
common inter-procedural knowledge to reduce false positives, improving the
overall precision.

Results. We evaluate Yuga using a dataset of known security vulnerabilities,
and a synthesized vulnerability dataset. We find that Yuga can detect LA bugs
with 75% precision. None of the existing static analysis tools we evaluated
could detect any of these vulnerabilities. We also ran Yuga on 372 Rust
libraries, and Yuga detected 312 potential bugs. We are in the process of
generating exploits of these bugs and reporting them to the developers.

Contributions: Our contributions in this paper are as follows.

  1. (1)

We are the first to characterize incorrect lifetime annotations that can lead
to memory safety bugs.

  2. (2)

We propose Yuga, a novel static analysis technique, that can automatically
scan Rust projects at scale and detect potential LA bugs that can lead to
vulnerabilities.

  3. (3)

We evaluate Yuga in a variety of settings and show that it can successfully
detect LA bugs with good precision. To the best of our knowledge, there are no
existing baseline static analyzers that can find these bugs.

  4. (4)

We contribute two new datasets of lifetime annotation bugs, one created from
Rust security vulnerabilities, and the other synthetic. We make the code and
dataset publicly available (anonymized for review) at
https://github.com/vnrst/Yuga.

The rest of the paper is structured as follows. In Section 2, we discuss the
features of Rust and lifetime annotations. Then, we define three patterns of
lifetime annotation bugs in Section 3.1. Section 3.2 presents the design of
Yuga, our tool to detect lifetime annotations bugs. We evaluate the
performance of Yuga in Sections 4 and 5, present related work in Section 7,
and conclude in Section 8.

##  2\. Background

(a) The lifetime of the borrow, _i.e.,_ b’s lifetime, must not extend beyond
the lifetime of the borrowed value a.

⬇

1let b : &i32;

2{ let a : i32 = 5;

3 b = &a;

4} println!("{}", b);

(b) The compiler will reject this program since b’s lifetime extends till Line
4, but a’s lifetime is terminated by the closing brace on Line 3.

⬇

1let mut a = 5;

2let ref1 = &a;

3let ref2 = &mut a;

4println!("{}", ref1);

(c) The compiler will reject this program because the lifetimes of immutable
borrow ref1 (Lines 2-4) and mutable borrow ref2 (Line 3) are not disjoint.

Figure 2. Lifetimes in Rust.

This section provides an overview of Rust’s ownership model and the memory
safety properties associated with it. Section 2.1 explains how Rust ensures
memory safety via its ownership model. LABEL:sec:unsafe_rust discusses how
Rust can be used in an unsafe manner.

###  2.1. Rust Memory Safety Model

####  2.1.1. Ownership.

Rust’s ownership model ensures that a memory location has exactly one owner at
any point in the program, and the associated memory is freed when the owner
goes out of scope. For example, in Figure 1(a), at Line 1, the identifier a is
assigned a String value. The characters of the String are stored on the heap,
and a takes ownership of this heap-allocated memory. At Line 2, a is assigned
to b. This move transfers the ownership of the heap-allocated memory to b.
Once b takes ownership of this memory, Rust no longer considers a use of a to
be valid, as a memory location must have exactly one owner. So the print
statement on Line 3 will result in a compile error.

####  2.1.2. Borrowing.

A value can be borrowed by creating a reference to that value using the ‘&’
symbol. A reference can be mutable or immutable, depending on whether one can
modify the borrowed value through the reference or not, respectively. Mutable
references are denoted as &mut. Figure 1(b) illustrates borrowing. At Line 1,
String "Hello" is assigned to an identifier a, and a takes ownership of the
String. At Line 2, b merely borrows the String (i.e., it does not take
ownership) by taking a reference to a. a retains ownership of the heap-
allocated memory associated with the String. Consequently, the compiler does
not reject the use of a at Line 3, and the program compiles.

⬇

struct Foo<’a> {

x: *const String,

..

}

fn bar<’a,’b>(arg1: &’a String, arg2: &’b String)

-> Foo<’a> {

Foo{x: arg2 as *const String, ..}

}

(a) The function returns a pointer that derives from arg2, but the annotation
indicates that it uses arg1.

(b) The string v2 is dropped on Line 4, and bar_obj will contain a pointer to
freed memory. This can cause a use-after-free error.

Figure 3. Incorrect lifetime annotations on functions can cause memory safety
errors.

####  2.1.3. Lifetimes.

A Rust lifetime is similar to a scope—it is a statically determined region of
a program. However, unlike a scope, it is not always defined by a lexical
marker such as a closing curly brace (nonlexicallifetimes, 17). For example,
in Figure 2(a), b’s lifetime is just Lines 3-4.

If a reference is assigned to an identifier, _e.g.,_ b = &a, then the lifetime
of the identifier is called the lifetime of the borrow. Two rules constrain
the lifetimes of borrows:

  1. Rule 1:

The lifetime of a borrow must not extend beyond the lifetime of the borrowed
value. In other words, the borrowed value must “outlive” the borrow.

  2. Rule 2:

If there are multiple borrows to the same value, every mutable borrow must
have a lifetime which is disjoint from that of every other borrow, whether
mutable or immutable.

Rust’s Borrow Checker ensures that these rules are not violated. The Borrow
Checker must assign a lifetime to each identifier such that the assignment
satisfies these rules. Rule 1 helps prevent some common memory errors as use-
after-free and double-free. Rule 2 promotes thread safety by preventing
concurrent writes and deadlocks. It further allows the compiler to perform
numerous low-level optimizations, e.g., eliminating unnecessary reads from
memory.

Figure 2 illustrates the concept of lifetimes. In Figure 2(a), a owns the
String while b borrows it. By Rule 1, it is essential that a outlives b, and
this is satisfied. In contrast, in Figure 2(b), b’s lifetime extends until
line 4, but a’s lifetime extends only until line 3. So the Borrow Checker
rejects this program. In Figure 2(c) the lifetime of ref2 (Line 3), which
borrows a mutably, is not disjoint from the lifetime of ref1 (Line 2-4) which
also borrows a. So the Borrow Checker will reject this program by Rule 2.

##### Lifetime Annotations on Functions.

So far, we have discussed how the compiler infers lifetimes when a reference
is assigned directly to an identifier, like b = &a. Now consider a function
call where a parameter or return type is a reference. In the simple case of a
function with one reference parameter and one returned reference, e.g., fn
foo(x: &String) -> &String, the lifetimes of the argument and the returned
reference are calculated as if the invocation of the function is just a use of
the argument. So,

⬇

let b = String::from("Hello");

let a = foo(&b);

is equivalent to

⬇

let b = String::from("Hello");

let a = &b;

for the purpose of inferring lifetimes. In both cases, the lifetime of a is
considered as the lifetime of the borrow, and b must outlive a. Consider,
however, a function that takes more than one parameter.

⬇

fn foo(x: &String, y: &String) -> &String

The returned reference must not outlive the value that it’s borrowing, by Rule
1. But it’s not clear what that borrowed value is. It could be derived from
any one of the two input arguments. In this situation, the compiler requires
the developer to add LAs.

⬇

fn foo<’a,’b>(x: &’a String, y: &’b String) -> &’b String { y }

Here, ’a and ’b are lifetime annotations (LAs) that represent the actual
lifetimes of the two input borrows. In this example, the developer has chosen
to declare that the returned reference derives from the second argument, by
placing the lifetime parameter ’b on the type of the second parameter and on
the return type. The compiler will reject the function if the returned
reference is not a reference to some part of y.

LAs are only a syntactic representation of a concrete lifetime, _i.e.,_ a
region of code. However for conciseness, we shall sometimes use expressions
like “the lifetime ’a” to mean “the lifetime associated with the LA ’a”.

##### Lifetime Annotations on Structures.

LAs can be used only in two specific contexts - the first is in function
signatures, as shown above, and the second is in the declaration of algebraic
data types like structures. If a structure contains a reference as one of its
fields, then that reference must have an associated LA. Further, that same
annotation must appear as part of the structure type. For example, !struct
Foo<’a> { x: &’a i32 }! is a structure \TT{Foo} containing a reference with
\la \TT{’a}, so it carries the annotation \TT{<’a>} as part of its type. %
Conversely, if a structure has no \las as part of its type, then it does not
contain any references. The significance of this annotation is that \TT{’a} is
the lifetime of the borrow, \textit{so the structure object must not outlive
\TT{’a}}. % The key principle with structures is that a structure’s lifetime
is bounded by the lifetime of every one of its reference fields. %\rust uses
{\em lifetimes}, a construct that assists the borrow checker (a compiler pass)
in verifying the validity of all the borrows. Lifetimes are similar to
scopes\textemdash a variable’s lifetime starts when it is created and ends
when it is destroyed (see~\Cref{fig:lifetime-a}\textemdash variable \TT{a}’s
lifetime, shown in the green line, starts at its declaration and ends at the
end of the function body). Note that a borrow variable and its value, \ie the
resource it is borrowing, can have different lifetimes. For example in
~\Cref{fig:lifetime}, borrow \TT{b}’s lifetime is shown in blue, while its
borrowed value \TT{a}’s lifetime is different, as marked in green. %To ensure
memory safety, the borrow checker ensures the following two rules : %\be
%\item[\textbf{Rule 1:}] \textit{The lifetime of a borrow cannot be longer
than the lifetime of the borrowed value.}~\Cref{fig:lifetime-b} shows an
example. Such a rule ensures that memory safety issues like use-after-free or
dangling pointers cannot happen as it disallows any references that outlive
the owner. %\rayb{Error in the figure...is it in the right line? shouldn’t it
be on the next line?} %\item[\textbf{Rule 2:}] \textit{In a given scope, for a
given variable, one can either have a single mutable borrow or any number of
immutable borrows.} %That means two mutable borrows to the same value in one
scope, or any combination of mutable and immutable borrows is not allowed.
%This is also implemented using lifetimes - the compiler checks if the
lifetimes of the borrows overlap. %~\Cref{fig:lifetime-c} shows an example.
%This rule disallows concurrent reads and writes at the same memory region and
thus prevents race conditions and other memory safety bugs that may arise due
to accessing invalid references. %\ee %Within a function, the compiler infers
all lifetimes automatically. But once a variable \textit{crosses function
boundaries}, in some cases the compiler does not automatically assign a
lifetime. Consider a function that takes two borrows as inputs and returns one
borrow. % \begin{lstlisting}[language=Rust, frame=none, style=colouredRust,
basicstyle=\small\ttfamily] %fn foo(x: &String, y: &String) -> &String
%\end{lstlisting} %\noindent The returned borrow must use one of the two input
borrows, but there is ambiguity about which one. The two input borrows could
have different lifetimes, in which case an appropriate lifetime must be
assigned to the returned borrow. Now although the compiler could technically
look at the body of the function and infer the lifetime of the returned
borrow, Rust makes a deliberate choice \textit{not} to infer certain borrow
lifetimes in function signatures\footnote{Except in some specific cases. See
\url{https://doc.rust-lang.org/nomicon/lifetime-elision.html}}. In this case,
the lifetimes must be specified using \textit{\las}. %
\begin{lstlisting}[language=Rust, frame=none, style=colouredRust,
basicstyle=\small\ttfamily] %fn foo<’a,’b>(x: &’a String, y: &’b String) % ->
&’b String { y } %\end{lstlisting} %Here \TT{’a} and \TT{’b} are lifetime
parameters. This function signature indicates that the function takes two
borrows, and returns another borrow with the lifetime of the \textit{second}
input borrow. The implementation, i.e., the body of the function, must match
its signature. %At compile time, the compiler assigns concrete lifetimes to
each lifetime parameter\cite{nonlexicallifetimes}.\footnote{A recent
reformulation of the borrow checker conceptualizes borrows as sets of
\textit{loans}, not regions. \cite{matsakis_2018}} If a borrow is annotated
with lifetime parameter \TT{’a}, then the borrowed value remains borrowed for
the \textit{entire} concrete lifetime associated with \TT{’a}. In conjunction
with Rule 1, this gives us the following interpretation of \las. %\noindent
\textbf{Rule 3:} \textit{If a borrow is annotated with lifetime parameter
\TT{’a}, then the borrowed value must live longer than (must outlive) the
concrete lifetime corresponding to \TT{’a}.} %\noindent Throughout the rest of
this paper, we shall use ‘‘a borrow has lifetime \TT{’a}’’ as shorthand for
‘‘a borrow is annotated with lifetime parameter \TT{’a}’’. %\noindent
Structures can also have \las. If a structure \TT{Foo} contains a borrow with
lifetime \TT{’a}, then the structure must be annotated with the same lifetime,
like \TT{Foo<’a>}. This means that all the ‘‘underlying’’ values of the
structure outlive \TT{’a}. And if a structure has no \las, then it contains
only owned values and no borrows. % Here \TT{’a} and \TT{’b} are lifetime
parameters. Informally, if a borrow is annotated with lifetime parameter
\TT{’a}, then the borrowed data lives \textit{at least} as long as \TT{’a}.
This function signature indicates that the function takes two borrows, and
returns another borrow with the lifetime of the \textit{first} input borrow.
This is analogous to how a statically typed language requires types to be
specified for all function parameters and returned values. The implementation,
i.e., the body of the function, must match its signature. So the following
code will \textbf{not} compile. % \begin{lstlisting}[language=Rust,
frame=none, style=colouredRust] % fn foo<’a,’b>(x: &’a String, y: &’b String)
% -> &’a String { y } % \end{lstlisting} % The compiler gives an error -
‘‘function was supposed to return data with lifetime \TT{’a} but it is
returning data with lifetime \TT{’b}’’. We can see that Rust clearly can infer
from the body that the returned borrow has lifetime \TT{’b}, but it still
requires explicit annotation as part of the function signature. This is a
design choice that the Rust language makes, to not infer \las in a function
signature except in some special cases\footnote{https://doc.rust-
lang.org/nomicon/lifetime-elision.html}. %\subsection{Raw Pointers and Unsafe
\rust} \subsection{Unsafe \rust} \label{sec:unsafe_rust} The framework
discussed above guarantees memory safety~\cite{bae2021rudra,nomicon}. However,
these guarantees are inherently conservative and prevent access to many useful
constructs often required for systems programming, like low-level memory
manipulation, external function calls, etc. To support such functionalities,
\rust has an extended language called unsafe \rust, which allows some
additional features that bypass some of the safety guarantees of safe \rust.
In this connection, we discuss the \TT{unsafe} keyword, \textit{raw pointers},
and \textit{lifetime annotation}. Evans \etal~\cite{evans2020rust} provide a
more comprehensive discussion of unsafe \rust. \subsubsection{The \TT{unsafe}
Keyword.} The \TT{unsafe} keyword is used to mark off regions containing
unsafe \rust from the rest of a program. If a function is marked unsafe then
the body of the function may use unsafe Rust and a function caller must treat
the function as unsafe. If a block within a function is marked unsafe, then it
is the responsibility of the developer to ensure the the function % has been
written in such a way that it behaves as if it were written entirely in safe
\rust. provides the same guarantees of safe \rust when it is used. Just one
function that violates this contract may introduce errors that break the
memory safety guarantees of the entire program. %Alternatively, the unsafety
can be ‘‘encapsulated’’ within an \TT{unsafe} block inside the function body.
In this case, the function must behave like a regular function to its callers.
For unsafe code, the onus is on the programmer to make sure that a function
encapsulates its unsafety appropriately. Even a single function that violates
memory safety properties can break the memory safety guarantees of the entire
program. \subsubsection{Raw Pointers.} %Raw pointers (\TT{*const}, \TT{mut})
Raw pointers are similar to pointers in C - they obey none of the guarantees
that references in \rust are expected to obey. For example, one can have
mutable and immutable raw pointers to the same location. The memory location
it points to need not live as long as a raw pointer itself, which means that a
raw pointer is not guaranteed to point to valid memory. A raw pointer type
does not allow \las. % \rayb{the following might go away---it is becoming very
complicated to understand the details.} % Consider the same program from
earlier, except we return a raw pointer instead of a borrow. %
\begin{lstlisting}[language=Rust, frame=none, style=colouredRust] % fn
foo<’a,’b>(x: &’a String, y: &’b String) % -> *const String % { y as *const
String } % \end{lstlisting} % This is perfectly valid and will compile. Notice
that if the memory that \TT{y} points to is freed, the raw pointer will point
to invalid memory! % \begin{lstlisting}[language=Rust, frame=none,
style=colouredRust] % let v1 = "Hello".to_string(); % let v2 =
"World".to_string(); % let raw = foo(&v1, &v2); % drop(v2); // raw points to
freed memory! % \end{lstlisting} Although \textit{creating} and manipulating a
raw pointer is permitted in safe Rust, any \textit{dereference} of a raw
pointer must be done in an \TT{unsafe} block or function.
\subsubsection{Unsafe Code and Lifetime Annotations.}
\label{sec:back_life_anno} Although raw pointers themselves don’t have \las,
they can be contained within \textit{structure objects}, and these structure
objects can have associated \las. In ~\Cref{fig:encapsulating}, function
\TT{bar} returns a structure containing a raw pointer. In \TT{bar}’s signature
the placement of the \la \textcolor{red}{\TT{’a}} in \TT{x:
\&\textcolor{red}{’a}} and \TT{Foo<\textcolor{red}{’a}>} informs the compiler
that the % lifetime of the returned structure is bounded by the lifetime of
the first argument in any invocation of \TT{bar}. structure object is tied to
the lifetime of \TT{x}. % \noindent We can see from this function signature
that the function returns a structure object with the lifetime of the input
borrow \TT{y}. Now if \TT{y} is dropped while the structure object is still
live, this \textit{will not compile}. This is shown in~\Cref{fig:invalid}. %
In this way, we can ‘‘encapsulate’’ raw pointers within structures and use the
\las on these structures to ensure memory safety. We will discuss this in more
detail in~\Cref{sec:patterns}. Although the code in the example contains no
\TT{unsafe} regions, it still contains a bug which the compiler did not
detect; the \la on the result type should be \TT{b}, not \TT{a}, because it is
\TT{y}, not \TT{x}, which is assigned to the \TT{inner} field of the returned
structure. This can pose a problem as shown in Fig \ref{fig:invalid}. The
borrow lifetime \TT{’a} is tied to \TT{bar\\_obj}, and extends till Line 5.
But the borrow lifetime \TT{’b} extends only till line 3, and so
\textit{\TT{v2} is no longer borrowed after line 3}. It can be dropped on Line
4 without a compile error. Now the \TT{inner} field of \TT{bar\\_obj} points
to freed memory, and will result in a use-after-free error if dereferenced in
an \TT{unsafe} block. % The error manifests when \TT{bar} is invoked in the
example in ~\Cref{fig:invalid}. The lifetime of the result is, erroneously,
bounded by the lifetime of \TT{v1}. \TT{v2}’s lifetime does not need to extend
longer than the function invocation where it is used on Line 3. Its memory may
be released immediately after the function returns; in the example, it is
explicitly released on Line 4 by the invocation of the \TT{drop} function. Any
subsequent dereference of the \TT{inner} field of \TT{bar\\_obj}, which must
occur in an \TT{unsafe} region, will read the location referred to previously
by \TT{v2}. This dereference is undefined behavior, and may result in an error
of the program. % The key difference here is that Rust \textit{cannot}
automatically infer the lifetimes in the function signature, because it does
not track lifetimes through raw pointers. So it relies on our provided
annotations in the signature being compatible with the implementation of the
function. In~\Cref{fig:encapsulating}, the signature now indicates that the
returned structure object has the lifetime of \textbf{\TT{x}}, but the
returned structure contains a pointer to \textbf{\TT{y}}. As shown
in~\Cref{fig:invalid}, this could cause a use-after-free error, which is an
example of Undefined Behaviour (UB). % If a structure contains raw pointers,
then there could be some methods that use unsafe code to dereference these raw
pointers. Figure \ref{fig:encapsulating} shows an example of such a program,
where a raw pointer is dereferenced inside an \TT{unsafe} block in the
\TT{get()} function. % Is it possible for this function to behave in a safe
manner to its callers? That is, \textit{no matter how this function is called,
can we have the same memory safety guarantees as safe \rust?} % This can be
achieved through proper \las. % For example, in~\Cref{fig:encapsulating}, we
annotate both \TT{self} and the returned \TT{String} reference with a \la
\textcolor{red}{\TT{’a}}. Informally, this annotation means that
\textit{\TT{self} will remain borrowed for as long as the returned reference
is used.} Further, \Cref{fig:invalid} creates a string \TT{s} inside a block
(at line 3), and tries to assign a borrow to \TT{s} to variable \TT{x}.
However, \TT{x} lives longer than the scope of \TT{s}. So once the string
\TT{s} is dropped on line 6, the variable \TT{x} points to invalid memory. The
\las \textcolor{red}{\TT{’a}} ensure that this program does not compile.
Recall that \TT{foo} remains borrowed as long as \TT{x} is used, till line 7.
But the object \TT{foo} lives only till line 6. A borrow cannot outlive the
borrowed value, so this will not compile. The compiler will report that
‘‘\TT{foo} doesn’t live long enough’’. % \subsection{Lifetime Rules} % Now
that we’ve provided an intuition for what \las mean, we provide some rules for
how to interpret them. At compile time, \rust translates each \la into a
concrete lifetime corresponding to a statically defined region of the program
\cite{nonlexicallifetimes} \footnote{A recent reformulation of the borrow
checker conceptualizes borrows as sets of \textit{loans}, not regions.
\cite{matsakis_2018}}. The rule that the compiler follows while translating
lifetime parameters on borrows into concrete lifetimes is as follows: %
\noindent \textbf{Rule 2.1:} \textit{If a borrow is annotated with lifetime
parameter \TT{’a}, then the borrow cannot last longer than (cannot outlive)
the concrete lifetime associated with \TT{’a}.} % \noindent When the borrow
checker validates a borrow with lifetime parameter \TT{’a}, the lifetime of
the borrow is taken as the \textit{entire} concrete lifetime associated with
\TT{’a}. In conjunction with Rule 1.1, this means that the borrowed value must
outlive \TT{’a}. This gives us the following equivalent form of Rule 2.1,
which we believe is more intuitive and easier to reason about: % \noindent
\textbf{Rule 2.1 (alternative statement):} \textit{If a borrow is annotated
with lifetime parameter \TT{’a}, then the borrowed value must live longer than
(must outlive) the concrete lifetime associated with \TT{’a}.} % \noindent
Throughout the rest of this paper, we shall use ‘‘a borrow has lifetime
\TT{’a}’’ as shorthand for ‘‘a borrow is annotated with lifetime parameter
\TT{’a}’’. Structures can also have \las, like \TT{Foo<’a>}. The meaning of
these annotations is as follows: % \noindent \textbf{Rule 2.2:} \textit{If a
structure is annotated with lifetime \TT{’a}, then it contains a borrow with
lifetime parameter \TT{’a}. Further, if a structure contains a borrow with a
lifetime parameter \TT{’a}, then the structure must be annotated with
\TT{’a}.} % \noindent This means that if a structure has a single \la \TT{’a},
then all the ‘‘underlying’’ values (values borrowed by fields) in this
structure outlive \TT{’a}. And if a structure contains no \las, then it
contains no borrows and all its underlying values are owned by the structure
object. % \begin{figure}[h] % \centering %
\includegraphics[width=0.5\textwidth]{figures/concrete.pdf} %
\caption{Assignment of a concrete lifetime to \TT{’a} in the example in Figure
\ref{fig:invalid}. The concrete lifetime (\dkgreen{green}) must be at least as
long as the implicit borrow to \TT{foo} (\orange{line 5-6}) and \TT{\&’a
String} (\blue{\textbf{line 5-7}}).} % \label{fig:concrete} % \end{figure} %
So each \la defines a constraint, and the compiler solves these constraints.
The concrete lifetime is chosen as the \textit{smallest} span of code that
satisfies all the constraints. Figure \ref{fig:concrete} shows the assignment
of a concrete lifetime for the example from Figure \ref{fig:invalid} %
\rayb{Can Figure \ref{fig:concrete} and Figure \ref{fig:invalid} put as sub
figures?}. The concrete lifetime must: % \be % \item extend at least until the
end of the lifetime of the returned reference \TT{\&’a String} (\textbf{line
5-7}). % \item extend at least until the end of the lifetime of the implicit
borrow to \TT{foo} (\textbf{line 5-6}). % \ee % The shortest span of code that
satisfies these constraints is \textbf{line 5-7}. So that is the concrete
lifetime associated with \TT{’a}. This means that \TT{foo} remains borrowed as
\TT{\&’a self} until line 7, but \TT{foo} is dropped on line 6, which causes
the borrow checker to raise an error. % The rule that the compiler follows
while translating lifetime parameters into concrete lifetimes is as follows.
If a variable is annotated with lifetime \TT{’a}, then the concrete lifetime
associated with \TT{’a} must be \textit{at least as long} as the lifetime of
the variable. % Such feature can also prevent illegal memory access by raising
compilation error, as shown in~\Cref{fig:invalid}. % Here, a short-lived value
is assigned to a longer-lived reference---the call to \TT{foo.get()} on Line 6
contains an internal borrow \TT{\&mut foo}~\rayb{Why foo, why not foo.inner?}.
The lifetime of this \TT{\&mut foo} (\textcolor{blue}{blue}) is constrained to
be at least as long as the lifetime of \TT{x} (\textcolor{orange}{orange})
because of the \TT{’a} lifetime constraint in the \TT{get} method. But the
lifetime of \TT{\&mut foo} (\textcolor{blue}{blue}) exceeds the lifetime of
\TT{foo} (\textcolor{ForestGreen}{green}). % A borrow cannot outlive the
borrowed value, so this will not compile. %In particular, if a function is not
marked \TT{unsafe}, then one must be able to call this function in any
context, with any combination of arguments, and not result in memory errors.
The onus is therefore on the programmer to make sure that a function
encapsulates its unsafety appropriately. Even a single function that can cause
memory safety errors breaks the memory safety guarantees of the entire
program. % Since we cannot rely on the borrow checker to validate borrows
involving raw pointers, we need other mechanisms to verify memory safety
properties. For \textit{structures} that contain raw pointers, RUST provides a
type in its standard library called \TT{PhantomData}. If a structure contains
an element of type \TT{PhantomData<&’a T>}, then it \textit{acts like} it
contains a borrow to a type \TT{T} with lifetime \TT{’a}, even though it may
not. This allows us to upper bound the lifetime of the structure by \TT{’a}. %
Consider the following definition of a structure \TT{Foo} containing a raw
pointer \TT{inner} and a \TT{PhantomData} field. We also define a method
\TT{set} on this structure that takes a reference with lifetime \TT{’a} and
assigns it to the raw pointer inside the structure. % Now, suppose we try to
use the \TT{set} method to create a borrow within a structure object that
lives shorter than the structure object itself. %
\lstset{xleftmargin=0.1\columnwidth, xrightmargin=0\columnwidth} %
\begin{lstlisting}[language=Rust, frame=none, style=colouredRust,
basicstyle=\footnotesize \ttfamily, numbers=left] % let i: i32 = 5; % let mut
foo = Foo{inner: &i, % phantom: PhantomData}; % { % let j: i32 = 10; %
foo.set(&j); % } % // Do something with foo here % \end{lstlisting} % The
first borrow \TT{\&i} is valid because there is a concrete lifetime comprising
lines 1-2 that satisfies the necessary constraints corresponding to \TT{’a}.
But when we consider the second borrow \TT{\&j}, the concrete lifetime
corresponding to \TT{’a} must: % \bi % \item not be longer than the lifetime
of \TT{j} % \item be at least as long as the lifetime of \TT{foo} % \ei %
There is no lifetime that satisfies these constraints, and the program will
not compile. So as long as we use only the \TT{set} method, we will have the
same memory safety guarantees as safe RUST. This means that the unsafe block
is encapsulated completely within the \TT{set} method.

##  3\. Methodology

This section is organized as follows. First we describe our process of
classifying and characterizing LA bugs in Section 3.1. Then we use these
patterns to develop Yuga, as described in Section 3.2.

###  3.1. Characterizing LA Bugs

In this subsection, we characterize the various types of bugs that arise from
incorrect LAs.

##### Overview.

Within a function, some values may be transferred between two arguments (arg-
arg) or between an argument and returned value (arg-return). When the transfer
of a value happens, the LAs on the target of the transfer should be consistent
with the source of the transferred value. Otherwise, it leads to a LA bug.

Arguments and return types are the only places where LAs can occur in a
function signature. Therefore, all LA bugs fall into one of two categories:
(i) mismatched arg-arg or (ii) mismatched arg-return. This claim is validated
by an initial study of LA bugs reported to the RustSec Security Advisory
Database (see Section 5 for details). Such incorrect LAs may lead to memory
safety bugs, like:

  1. (1)

Use-after-free: Such bugs occur when we attempt to access memory that has been
freed or de-allocated.

  2. (2)

Non-exclusive mutability: Such bugs occur when two mutable borrows co-occur
within the same lifetime.

We describe these bugs in the rest of the section in detail.

####  3.1.1. Use-after-free Bugs

Let’s say a function takes a value that is associated with a borrow lifetime
’a and assigns it to a location where it is associated with a borrow lifetime
’b. If ’b is longer than ’a, a use-after-free error could occur (violation of
Rule 1 in Section 2.1.3). This kind of error can be caused by arg-arg or arg-
return assignment.

Arg-Return Assignment:

Table 1. Lifetime Annotation Bugs of Different Types. The incompatible
lifetime annotations are highlighted in red. Example 1. RUSTSEC-2021-0130: A
use-after-free bug in the lru crate caused by assigning a value from an
argument to return (arg-return)
---
⬇ 1pub struct LruEntry<K, V> { 2 next: *mut LruEntry<K, V>, .. 3} 4pub struct
LruCache<K, V> { 5 head: *mut LruEntry<K, V>, .. 6} 7pub struct Iter<’a, K:
’a, V: ’a> { 8 ptr: *const LruEntry<K, V>, .. 9} 10impl<K, V, S> LruCache<K,
V, S> { 11 ... 12 pub fn iter<’a>(&’_ self) -> Iter<’a, K, V> {  13 Iter { 14
ptr: unsafe { (*self.head).next }, 15 .. 16 } 17 } 18}
Example 2. RUSTSEC-2021-0128: A use-after-free bug in the rusqlite crate
caused by assigning a value from one argument to another argument (arg-arg).
⬇ 1pub struct InnerConnection { 2 db: *mut ffi::sqlite3, 3 .. 4} 5pub struct
Connection { 6 db: RefCell<InnerConnection> 7} 8impl Connection { 9 .. 10 pub
fn update_hook<’c, F>(&’c self, hook: Option<F>) 11 where 12 F: .. + ’c 13 {
14 self.db.borrow_mut().update_hook(hook); 15 } 16}
Example 3. RUSTSEC-2020-0023: A non-exclusive mutability bug in the rulinalg
crate caused by assigning a value from an argument to return (arg-return)
⬇ 1pub struct MatrixSliceMut<’a, T: ’a> { 2 ptr: *mut T, .. 3} 4pub struct
RowMut<’a, T: ’a> { 5 row: MatrixSliceMut<’a, T> 6} 7impl<’a, T: ’a>
RowMut<’a, T> { 8 /// Returns the row as a slice. 9 pub fn raw_slice_mut(&’_
mut self) -> &’a mut [T] { 10 unsafe { from_raw_parts_mut(self.row.ptr, ..) }
11 } 12}

Example 1 in Table 1 shows an example of a real-world use-after-free bug
caused by arg-return assigningment. On Line 12, the function iter, takes an
argument self, and by following the fields of each structure, we see that
(*self.head).next is a raw pointer to a value of type LruEntry, and it is
associated with the LA ’_. On Line 14, it is assigned to the ptr field of the
returned Iter object, where it is associated with the LA ’a on Iter<’a, ..>.
The LAs do not correctly specify the relationship between the lifetimes of the
two values, so the compiler will accept a program that uses the returned Iter
object even after (*self.head).next has been freed, leading to a use-after-
free.

Arg-Arg Assignment: There is a subtle difference in checking LAs for arg-arg
assignments. In Example 2 in Table 1, for every call of the update_hook
function, hook must live at least as long as self. However, the LAs do not
enforce this requirement and could lead to a use-after-free. Both hook and
self have the same LA ’c, which means that they both live at least as long as
’c. But this does not mean that hook lives as long as self.

####  3.1.2. Non-Exclusive Mutability Bugs

Incorrect LAs can allow the lifetimes of multiple mutable borrows to overlap
(i.e., violate Rule 2 in Section 2.1.3), leading to non-exclusive mutability.
This kind of error can be caused by arg-return or arg-arg assignment. However,
in our empirical analysis (as we shall describe in Section 4.2.3), we did not
observe any non-exclusive mutability bugs caused by arg-arg assignment. We
therefore exclude them from the scope of this paper, and leave it to future
work.

Example 3 in Table 1 shows a real-world example of a non-exclusive mutability
bug caused by arg-return assignment. On Line 9, raw_slice_mut, takes a mutable
borrow to self. The mutable pointer self.row.ptr of type *mut T is re-borrowed
for the lifetime ’_. This same value is then returned through a borrow with
lifetime ’a. It is possible for ’a to be longer than ’_, so raw_slice_mut can
be called multiple times to create multiple mutable borrows to the same
*(self.row.ptr) value.

###  3.2. Algorithm Design

⬇

struct Foo<’a> { x: *mut String,

w: &’a mut i32 }

struct Bar { y: String,

z: *mut i32 }

fn bar<’a,’b>(arg1: &’a mut i32,

arg2: &’b mut Bar)

-> Foo<’a> {

let ret = Foo{ x: &mut (*arg2).y,

w: arg1 };

ret

}

Value | Type | Borrowed For
---|---|---
arg1 | &’a mut i32 | None
*arg1 | i32 |  ’a
arg2 | &’b Bar | None
*arg2 | Bar | ’b
(*arg2).y | String |  ’b
(*arg2).z | *mut i32 |  ’b
*(*arg2).z | i32 |  ’b
ret | Foo<’a> | None
ret.w | &’a mut i32 | None
*(ret.w) | i32 |  ’a
ret.x | *mut String | None
*(ret.x) | String |  ’a

Figure 4. Motivating example. We calculate borrow lifetimes for each value and
look for lifetime bug patterns. The arrows $\longleftrightarrow$ show pairs of
values associated with potential violations, and the corresponding rows are
shaded in gray. We then use Alias Analysis to filter these violations, leaving
only the one shown with a red arrow $\longleftrightarrow$.

In this subsection, we present Yuga, a tool to automatically detect incorrect
LAs on function signatures in Rust projects. An overview of the entire system
is shown in Figure 5. The input to Yuga is the source code of a Rust project,
and the output is a list of functions with potential LA errors. At a high
level, Yuga works in four steps.

  * •

Step-I. Yuga extracts lifetimes from each type of a function signature.

  * •

Step-II. Next, Yuga uses these lifetimes to check for the LA bug patterns
identified in Section 3.1 and marks potential buggy functions.

  * •

Step-III. The potential buggy functions are then sent to an alias analyzer to
check whether values are actually transferred between the locations with LAs.

  * •

Step-IV. Finally, Yuga filters out some common patterns of false positives
that arise due to intra-procedural alias analysis.

We now discuss each step of our system in detail and refer Figure 4 as a
motivating example to illustrate the steps. In Figure 4, the function
signature is: fn bar<’a,’b>(arg1: &’a mut i32, arg2: &’b mut Bar) -> Foo<’a>.
This means that bar is a function name, and ’a,’b are LAs associated with the
function bar. The function takes a parameter arg1, which is a mutable
reference with borrow lifetime a to an i32 value, and another parameter arg2,
which is a mutable borrow with lifetime ’b to a structure of type Bar. The
function’s return type is Foo<’a>, which is a structure containing a reference
with borrow lifetime ’a.

####  3.2.1. Step-I: Get Borrow Lifetimes

Given a function argument or return type, we extract lifetimes for each nested
value as follows:

  1. (1)

If a value is borrowed with LA ’b, then the value and all its fields must
outlive ’b, as per Rule1 in Section 2.1.3. For example, in Figure 4, *arg2 is
borrowed with lifetime ’b, so *arg2 and (*arg2).y must outlive ’b.

  2. (2)

If a value is pointed by a raw pointer and the raw pointer is contained inside
a structure with LA ’a, then the value must outlive ’a. For example, in Figure
4, ret.x is a raw pointer inside a structure with LA ’a, so *(ret.x) must
outlive ’a.

  3. (3)

If a value is pointed by a raw pointer and the raw pointer is contained inside
a structure with no LA, then it is considered to be owned by the structure
object. For example, in Figure 4, (*arg2).z is a raw pointer in a structure
with no LA. So *(*arg2).z is considered to be owned by *arg2 and must outlive
’b.

The type system of Rust uses lifetimes to ensure memory safety when we are
only dealing with references. We extend this system to raw pointers using the
above rules by treating raw pointers as though they have borrow lifetimes too.
For a formal definition of these rules, please refer to the supplementary
material.

Figure 5. Yuga workflow.

####  3.2.2. Step-II. Check for Lifetime Bug Patterns

After we derive lifetimes for each value, we iterate through these lifetimes
and look for potential violations. As we discussed in Section 3.1, there are
two main causes of bugs - assignment from an argument to the returned value
(arg-return), or from an argument to another argument (arg-arg).

Arg-Return: We iterate through all the values in the arguments, and pair them
against all the returned values. We consider only the cases where at least one
of the two values is held by a raw pointer, because Rust will automatically
infer the lifetimes in all other cases. The patterns that we look out for are:

  1. (1)

Use-after-free: If the types match, and the lifetime of the returned value can
be longer than the lifetime of the value in the argument, then this is a
potential violation (see Rule1 in Section 2.1.3). For example, in Figure 4,
(*arg2).y and *(ret.x) have the same type String, but different lifetimes ’b
and ’a. This is a potential violation.

  2. (2)

Non-exclusive Mutability: If one value is of type *mut T or &mut T, and the
other value is of type T for some type T, then the lifetime of the latter
cannot be longer than the lifetime of the former (see Rule2 in Section 2.1.3).
For example, in Figure 4, (*arg2).z and *(ret.w) have types *mut i32, and i32,
but different lifetimes ’b and ’a. This is a potential violation.

Arg-Arg: We only focus on use-after-free bugs caused by assignments from
argument to argument. We take the two arguments at a time, and iterate through
all the pairs of values in these arguments. We ignore cases where both values
are behind immutable references because an assignment can only be performed if
one value is mutable. If the types of the two values match, then we report
this as a bug. The actual borrow lifetimes do not matter, as we discussed in
Section 3.1.1. For example, in Figure 4, *arg1 and *(*arg2).z have the same
type i32, and are mutable. So this is a potential violation.

####  3.2.3. Step-III. Perform Alias Analysis

The previous steps give us a list of pairs of values such that it would be
dangerous to perform an assignment between them. For instance, in Figure 4, if
the value in (*arg2).y becomes the value in *(ret.x), then this could lead to
a use-after-free.

This is the problem of alias analysis, or determining whether two pointers
point to the same memory location(landi1992undecidability, 13). Our algorithm
works by computing a “points-to” set of values that each pointer may point to.
It has the following properties:

  * •

Intra-procedural: We perform our analysis on each function body individually,
treating function calls as opaque.

  * •

Field-sensitive: We treat each field of a structure separately.

  * •

Flow-sensitive: We consider the program statements in order and compute
points-to sets at each program point. This is usually infeasible for whole
program analysis, but becomes feasible for intra-procedural analysis.

We follow a similar setup to Andersen’s analysis(andersen1994program, 2),
where we update points-to sets in different ways depending on the type of
assignment statement, for example, if we have a = b then we merge b’s points-
to set into a’s. However, our algorithm is flow-sensitive because we process
each statement just once in order, unlike Andersen’s analysis which is flow-
insensitive and iterates over the statements till convergence. We provide
pseudocode and more details about our algorithm in the supplementary material.

While implementing field sensitivity, we make a deliberate choice to ignore
“unknown” fields in function calls. For example, if we have foo(a, b), and a
has a field a.x, then we don’t make a connection between a.x and b unless a.x
is already “known” to our pointer analysis, _i.e.,_ it has been used
elsewhere. As we will show in Section 5.2, we empirically found that this
eliminates false positives and increases precision.

####  3.2.4. Step-IV. Apply Shallow Filter

Here we apply a shallow filter to eliminate false positives. Our intra-
procedural pointer analysis is insufficiently granular to distinguish between
accesses to different fields of the same object across function boundaries. We
partially address this issue by identifying some common patterns across Rust
projects where our analysis reports false positives because of insufficient
granularity in its reasoning. For example, the functions next and next_back
from the IteratorMut trait in the Rust standard library(splitting_borrows,
29). We exclude functions matching these patterns from our bug reports.

##  4\. Experimental Setup

###  4.1. Implementation

When Rust code is compiled, it goes through several intermediate
representations (IRs), two of which are the High-level IR (HIR) and the Mid-
level IR (MIR). The HIR is a tree representation of the program that is
similar to an Abstract Syntax Tree (AST). The MIR represents each function as
a control-flow graph of basic blocks, with each basic block consisting of a
number of statements. MIR boils the different kind of statements occurring in
a program down to a core set of statement types like assignments, memory
allocation, and memory de-allocation. We use a hybrid approach that combines
information from the HIR and the MIR. We use the HIR to get struct definitions
and function signatures, and use the MIR to perform alias analysis.

We implement our system Yuga in Rust as a fork of the Rudra (bae2021rudra, 4)
project. We use the nightly-2022-11-18 version of rustc and cargo, and run our
tool on Rust projects as a cargo subcommand.

###  4.2. Study Subject

We evaluate Yuga in three different settings: (i) 21 real-world vulnerable
functions curated from 9 crate libraries, (ii) a synthetic vulnerability
dataset, and (iii) running Yuga across 372 popular Rust crate libraries. This
section describes each setting in detail.

####  4.2.1. Curating bugs from Vulnerability Reports.

A library crate (or crate for short) in Rust is a project that provides
functionality that can be used in other Rust projects. This is similar to a
package or library in other programming languages. Rust hosts a community
crate registry at crates.io, and any project can add a library crate from this
registry as its dependency. Adding a crate as a project dependency allows one
to use APIs from that crate in the project. The RustSec Security Vulnerability
Database(rustsec, 25) is a collection of security vulnerability reports in
Rust crates. We manually inspected each report in the RustSec database
(rustsec, 25), looking for issues related to incorrect LA. We found 9
vulnerabilities that matched this pattern. These are shown in Table 2. Each of
these corresponds to one crate containing one or more buggy functions. There
are a total of 21 functions with bugs across the 9 vulnerabilities.

####  4.2.2. Creating a Synthetic Bug Dataset.

In addition to evaluating Yuga on the bugs from vulnerability reports, we
would like to check whether it can generalize to similar patterns of bugs. To
do this, we prepared a synthetic bug dataset based on the above 9
vulnerability reports in three steps, as follows.

  * •

Program Slicing and Simplification. Each of the 9 reports contains one or more
functions with a LA bug. We selected one vulnerable function from each report,
isolated the structures and functions responsible for the bug, and rewrote
them in a minimal form. This gave us a list of 9 synthetic bugs.

  * •

Program Transformations. For each of the 9 synthetic bugs from the previous
step, we applied a variety of transformations to them that retain the
semantics of the code but change the high level structure. For instance, we
wrap borrows in structures or enums, change concrete types into generic types,
change datatypes, add more dummy borrows with different lifetime annotations,
etc. We transformed the 9 bugs in two different ways each by applying selected
transformations, to get a total of 27 synthetic bugs.

  * •

Exploit Construction. For each synthetic bug, we construct an “exploit”
function that showcases the vulnerability present in it and triggers undefined
behavior.

We make this dataset of 27 synthetic bugs publicly available
(https://github.com/vnrst/rust-lifetime-bugs).

####  4.2.3. Scanning Crates from the Registry

We also use our tool to scan crates from the crates.io registry. We pick the
top 2000 most downloaded crates as of November 15th, 2022, and filter out
those which do not use unsafe code or lifetime annotations. This leaves us
with 372 crates. We download the original source for each of them using the
cargo-download tool. Our tool is implemented as a cargo subcommand, and we run
this subcommand on the downloaded source folders.

###  4.3. Evaluation and Metrics

For each scanned crate, Yuga gives a list of functions with possible memory
safety bugs. To evaluate Yuga, we first define a “ground truth” memory safety
violation. For the RustSec and Synthetic bug dataset, we know by construction
that each of the functions reported in the security vulnerability are
confirmed violations. For all other functions that our tool marks as potential
bugs, we manually inspect each one. We classify a reported bug as genuine only
if we are able to clearly exploit the vulnerability to cause undefined
behavior. If we are uncertain or unable to cause undefined behavior, we
classify this as a false positive.

We assess Yuga’s ability to identify lifetime annotation bugs using precision
and recall metrics. In a given dataset, if the bugs detected by Yuga are
denoted by $S_{\textsc{Yuga}{}}$, and the ground truth bugs are denoted by
$S_{GT}$, the precision and recall of Yuga can be defined as
$\dfrac{|S_{GT}\cap S_{\textsc{Yuga}{}}|}{|S_{\textsc{Yuga}{}}|}$ and
$\dfrac{|S_{GT}\cap S_{\textsc{Yuga}{}}|}{|S_{GT}|}$ respectively.

###  4.4. Baselines

We evaluate against the following baselines:

  * •

Rudra(bae2021rudra, 4): Rudra is a static analyis based bug detector that
detects certain kinds of errors in unsafe Rust.

  * •

MirChecker(li2021mirchecker, 14): MirChecker is a static analysis based
analyzer that can detect certain categories of undefined behavior, like
overflows and out-of-bounds accesses.

  * •

Miri(miri, 20): Miri is a dynamic analysis tool that interprets one MIR
instruction at a time and detects memory errors.

##  5\. Research Questions

We aim to answer the following research questions:

  * •

RQ1: Effectiveness of our tool. We evaluate the effectiveness of Yuga in three
settings: 1) Can Yuga detect reported Rust security vulnerabilities that
result from incorrect LAs? 2) How does Yuga generalize to the synthetic bug
dataset that we curated? 3) How does Yuga perform when we run it on a large
set of real-world Rust crates?

  * •

RQ2: Impact of Design Choices. How do the different model components of Yuga
impact its performance on vulnerabilities and synthesized bugs?

  * •

RQ3: Existing tools. Are there any existing tools that can detect incorrect
lifetime annotations?

###  5.1. RQ1: Effectiveness of our Tool

This research question is structured as follows. First, we shall evaluate the
performance of Yuga by running it on the 21 functions from 9 crates from
RustSec vulnerabilities. Then, we will measure the ability of Yuga to
generalize by running it on our synthetic bug dataset of 27 bugs. Finally, we
run Yuga on a large set of real-world Rust crates.

Table 2. Running Yuga on Rustsec vulnerabilities due to LA bugs

|  | Error | #Vulnerable |  | False | False
---|---|---|---|---|---|---
| RustSec ID | Type | Funcs | #Detected | Positives | Negatives
1 | 2018-0020 | Use-after-free | 1 | 2 | 2 | 1
2 | 2020-0023 | Mutability | 2 | 2 | 0 | 0
3 | 2020-0060 | Use-after-free | 1 | 0 | 0 | 1
4 | 2021-0128 | Use-after-free | 7 | 7 | 2 | 2
5 | 2021-0130 | Use-after-free | 2 + 3* | 5 | 0 | 0
6 | 2022-0028 | Use-after-free | 2 | 0 | 0 | 2
7 | 2022-0040 | Use-after-free | 1 | 0 | 0 | 1
8 | 2022-0070 | Use-after-free | 1 | 0 | 0 | 1
9 | 2022-0078 | Use-after-free | 1 | 0 | 0 | 1
| Total |  | 21 | 16 | 4 | 9

The asterisk * denotes newly exposed bugs that weren’t part of the initial
report.

####  5.1.1. Evaluation on RustSec Vulnerabilities

We run Yuga on the 9 crates from RustSec vulnerabilities, containing 21 buggy
functions. Its performance is summarized in Table 2. Overall, the precision is
75%, and the recall is 57.1%.

Detected bugs: Yuga detects 16 vulnerable functions from 3 crates. 2 of these
vulnerabilities are aliased mutability bugs, and the other 14 are use-after-
free. The 3 bugs in Table 1 are among the 12 vulnerable functions that Yuga is
able to detect correctly.

Exposing new bugs: For the vulnerability RUSTSEC-2021-0130 corresponding to
the lru-rs crate, the report had only 2 functions listed as bugs. However, our
tool detected 3 additional functions as potential bugs - peek_lru,
get_or_insert, get_or_insert_mut. When we looked at the commit history on
GitHub(lru, 16), it turned out that these functions had been subsequently
identified as bugs and fixed. Further, the commit messages indicated that
these were memory safety bugs. The fact that Yuga was able to detect these
bugs despite them not being explicitly labeled is a strong validation of our
tool and approach.

⬇

1pub struct MainloopInner<T> ... {

2 ...

3 api: *const MainloopApi

4}

5pub struct Mainloop {

6 /// The ref-counted inner data.

7 pub _inner: Rc<MainloopInner<MainloopInternal>>,

8}

9impl Mainloop {

10 pub fn get_api<’a>(&self) -> &’a MainloopApi {

11 let ptr = self._inner.get_api_ptr();

12 assert_eq!(false, ptr.is_null());

13 unsafe { &*ptr }

14 }

15 ...

Listing 1: A False Positive in the pulsebinding crate

False Positives: In the pulse-binding crate corresponding to the vulnerability
RUSTSEC-2018-0020, Yuga flags two additional functions as potential bugs. We
have corresponded with the developer(pulse_binding, 33) regarding these
functions, and have labeled this as a false positive because we are unable to
exploit the bug to cause undefined behavior. Listing LABEL:lst:pulsebinding
shows one of these functions.

The lifetime of the returned MainloopApi borrow on line 16 is different from
the lifetime of the borrow to self. &self has no explicit LA, and will be
given an implicit anonymous lifetime which is different from ’a. So the
returned borrow will still be accessible after the Mainloop object is dropped.
If the MainloopApi object is also deallocated when the Mainloop is dropped,
this can lead to undefined behavior. However, the MainloopApi object is not
dropped, and so dereferencing the returned borrow is safe. This example
illustrates how the difference between a bug and a false positive can be very
subtle. The Rust code here is a wrapper for a C API, and understanding the
mechanism of allocation/deallocation of memory in this case would involve
going into the C API which our tool doesn’t have access to.

False Negatives: Our tool is unable to detect 9 of the 21 functions. Some of
the reasons our tool fails on these examples are:

  1. (1)

“Hidden” Raw Pointers: Our tool reports violations only in cases where there
is a raw pointer involved. Sometimes, it is not easy to infer that a certain
type contains a raw pointer. pub fn waker<W>(wake: Arc<W>) -> Waker { ... } is
an example.

Here, Waker is a structure containing a raw pointer, but we don’t have access
to the definition of this structure because it is an external dependency. So
our tool ignores this. 4 out of the 9 false negatives are because of hidden
raw pointers.

  2. (2)

Type conversion: To increase precision, Yuga only considers examples where the
types of the source and target values match. But that can also be too
restrictive, as Listing LABEL:lst:aggregate shows:

⬇

1pub struct InnerConnection {

2 pub db: *mut ffi::sqlite3, ...

3}

4pub struct Connection {

5 db: RefCell<InnerConnection>, ...

6}

7impl Connection {

8 pub fn create_aggregate_function<A, D, T>(

9 &self, ...,

10 aggr: D,

11 ) -> Result<()>

12 where

13 A: RefUnwindSafe + UnwindSafe,

14 D: Aggregate<A, T>,

15 T: ToSql,

16 ...

Listing 2: False negative in the rusqlite crate corresponding to
RUSTSEC-2021-0128

Here, the type of the raw db pointer on line 2 is ffi::sqlite3, and the type
of aggr on line 13 is a generic type D. Yuga would filter this out because the
types do not match, but in fact, D is converted to a c_void pointer which is
then attached to the db using a C foreign function call (not shown in the
snippet). This kind of type conversion is difficult to reason about. 2 of the
9 false negatives are due to type conversion.

####  5.1.2. Evaluating Generalizibility using Synthetic Dataset.

We run Yuga on the 27 synthetic bugs curated by us. Table 3 summarizes the
result. For each of the 9 original RustSec vulnerability reports, we derive 3
synthetic bugs. The three synthetic bugs derived from the n-th RustSec report
are denoted by n.1, n.2 and n.3.

As shown in Table 3, Yuga is able to detect 16 out of 27 bugs, corresponding
to a recall of 59.3%. There are some cases where Yuga is unable to detect the
bug in the original RustSec report, but is able to detect one or more of the
corresponding bugs in the synthetic dataset. A few of the reasons for this are
as follows:

  * •

We re-implement some external dependencies. For example, Yuga is unable to
detect the bug in pub fn waker<W>(wake: Arc<W>) -> Waker, because it does not
have access to the implementation of the Waker structure. But in our synthetic
examples 3.1 and 3.2, we re-implement the Waker structure, and thus Yuga is
able to see that there is a raw pointer inside.

  * •

Some types are simplified. For example in the 6th RustSec report
RUSTSEC-2022-0028, Yuga is unable to detect a raw pointer because it is
“hidden” behind a chain of type re-definitions and imports. In our synthetic
examples 6.1 and 6.2, the types are simplified and it is possible to detect
the raw pointer.

Since we constructed this dataset ourselves, there aren’t many functions apart
those containing bugs. So our tool does not report any false positives on this
dataset.

Table 3. Results of Yuga on synthetic bug dataset.  Bug | Detected | Bug | Detected | Bug | Detected
---|---|---|---|---|---
1.1 | No | 4.1 | Yes | 7.1 | No
1.2 | No | 4.2 | Yes | 7.2 | No
1.3 | No | 4.3 | No | 7.3 | No
2.1 | Yes | 5.1 | Yes | 8.1 | No
2.2 | Yes | 5.2 | Yes | 8.2 | Yes
2.3 | Yes | 5.3 | Yes | 8.3 | Yes
3.1 | Yes | 6.1 | Yes | 9.1 | Yes
3.2 | Yes | 6.2 | Yes | 9.2 | Yes
3.3 | No | 6.3 | No | 9.3 | No

####  5.1.3. Evaluation on Real World Rust Crates.

We would like Yuga to be able to quickly scan and flag potential bugs in Rust
crates, and scale to the thousands of crates in the Rust crate ecosystem. We
run Yuga on a filtered list of 372 Rust crates as described in Section 4.2.3.
Yuga is able to scan these crates in just under 2 hours, and flags 312
potential bugs from 77 crates.

We are in the process of going through these reports, classifying them, and
reporting them to developers. This is a time consuming process, since the
difference between a bug and a false positive can be very subtle, as shown
earlier. For the purposes of this paper, in Listing LABEL:lst:cslice, we
present one example of a genuine bug that we have identified while going
through these reports.

⬇

1#[derive(Clone, Copy)]

2pub struct CMutSlice<’a, T> {

3 base: *mut T,

4 ...

5}

6pub fn as_mut_slice(&mut self) -> &’a mut [T]

7{ unsafe { slice::from_raw_parts_mut(self.base, self.len)} }

Listing 3: A genuine bug that Yuga found in the cslice crate

On line 7, the lifetime ’a doesn’t match with the lifetime of the borrow &self
which has an implicit anonymous lifetime. So this allows aliased mutable
references.

Summary: We evaluate Yuga in different settings. On the RustSec
vulnerabilities, it achieves a precision of 75% and a recall of 57.1%. On our
synthetic dataset, it achieves a recall of 59.3%. Finally, we were able to use
Yuga to scan 357 Rust crates “in the wild” in under 2 hours, and found 312
potential bugs.

###  5.2. RQ2: Impact of Design Choices

We investigate the effect of three design choices in Yuga \- the Alias
Analysis module, our handling of unknown fields in Alias Analysis, and the
Shallow Filter.

####  5.2.1. Alias Analysis.

We investigate the effect of the alias analysis module by removing it entirely
and evaluating Yuga on the 21 functions from RustSec reports as well as our
synthetic bug dataset. As shown in in Table 4, the recall increases, but the
precision drops tremendously from 75% to 29.5%. This shows that simple pattern
matching with types and lifetimes is not sufficient, and deeper pointer
analysis is necessary.

####  5.2.2. Unknown Fields in Alias Analysis.

In Section 3.2.3, we described how we made a choice to exclude “unknown”
fields in function calls, while designing our Alias Analysis algorithm. Here
we explore the impact of that choice. We run Yuga with and without considering
unknown fields, on both the 21 functions from RustSec reports, as well as our
synthetic bug dataset. The results are shown in Table 4. We can see that
considering unknown fields increases the recall slightly on both the RustSec
and Synthetic bugs, but the precision on RustSec falls from 75% to 40.6%.

Table 4. Impacts of different design choices. The numbers that are different from the original are shown in bold. | RustSec | Synthetic
---|---|---
| Recall | Precision | Recall | Precision
Original (Yuga) | 57.1% | 75% | 59.3% | —
w/o Shallow Filter | 57.1% | 54.5% | 59.3% | —
w/ Unknown Fields | 61.9% | 40.6% | 62.9% | —
w/o Alias Analysis | 61.9% | 29.5% | 74.1% | —

####  5.2.3. Shallow Filter.

Our shallow filter is used to filter out common patterns of false positives
that result from trait implementations. We run Yuga on the 21 functions from
RustSec reports. With the filter, there were 4 false positives; without the
filter, that number increases to 10. The precision drops from 75% to 55%.

Summary: All three of the design choices we investigate contribute
significantly to the precision of Yuga.

###  5.3. RQ3: Existing tools

In this section, we aim to evaluate existing static analysis tools for
detecting memory safety bugs in Rust, to see if they can detect bugs caused by
incorrect LA.

####  5.3.1. Rudra(bae2021rudra, 4):

We run Rudra on the 21 RustSec bugs and our synthetic bug dataset of 27 bugs.
We found that Rudra was unable to detect any of these 48 bugs. This is because
Rudra is designed only to detect certain specific types of memory safety and
thread safety errors, and cannot reason about LA bugs.

####  5.3.2. MirChecker(li2021mirchecker, 14):

This project is old and not compatible with the toolchains used by most
current Rust projects. Nevertheless, we were able to run it on our synthetic
bug dataset. MirChecker was unable to detect any of the 27 bugs. This shows
MirChecker will also not be able to detect other more complicated bugs.

####  5.3.3. Miri(miri, 20):

For each of the 27 synthetic bugs, we ran Miri directly with the exploit
function (see Section 4.2.2) that exposes the vulnerability. Miri detected a
memory safety error in all 27 of the cases, but without the exploit function,
Miri cannot detect any one of them. This shows that given a large enough test
suite, Miri might be able to find these bugs, but constructing that test suite
is non-trivial. As such, Miri is orthogonal to our problem, because it detects
actual bugs arising during execution, as opposed to potential bugs. We discuss
more about dynamic tools in Section 7.

Summary: There are no existing static tools that are well-suited to this
problem. The potential ones that we tried, namely Rudra and MirChecker, were
unable to detect any of the lifetime annotation bugs. The dynamic tool Miri,
in contrast, was able to detect the bugs, but they require manually crafted
test cases, which is non-trivial in real project settings.

##  6\. Threats to Validity

We acknowledge that our evaluation of Yuga is primarily based on only 21
vulnerable functions from 9 crates, which might limit the generalizability of
the results. To address this concern, we generate 27 synthesized vulnerable
functions by varying context, types, etc. Thus, we evaluate on a total of 48
vulnerable functions and on more than 300 real Rust libraries.

Yuga achieves a precision of 75% and a recall of $\sim$60%. However, there is
an inherent tradeoff between these two quantities, as shown in 5.2. Higher
recall can be obtained at the cost of sacrificing some precision, if desired.
We emphasize that this is inherently a hard problem, and there is no other
tool that can handle such bugs.

##  7\. Related Work

Despite the Rust language being relatively new, there has been a large body of
work that aims to study its properties.

Dynamic testing of Rust code: Miri (miri, 20) is an interpreter to detect
invalid memory accesses or memory leaks (see Section 5.3). Stacked
Borrows(jung2019stacked, 11) (incorporated into Miri) develops a “stack” model
to reason about borrows without explicitly using lifetimes. Fuzzing with an
address sanitizer is another way to detect potential errors, but existing Rust
fuzzers are not well suited to our problem. cargo-fuzz (cargofuzz, 26) is a
fuzzing tool for Rust that uses libFuzzer (libfuzzer, 27) as a backend. But it
is limited to fuzzing functions that take input strings of a fixed format and
type, and cannot handle functions with more complex inputs. Fuzzcheck
(fuzzcheck, 15) is another tool that is limited to functions that take a
single reference argument.

Static analysis for detecting bugs in Rust: MirChecker (li2021mirchecker, 14)
and SafeDrop (cui2021safedrop, 8) are static analyzers on the Rust MIR that
detect certain memory safety errors. However, much like dynamic approaches,
these approaches tend to have high false negatives. Rudra (bae2021rudra, 4)
identifies three categories of bugs arising from unsafe code, and scans the
entire Rust crate ecosystem for these bug patterns. Rudra is the closest work
to ours in the sense that it uses static analysis to identify potential memory
safety violations. However, Rudra can handle only three specific kinds of
errors, and cannot detect memory safety bugs caused by incorrect lifetime
annotations.

Empirical analysis of unsafe Rust: Recent works (qin2020understanding, 22, 9,
3, 35) characterize why and how developers use unsafe code in Rust, and build
an empirical understanding of bugs arising from them.

Formal semantics of Rust: Patina (reed2015patina, 23) formalizes the type
system of Rust. FR (pearce2021lightweight, 21) is a lightweight formalism of
Rust that captures type checking and borrow checking. Oxide (weiss2019oxide,
34) models Rust code with non-lexical lifetimes (nonlexicallifetimes, 17) and
a syntax close to safe surface Rust. However, these methods do not model
unsafe code.

There have also been attempts to model the semantics of unsafe Rust. RustBelt
(jung2017rustbelt, 12) develops a comprehensive formal semantics based on
lifetimes for a realistic subset of Rust including unsafe code. However, this
cannot scale to larger codebases and crates. Verifying the safety of a given
library with RustBelt involves writing proofs with the Coq proof assistant
(coqproofassistant, 7), which requires considerable expertise and effort. In
contrast, our approach aims to be a lightweight automatic error detector that
can aid developers.

##  8\. Conclusion

In this paper, we investigate memory safety bugs arising from incorrect
lifetime annotations in the Rust language. We demonstrate how such bugs can
arise, and characterize bug patterns. Leveraging these patterns, we design
Yuga to detect incorrect lifetime annotations in Rust. We show that Yuga is
able to effectively detect bugs in real-world Rust projects, compared to
existing approaches which are unable to detect any of these bugs. Future work
could involve making the static analysis framework more precise, and expanding
this framework to include other kinds of bugs in unsafe Rust.

## References

  * (1) Hussain MJ Almohri and David Evans  “Fidelius charm: Isolating unsafe rust code”  In _Proceedings of the Eighth ACM Conference on Data and Application Security and Privacy_ , 2018, pp. 248–255
  * (2) Lars Ole Andersen  “Program analysis and specialization for the C programming language”, 1994
  * (3) Vytautas Astrauskas et al.  “How do programmers use unsafe rust?”  In _Proceedings of the ACM on Programming Languages_ 4.OOPSLA ACM New York, NY, USA, 2020, pp. 1–27
  * (4) Yechan Bae et al.  “RUDRA: finding memory safety bugs in Rust at the ecosystem scale”  In _Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles_ , 2021, pp. 84–99
  * (5) Marek Baranowski, Shaobo He and Zvonimir Rakamarić  “Verifying Rust programs with SMACK”  In _International Symposium on Automated Technology for Verification and Analysis_ , 2018, pp. 528–535  Springer
  * (6) Clippy Contributors  “Rust-clippy”  In _GitHub repository_ GitHub, https://github.com/rust-lang/rust-clippy, 2022
  * (7) Coq team  “The Coq proof assistant”, https://coq.inria.fr, 2022
  * (8) Mohan Cui, Chengjun Chen, Hui Xu and Yangfan Zhou  “SafeDrop: Detecting memory deallocation bugs of rust programs via static data-flow analysis”  In _arXiv preprint arXiv:2103.15420_ , 2021
  * (9) Ana Nora Evans, Bradford Campbell and Mary Lou Soffa  “Is Rust used safely by software developers?”  In _2020 IEEE/ACM 42nd International Conference on Software Engineering (ICSE)_ , 2020, pp. 246–257  IEEE
  * (10) Google  “Rust in the Android platform”, 2021  URL: https://security.googleblog.com/2021/04/rust-in-android-platform.html
  * (11) Ralf Jung, Hoang-Hai Dang, Jeehoon Kang and Derek Dreyer  “Stacked borrows: an aliasing model for Rust”  In _Proceedings of the ACM on Programming Languages_ 4.POPL ACM New York, NY, USA, 2019, pp. 1–32
  * (12) Ralf Jung, Jacques-Henri Jourdan, Robbert Krebbers and Derek Dreyer  “RustBelt: Securing the foundations of the Rust programming language”  In _Proceedings of the ACM on Programming Languages_ 2.POPL ACM New York, NY, USA, 2017, pp. 1–34
  * (13) William Landi  “Undecidability of static analysis”  In _ACM Letters on Programming Languages and Systems (LOPLAS)_ 1.4 ACM New York, NY, USA, 1992, pp. 323–337
  * (14) Zhuohua Li, Jincheng Wang, Mingshen Sun and John CS Lui  “MirChecker: detecting bugs in Rust programs via static analysis”  In _Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security_ , 2021, pp. 2183–2196
  * (15) Loïc Lecrenier  “Fuzzcheck”  In _GitHub repository_ GitHub, https://github.com/loiclec/fuzzcheck-rs, 2022
  * (16) Lru Cache contributors  “Lru Cache”  In _GitHub repository_ GitHub, https://github.com/jeromefroe/lru-rs/, 2023
  * (17) Nicholas D. Matsakis  “Non-lexical lifetimes: introduction”, http://smallcultfollowing.com/babysteps/blog/2016/04/27/non-lexical-lifetimes-introduction/, 2016
  * (18) Yusuke Matsushita, Xavier Denis, Jacques-Henri Jourdan and Derek Dreyer  “RustHornBelt: a semantic foundation for functional verification of Rust programs with unsafe code”  In _Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation_ , 2022, pp. 841–856
  * (19) Yusuke Matsushita, Takeshi Tsukada and Naoki Kobayashi  “RustHorn: CHC-based verification for Rust programs”  In _ACM Transactions on Programming Languages and Systems (TOPLAS)_ 43.4 ACM New York, NY, 2021, pp. 1–54
  * (20) Miri contributors  “Miri”  In _GitHub repository_ GitHub, https://github.com/rust-lang/miri, 2022
  * (21) David J Pearce  “A lightweight formalism for reference lifetimes and borrowing in Rust”  In _ACM Transactions on Programming Languages and Systems (TOPLAS)_ 43.1 ACM New York, NY, USA, 2021, pp. 1–73
  * (22) Boqin Qin et al.  “Understanding memory and thread safety practices and issues in real-world Rust programs”  In _Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation_ , 2020, pp. 763–779
  * (23) Eric Reed  “Patina: A formalization of the Rust programming language”  In _University of Washington, Department of Computer Science and Engineering, Tech. Rep. UW-CSE-15-03-02_ , 2015, pp. 264
  * (24) Elijah Rivera et al.  “Keeping safe Rust safe with Galeed”  In _Annual Computer Security Applications Conference_ , 2021, pp. 824–836
  * (25) Rust developers  “Rust Security Advisory Database”, 2022  URL: https://rustsec.org/advisories/
  * (26) Rust team  “cargo fuzz”  In _GitHub repository_ GitHub, https://github.com/rust-fuzz/cargo-fuzz, 2022
  * (27) LLVM Team  “libFuzzer – a library for coverage-guided fuzz testing”, 2023  URL: https://llvm.org/docs/LibFuzzer.html
  * (28) Rust Team  “Fix UB due to missing ’static on task::waker”, 2020  URL: https://github.com/rust-lang/futures-rs/pull/2206/files
  * (29) Rust Team  “Rustonomicon - Splitting Borrows”, 2023  URL: https://doc.rust-lang.org/nomicon/borrow-splitting.html
  * (30) Rust Team  “The Rustonomicon: The Dark Arts of Unsafe Rust”, 2018  URL: https://doc.rust-lang.org/nomicon/
  * (31) John Toman, Stuart Pernsteiner and Emina Torlak  “Crust: a bounded verifier for rust (N)”  In _2015 30th IEEE/ACM International Conference on Automated Software Engineering (ASE)_ , 2015, pp. 75–80  IEEE
  * (32) Steven Vaughan-Nichols  “Linus Torvalds: Rust will go into Linux 6.1”, 2022  URL: https://www.zdnet.com/article/linus-torvalds-rust-will-go-into-linux-6-1/
  * (33) vnrst  “Possible UB in get_api function”, 2023  URL: https://github.com/jnqnfe/pulse-binding-rust/issues/53
  * (34) Aaron Weiss, Olek Gierczak, Daniel Patterson and Amal Ahmed  “Oxide: The essence of rust”  In _arXiv preprint arXiv:1903.00982_ , 2019
  * (35) Hui Xu, Zhuangbin Chen, Mingshen Sun and Yangfan Zhou  “Memory-safety challenge considered solved? an empirical study with all rust cves”  In _arXiv preprint arXiv:2003.03296_ , 2020

##  Appendix A Extracting Lifetime Bounds

###  A.1. Notation

####  A.1.1. Grammar

These are the types that we work with, and lifetime annotations.

$\displaystyle T::$
$\displaystyle~{}\&L~{}{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{mut}}}}~{}T$
A mutable borrow to some type $\displaystyle|~{}\&L~{}T$ An immutable borrow
to some type $\displaystyle|~{}O$ A structure or a primitive type
$\displaystyle|~{}{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{*const}}}}~{}|~{}{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{*mut}}}}$
(Im)mutable raw pointer to some type $\displaystyle O::$ $\displaystyle~{}S$ A
struct or prim type not containing borrows
$\displaystyle|~{}S{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{<}}}}L{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{>}}}}$
A struct containing borrows $\displaystyle L::$
$\displaystyle~{}{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{'id}}}}~{}|~{}{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{'static}}}}$
Lifetime names $\displaystyle S::$ id Identifier names

This surface syntax is almost identical to Rust. One important difference is
that we assume that all borrow lifetimes are explicitly specified, whereas
Rust allows some lifetimes to be inferred or elided. Further, we’ve
deliberately considered only structures with one lifetime annotation for
simplicity, whereas Rust can have multiple.

####  A.1.2. Judgements

$\displaystyle O\\{T\\}\;\;\;$ $\displaystyle\text{``}O\text{ contains a value
of type }T\text{ as one of its fields''}$ $\displaystyle T\rightarrow
T^{\prime}:~{}L$ $\displaystyle\text{``}T\text{ contains another type T' that
outlives lifetime }L\text{''}$ $\displaystyle T\rightarrow
T^{\prime}:~{}\epsilon$ $\displaystyle\text{``}T\text{ contains another
{owned} type }T^{\prime}\text{''}$ $\displaystyle T\rightarrow L_{1}:~{}L_{2}$
$\displaystyle\text{``From }T\text{, we can infer that }L_{1}\text{ is longer
than }L_{2}\text{''}$

###  A.2. Rules for Decomposing a Type

We want to take a type $T$ and extract all of its contained types with their
associated lifetimes. We will do this using the rules in Figure 6.

  * •

The simplest case - any owned type contains itself and owns itself (contains-
self).

  * •

If there is a borrow to an owned type, then it has to live at least as long as
the lifetime of that borrow (borrow and mut-borrow).

  * •

If a structure has a field of type $T$, then anything that can be extracted
from that $T$ can also be extracted from the structure (field and field-eps).

  * •

If an extracted type already has an associated lifetime, then any outer borrow
lifetime does not attach to it (inner-lifetime).

  * •

Any outer borrow lifetime must be shorter than an inner borrow lifetime
(B-inner-longer).

  * •

We can always conclude that a lifetime outlives itself
(B-reflexive).

  * •

The static lifetime111https://doc.rust-lang.org/rust-by-
example/scope/lifetime/static_lifetime.html always outlives any other lifetime
(B-static).

  * •

Lifetime bounds can also be extracted from inner types
(B-extract-inner1 and B-extract-inner2).

$O\rightarrow O:\epsilon$ $\&LT\rightarrow T_{1}:LT\rightarrow T_{1}:\epsilon$
$\&L~{}{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{mut}}}}~{}T\rightarrow
T_{1}:LT\rightarrow T_{1}:\epsilon$ $O\rightarrow T_{1}:L\lx@proof@logical@and
O\\{T\\}T\rightarrow T_{1}:L$ $S\rightarrow
T_{1}:\epsilon\lx@proof@logical@and O\\{T\\}T\rightarrow T_{1}:\epsilon$
$\&LT\rightarrow T_{1}:L_{1}T\rightarrow T_{1}:L_{1}$
$S\rightarrow T:\epsilon
S\\{{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{*const}}}}~{}T\\}$
$S\rightarrow T:\epsilon
S\\{{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{*mut}}}}~{}T\\}$
$S{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{<}}}}L{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{>}}}}\rightarrow
T:LS{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{<}}}}L{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{>}}}}\\{{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{*const}}}}~{}T\\}$
$S{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{<}}}}L{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{>}}}}\rightarrow
T:LS{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{<}}}}L{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{>}}}}\\{{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{*mut}}}}~{}T\\}$
$\&LT\rightarrow L_{1}:LT\rightarrow T_{1}:L_{1}$ $T\rightarrow L:~{}L$
$T\rightarrow{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{'static}}}}:~{}L$
$T\rightarrow L_{1}:~{}L_{2}\lx@proof@logical@and T\rightarrow
T_{1}:LT_{1}\rightarrow L_{1}:~{}L_{2}$ $T\rightarrow
L_{1}:~{}L_{2}\lx@proof@logical@and T\rightarrow T_{1}:\epsilon
T_{1}\rightarrow L_{1}:~{}L_{2}$

Figure 6. Rules for Extracting Lifetime Bounds

###  A.3. In the Presence of Raw Pointers

In an ideal world, we want a structure’s annotation to be representative of
what it holds.

  * •

If a structure is annotated with lifetime <’a>, then we would like everything
accessible from the structure to outlive ’a.

  * •

If a structure has no lifetime annotation, then we would like everything
accessible from the structure to be owned by the structure object.

But raw pointers break that guarantee. A structure can have lifetime
annotation <’a>, but the thing pointed to by the raw pointer can live shorter
than that. We want to enforce these guarantees. We extend our rules as
follows:

  * •

If a structure with no lifetime annotations contains a raw pointer, then the
pointed-at type acts as though it is owned by the structure object (raw-
lifetime and raw-mut-lifetime).

  * •

If a structure with a lifetime annotation <’a> contains a raw pointer, then
the data that it points to must outlive ’a (raw-owned and raw-mut-owned).

##  Appendix B Checking Violations

###  B.1. Arg-Return Use-after-free

Suppose an argument and return type are of types $T_{1}$ and $T_{2}$
respectively. Then for all $L_{1},L_{2}$ such that $T_{1}\rightarrow
T^{\prime}:L_{1}$ and $T_{2}\rightarrow T^{\prime}:L_{2}$, if
$T_{1}\rightarrow L_{1}:L_{2}$ is not true, this is potentially Undefined
Behavior (UB). In notation,

${{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{UB}}}}\lx@proof@logical@and
T_{1}\rightarrow T^{\prime}:L_{1}T_{2}\rightarrow
T^{\prime}:L_{2}T_{1}\nrightarrow L_{1}:L_{2}$
${{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{UB}}}}\lx@proof@logical@and
T_{1}\rightarrow T^{\prime}:L_{1}T_{2}\rightarrow T^{\prime}:\epsilon$

Here we abuse notation by using judgement $T_{1}\nrightarrow L_{1}:L_{2}$ to
mean that we cannot extract $L_{1}:L_{2}$ from $T_{1}$. We do not check if
$T_{2}\nrightarrow L_{1}:L2$, because we can only infer constraints from the
arguments we are given. We impose constraints on the return types.

We report violations to our alias analysis module that checks if there is
actually a transfer of a value of type $T^{\prime}$ between $T_{1}$ and
$T_{2}$.

###  B.2. Arg-Arg Use-after-free

Suppose two arguments are of types $T_{1}$ and $T_{2}$. Then, the rules for
checking Arg-Arg Use-after-free violations are:

${{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{UB}}}}\lx@proof@logical@and
T_{1}\rightarrow T^{\prime}:L_{1}T_{2}\rightarrow
T^{\prime}:L_{2}T_{1}\nrightarrow
L_{1}:{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{'static}}}}$

Any non-static lifetime being assigned to another lifetime, between matching
types, gets flagged as a violation, to be taken care of by the alias analyzer.

###  B.3. Arg-Return Non-Exclusive Mutability

Suppose an argument and return type are of types $T_{1}$ and $T_{2}$
respectively. Then, the rules for checking Non-Exclusive Mutability (NEM)
violations are:

${{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{UB}}}}\lx@proof@logical@and
T_{1}\rightarrow
T^{\prime}:L_{1}T_{2}\rightarrow\&{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{mut}}}}~{}T^{\prime}:L_{2}T_{1}\nrightarrow
L_{1}:L_{2}$
${{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{UB}}}}\lx@proof@logical@and
T_{1}\rightarrow
T^{\prime}:L_{1}T_{2}\rightarrow{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{*mut}}}}~{}T^{\prime}:L_{2}T_{1}\nrightarrow
L_{1}:L_{2}$
${{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{UB}}}}\lx@proof@logical@and
T_{1}\rightarrow{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{*mut}}}}~{}T^{\prime}:L_{1}T_{2}\rightarrow
T^{\prime}:L_{2}T_{1}\nrightarrow L_{1}:L_{2}$
${{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{UB}}}}\lx@proof@logical@and
T_{1}\rightarrow\&{{\color[rgb]{0.25,0.35,0.75}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.35,0.75}{\texttt{mut}}}}~{}T^{\prime}:L_{1}T_{2}\rightarrow
T^{\prime}:L_{2}T_{1}\nrightarrow L_{1}:L_{2}$

Again, we report violations to our alias analysis module that checks if there
is actually a transfer of a value of type $T^{\prime}$ between $T_{1}$ and
$T_{2}$.

##  Appendix C Alias Analysis

This section describes our alias analysis in more detail. For a variable $a$,
we denote its points-to set by $S_{a}$. For dereferencing, we define
$*S_{a}=\bigcup_{x\in S_{a}}S_{x}$. We process each statement in order, and
for each type of assignment statement, like a = b, a = *b, etc, we update the
points-to sets accordingly. If there is a function call, then we consider all
possible kinds of assignments and dereferences between the function arguments,
like arg1 = *arg2,  **arg1 = arg2, etc. The pseudocode is shown in Algorithm
1. Note that this is a simplified version that does not include field
sensitivity. For the full algorithm, please refer to our code on GitHub.

⬇

1input: body

2input: source, target

3

4source_val := alloc()

5$S_{\text{source}}$ := { source_val }

6

7for basic_block in reverse_postorder(body):

8 for statement in basic_block.statements:

9 match statement

10 [a = b] =>

11 $S_{a}:=S_{a}\cup S_{b}$

12

13 [*a = b] =>

14 if $S_{a}$ is empty:

15 $S_{a}:=\\{~{}\texttt{alloc()}~{}\\}$

16 for $x\in*S_{a}$:

17 $S_{x}:=S_{x}\cup S_{b}$

18

19 [a = *b] =>

20 if $S_{b}$ is empty:

21 $S_{b}:=\\{~{}\texttt{alloc()}~{}\\}$

22 for $x\in*S_{b}$:

23 $S_{a}:=S_{a}\cup S_{x}$

24

25 [a = &b] =>

26 $S_{a}:=S_{a}\cup\\{~{}b~{}\\}$

27

28 [ret = f(args)] =>

29 for a, b $\in$ choose(args, 2):

30 for $x\in(S_{a}\cup*S_{a}\cup**S_{a}...)$:

31 for $y\in(S_{b}\cup*S_{b}\cup**S_{b}...)$:

32 $S_{x}:=S_{x}\cup S_{y}$

33 $S_{y}:=S_{x}\cup S_{y}$

34 for a in args:

35 $S_{\text{ret}}:=S_{\text{ret}}\cup S_{a}\cup*S_{a}\cup**S_{a}...$

36

37if $\texttt{source\\_val}\in S_{\texttt{target}}$:

38 return True // May Alias

39else:

40 return False // Not Aliased

Algorithm 1 Alias Analysis