Towards Porting Operating Systems with Program Synthesis

Jingmei Hu, Eric Lu, David A. Holland, Ming Kawaguchi, Stephen Chong, Margo Seltzer

TL;DR

This paper presents "Aquarium," a novel system that uses program synthesis to automatically generate machine-dependent operating system (OS) code. By leveraging domain-specific languages for OS functionality and machine architectures, Aquarium significantly reduces the effort required to port OSes to new hardware, a growing challenge in the post-Moore's Law era.

What Problem Does This Paper Address?

The rapid diversification of hardware architectures, coupled with the slowing of Moore's Law, has made porting operating systems (OS) to new machines an increasingly critical and expensive task. Traditionally, this involves significant manual effort by experienced kernel developers to reimplement machine-dependent code, which is time-consuming and prone to errors. The authors aim to automate this process by using program synthesis to generate this low-level assembly code from high-level specifications.

Methods

The core of the Aquarium system lies in its two domain-specific languages:

  • Alewife: A language for writing machine-independent specifications of machine-dependent OS functionality. It abstracts away hardware details, allowing OS developers to focus on the intended behavior.
  • Cassiopea: A language for describing instruction set architecture (ISA) semantics. This allows computer architects to formally define how a machine operates at the assembly level.

The workflow involves:

  1. An OS developer writes an Alewife specification for a piece of OS functionality.
  2. A computer architect provides a Cassiopea description of the target architecture.
  3. An "Alewife compiler" uses these inputs, along with "lowering files" (which map Alewife abstractions to machine-specific details), to generate a machine-dependent specification.
  4. The Cassiopea synthesis engine then uses this machine-dependent specification and the Cassiopea machine description to synthesize assembly code. This process includes verification to ensure correctness.

The system also incorporates several optimizations to improve the scalability of assembly synthesis, including read/write constraints, state gating, dependency constraints, and rule-based decomposition.

Datasets

The authors evaluated their system using:

  • Two pre-existing operating systems: Barrelfish and OS/161.
  • Four real hardware architectures: 32-bit MIPS, 32-bit ARM, 32-bit RISC-V, and x86_64.

They synthesized 140 OS components in total from these sources.

Key Insights and Ideas

  • Decoupling Expertise: The system effectively separates the concerns of OS developers (specifying functionality) and computer architects (describing hardware), enabling them to work with specialized languages.
  • Abstraction is Key: Alewife's ability to abstract machine-dependent details is crucial for writing reusable specifications, making the porting effort proportional to the number of OSes and architectures (N+M) rather than their product (N*M).
  • Synthesis for Assembly is Hard, But Feasible: The paper demonstrates that program synthesis, while challenging for low-level assembly code due to large search spaces, is indeed feasible for generating correct OS components.
  • Optimizations are Critical: The significant speedups achieved by optimizations highlight their necessity for making synthesis practical for complex code.
  • Formal Specifications as a Bridge: The use of formal languages like Alewife and Cassiopea provides a precise and verifiable bridge between high-level OS logic and low-level hardware implementation.

Key Results

  • Successful Synthesis: The system successfully synthesized 140 OS components from two OSes across four architectures.
  • Efficiency Gains: The optimizations improved synthesis performance by an average of 21x, with one case showing a 1380x speedup.
  • Reduced Porting Effort: The authors estimate that the incremental cost of a new port is significantly reduced, with a ratio of manual lowering files to synthesized code lines of 0.175.
  • Verification: The synthesis engine also verifies hand-written assembly code, demonstrating its utility for validation.
  • Scalability: While not fully solved, the optimizations significantly improve scalability, with no timeouts observed within a half-hour limit.

Limitations and Future Work

  • Scalability: While improved, synthesis still faces scalability challenges for very long assembly code sequences.
  • Machine-Specific Code: Alewife struggles with highly machine-specific code that doesn't map well to machine-independent abstractions.
  • Concurrency and Time: The current system does not model concurrency or real-time aspects, limiting its applicability to hard real-time OSes.
  • Security: The system does not address security vulnerabilities arising from microarchitectural details (e.g., Spectre, Meltdown).
  • Future Work: The authors suggest exploring ways to reuse existing implementations, improve the automation of lowering files, develop better declarative description languages, and extend the system to handle concurrency and time-sensitive code. They also propose integrating security-related constraints into the synthesis process.

Summary updated

Abstract

The end of Moore’s Law has ushered in a diversity of hardware not seen in decades. Operating system (OS) (and system software) portability is accordingly becoming increasingly critical. Simultaneously, there has been tremendous progress in program synthesis. We set out to explore the feasibility of using modern program synthesis to generate the machine-dependent parts of an operating system. Our ultimate goal is to generate new ports automatically from descriptions of new machines. One of the issues involved is writing specifications, both for machine-dependent operating system functionality and for instruction set architectures. We designed two domain-specific languages: Alewife for machine-independent specifications of machine-dependent operating system functionality and Cassiopea for describing instruction set architecture semantics. Automated porting also requires an implementation. We developed a toolchain that, given an Alewife specification and a Cassiopea machine description, specializes the machine-independent specification to the target instruction set architecture and synthesizes an implementation in assembly language with a customized symbolic execution engine. Using this approach, we demonstrate the successful synthesis of a total of 140 OS components from two pre-existing OSes for four real hardware platforms. We also developed several optimization methods for OS-related assembly synthesis to improve scalability. The effectiveness of our languages and ability to synthesize code for all 140 specifications is evidence of the feasibility of program synthesis for machine-dependent OS code. However, many research challenges remain; we also discuss the benefits and limitations of our synthesis-based approach to automated OS porting.
BibTeX
@article{hu2022towards,
  author = {Jingmei Hu and Eric Lu and David A. Holland and Ming Kawaguchi and Stephen Chong and Margo Seltzer},
  title = {{Towards Porting Operating Systems with Program Synthesis}},
  journal = {ACM Transactions on Programming Languages and Systems},
  year = {2022},
  doi = {10.1145/3563943},
}
Figure