Verify Rust Standard Library Effort
The Verify Rust Standard Library effort is an ongoing investment that targets the verification of the Rust standard library. The goal of this is to provide automated verification that can be used to verify that a given Rust standard library implementation is safe.
Verifying the Rust libraries is difficult because:
- Lack of a specification,
- Lack of an existing verification mechanism in the Rust ecosystem,
- The large size of the verification problem,
- The unknowns of scalable verification.
Given the magnitude and scope of the effort, we believe this should be a community owned effort. For that, we are launching a contest that includes a series of challenges that focus on verifying memory safety and a subset of undefined behaviors in the Rust standard library.
Efforts are largely classified in the following areas:
- Contributing to the core mechanism of verifying the rust standard library
- Creating new techniques to perform scalable verification
- Apply techniques to verify previously unverified parts of the standard library.
There is a financial award tied to each challenge per its specification, which is awarded upon its successful completion.
We encourage everyone to watch this repository to be notified of any changes.
General Rules
Terms / Concepts
Verification Target: Our repository is a fork of the original Rust repository,
and we kept a copy of the Rust standard library inside the library/
folder that shall be used as the verification target for all our challenges.
We will periodically update the library/
folder to track newer versions of the official Rust standard library.
Challenges: Each individual verification effort will have a tracking issue where contributors can add comments and ask clarification questions. You can find the list of open challenges here.
Solutions: Solutions to a problem should be submitted as a single Pull Request (PR) to this repository. The solution should run as part of the CI. See more details about minimum requirements for each solution.
Basic Workflow
-
A verification effort will be published in the repository with appropriate details, and a tracking issue labeled with “Challenge” will be opened, so it can be used for clarifications and questions, as well as to track the status of the challenge.
-
Participants should create a fork of the repository where they will implement their proposed solution.
-
Once they submit their solution for analysis, participants should create a PR against the repository for analysis. Please make sure your solution meets the minimum requirements described here.
-
Each contribution will be reviewed on a first come, first served basis. Acceptance will be based on a review by a committee.
-
Once approved by the review committee, the change will be merged into the repository.
Solution Requirements
A proposed solution to a verification problem will only be reviewed if all the minimum requirements below are met:
- Each contribution or attempt should be submitted via a pull request to be analyzed by reviewers.
- By submitting the solution, participants confirm that they can use, modify, copy, and redistribute their contribution, under the terms of their choice.
- The contribution must be automated and should be checked and pass as part of the PR checks.
- All tools used by the solution must be in the list of accepted tools, and previously integrated in the repository. If that is not the case, please submit a separate tool application first.
- There is no restriction on the number of contributors for a solution. Make sure you have the rights to submit your solution and that all contributors are properly mentioned.
- The solution cannot impact the runtime logic of the standard library unless the change is proposed and incorporated into the Rust standard library.
Any exception to these requirements will only be considered if it is specified as part of the acceptance criteria of the challenged being solved.
Call for Challenges
The goal of the effort is to enable the verification of the entire Rust standard library. The type of obstacles users face may depend on which part of the standard library you would like to verify. Thus, our challenges are developed with the target of verifying a specific section of the standard library or strengthening existing verification.
Everyone is welcome to submit new challenge proposals for review by our committee. Follow the following steps to create a new proposal:
- Create a tracking issue using the challenge template for your challenge.
- In your fork of this repository do the following:
- Copy the template file (
book/src/challenge_template.md
) tobook/src/challenges/<ID_NUMBER>-<challenge-name>.md
. - Fill in the details according to the template instructions.
- Add a link to the new challenge inside
book/src/SUMMARY.md
- Submit a pull request.
- Copy the template file (
- Address any feedback in the pull request.
- If approved, we will publish your challenge and add the “Challenge” label to the tracking issue.
Tool Applications
Solutions must be automated using one of the tools previously approved and listed here. To use a new tool, participants must first submit an application for it.
- To submit a tool application, open a new issue in this repository using the "Tool Application" issue template.
- The committee will review the application. Once a committee member approves the application, the participant needs to create a PR with:
- A new workflow that runs the tool against the standard library.
- A new entry to the “Approved Tools” section of this book.
- Once this PR is merged, the tool is considered integrated, and the tool application issue will be closed.
The repository will be updated periodically, which can impact a tool's capacity to analyze the new version of the repository (i.e., the workflow may no longer pass after an update). If it is determined that the tool requires changes and such changes cannot be provided in a timely fashion the tool's approval may be revoked.
Committee Applications
You can apply to be part of the committee by submitting a pull request that adds your GitHub login name to the pull_request.toml
file.
For example, if your user login is @rahulku, add the login without @ to the committee member's list,
[committee]
members = [
+ "rahulku"
]
Committee members are expected to contribute by reviewing pull requests (all pull requests review approvals from at least two committee members before they can be merged). Reviews of solutions towards challenges should consider at least the following aspects:
- Does the pull request implement a solution that respects/meets the success criteria of the challenge?
- Do the contracts and harnesses incorporate the safety conditions stated in the documentation (from comments in the code and the standard library documentation)? Note that we currently focus on safety verification. Pre- and post-conditions towards functional correctness are acceptable as long as they do not negatively impact verification of safety, such as over-constraining input values or causing excessive verification run time.
- Is the contributed code of adequate quality, idiomatic, and stands a chance to be accepted into the standard library (to the best of the committee member's knowledge)?
Challenge XXXX1: Challenge Title
- Status: One of the following: [Open | Resolved | Expired]
- Solution: Option field to point to the PR that solved this challenge.
- Tracking Issue: Link to issue
- Start date: YYYY/MM/DD
- End date: YYYY/MM/DD
- Reward: TBD2
Goal
Describe the goal of this challenge with 1-2 sentences.
Motivation
Explain why this is a challenge that should be prioritized. Consider using a motivating example.
Description
Describe the challenge in more details.
Assumptions
Mention any assumption that users may make. Example, "assuming the usage of Stacked Borrows".
Success Criteria
Here are some examples of possible criteria:
All the following unsafe functions must be annotated with safety contracts and the contracts have been verified:
Function | Location |
---|---|
abc | def |
At least N of the following usages were proven safe:
Function | Location |
---|---|
xyz | 123 |
All proofs must automatically ensure the absence of the following undefined behaviors ref:
List of UBs
Note: All solutions to verification challenges need to satisfy the criteria established in the challenge book in addition to the ones listed above.
The number of the challenge sorted by publication date.
Leave it as TBD when creating a new challenge. This should only be filled by the reward committee.
The following form is designed to provide information for your tool that should be included in the effort to verify the Rust standard library. Please note that the tool will need to be supported if it is to be included.
Tool Name
Please enter your tool name here.
Description
Please enter a description for your tool and any information you deem relevant.
Tool Information
- Does the tool perform Rust verification?
- Does the tool deal with unsafe Rust code?
- Does the tool run independently in CI?
- Is the tool open source?
- Is the tool under development?
- Will you or your team be able to provide support for the tool?
Comparison to Other Approved Tools
Describe how this tool compares to the other approved tools. For example, are there certain properties that this tool can prove that the other tools cannot? The comparison does not need to be exhaustive; the purpose of this section is for the committee to understand the salient differences, and how this tool would fit into the larger effort.
Licenses
Please list the license(s) that are used by your tool, and if to your knowledge they conflict with the Rust standard library license(s).
Steps to Use the Tool
- [First Step]
- [Second Step]
- [and so on...]
Artifacts & Audit Mechanisms
If there are noteworthy examples of using the tool to perform verification, please include them in this section. Links, papers, etc. Also include mechanisms for the committee to audit the implementation and correctness of this tool (e.g., regression tests).
Versioning
Please describe how you version the tool.
CI
If your tool is approved, you will be responsible merging a workflow into this repository that runs your tool against the standard library. For an example, see the Kani workflow (.github/workflows/kani.yml). Describe, at a high level, how your workflow will operate. (E.g., how will you package the tool to run in CI, how will you identify which proofs to run?).
Verification Tools
The verification tool ecosystem for Rust is rapidly growing, and we welcome the usage of different tools to solve our challenges. In this chapter, you can find a list of tools that have already been approved for new solutions, what is their CI current status, as well as more details on how to use them.
If you would like to add a new tool to the list of tool applications, please see the Tool Application section.
Approved tools:
Kani Rust Verifier
The Kani Rust Verifier is a bit-precise model checker for Rust. Kani is designed to prove safety properties in your code as well as the absence of some forms of undefined behavior. It uses model checking under the hood to ensure that Rust programs adhere to user specified properties.
You can find more information about how to install in the installation section of the Kani book.
Usage
Consider a Rust function that takes an integer and returns its absolute value and a Kani proof that invokes the function that you want to verify
fn abs_diff(a: i32, b: i32) -> i32 {
if a > b {
a - b
} else {
b - a
}
}
#[cfg(kani)]
#[kani::proof]
fn harness() {
let a = kani::any::<i32>();
let b = kani::any::<i32>();
let result = abs_diff(a, b);
kani::assert(result >= 0, "Result should always be more than 0");
}
Running the command cargo kani
in your cargo crate will give the result
RESULTS:
Check 1: abs_diff.assertion.1
- Status: FAILURE
- Description: "attempt to subtract with overflow"
- Location: src/main.rs:5:9 in function abs_diff
... Other properties that might have failed or succeeded.
Summary:
Verification failed for - harness
Complete - 0 successfully verified harnesses, 1 failures, 1 total.
For a more detailed tutorial, you can refer to the tutorial section of the Kani book.
Using Kani to verify the Rust Standard Library
Here is a short tutorial of how to use Kani to verify proofs for the standard library.
Step 1 - Add some proofs to your copy of the model-checking std
Create a local copy of the model-checking fork of the Rust Standard Library. The fork comes with Kani configured, so all you'll need to do is to call Kani's building-block APIs (such as
assert
, assume
, proof
and function-contracts such as modifies
, requires
and ensures
) directly.
For example, insert this module into an existing file in the core library, like library/core/src/hint.rs
or library/core/src/error.rs
in your copy of the library.
This is just for the purpose of getting started, so you can insert it in a different (existing) file in the core library instead.
#[cfg(kani)]
#[unstable(feature = "kani", issue = "none")]
pub mod verify {
use crate::kani;
#[kani::proof]
pub fn harness_introduction() {
kani::assert(true, "yay");
}
#[kani::proof_for_contract(trivial_function)]
fn dummy_proof() {
trivial_function(true);
}
#[kani::requires(x == true)]
fn trivial_function(x: bool) -> bool {
x
}
}
Step 2 - Run the Kani script on the std library
To aid the Rust Standard Library verification effort, Kani provides a script out of the box to help you get started. Run the following command in your local terminal from the verify repository root:
./scripts/run-kani.sh --path .
To pass kani arguments such as --harness
, you can run the script with --kani-args
and continue passing in all the necessary arguments:
./scripts/run-kani.sh --path . --kani-args --harness alloc::layout::verify::check_array_i32 --output-format=terse
The script run-kani
installs the right version of Kani for you, builds it and then finally runs the verify-std sub-command of the kani
with some default flags.
NOTE: This script may crash due to linking issues. If the script fails with an error message related to linking, link the new CBMC version, delete the ./kani_build
directory and re-run.
Step 3 - Check verification result
After running the command, you can expect an output that looks like this:
SUMMARY:
** 0 of 1 failed
VERIFICATION:- SUCCESSFUL
Verification Time: 0.017101772s
Complete - 2 successfully verified harnesses, 0 failures, 2 total.
Running on a specific harness
You can specify a specific harness to be verified using the --harness
flag.
For example, in your local copy of the verify repo, run the following command.
./scripts/run-kani.sh --kani-args --harness harness_introduction
This gives you the verification result for just harness_introduction
from the aforementioned blob.
RESULTS:
Check 1: verify::harness_introduction.assertion.1
- Status: SUCCESS
- Description: "yay"
- Location: library/core/src/lib.rs:479:9 in function verify::harness_introduction
SUMMARY:
** 0 of 1 failed
VERIFICATION:- SUCCESSFUL
Verification Time: 0.01885804s
Complete - 1 successfully verified harnesses, 0 failures, 1 total.
Now you can write proof harnesses to verify specific functions in the library. The current convention is to keep proofs in the same module file of the verification target.
To run Kani for an individual proof, use --harness [harness_function_name]
.
Note that Kani will batch run all proofs in the library folder if you do not supply the --harness
flag.
If Kani returns the error no harnesses matched the harness filter
, you can give the full name of the harness.
For example, to run the proof harness named check_new
in library/core/src/ptr/unique.rs
, use
--harness ptr::unique::verify::check_new
. To run all proofs in unique.rs
, use --harness ptr::unique::verify
.
To find the full name of a harness, check the Kani output and find the line starting with Checking harness [harness full name]
.
More details
You can find more information about how to install and how you can customize your use of Kani in the Kani book.
This chapter contains all existing challenges, including the ones that have already been solved or expired.
For the most up-to-date information on a challenge status, please check their tracking issue linked in the challenge description.
If you would like to submit a new challenge, please see "Call for Challenges" section.
Challenge 1: Verify core
transmuting methods
- Status: Open
- Tracking Issue: #19
- Start date: 2024/06/12
- End date: 2025/04/10
- Reward: N/A
Goal
Confirm the soundness of value transmutations performed by libcore, including those transmutations exposed as public methods provided by libcore. A value-to-value transmutation is sound if:
- the source value is a bit-valid instance of the destination type;
- violations of library safety invariants (e.g., invariants on a field's value) of the destination type are not violated by subsequent use of the transmuted value.
If the context of the transmute is safe, these conditions should be proven with local reasoning. If the context of the transmute is unsafe, they may be discharged with a safety obligation on the caller.
To keep the goal somewhat manageable, it excludes some classes of code (e.g., UTF8-validation, async tasks, and others); see the assumptions listed below for the full list of excluded categories.
Details
Motivating Example
There are several calls to unsafe methods using transmute within the code of safe methods exported by libcore itself, so having clear and verifiable safety contracts is critical for verifying the safety of the safe methods that invoke them.
For example, std::slice::align_to
(which unsafely converts any slice &[T]
into a tuple (&[T], &[U], &[T])
composed of a prefix, a maximal sequence of values of type U
, and a suffix) just says for its safety that “all the usual caveats pertaining to transmute::<T, U>
also apply here”, which might be an under specification. For more details, see the documentation for transmute
.
Breaking-down the verification
We lay out the verification challenge from the bottom up. Starting with the core implementation of transmute
moving up to all unsafe and safe APIs that rely on it.
Part I - The Two Intrinsics
The public unsafe intrinsic transmute<T, U>
takes a value of type T
and reinterprets it to have type U
, with the sole (statically-enforced) restriction being that the types T
and U
must have the same size. The unstable intrinsic transmute_unchecked<T, U>
is similar, except that it removes the static size restriction, treating violations of it as undefined behavior.
What is the right way to encode the preconditions of the two transmutation intrinsics?
If one is solely concerned about safety: The Rustonomicon lists several ways that transmutation can yield undefined behavior. Encoding a safety contract for transmute that captures all the relevant criteria laid out in the documentation is crucial.
If one is concerned about proving functional correctness, then reasoning about transmutation will require reasoning about the byte representation of values to justify that the reinterpretation of the value’s bytes for satisfying the pending proof obligation associated with the output value.
Part II - unsafe
APIs with Validity Constraints
There are unsafe methods (which are defined by libcore and reexported by libstd) that have the effect of a transmutation between a (sequence of) T
and a (sequence of) U
. Come up with an appropriate safety contract for each of them.
Part III - unsafe
APIs with Richer Constraints
Similar to part 2, there are also unsafe methods, but now the safety condition is more complicated, such as “is valid ascii character” or "is valid unicode scalar value."
Part IV - safe
APIs
These are safe APIs that call into the unsafe API's from parts 1 through 3 above. Now our final goal is to prove that they actually are safe, despite calling transmute or transmute-related methods in their implementations.
Assumptions
For this challenge, the following assumptions are acceptable:
We are not attempting to validate all details of the memory model for this challenge; for example, you do not need to worry about whether we are using the Stacked Borrows or Tree Borrows aliasing models. Likewise, you do not need to validate the provenance-related API in std::ptr
.
You are allowed, but not required, to leverage the unstable Transmutability
trait under development as part of your solution. This is a libstd-internal feature for auditing whether a given transmutation is safe. (It seems like something tools should try to leverage in some way; but it is also experimental.) Note that if you need to add new impls of Transmutability
, then those new impl’s need to be accepted by (and landed in) the upstream Rust project before your solution can be considered completed. See also https://github.com/rust-lang/rust/issues/99571
You do not need to verify the correctness of the transmute calls in the unit tests embedded in libcore, though it would be great to do so!
To keep the goal somewhat manageable, we are omitting the following classes of code from the acceptance criteria for this challenge:
- utf8-validation (such as
str::from_utf8_unchecked
) - the provenance-related API in
std::ptr
(such asaddr
, orwithout_provenance
) - the num methods (from modules like
core::num::f64
,core::num::i32
, etc) - pointer-metadata and vtable APIs (from modules like
core::ptr::metadata
) - async rust runtime/task API (from
core::task
) - core-internal specialization methods (such as traits like
RangeIteratorImpl
with methods prefixed with "spec_") - core-internal
__iterator_get_unchecked
calls - value output formatting machinery (from
std::fmt::rt
) You do not need to verify those (potentially indirect) uses of transmute, unless you need to establish the safety/correctness of some of those methods in order to verify some other type in this list. (That is, you cannot assume them to be safe nor correct in your verification of other methods listed here.) We expect to issue future challenges tailored to each of the categories of transmutation uses listed above.
Success Criteria
A new entry to the specification book is created explaining the relevant patterns for verifying code that calls transmute.
At least 35 of the following 47 intrinsics and functions (i.e. approximately 75%) have been annotated with contracts, and, for non-intrinsics, had their bodies verified.
For the safe functions, you do not need to provide a full-functional correctness specification; it will suffice to add pre- and post-conditions (i.e. assumptions and assertions) around the relevant part of the code that calls the transmutation-related unsafe function or intrinsic.
Function | Location |
---|---|
transmute_unchecked | core::intrinsics |
transmute | core::intrinsics |
MaybeUninit<T>::array_assume_init | core::mem |
MaybeUninit<[T; N]>::transpose | core::mem |
<[MaybeUninit<T>; N]>::transpose | core::mem |
<[T; N] as IntoIterator>::into_iter | core::array::iter |
BorrowedBuf::unfilled | core::io::borrowed_buf |
BorrowedCursor::reborrow | core::io::borrowed_buf |
str::as_bytes | core::str |
from_u32_unchecked | core::char::convert |
char_try_from_u32 | core::char::convert |
Ipv6Addr::new | core::net::ip_addr |
Ipv6Addr::segments | core::net::ip_addr |
align_offset | core::ptr |
Alignment::new_unchecked | core::ptr::alignment |
MaybeUninit<T>::copy_from_slice | core::mem |
str::as_bytes_mut | core::str |
<Filter<I,P> as Iterator>::next_chunk | core::iter::adapters |
<FilterMap<I,F> as Iterator>::next_chunk | core::iter::adapters |
try_from_fn | core::array |
iter_next_chunk | core::array |
from_u32_unchecked | core::char |
AsciiChar::from_u8_unchecked | core::ascii_char |
memchr_aligned | core::slice::memchr |
<[T]>::align_to_mut | core::slice |
run_utf8_validation | core::str::validations |
<[T]>::align_to | core::slice |
is_aligned_to | core::const_ptr |
is_aligned_to | core::mut_ptr |
Alignment::new | core::ptr::alignment |
Layout::from_size_align | core::alloc::layout |
Layout::from_size_align_unchecked | core::alloc::layout |
make_ascii_lowercase | core::str |
make_ascii_uppercase | core::str |
<char as Step>::forward_checked | core::iter::range |
<Chars as Iterator>::next | core::str::iter |
<Chars as DoubleEndedIterator>::next_back | core::str::iter |
char::encode_utf16_raw | core::char |
<char as Step>::backward_unchecked | core::iter::range |
<char as Step>::forward_unchecked | core::iter::range |
AsciiChar::from_u8 | core::ascii_char |
char::as_ascii | core::char |
<[T]>::as_simd_mut | core::slice |
<[T]>::as_simd | core::slice |
memrchr | core::slice::memchr |
do_count_chars | str::count |
- All solutions to verification challenges need to satisfy the criteria established in the challenge book in addition to the ones listed below
Appendix A: The list construction
The list of methods and intrinsics was gathered by surveying the call-graph (solely within the libcore source) of function bodies that could eventually invoke transmute
or transmute_unchecked
. For each caller: if the caller was itself unsafe
, then its callers were then surveyed; if the caller was not unsafe
, then it was treated as an end point for the survey.
As mentioned in the assumptions, some (large) classes of methods were omitted from the challenge, either because 1. they encompassed a large API surface (e.g. core::num
) that deserved separate treatment, 2. they had an enormous number of callers that would deserve separate treatment (e.g. core::str::from_utf8_unchecked
), or 3. they interact with aspects of the Rust memory model that still need to be better understood by reasoning tools (e.g. the provenance APIs).
You can see the call graph produced by the survey here.
Challenge 2: Verify the memory safety of core intrinsics using raw pointers
- Status: Open
- Tracking Issue: #16
- Start date: 2024/06/12
- End date: 2025/04/10
- Reward: N/A
Goal
Annotate Rust core::intrinsics functions that manipulate raw pointers with their safety contract. Verify their usage in the standard library is in fact safe.
Success Criteria
- All the following intrinsic functions must be annotated with safety contracts.
- Any fallback intrinsic implementation must be verified.
- For intrinsics modeled in the tool of choice, explain how their implementation matches the intrinsics definition. This can either be done in the PR description or as an entry to the contest book as part of the “Tools” chapter.
- For each function, contestants must state clearly the list of assumptions for each proof, how the proofs can be audited, and the list of (implicit and explicit) properties that are guaranteed.
- The verification of each intrinsic should ensure all the documented safety conditions are met, and that meeting them is enough to guarantee safe usage.
Intrinsic functions to be annotated with safety contracts
Function | Location |
---|---|
typed_swap | core::intrisics |
vtable_size | core::intrisics |
vtable_align | core::intrisics |
copy_nonoverlapping | core::intrisics |
copy | core::intrisics |
write_bytes | core::intrisics |
size_of_val | core::intrisics |
arith_offset | core::intrisics |
volatile_copy_nonoverlapping_memory | core::intrisics |
volatile_copy_memory | core::intrisics |
volatile_set_memory | core::intrisics |
volatile_load | core::intrisics |
volatile_store | core::intrisics |
unaligned_volatile_load | core::intrisics |
unaligned_volatile_store | core::intrisics |
compare_bytes | core::intrisics |
min_align_of_val | core::intrisics |
ptr_offset_from | core::intrisics |
ptr_offset_from_unsigned | core::intrisics |
read_via_copy | core::intrisics |
write_via_move | core::intrisics |
All the following usages of intrinsics were proven safe:
Function | Location |
---|---|
copy_from_slice | core::slice |
parse_u64_into | std::fmt |
swap | core::mem |
align_of_val | core::mem |
zeroed | core::mem::maybe_uninit |
Annotate and verify all the functions below that expose intrinsics with safety contracts
Function | Location |
---|---|
copy_from_slice | std::ptr |
parse_u64_into | std::ptr |
swap | std::ptr |
align_of_val | std::ptr |
zeroed | std::ptr |
List of UBs
All proofs must automatically ensure the absence of the following undefined behaviors ref:
- Invoking undefined behavior via compiler intrinsics.
- Accessing (loading from or storing to) a place that is dangling or based on a misaligned pointer.
- Reading from uninitialized memory except for padding or unions.
- Mutating immutable bytes.
- Producing an invalid value
Note: All solutions to verification challenges need to satisfy the criteria established in the challenge book in addition to the ones listed above.
Challenge 3: Verifying Raw Pointer Arithmetic Operations
- Status: Resolved
- Tracking Issue: #76
- Start date: 2024/06/24
- End date: 2024/12/11
- Reward: N/A
- Contributors: Surya Togaru, Yifei Wang, Szu-Yu Lee, Mayuresh Joshi
Goal
The goal of this challenge is to verify safety of code that relies on raw pointer arithmetic, and eventual raw pointer access.
Motivation
Raw pointer arithmetic is a common operation employed in the implementation of highly optimized code,
as well as containers with dynamic size.
Examples of the former are str::repeat
, [u8]::is_ascii
,
while for the latter we have Vec
, VecDeque
, HashMap
.
These unsafe operations are usually abstracted from the end user with the usage of
safe abstractions.
However, bugs in these abstractions may compromise entire applications, potentially becoming a security concern.
See CVE-2018-1000810 for an example of an issue with an
optimization of str::repeat
.
These safe abstractions are great candidates for software verification. They are critical for Rust applications safety, and they are modular by design.
Description
Rust provides different options for pointer arithmetic, which have different semantics when it comes to safety.
For example, methods such as ptr::offset
,
ptr::add
,
and ptr::sub
are unsafe, and one of their safety conditions is that:
- Both the starting and resulting pointer must be either in bounds or one byte past the end of the same allocated object.
I.e., violating this safety condition triggers immediate UB.
On the other hand, wrapping operations such as
ptr::wrapping_offset
,
ptr::wrapping_add
,
ptr::wrapping_sub
,
are safe, however, the resulting pointer must not be used to read or write other allocated objects.
Thus, we would like to be able to verify usage of these different methods within the standard library to ensure they are safely employed, as well as provide function contracts that can be used by other Rust crates to verify their own usage of these methods.
Assumptions
For this challenge, we do not require a full proof that is independent of the pointee type T
.
Instead, we require that the verification is done for the following pointee types:
- All integer types.
- At least one
dyn Trait
. - At least one slice.
- For unit type.
- At least one composite type with multiple non-ZST fields.
Success Criteria
All the following unsafe functions must be annotated with safety contracts and the contracts have been verified:
Function | Location |
---|---|
*const T::add | core::ptr |
*const T::sub | core::ptr |
*const T::offset | core::ptr |
*const T::offset_from | core::ptr |
*const T::byte_add | core::ptr |
*const T::byte_sub | core::ptr |
*const T::byte_offset | core::ptr |
*const T::byte_offset_from | core::ptr |
*mut T::add | core::ptr |
*mut T::sub | core::ptr |
*mut T::offset | core::ptr |
*mut T::offset_from | core::ptr |
*mut T::byte_add | core::ptr |
*mut T::byte_sub | core::ptr |
*mut T::byte_offset | core::ptr |
*mut T::byte_offset_from | core::ptr |
At least 3 of the following usages were proven safe:
Function | Location |
---|---|
[u8]::is_ascii | core::slice |
String::remove | alloc::string |
Vec::swap_remove | alloc::vec |
Option::as_slice | core::option |
VecDeque::swap | collections::vec_deque |
All proofs must automatically ensure the absence of the following undefined behaviors ref:
- Accessing (loading from or storing to) a place that is dangling or based on a misaligned pointer.
- Performing a place projection that violates the requirements of in-bounds pointer arithmetic. A place projection is a field expression, a tuple index expression, or an array/slice index expression.
- Invoking undefined behavior via compiler intrinsics.
- Producing an invalid value, even in private fields and locals.
Note: All solutions to verification challenges need to satisfy the criteria established in the challenge book in addition to the ones listed above.
Challenge 4: Memory safety of BTreeMap's btree::node
module
- Status: Open
- Tracking Issue: #77
- Start date: 2024/07/01
- End date: 2025/04/10
- Reward: 10,000 USD
Goal
Verify the memory safety of the alloc::collections::btree::node
module.
This is one of the main modules used for implementing the BTreeMap
collection, and it includes a lot of unsafe code.
Success Criteria
The memory safety of all public functions (especially safe ones) containing unsafe code must be verified, e.g.:
LeafNode::new
NodeRef::as_internal_mut
NodeRef::len
NodeRef::ascend
NodeRef::first_edge
NodeRef::last_edge
NodeRef::first_kv
NodeRef::last_kv
NodeRef::into_leaf
NodeRef::keys
NodeRef::as_leaf_mut
NodeRef::into_leaf_mut
NodeRef::as_leaf_dying
NodeRef::pop_internal_level
NodeRef::push
Handle::left_edge
Handle::right_edge
Handle::left_kv
Handle::right_kv
Handle::descend
Handle::into_kv
Handle::key_mut
Handle::into_val_mut
Handle::into_kv_mut
Handle::into_kv_valmut
Handle::kv_mut
Verification must be unbounded for functions that use recursion or contain loops, e.g.
NodeRef::new_internal
Handle::insert_recursing
BalancingContext::do_merge
BalancingContext::merge_tracking_child_edge
BalancingContext::steal_left
BalancingContext::steal_right
BalancingContext::bulk_steal_left
BalancingContext::bulk_steal_right
List of UBs
All proofs must automatically ensure the absence of the following undefined behaviors:
- Accessing (loading from or storing to) a place that is dangling or based on a misaligned pointer.
- Reading from uninitialized memory.
- Mutating immutable bytes.
- Producing an invalid value
Note: All solutions to verification challenges need to satisfy the criteria established in the challenge book in addition to the ones listed above.
Challenge 5: Verify functions iterating over inductive data type: linked_list
- Status: Open
- Tracking Issue: #29
- Start date: 2024/07/01
- End date: 2025/04/10
- Reward: 5,000 USD
Goal
Verify the memory safety of alloc::collections::linked_list
functions that iterate over its internal inductive-defined data type.
Details
The internal representations of linked_list
are bi-direction linked list nodes. To unboundedly prove the memory safety of functions that iterating over such inductive-defined data type, we need to illustrate the memory safety for linked lists of arbitrary shape. On the other hand, if we can only prove the memory safety for certain shapes of linked lists, how should we specify the precondition---the assumptions on the shape of the inductive-defined data type---of such functions.
Success Criteria
The memory safety of the following public functions that iterating over the internal inductive data type must be verified:
Function | Location |
---|---|
clear | alloc::collections::linked_list |
contains | alloc::collections::linked_list |
split_off | alloc::collections::linked_list |
remove | alloc::collections::linked_list |
retain | alloc::collections::linked_list |
retain_mut | alloc::collections::linked_list |
extract_if | alloc::collections::linked_list |
The verification must be unbounded---it must hold for linked lists of arbitrary shape.
It is OK to assume that the generic type T
of the proofs is primitive types, e.g., i32
, u32
, bool
, etc.
List of UBs
All proofs must automatically ensure the absence of the following undefined behaviors ref:
- Accessing (loading from or storing to) a place that is dangling or based on a misaligned pointer.
- Reading from uninitialized memory except for padding or unions.
- Mutating immutable bytes.
- Producing an invalid value
Note: All solutions to verification challenges need to satisfy the criteria established in the challenge book in addition to the ones listed above.
Challenge 6: Safety of NonNull
- Status: Open
- Tracking Issue: #53
- Start date: 2024/08/16
- End date: 2025/04/10
- Reward: N/A
Goal
Verify absence of undefined behavior of the ptr::NonNull
module.
Most of its functions are marked unsafe
, yet they are used in 62 other modules
of the standard library.
Success Criteria
Prove absence of undefined behavior of the following 48 public functions. You may wish to do so by attaching pre- and postconditions to these, and then (if needed by the tooling that you choose to use) adding verification harnesses.
NonNull<T>::add
NonNull<T>::addr
NonNull<T>::align_offset
NonNull<T>::as_mut<'a>
NonNull<T>::as_mut_ptr
NonNull<T>::as_non_null_ptr
NonNull<T>::as_ptr
NonNull<T>::as_ref<'a>
NonNull<T>::as_uninit_mut<'a>
NonNull<T>::as_uninit_ref<'a>
NonNull<T>::as_uninit_slice<'a>
NonNull<T>::as_uninit_slice_mut<'a>
NonNull<T>::byte_add
NonNull<T>::byte_offset_from<U: ?Sized>
NonNull<T>::byte_offset
NonNull<T>::byte_sub
NonNull<T>::cast<U>
NonNull<T>::copy_from_nonoverlapping
NonNull<T>::copy_from
NonNull<T>::copy_to_nonoverlapping
NonNull<T>::copy_to
NonNull<T>::dangling
NonNull<T>::drop_in_place
NonNull<T>::from_raw_parts
NonNull<T>::get_unchecked_mut<I>
NonNull<T>::is_aligned_to
NonNull<T>::is_aligned
NonNull<T>::is_empty
NonNull<T>::len
NonNull<T>::map_addr
NonNull<T>::new_unchecked
NonNull<T>::new
NonNull<T>::offset_from
NonNull<T>::offset
NonNull<T>::read_unaligned
NonNull<T>::read_volatile
NonNull<T>::read
NonNull<T>::replace
NonNull<T>::slice_from_raw_parts
NonNull<T>::sub_ptr
NonNull<T>::sub
NonNull<T>::swap
NonNull<T>::to_raw_parts
NonNull<T>::with_addr
NonNull<T>::write_bytes
NonNull<T>::write_unaligned
NonNull<T>::write_volatile
NonNull<T>::write
List of UBs
In addition to any properties called out as SAFETY
comments in the source
code,
all proofs must automatically ensure the absence of the following undefined behaviors:
- Accessing (loading from or storing to) a place that is dangling or based on a misaligned pointer.
- Reading from uninitialized memory.
- Mutating immutable bytes.
- Producing an invalid value
Note: All solutions to verification challenges need to satisfy the criteria established in the challenge book in addition to the ones listed above.
Challenge 7: Safety of Methods for Atomic Types & Atomic Intrinsics
- Status: Open
- Tracking Issue: #83
- Start date: 2024/10/30
- End date: 2025/04/10
- Reward: 10,000 USD
Goal
core::sync::atomic
provides methods that operate on atomic types.
For example, AtomicBool::store(&self, val: bool, order: Ordering)
stores val
in the atomic boolean referenced by self
according to the specified atomic memory ordering.
The goal of this challenge is to verify that these methods are safe.1
Success Criteria
Part 1: Unsafe Methods
First, verify that the unsafe from_ptr
methods are safe, given that their safety preconditions are met.
Write safety contracts for each of the from_ptr
methods:
AtomicBool::from_ptr
AtomicPtr::from_ptr
AtomicI8::from_ptr
AtomicU8::from_ptr
AtomicI16::from_ptr
AtomicU16::from_ptr
AtomicI32::from_ptr
AtomicU32::from_ptr
AtomicI64::from_ptr
AtomicU64::from_ptr
AtomicI128::from_ptr
AtomicU128::from_ptr
Specifically, encode the conditions about ptr
's alignment and validity (marked #Safety
in the methods' documentation) as preconditions.
Then, verify that the methods are safe for all possible values for the type that ptr
points to, given that ptr
satisfies those preconditions.
For example, AtomicI8::from_ptr
is defined as:
/// `ptr` must be [valid] ... (comment continues; omitted for brevity)
pub const unsafe fn from_ptr<'a>(ptr: *mut i8) -> &'a AtomicI8 {
// SAFETY: guaranteed by the caller
unsafe { &*ptr.cast() }
}
To verify this method, first encode the safety comments (e.g., about pointer validity) as preconditions, then verify the absence of undefined behavior for all possible i8
values.
For the AtomicPtr
case only, we do not require that you verify safety for all possible types.
Concretely, below is the type signature for AtomicPtr::from_ptr
:
pub const unsafe fn from_ptr<'a>(ptr: *mut *mut T) -> &'a AtomicPtr<T>
The type pointed to is a *mut T
.
Verify that for any arbitrary value for this *mut T
(i.e., any arbitrary memory address), the method is safe.
However, you need not verify the method for all possible instantiations of T
.
It suffices to verify this method for T
of byte sizes 0, 1, 2, 4, and at least one non-power of two.
Part 2: Safe Abstractions
The atomic types expose safe abstractions for atomic operations. In this part, you will work toward verifying that these abstractions are indeed safe by writing and verifying safety contracts for the unsafe code in their bodies.
For example, AtomicBool::store
is the (public) safe method that atomically updates the boolean's value.
This method invokes the unsafe function atomic_store
, which in turn calls intrinsics::atomic_store_relaxed
, intrinsics::atomic_store_release
, or intrinsics::atomic_store_seqcst
, depending on the provided ordering.
Write and verify safety contracts for the unsafe functions:
atomic_store
atomic_load
atomic_swap
atomic_add
atomic_sub
atomic_compare_exchange
atomic_compare_exchange_weak
atomic_and
atomic_nand
atomic_or
atomic_xor
atomic_max
atomic_umax
atomic_umin
Then, for each of the safe abstractions that invoke the unsafe functions listed above, write contracts that ensure that they are not invoked with order
s that would cause panics.
For example, atomic_store
panics if invoked with Acquire
or AcqRel
ordering.
In this case, you would write contracts on the safe store
methods that enforce that they are not called with either of those order
s.
Part 3: Atomic Intrinsics
Write and verify safety contracts for the intrinsics invoked by the unsafe functions from Part 2 (in core::intrinsics
):
Operations | Functions |
---|---|
Store | atomic_store_relaxed , atomic_store_release , atomic_store_seqcst |
Load | atomic_load_relaxed , atomic_load_acquire , atomic_load_seqcst |
Swap | atomic_xchg_relaxed , atomic_xchg_acquire , atomic_xchg_release , atomic_xchg_acqrel , atomic_xchg_seqcst |
Add | atomic_xadd_relaxed , atomic_xadd_acquire , atomic_xadd_release , atomic_xadd_acqrel , atomic_xadd_seqcst |
Sub | atomic_xsub_relaxed , atomic_xsub_acquire , atomic_xsub_release , atomic_xsub_acqrel , atomic_xsub_seqcst |
Compare Exchange | atomic_cxchg_relaxed_relaxed , atomic_cxchg_relaxed_acquire , atomic_cxchg_relaxed_seqcst , atomic_cxchg_acquire_relaxed , atomic_cxchg_acquire_acquire , atomic_cxchg_acquire_seqcst , atomic_cxchg_release_relaxed , atomic_cxchg_release_acquire , atomic_cxchg_release_seqcst , atomic_cxchg_acqrel_relaxed , atomic_cxchg_acqrel_acquire , atomic_cxchg_acqrel_seqcst , atomic_cxchg_seqcst_relaxed , atomic_cxchg_seqcst_acquire , atomic_cxchg_seqcst_seqcst |
Compare Exchange Weak | atomic_cxchgweak_relaxed_relaxed , atomic_cxchgweak_relaxed_acquire , atomic_cxchgweak_relaxed_seqcst , atomic_cxchgweak_acquire_relaxed , atomic_cxchgweak_acquire_acquire , atomic_cxchgweak_acquire_seqcst , atomic_cxchgweak_release_relaxed , atomic_cxchgweak_release_acquire , atomic_cxchgweak_release_seqcst , atomic_cxchgweak_acqrel_relaxed , atomic_cxchgweak_acqrel_acquire , atomic_cxchgweak_acqrel_seqcst , atomic_cxchgweak_seqcst_relaxed , atomic_cxchgweak_seqcst_acquire , atomic_cxchgweak_seqcst_seqcst |
And | atomic_and_relaxed , atomic_and_acquire , atomic_and_release , atomic_and_acqrel , atomic_and_seqcst |
Nand | atomic_nand_relaxed , atomic_nand_acquire , atomic_nand_release , atomic_nand_acqrel , atomic_nand_seqcst |
Or | atomic_or_seqcst , atomic_or_acquire , atomic_or_release , atomic_or_acqrel , atomic_or_relaxed |
Xor | atomic_xor_seqcst , atomic_xor_acquire , atomic_xor_release , atomic_xor_acqrel , atomic_xor_relaxed |
Max | atomic_max_relaxed , atomic_max_acquire , atomic_max_release , atomic_max_acqrel , atomic_max_seqcst |
Min | atomic_min_relaxed , atomic_min_acquire , atomic_min_release , atomic_min_acqrel , atomic_min_seqcst |
Umax | atomic_umax_relaxed , atomic_umax_acquire , atomic_umax_release , atomic_umax_acqrel , atomic_umax_seqcst |
Umin | atomic_umin_relaxed , atomic_umin_acquire , atomic_umin_release , atomic_umin_acqrel , atomic_umin_seqcst |
List of UBs
In addition to any safety properties mentioned in the API documentation, all proofs must automatically ensure the absence of the following undefined behaviors:
- Data races.
- Accessing (loading from or storing to) a place that is dangling or based on a misaligned pointer.
- Reading from uninitialized memory.
- Invoking undefined behavior via compiler intrinsics.
- Producing an invalid value.
Note: All solutions to verification challenges need to satisfy the criteria established in the challenge book in addition to the ones listed above.
Throughout this challenge, when we say "safe", it is identical to saying "does not exhibit undefined behavior".
Challenge 8: Contracts for SmallSort
- Status: Open
- Tracking Issue: #56
- Start date: 2024/08/17
- End date: 2025/04/10
- Reward: 10,000 USD
Goal
The implementations of the traits StableSmallSortTypeImpl
, UnstableSmallSortTypeImpl
, and UnstableSmallSortFreezeTypeImpl
in the smallsort
module of the Rust standard library are the sorting
algorithms optimized for slices with small lengths.
In this challenge, the goal is to, first prove the memory safety of the public functions in the smallsort
module, and, second, write contracts for them to
show that the sorting algorithms actually sort the slices.
Success Criteria
Prove absence of undefined behavior of the following public functions.
<T as slice::sort::shared::smallsort::StableSmallSortTypeImpl>::small_sort
<T as slice::sort::shared::smallsort::UnstableSmallSortTypeImpl>::small_sort
<T as slice::sort::shared::smallsort::UnstableSmallSortFreezeTypeImpl>::small_sort
slice::sort::shared::smallsort::swap_if_less
slice::sort::shared::smallsort::insertion_sort_shift_left
slice::sort::shared::smallsort::sort4_stable
slice::sort::shared::smallsort::has_efficient_in_place_swap
Write contracts for the following public functions that show that they actually sort the slices.
<T as slice::sort::shared::smallsort::StableSmallSortTypeImpl>::small_sort
<T as slice::sort::shared::smallsort::UnstableSmallSortTypeImpl>::small_sort
<T as slice::sort::shared::smallsort::UnstableSmallSortFreezeTypeImpl>::small_sort
The memory safety and the contracts of the above listed functions must be verified for all possible slices with arbitrary valid length.
Note that most of the functions listed above call functions that contain loops. Function contracts and loop contracts of those callee functions may be required.
List of UBs
In addition to any properties called out as SAFETY
comments in the source
code,
all proofs must automatically ensure the absence of the following undefined behaviors:
- Accessing (loading from or storing to) a place that is dangling or based on a misaligned pointer.
- Reading from uninitialized memory.
- Mutating immutable bytes.
- Producing an invalid value
Note: All solutions to verification challenges need to satisfy the criteria established in the challenge book in addition to the ones listed above.
Challenge 9: Safe abstractions for core::time::Duration
- Status: Resolved
- Tracking Issue: #72
- Start date: 2024/08/20
- End date: 2024/12/10
- Reward: N/A
- Contributors: Samuel Thomas and Cole Vick
Goal
Write function contracts for core::time::Duration
that can be used as safe abstractions.
Even though the majority of Duration
methods are safe, many of them are safe abstractions over unsafe code.
For instance, the new
method is implemented as follows in v1.3.0:
pub const fn new(secs: u64, nanos: u32) -> Duration {
if nanos < NANOS_PER_SEC {
// SAFETY: nanos < NANOS_PER_SEC, therefore nanos is within the valid range
Duration { secs, nanos: unsafe { Nanoseconds(nanos) } }
} else {
let secs = match secs.checked_add((nanos / NANOS_PER_SEC) as u64) {
Some(secs) => secs,
None => panic!("overflow in Duration::new"),
};
let nanos = nanos % NANOS_PER_SEC;
// SAFETY: nanos % NANOS_PER_SEC < NANOS_PER_SEC, therefore nanos is within the valid range
Duration { secs, nanos: unsafe { Nanoseconds(nanos) } }
}
}
Success Criteria
Write a type invariant for the struct Duration
. Write function contracts for the following public functions.
-
Duration::new(secs: u64, nanos: u32) -> Duration
-
Duration::from_secs(secs: u64) -> Duration
-
Duration::from_millis(millis: u64) -> Duration
-
Duration::from_micros(micros: u64) -> Duration
-
Duration::from_nanos(nanos: u64) -> Duration
-
Duration::as_secs(&self) -> u64
-
Duration::as_millis(&self) -> u128
-
Duration::as_micros(&self) -> u128
-
Duration::as_nanos(&self) -> u128
-
Duration::subsec_millis(&self) -> u32
-
Duration::subsec_micros(&self) -> u32
-
Duration::subsec_nanos(&self) -> u32
-
Duration::checked_add(&self, rhs: Duration) -> Option<Duration>
-
Duration::checked_sub(&self, rhs: Duration) -> Option<Duration>
-
Duration::checked_mul(&self, rhs: u32) -> Option<Duration>
-
Duration::checked_div(&self, rhs: u32) -> Option<Duration>
The memory safety and the contracts of the above listed functions must be verified for all possible input values.
List of UBs
In addition to any properties called out as SAFETY
comments in the source
code,
all proofs must automatically ensure the absence of the following undefined behaviors:
- Accessing (loading from or storing to) a place that is dangling or based on a misaligned pointer.
- Reading from uninitialized memory.
- Mutating immutable bytes.
- Producing an invalid value
Note: All solutions to verification challenges need to satisfy the criteria established in the challenge book in addition to the ones listed above.
Challenge 10: Memory safety of String
- Status: Open
- Tracking Issue: #61
- Start date: 2024/08/19
- End date: 2025/04/10
- Reward: N/A
Goal
In this challenge, the goal is to verify the memory safety of std::string::String
.
Even though the majority of String
methods are safe, many of them are safe abstractions over unsafe code.
For instance, the insert
method is implemented as follows in v1.80.1:
pub fn insert(&mut self, idx: usize, ch: char) {
assert!(self.is_char_boundary(idx));
let mut bits = [0; 4];
let bits = ch.encode_utf8(&mut bits).as_bytes();
unsafe {
self.insert_bytes(idx, bits);
}
}
where insert_bytes
has the following implementation:
unsafe fn insert_bytes(&mut self, idx: usize, bytes: &[u8]) {
let len = self.len();
let amt = bytes.len();
self.vec.reserve(amt);
unsafe {
ptr::copy(self.vec.as_ptr().add(idx), self.vec.as_mut_ptr().add(idx + amt), len - idx);
ptr::copy_nonoverlapping(bytes.as_ptr(), self.vec.as_mut_ptr().add(idx), amt);
self.vec.set_len(len + amt);
}
}
The call to the unsafe insert_bytes
method (which itself contains unsafe code) makes insert
susceptible to undefined behavior.
Success Criteria
Verify the memory safety of all public functions that are safe abstractions over unsafe code:
from_utf16le
(unbounded)from_utf16le_lossy
(unbounded)from_utf16be
(unbounded)from_utf16be_lossy
(unbounded)pop
remove
remove_matches
(unbounded)retain
(unbounded)insert
insert_str
(unbounded)split_off
(unbounded)drain
replace_range
(unbounded)into_boxed_str
leak
Ones marked as unbounded must be verified for any string/slice length.
List of UBs
All proofs must automatically ensure the absence of the following undefined behaviors:
- Accessing (loading from or storing to) a place that is dangling or based on a misaligned pointer.
- Reading from uninitialized memory.
- Mutating immutable bytes.
- Producing an invalid value
Note: All solutions to verification challenges need to satisfy the criteria established in the challenge book in addition to the ones listed above.
Challenge 11: Safety of Methods for Numeric Primitive Types
- Status: Resolved
- Tracking Issue: #59
- Start date: 2024/08/20
- End date: 2024/12/04
- Reward: N/A
- Contributors: Rajath M Kotyal, Yen-Yun Wu, Lanfei Ma, Junfeng Jin
Goal
Verify the safety of public unsafe methods for floats and integers in core::num
.
To find the documentation for these methods, navigate first to the core::num
documentation, then click on the appropriate primitive type in the left-side menu bar. For example, for i8::unchecked_add
, click on i8
.
Success Criteria
Part 1: Unsafe Integer Methods
Prove the absence of arithmetic overflow/underflow and undefined behavior in the following methods for each of the listed integer types, given that their safety preconditions are satisfied:
Method | Integer Types |
---|---|
unchecked_add | i8 , i16 , i32 , i64 , i128 , u8 , u16 , u32 , u64 , u128 |
unchecked_sub | i8 , i16 , i32 , i64 , i128 , u8 , u16 , u32 , u64 , u128 |
unchecked_mul | i8 , i16 , i32 , i64 , i128 , u8 , u16 , u32 , u64 , u128 |
unchecked_shl | i8 , i16 , i32 , i64 , i128 , u8 , u16 , u32 , u64 , u128 |
unchecked_shr | i8 , i16 , i32 , i64 , i128 , u8 , u16 , u32 , u64 , u128 |
unchecked_neg | i8 , i16 , i32 , i64 , i128 |
Part 2: Safe API Verification
Now, verify some of the safe APIs that leverage the unsafe integer methods from Part 1. Verify the absence of arithmetic overflow/underflow and undefined behavior of the following methods for each of the listed integer types:
Method | Integer Types |
---|---|
wrapping_shl | i8 , i16 , i32 , i64 , i128 , u8 , u16 , u32 , u64 , u128 |
wrapping_shr | i8 , i16 , i32 , i64 , i128 , u8 , u16 , u32 , u64 , u128 |
widening_mul | u8 , u16 , u32 , u64 |
carrying_mul | u8 , u16 , u32 , u64 |
Part 3: Float to Integer Conversion
Verify the absence of arithmetic overflow/underflow and undefined behavior in to_int_unchecked
for f16
, f32
, f64
, and f128
.
List of UBs
In addition to any properties called out as SAFETY comments in the source code, all proofs must automatically ensure the absence of the following undefined behaviors:
- Invoking undefined behavior via compiler intrinsics.
- Reading from uninitialized memory.
- Mutating immutable bytes.
- Producing an invalid value.
Note: All solutions to verification challenges need to satisfy the criteria established in the challenge book in addition to the ones listed above.
Challenge 12: Safety of NonZero
- Status: Open
- Tracking Issue: #71
- Start date: 2024/08/23
- End date: 2025/04/10
- Reward: N/A
Goal
Verify the safety of NonZero
in core::num
.
Assumptions
new
and get
leverage transmute_unchecked
, so verifying the safety of these methods would require verifying that transmutations are safe. This task is out of scope for this challenge (instead, it's work for Challenge 1). For this challenge, for a transmutation from type T
to type U
, it suffices to write and verify a contract that T
and U
have the same size.
You may assume that each NonZeroInner
type upholds the safety conditions of the ZeroablePrimitive
trait. Specifically, you need not verify that the integer primitives which implement ZeroablePrimitive
are valid when 0, or that transmutations to the Option
type are sound.
Success Criteria
Part 1: new
and new_unchecked
Verify the safety and correctness of NonZero::new
and NonZero::new_unchecked
.
Specifically, write and verify contracts specifying the following:
- The preconditions specified by the
SAFETY
comments are upheld. - For an input
n
:
a. ANonZero
object is created if and only if the input was nonzero.
b. The value of theNonZeroInner
object equalsn
.
Part 2: Other Uses of unsafe
Verify the safety of the following functions and methods (all located within core::num::nonzero
):
Function |
---|
max |
min |
clamp |
bitor (all 3 implementations) |
count_ones |
rotate_left |
rotate_right |
swap_bytes |
reverse_bits |
from_be |
from_le |
to_be |
to_le |
checked_mul |
saturating_mul |
unchecked_mul |
checked_pow |
saturating_pow |
neg |
checked_add |
saturating_add |
unchecked_add |
checked_next_power_of_two |
midpoint |
isqrt |
abs |
checked_abs |
overflowing_abs |
saturating_abs |
wrapping_abs |
unsigned_abs |
checked_neg |
overflowing_neg |
wrapping_neg |
from_mut |
from_mut_unchecked |
You are not required to write correctness contracts for these methods (e.g., for max
, ensuring that the result
is indeed the maximum of the inputs), but it would be great to do so!
List of UBs
In addition to any properties called out as SAFETY
comments in the source
code, all proofs must automatically ensure the absence of the following undefined behaviors ref:
- Invoking undefined behavior via compiler intrinsics.
- Reading from uninitialized memory.
- Producing an invalid value.
Note: All solutions to verification challenges need to satisfy the criteria established in the challenge book in addition to the ones listed above.
Challenge 13: Safety of CStr
- Status: Open
- Solution:
- Tracking Issue: #150
- Start date: 2024/11/04
- End date: 2025/04/10
- Reward: N/A
Goal
Verify that CStr
safely represents a borrowed reference to a null-terminated array of bytes sequences similar to
the C string representation.
Motivation
The CStr
structure is meant to be used to build safe wrappers of FFI functions that may leverage CStr::as_ptr
and the unsafe CStr::from_ptr
constructor to provide a safe interface to other consumers.
It provides safe methods to convert CStr
to a Rust &str
by performing UTF-8 validation, or into an owned CString
.
Any issue with this structure or misusage of its unsafe methods could trigger an invalid memory access, which poses a security risk for their users.
Description
The goal of this challenge is to ensure the safety of the CStr
struct implementation.
First, we need to specify a safety invariant that captures the essential safety properties that must be maintained.
Next, we should verify that all the safe, public methods respect this invariant.
For example, we can check that creating a CStr
from a byte slice with method from_bytes_with_nul
will only yield
safe values of CStr
.
Finally, for unsafe methods like from_ptr()
and from_bytes_with_nul_unchecked
, we need to specify appropriate safety contracts.
These contracts should ensure no undefined behavior occurs within the unsafe methods themselves,
and that they maintain the overall safety invariant of CStr
when called correctly.
Assumptions
- Harnesses may be bounded.
Success Criteria
-
Implement the
Invariant
trait forCStr
. -
Verify that the
CStr
safety invariant holds after calling any of the following public safe methods.
Function | Location |
---|---|
from_bytes_until_nul | core::ffi::c_str |
from_bytes_with_nul | core::ffi::c_str |
count_bytes | core::ffi::c_str |
is_empty | core::ffi::c_str |
to_bytes | core::ffi::c_str |
to_bytes_with_nul | core::ffi::c_str |
bytes | core::ffi::c_str |
to_str | core::ffi::c_str |
as_ptr | core::ffi::c_str |
- Annotate and verify the safety contracts for the following unsafe functions:
Function | Location |
---|---|
from_ptr | core::ffi::c_str |
from_bytes_with_nul_uncheked | core::ffi::c_str |
strlen | core::ffi::c_str |
- Verify that the following trait implementations for the
CStr
type are safe:
Trait | Implementation Location |
---|---|
CloneToUninit 1 | core::clone |
ops::Index<ops::RangeFrom<usize>> | core::ffi::c_str |
Unsafe functions will require safety contracts.
All proofs must automatically ensure the absence of the following undefined behaviors ref:
- Accessing (loading from or storing to) a place that is dangling or based on a misaligned pointer.
- Performing a place projection that violates the requirements of in-bounds pointer arithmetic.
- Mutating immutable bytes.
- Accessing uninitialized memory.
Note: All solutions to verification challenges need to satisfy the criteria established in the challenge book in addition to the ones listed above.
Challenge 14: Safety of Primitive Conversions
- Status: Open
- Tracking Issue: https://github.com/model-checking/verify-rust-std/issues/220
- Start date: 2024/12/15
- End date: 2025/2/28
- Prize: TBD
Goal
Verify the safety of number conversions in core::convert::num
.
There are two conversions that use unsafe code: conversion from NonZero integer to NonZero integer and conversion from floating point number to integer. All conversions use macros to implement traits for primitive types in bulk. You will need to add contracts into the macros so that contracts are generated for each implementation. As the conversions are all macro generated, it is probably a good idea to write your own macro for generating the harnesses.
Success Criteria
NonZero Conversions
Write a type invariant for core::num::NonZero
, then write harnesses for all nonzero
conversions.
Write proof contracts for each NonZero primitive conversion, listed in full below. These conversions are implemented through two macros: impl_nonzero_int_from_nonzero_int!
and impl_nonzero_int_try_from_nonzero_int!
.
For each invocation of impl_nonzero_int_from_nonzero_int!
, prove that the conversion it implements does not cause undefined behavior nor panic. For example, for impl_nonzero_int_from_nonzero_int!(u8 => u16);
, prove that calling NonZero<u16>::from(small: NonZero<u8>)
does not cause undefined behavior nor panic for an arbitrary small
that satisfies the NonZero
type invariant.
For each invocation of impl_nonzero_int_try_from_nonzero_int!
, prove that the conversion it implements does not cause undefined behavior. For example, for impl_nonzero_int_try_from_nonzero_int!(u16 => u8);
, prove that calling NonZero<u8>::try_from(value: NonZero<u16>)
does not cause undefined behavior for an arbitrary value
that satisfies the NonZero
type invariant. Additionally, prove that if the value
does not fit into the target type (e.g., value
is too large to fit into a NonZero<u8>
) that the function panics.
non-zero unsigned integer -> non-zero unsigned integer
impl_nonzero_int_from_nonzero_int!(u8 => u16);
impl_nonzero_int_from_nonzero_int!(u8 => u32);
impl_nonzero_int_from_nonzero_int!(u8 => u64);
impl_nonzero_int_from_nonzero_int!(u8 => u128);
impl_nonzero_int_from_nonzero_int!(u8 => usize);
impl_nonzero_int_from_nonzero_int!(u16 => u32);
impl_nonzero_int_from_nonzero_int!(u16 => u64);
impl_nonzero_int_from_nonzero_int!(u16 => u128);
impl_nonzero_int_from_nonzero_int!(u16 => usize);
impl_nonzero_int_from_nonzero_int!(u32 => u64);
impl_nonzero_int_from_nonzero_int!(u32 => u128);
impl_nonzero_int_from_nonzero_int!(u64 => u128);
non-zero signed integer -> non-zero signed integer
impl_nonzero_int_from_nonzero_int!(i8 => i16);
impl_nonzero_int_from_nonzero_int!(i8 => i32);
impl_nonzero_int_from_nonzero_int!(i8 => i64);
impl_nonzero_int_from_nonzero_int!(i8 => i128);
impl_nonzero_int_from_nonzero_int!(i8 => isize);
impl_nonzero_int_from_nonzero_int!(i16 => i32);
impl_nonzero_int_from_nonzero_int!(i16 => i64);
impl_nonzero_int_from_nonzero_int!(i16 => i128);
impl_nonzero_int_from_nonzero_int!(i16 => isize);
impl_nonzero_int_from_nonzero_int!(i32 => i64);
impl_nonzero_int_from_nonzero_int!(i32 => i128);
impl_nonzero_int_from_nonzero_int!(i64 => i128);
non-zero unsigned -> non-zero signed integer
impl_nonzero_int_from_nonzero_int!(u8 => i16);
impl_nonzero_int_from_nonzero_int!(u8 => i32);
impl_nonzero_int_from_nonzero_int!(u8 => i64);
impl_nonzero_int_from_nonzero_int!(u8 => i128);
impl_nonzero_int_from_nonzero_int!(u8 => isize);
impl_nonzero_int_from_nonzero_int!(u16 => i32);
impl_nonzero_int_from_nonzero_int!(u16 => i64);
impl_nonzero_int_from_nonzero_int!(u16 => i128);
impl_nonzero_int_from_nonzero_int!(u32 => i64);
impl_nonzero_int_from_nonzero_int!(u32 => i128);
impl_nonzero_int_from_nonzero_int!(u64 => i128);
There are also the fallible versions. Remember to cover both the panicking and non-panicking cases.
unsigned non-zero integer -> unsigned non-zero integer
impl_nonzero_int_try_from_nonzero_int!(u16 => u8);
impl_nonzero_int_try_from_nonzero_int!(u32 => u8, u16, usize);
impl_nonzero_int_try_from_nonzero_int!(u64 => u8, u16, u32, usize);
impl_nonzero_int_try_from_nonzero_int!(u128 => u8, u16, u32, u64, usize);
impl_nonzero_int_try_from_nonzero_int!(usize => u8, u16, u32, u64, u128);
signed non-zero integer -> signed non-zero integer
impl_nonzero_int_try_from_nonzero_int!(i16 => i8);
impl_nonzero_int_try_from_nonzero_int!(i32 => i8, i16, isize);
impl_nonzero_int_try_from_nonzero_int!(i64 => i8, i16, i32, isize);
impl_nonzero_int_try_from_nonzero_int!(i128 => i8, i16, i32, i64, isize);
impl_nonzero_int_try_from_nonzero_int!(isize => i8, i16, i32, i64, i128);
unsigned non-zero integer -> signed non-zero integer
impl_nonzero_int_try_from_nonzero_int!(u8 => i8);
impl_nonzero_int_try_from_nonzero_int!(u16 => i8, i16, isize);
impl_nonzero_int_try_from_nonzero_int!(u32 => i8, i16, i32, isize);
impl_nonzero_int_try_from_nonzero_int!(u64 => i8, i16, i32, i64, isize);
impl_nonzero_int_try_from_nonzero_int!(u128 => i8, i16, i32, i64, i128, isize);
impl_nonzero_int_try_from_nonzero_int!(usize => i8, i16, i32, i64, i128, isize);
signed non-zero integer -> unsigned non-zero integer
impl_nonzero_int_try_from_nonzero_int!(i8 => u8, u16, u32, u64, u128, usize);
impl_nonzero_int_try_from_nonzero_int!(i16 => u8, u16, u32, u64, u128, usize);
impl_nonzero_int_try_from_nonzero_int!(i32 => u8, u16, u32, u64, u128, usize);
impl_nonzero_int_try_from_nonzero_int!(i64 => u8, u16, u32, u64, u128, usize);
impl_nonzero_int_try_from_nonzero_int!(i128 => u8, u16, u32, u64, u128, usize);
impl_nonzero_int_try_from_nonzero_int!(isize => u8, u16, u32, u64, u128, usize);
Safety for Float to Int
macro_rules! impl_float_to_int {
($Float:ty => $($Int:ty),+) => {
#[unstable(feature = "convert_float_to_int", issue = "67057")]
impl private::Sealed for $Float {}
$(
#[unstable(feature = "convert_float_to_int", issue = "67057")]
impl FloatToInt<$Int> for $Float {
#[inline]
unsafe fn to_int_unchecked(self) -> $Int {
// SAFETY: the safety contract must be upheld by the caller.
unsafe { crate::intrinsics::float_to_int_unchecked(self) }
}
}
)+
}
}
The safety constraints referenced in the comments are that the input value must:
- Not be NaN
- Not be infinite
- Be representable in the return type Int, after truncating off its fractional part
These constraints are given in the documentation.
The intrinsic corresponds to the fptoui/fptosi LLVM instructions, which may be useful for reference. Prove safety for each of the following conversions:
impl_float_to_int!(f16 => u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize)
impl_float_to_int!(f32 => u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize)
impl_float_to_int!(f64 => u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize)
impl_float_to_int!(f128 => u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize)
List of UBs
In addition to any properties called out as SAFETY
comments in the source
code,
all proofs must automatically ensure the absence of the following undefined behaviors:
- Accessing (loading from or storing to) a place that is dangling or based on a misaligned pointer.
- Reading from uninitialized memory.
- Mutating immutable bytes.
- Producing an invalid value
Note: All solutions to verification challenges need to satisfy the criteria established in the challenge book in addition to the ones listed above.