<?xml-model href='http://www.tei-c.org/release/xml/tei/custom/schema/relaxng/tei_all.rng' schematypens='http://relaxng.org/ns/structure/1.0'?><TEI xmlns="http://www.tei-c.org/ns/1.0">
	<teiHeader>
		<fileDesc>
			<titleStmt><title level='a'>RedLeaf: Towards An Operating System for Safe and Verified Firmware</title></titleStmt>
			<publicationStmt>
				<publisher></publisher>
				<date>2019 May</date>
			</publicationStmt>
			<sourceDesc>
				<bibl> 
					<idno type="par_id">10110227</idno>
					<idno type="doi">10.1145/3317550.3321449</idno>
					<title level='j'>Proceedings of the Workshop on Hot Topics in Operating Systems (HotOS)</title>
<idno></idno>
<biblScope unit="volume"></biblScope>
<biblScope unit="issue"></biblScope>					

					<author>Vikram Narayanan</author><author>Marek S. Baranowski</author><author>Leonid Ryzhyk</author><author>Zvonimir Rakamarić</author><author>Anton Burtsev</author>
				</bibl>
			</sourceDesc>
		</fileDesc>
		<profileDesc>
			<abstract><ab><![CDATA[RedLeaf is a new operating system being developed from scratch to utilize formal verification for implementing provably secure firmware. RedLeaf is developed in a safe language, Rust, and relies on automated reasoning using satisfiability modulo theories (SMT) solvers for formal verification. RedLeaf builds on two premises: (1) Rust's linear type system enables practical language safety even for systems with tightest performance and resource budgets (e.g., firmware), and (2) a combination of SMT-based reasoning and pointer discipline enforced by linear types provides a unique way to automate and simplify verification effort scaling it to the size of a small OS kernel.]]></ab></abstract>
		</profileDesc>
	</teiHeader>
	<text><body xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink">
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1">Introduction</head><p>Every modern off-the-shelf system (desktop and server) executes several layers of firmware underneath the most privileged layer of software be it an operating system (OS) or a hypervisor. On an Intel platform, firmware subsystems such as System Management Mode (SMM), Management Engine (ME) <ref type="bibr">[28]</ref>, Innovation Engine (IE) <ref type="bibr">[27]</ref>, Baseboard Management Controller (BMC) <ref type="bibr">[43]</ref>, power-management controllers (P-Unit <ref type="bibr">[29]</ref> and PMC <ref type="bibr">[59]</ref>), and likely many others, leverage hardware memory isolation and dedicated microcontrollers to run in isolation from the systems software. For example, anecdotal evidence suggests that at least four different firmware subsystems are running on the Intel Silvermont Moorefield system-on-chip along with regular cores <ref type="bibr">[58]</ref>. Some firmware subsystems have complete control over the hardware platform. For example, SMM, IE, and ME have unrestricted access to the entire memory of the system. BMC, ME, and IE provide physical-like access to the system over the network, i.e., have the capability to power cycle the machine, boot from a network drive, install system software, intercept keyboard, mouse, and video I/O, and perform direct memory access (DMA) transactions. Moreover, some firmware subsystems <ref type="bibr">[27,</ref><ref type="bibr">28]</ref> are enabled and continue execution as long as the power is connected to the machine, i.e., even if the rest of the system is powered down.</p><p>Being the most privileged part of the system, the platform firmware becomes a primary target for security attacks. A single SMM, IE, ME, or BMC vulnerability gives an attacker full control over the machine. Furthermore, the attack is virtually undetectable with existing anti-virus and forensics tools.</p><p>To make things worse, modern firmware is fundamentally insecure. The software engineering technology behind the platform firmware has remained unchanged for decades. Modern firmware is developed in a combination of low-level assembly and an unsafe programming language, namely C. (Several rare exceptions demonstrate applications of fuzzing and symbolic execution <ref type="bibr">[24,</ref><ref type="bibr">40]</ref>.) Typical firmware both adheres to multiple low-level hardware specifications and implements functionality of a minimal OS, i.e., implements multiple device drivers and sometimes even provides support for file systems and network protocols <ref type="bibr">[27,</ref><ref type="bibr">28,</ref><ref type="bibr">43]</ref>. Due to such inherent complexity, bugs and vulnerabilities are routinely introduced in the omni-privileged firmware code. Multiple attacks on platform firmware were demonstrated in recent years <ref type="bibr">[25,</ref><ref type="bibr">39,</ref><ref type="bibr">50,</ref><ref type="bibr">51,</ref><ref type="bibr">[72]</ref><ref type="bibr">[73]</ref><ref type="bibr">[74]</ref><ref type="bibr">[75]</ref>, and Intel disclosed 20 firmware vulnerabilities overall in 2018 <ref type="bibr">[1]</ref><ref type="bibr">[2]</ref><ref type="bibr">[3]</ref><ref type="bibr">[4]</ref><ref type="bibr">[5]</ref><ref type="bibr">[6]</ref><ref type="bibr">[7]</ref><ref type="bibr">[8]</ref><ref type="bibr">[9]</ref><ref type="bibr">[10]</ref><ref type="bibr">[11]</ref><ref type="bibr">[12]</ref><ref type="bibr">[13]</ref><ref type="bibr">[14]</ref><ref type="bibr">[15]</ref><ref type="bibr">[16]</ref><ref type="bibr">[17]</ref><ref type="bibr">[18]</ref><ref type="bibr">[19]</ref><ref type="bibr">[20]</ref>. Likely, this is just a tip of an iceberg. We anticipate that similar to modern operating systems that face hundreds of vulnerabilities a year, modern firmware as it exists today will likely go through a cycle of aggressive vulnerability discovery and exploitation in the next several years. Furthermore, it is unlikely that existing security mechanisms will be able to ensure the security of firmware subsystems.</p><p>We argue that ensuring the security and correctness of firmware requires a clean-slate approach. Modern attacks utilize automated bug finding tools for discovery of vulnerabilities. A promising approach to win the arms race against such attacks is to utilize a rigorous approach to program correctness.</p><p>RedLeaf is a new operating system aimed at leveraging a safe, linear-typed programming language, Rust, for developing safe and provably secure firmware. RedLeaf aims at creating an efficient execution environment that is verifiably end-to-end secure, meaning that: (1) verification covers all code that executes on the machine from the kernel and platform-specific device drivers to applications that implement firmware-specific functionality, (2) it is feasible to demonstrate equivalence to a high-level specificationimplementation of the system is indistinguishable from the high-level abstract state machine, and (3) the verified code remains fast.</p><p>RedLeaf builds on two premises: (1) Rust's linear type system enables practical language safety even for systems with the tightest performance and resource budgets, e.g., firmware, (2) a combination of SMT-based reasoning and pointer discipline enforced by linear types provides a way to automate and simplify verification effort and scale it to the size of a small operating system kernel that can run firmware subsystems. RedLeaf provides a Floyd-Hoare-style <ref type="bibr">[42,</ref><ref type="bibr">47]</ref> modular verification (i.e., based on pre-conditions, post-conditions, and loop invariants) for low-level systems that are designed to be fast and small. It achieves that by developing a new verification toolchain built on the SMACK verifier <ref type="bibr">[36,</ref><ref type="bibr">69]</ref>, Boogie intermediate verification language <ref type="bibr">[31,</ref><ref type="bibr">54]</ref>, and Z3 SMT solver <ref type="bibr">[30]</ref>.</p><p>In the past, IronClad <ref type="bibr">[46]</ref> achieved whole stack verification of non-trivial systems, but the systems incurred 100-189x slowdown. We target the same level of guarantees of wholestack verification, but with the performance of our system remaining close to the unverified unmanaged code. Specifically, our verified code will compile into low-level machine code, require no runtime, and avoid garbage collection.</p><p>We argue that unique properties of Rust's linear type system, and specifically its ability to lift the burden of resolving memory aliasing from the verifier, open a new page in the domain of practical and scalable verification. While RedLeaf is an early work in progress, we believe that our methodology and approach can be useful to enable new directions in the development of the next generation of secure and reliable systems.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2">Overview of RedLeaf</head><p>RedLeaf is a minimal operating system aimed at implementing firmware subsystems. Today, a broad range of firmware requires functionality of an operating system with support for running concurrent activities (i.e., threads of execution), interrupt handling, scheduling, memory management, and even process isolation and inter-process communication. For example, recent analysis of the Intel ME <ref type="bibr">[28]</ref> revealed that it runs a small, possibly, Minix-based microkernel that provides support for conventional process isolation and all traditional primitives of a microkernel operating system <ref type="bibr">[71]</ref>. Trusty <ref type="bibr">[32]</ref> and Little Kernel <ref type="bibr">[37]</ref> are minimal kernels used for implementing firmware of a Trusted Execution Environment (TEE) on Android devices. Firmware subsystems of Baseboard Management Controller (BMC) <ref type="bibr">[43]</ref>, numerous network switches, and recent BIOS implementations rely on the full Linux operating system as their firmware OS <ref type="bibr">[34,</ref><ref type="bibr">41,</ref><ref type="bibr">63,</ref><ref type="bibr">65]</ref>.</p><p>Furthermore, there is a growing trend motivated by both security concerns <ref type="bibr">[32,</ref><ref type="bibr">41,</ref><ref type="bibr">60]</ref> and economics of open hardware and software development to open up traditionally closed firmware subsystems. EDK II is an open source implementation of the UEFI firmware from Intel <ref type="bibr">[49]</ref>. Linux-Boot <ref type="bibr">[34]</ref> and OpenBMC <ref type="bibr">[41]</ref> are open-sourced versions of BIOS and BMC controller firmware subsystems. Started as part of the Open Compute Project <ref type="bibr">[68]</ref>, today multiple switch vendors support open bare metal switches, i.e., switches that allow execution of a third-party operating system like Linux on the switch itself <ref type="bibr">[62]</ref>. Switch vendors develop the switch hardware, and provide libraries for programming it, but leave the software stack that controls the hardware open. Multiple Linux-based switch operating systems are available <ref type="bibr">[63,</ref><ref type="bibr">65]</ref>.</p><p>RedLeaf Architecture We develop RedLeaf as a minimal operating system aimed at the needs of a diverse family of firmware subsystems. RedLeaf is designed to run as a small core kernel and a collection of language-enforced protection domains <ref type="bibr">[21,</ref><ref type="bibr">48,</ref><ref type="bibr">66]</ref> that implement kernel subsystems and specific firmware logic. Isolated kernel subsystems do not share data in RedLeaf. Instead, they rely on the linear type system to implement lightweight zero-copy communication <ref type="bibr">[21]</ref>. Whenever an object is passed from one domain to another, e.g., via a function call, the sender loses ownership of the object-the compiler enforces that it cannot reference the object in the future. This allows us to modularize the verification effort, since verifying a Rust function in general does not require reasoning or maintaining complex shape invariants about the objects on the heap not owned by it.</p><p>Rust and Linear Types RedLeaf builds on the premise that linear types are critical for creating a scalable automated verification infrastructure. In particular, Rust enforces (using its type system) a rigorous discipline for controlling of sharing and aliasing in the program heap. In a software verifier for a traditional procedural language, developers are required to provide complex program heap non-aliasing and partition invariants by writing cumbersome quantified annotations. Such annotations are complicated to come up with and write, as well as to reason about using SMT solvers. Rust's linear type system and ownership model "forces" developers to carefully think about and essentially explicitly specify their program heap sharing/non-aliasing properties early on in the development process. Our verification toolchain leverages this information to (1) remove the burden of specifying a large class of program heap invariants from the user and (2) scale up the verification by performing an efficient quantifier-and array-free encoding of the program heap (see section 3).</p><p>In contrast to previous efforts aimed at developing scalable automated verification in a verification-friendly language <ref type="bibr">[45,</ref><ref type="bibr">46]</ref>, Rust allows RedLeaf to remain fast. Historically, to implement safety, programming languages rely on managed runtime, and specifically garbage collection. Despite many advances in garbage collection, its overhead remains prohibitive for systems with tight time and space budgets. Rust, however, implements safety without garbage collection, and instead relies on a restricted ownership model enforced by its linear type system-there exists a unique reference to each live object in memory. Single ownership allows static tracking of the object lifetime and its deallocation without a garbage collector.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Related Work</head><p>In the domain of operating systems, several verified kernels have been tried in the past. Unfortunately, with no or minimal automation of proofs the cost of verifying OS code is prohibitively high. It took over 20 person-years to develop the first verified microkernel, seL4 <ref type="bibr">[53]</ref>, which is only 10,000 lines of code. Concentrating on multicore support, CertiKOS <ref type="bibr">[44]</ref> and later Xu et al. 's <ref type="bibr">[76]</ref> framework for reasoning about interrupts in the &#181;C/OS-II kernel rely on the Coq interactive theorem prover <ref type="bibr">[33]</ref> to construct proofs, yet, still taking 2 and 5.5 person-years, respectively. Both seL4 and CertiKOS verify only the core kernel and leave device drivers unverified. Hyperkernel introduces push button verification, i.e., translates LLVM intermediate representation (IR) into SMT queries, to achieve significant progress in automation of OS proofs <ref type="bibr">[61]</ref>. Yet, without explicit support from the programming language that simplifies the specification of loop invariants, only the simplest kernel, i.e., the kernel in which all code paths are finite, is amenable to the suggested verification approach.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3">Leveraging Rust for Verification</head><p>Software verification involves reasoning about program state, which typically consists of the program counter, valuations of local and global variables, and program heap that stores dynamically allocated objects and data structures. When running on an actual machine the heap is bounded, however, its size is so large that for the purpose of verification it is customary to assume it is unbounded. Hence, in theoremprover-based software verifiers it is straightforward to model the program heap using an unbounded array (i.e., map) that maps addresses into values. In practice, however, having just one large array has a detrimental impact on scalability since current state-of-the-art automatic theorem provers, namely SMT solvers, struggle in the presence of numerous array reads and writes. Hence, various approaches have been devised to split the program heap into a collection of arrays, thereby having less read/write pressure on each array. The key idea is to place dynamically allocated objects, or their parts, that cannot alias into separate arrays. To conservatively establish non-aliasing, these approaches typically leverage either type information <ref type="bibr">[26]</ref> or results of a conservative pointer analysis <ref type="bibr">[70]</ref>. Still, despite significantly improving scalability, even such memory-splitting-based approaches run out of steam when faced with programs with a lot of aliasing and intricate multi-level linked data structures.</p><p>Our main goal is to perform full functional verification of RedLeaf. Currently, performing such deep and detailed verification of even a small-sized system can only be achieved using modular reasoning that relies on the design-by-contract paradigm. This entails requiring from a developer to manually annotate their programs with procedure contracts in the form of pre-and post-conditions, and loop invariants. In an imperative language designed with verification in mind, such as Dafny <ref type="bibr">[55]</ref>, the presence of dynamic memory allocation, pointers, side-effects, and unbounded (linked) data structures entails that the most complex and painful aspect of writing annotations is describing memory aliasing and separation constraints.</p><p>In Rust, on the other hand, either alias-freedom or immutability comes for free. More specifically, if there is a mutable reference, then there is no aliasing, but a program can have any number of immutable references to an object. We next present several examples that explore to which extent the non-aliasing and immutability rules baked into Rust help with both the specification and verification processes.</p><p>Frame Example Figure <ref type="figure">1</ref> (top) gives a simple example illustrating how uncontrolled side-effects make modular verification much more complicated and involved. To be able to modularly verify the assertion in the C code on the left, we need to provide the verifier with a postcondition on foo() of the following form:  simple unbounded arrays and linked data structures such as lists. In terms of proving them, they present a major burden for SMT solvers since they always involve quantifiers, which SMT solvers often struggle with since the quantifier instantiation approach they implement is very brittle. If we encode this example in Rust, as shown on the topright in Figure <ref type="figure">1,</ref><ref type="figure"/> x would be passed as an immutable reference (i.e., x:&amp;i32 versus x:&amp;mut i32), in which case the listed frame rule could be derived automatically from the function signature. In fact, if we push this further, the frame rule (and the quantifier it brings into its SMT encoding) would not actually be needed, as we know from the function signature that the function cannot modify x; in particular, it cannot modify it even via some other alias to the same memory location. Moreover, when verifying modules written in a pure subset of Rust, there is no need to model memory as an array, since the main reason to do so for imperative languages is the possibility of aliasing. Instead, we can model the program heap as a collection of typed variables.</p><p>Aliasing Example Figure <ref type="figure">1</ref> (bottom) gives a simple example illustrating how unrestricted aliasing make modular verification much more complicated and involved. To be able to modularly verify the assertion in the C code on the left, we need to provide the verifier with two pre-conditions on bar(). The first one is obvious: requires *y == 10. However, the second one has to ensure that pointers x and y do not alias: requires x != y. Similarly to specifying frame rules, non-aliasing specifications become really complex really fast, again for example in the presence of linked data structures. For instance, if bar() would take two linked lists as input, we would often need to specify that the lists are completely disjoint, meaning that no two list elements can alias. This typically requires the introduction of quantified list reachability predicates, which are very hard to reason about. If we encode this example in Rust, as shown on the bottomright in Figure <ref type="figure">1</ref>, we can drop the second pre-condition as we know by construction that x and y cannot alias the same memory location. Also, Rust does not have dynamic memory allocation akin to malloc. Instead, we would write x = Box::new(); y = Box::new(), which would introduce two new variables to the program state. Their location in memory is irrelevant since they cannot alias each other or any other variables. Hence, in the SMT encoding of Rust, we could use scalar variables to capture x and y, instead of the more expensive memory maps used in the traditional encodings of imperative languages.</p><p>To summarize, it is well-accepted that pointer separation and non-aliasing is really hard to both specify and reason about, especially once one starts introducing linked data structures such as lists and trees. Separation logic helps with that to some extent, since it enables focusing only on the parts of the heap that are being touched by a particular function. Once we ensure that every variable is disjoint from every other variable (i.e., no two variables can alias), as in Rust, we do not need any more to use arrays to model the program heap/memory. In other words, the semantics of pure Rust can be defined without introducing a heap (typed or untyped). This enables us to encode many interesting verification problems to SMT without arrays or quantifiers, thereby greatly improving the scalability and performance of the verifier. In general, clearly there is no way around having an unbounded program heap if we want to model real programs precisely, such as programs that allocate unbounded vectors or linked data structures. However, this program heap can be much better structured within a Rust verifier than in verifiers for conventional languages. For example, instead of using an untyped array of bytes to represent program heap, we can leverage typed lists and maps provided by SMT solvers, which are both unbounded, but are much more efficient. More specifically, the state of a Rust program is a set of variables, where each variable describes a potentially unbounded tree of typed objects. It is a tree because there is no aliasing and it is potentially unbounded due to the existence of recursive data structures.</p><p>Rust Verifier As a part of RedLeaf's verification effort, we work on creating a rigorous (i.e., sound) modular Rust verifier based on SMT solving. Figure <ref type="figure">2</ref> outlines the toolflow of the verifier. We leverage the mid-level IR (MIR) <ref type="bibr">[64]</ref> format as the starting point for our translation into Boogie <ref type="bibr">[22]</ref>. MIR is a simple core representation of Rust programs that compiles away many of the complexities of Rust. For example, all of the Rust control-flow-related keywords, such as loop, break, and continue, are compiled away into simple goto statements supported by MIR. Internally, MIR is represented as a controlflow graph, which also makes it suitable to be the verification target. Given that MIR contains only a very limited number of language primitives, building a translator into Boogie is a modest development effort. At the same time, MIR makes all types explicit and includes full type information, since it gets constructed after all the Rust type-checking is already done. Hence, the encoding of the program heap can be performed much more efficiently, as we already described. Finally, at the MIR level, program annotations are easier to parse and translate into Boogie compared to translating from LLVM-IR.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4">Verification of the Core Kernel</head><p>We approach verification of the RedLeaf kernel and application domains using modular assume-guarantee Floyd-Hoarestyle reasoning <ref type="bibr">[42,</ref><ref type="bibr">47]</ref>. Specifically, we annotate Rust programs, in particular functions and loops, with predicates about program state in the form of pre-conditions, postconditions, and loop invariants. Then, the verification process can modularly discharge proofs for each function in #[ensures="(x.len() == old(x).len()) &amp;&amp; (forall i,j in 0..x.len(): i&lt;=j ==&gt; x[i] &lt;= x[j]) &amp;&amp; (forall i in 0..x.len(): exists j in 0..x.len():</p><p>x[i] == old(x)[j])"] fn sort(x: &amp;mut Vec&lt;i32&gt;) { // ... Code to sort the vector ... } isolation, thereby allowing for the full-functional verification process to scale to operating-system-size programs. For example, the Rust function in Figure <ref type="figure">3</ref> is annotated with a post-condition about the program state, encoded as a function attribute. The first conjunct ensures that the vector's length does not change, the second ensures that the vector is sorted in the end of the function, and finally the third ensures that every value in the sorted vector is present in the unsorted input vector.</p><p>If this Rust code is appropriately translated into a Boogie program <ref type="bibr">[31,</ref><ref type="bibr">54]</ref>, the Boogie verifier <ref type="bibr">[23]</ref> can automatically verify that the post-condition holds (for all possible inputs x) as long as the code to sort the vector is correct. Boogie is sound, i.e., it will never prove an incorrect program, but it will often fail to automatically recognize valid programs as correct. Hence, the majority of the verification effort goes into developing proper pre-conditions, post-conditions, and loop invariants inside every subsystem to help Boogie complete the verification.</p><p>Specifications We develop a simple language for writing specifications as an abstract description of the desired system behavior, e.g., we allow specifying how the state of the kernel that is modeled as a state machine advances with every system call. The verification process then ensures that the system implementation meets this high-level description. Specifications are a part of the trusted computing base, so it is important to develop them correctly.</p><p>Unsafe Rust Extensions While recent work on implementing an embedded operating system in Rust <ref type="bibr">[38,</ref><ref type="bibr">56]</ref> develops techniques for minimizing the amount of unsafe Rust code in the OS kernel, development in a pure safe code is simply impossible, e.g., all code that accesses raw memorymapped machine state, e.g., DMA ring buffers, requires an unsafe cast <ref type="bibr">[38]</ref>.</p><p>The RustBelt project provides a guide for ensuring that unsafe code is encapsulated within a safe interface <ref type="bibr">[52]</ref>. Specifically, by modeling the semantics of the type system, Rust-Belt's rules can be used to determine if an unsafe program can have a safe encapsulation. It does so by generating a code contract specifying what conditions must be true for the library to be safely accessed. The rules given in Rust-Belt only cover reasoning about unsafe pointers generated from within the Rust programming language. In RedLeaf we extend the rule system to model DMA and other hardware level pointers. This allows us to produce the appropriate code contract to ensure safety. Then a verifier can check the code contract, proving the library is safe.</p><p>Memory Allocation Rust programs allocate memory on the stack and on the heap. Both allocation mechanisms require extra steps to be safe. The program is "stack safe" if the stack pointer never points outside of allocated memory specifically dedicated to the stack. In Rust the violation of this property is possible through a stack overflow, which happens when the stack does not have enough space to store the new stack frame. Currently, Rust implements a dynamic check that ensures that there is always enough space on the stack for a function to proceed. In RedLeaf we allocate the new stack from the verified dynamic memory allocator (heap allocator).</p><p>Heap allocation requires dynamic memory management. In RedLeaf we adapt one of the existing verified memory allocators. Specifically, we adapt the memb from Contiki <ref type="bibr">[57]</ref>, a popular open-source operating system for IoT. Memb's specifications were fully proven automatically using Frama-C <ref type="bibr">[57]</ref>. While the existing and verified Memb allocator allows us to get the system running, in the future we plan to investigate how we can develop and verify a more sophisticated memory allocator implemented in Rust.</p><p>Threads and Context Switching Executing on bare metal, RedLeaf has to provide support for creating threads of execution and context switching between them. A minimal thread is represented by a thread structure that stores run-time state of the thread (i.e., callee saved registers) and a pointer to the thread's stack. To implement support for creating a new thread we allocate a new thread data structure and stack using the verified memory allocator.</p><p>To switch between threads we implement and verify a small assembly routine that saves the runtime state of the process, restores the state of the next process by loading its runtime state in the CPU registers, and switches the stack between the old and the new thread. The entire context switch routine is only 13 machine instructions on 32bit x86. However, the code for performing a context switch is necessarily architecture specific, and is written in assembly. In order to verify the correctness of the context switch code, we need to model the effects of the machine instructions. We rely on McSema <ref type="bibr">[35]</ref>, which translates native machine code into LLVM bitcode. As the Rust compiler emits LLVM bytecode, we inline the translated context switch routine directly into the emitted bytecode.</p><p>Interrupts RedLeaf disables interrupts while running inside the kernel. Interrupt handlers are inherently unsafe as they preempt execution of the code asynchronously leaving memory in a possibly inconsistent state. By disabling the interrupts, we can reason about the code path through the kernel atomically (i.e., we rule out interleaved execution, and allow the verifier to reason about each "system call" from start to finish and independent from the rest of the system). As a consequence, RedLeaf disables preemption of a thread inside the core kernel. The path through the kernel is short, hence executing it with preemption disabled is actually in many cases faster than fine-grained locking <ref type="bibr">[67]</ref>. Interrupts are delivered when the kernel returns from the system call. The interrupt handler again runs atomically.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5">Conclusions</head><p>RedLeaf brings together results from the domains of verification, programming languages, and systems to enable new methodology for developing verified systems software. To achieve complete verification of a small operating system aimed at the development of firmware subsystems, we propose a set of new tools, a collection of techniques and engineering principles, and a methodology focused on scalable development of verified systems.</p></div></body>
		</text>
</TEI>
