ALLSTAR: Analyzing and Lifting Legacy Software To Aid Rewriting
Award last edited on: 9/10/2023

Sponsored Program
Awarding Agency
Total Award Amount
Award Phase
Solicitation Topic Code
Principal Investigator
Michael Dodds

Company Information

Galois Inc (AKA: Galois Connections Inc)

421 Southwest Sixth Avenue Suite 300
Portland, OR 97204
   (503) 626-6616
Location: Single
Congr. District: 03
County: Multnomah

Phase I

Contract Number: N6523622P0037
Start Date: 1/31/2022    Completed: 2/3/2023
Phase I year
Phase I Amount
The overall vision of the CAMDEN project is to explore the use of mechanism design as a solution to incentivize the creation of collaborative API designs for the DoD. APIs are not merely software interfaces: they enable a decentralized marketplace of services. It would be highly desirable to apply this decentralized API-driven approach to DoD missions. We believe the barriers to this vision are largely not technological: this world already exists in industry. Instead, the barriers involve the proper selection of incentives. The commercial world has had great success in applying mechanism design as a problem-solving technique: High-profile successes include the design of frequency spectrum auctions, which are constructed so that players have the incentive to reveal their true valuations of the items up for auction. For the auction designers, this accomplishes their objective of maximizing revenue. Our proposed effort consists of four interlocking research themes that comprise the technical objectives for the project. 1. Get it right in theory: understand how mechanism design works in theory for DoD API-relevant use cases. 2. Get it right in implementation: develop a software-based simulation environment for the evaluation of candidate API design mechanisms. 3. Get it right in practice: Develop simple “wargaming” scenarios with human participants who are encouraged to ‘game’ the system in order to test the ability of the mechanisms to induce the right player behaviors even when the system is perturbed and under stress. 4. Get it right in evaluation: Develop appropriate metrics for the evaluation of the efficacy of incentive mechanisms This 8-month effort aims to provide clarity on the fundamental questions and issues involved in mechanism design, evidence of the feasibility of our approach, and a roadmap for further research leading to deployable API.

Phase II

Contract Number: HR001122C0020
Start Date: 12/17/2021    Completed: 12/16/2024
Phase II year
Phase II Amount
The goal of the ALLSTAR project is to reduce vulnerabilities related to memory safety by migrating legacy C code to Rust. Memory safety bugs cause the majority of the vulnerabilities found in systems software, and Rust prevents memory safety bugs using an advanced type system that thereby eliminates the possibility of memory safety vulnerabilities. In previous work, we have built a tool, C2Rust, that automatically transpiles C code into unsafe Rust, which still contains the same memory safety bugs as the original code. Users can then manually refactor and migrate the resulting unsafe Rust to the safe subset of Rust using the C2Rust refactoring engine to perform a sequence of rewrites of the code. Although we have demonstrated that this approach can produce safe Rust code, the primary barrier to transition of C2Rust is that this requires a high degree of manual work, guided by experts. For the ALLSTAR project, we aim to automate this process as much as possible, thereby greatly reducing the expertise and manual effort required to take advantage of Rust’s memory safety guarantees. The key technical difficulty in automating the migration from unsafe C to safe Rust is inferring memory ownership patterns in code. Ownership is a key concept that Rust uses to ensure memory-safety. Every pointer or reference in safe Rust has a type that indicates whether it owns or borrows the object or objects it points to. By tracking ownership explicitly in the type system, and enforcing certain rules about how objects may be borrowed throughout program execution, the Rust compiler ensures that programs obey well-defined ownership patterns that are guaranteed to satisfy memory safety. C code, on the other hand, does not have an explicit notion of ownership, and so ownership patterns are implicit. Migrating C code to safe Rust thus requires inferring the implicit ownership patterns and converting them to explicit ownership patterns expressed in the Rust type system. The ALLSTAR project will solve the problem of inferring ownership patterns in unsafe Rust code using a novel two-part lifting algorithm to lift two different sorts of code into safe Rust. The low-level lifting algorithm lifts code whose ownership patterns map directly to safe Rust by lifting its unsafe pointers to safe Rust types that make their ownership patterns explicit. This algorithm will utilize a novel combination of dynamic analysis and type inference to infer the ownership patterns of pointers that will then be mapped to the corresponding safe Rust types. The high-level lifting algorithm identifies code fragments whose individual operations cannot be lifted to safe Rust but which overall correspond to some API that is known to be safe. The identified code fragments are then replaced by the corresponding safe APIs.