Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add mir_mux_values command for muxing two MIR values #2000

Closed
RyanGlScott opened this issue Dec 19, 2023 · 0 comments · Fixed by #2039
Closed

Add mir_mux_values command for muxing two MIR values #2000

RyanGlScott opened this issue Dec 19, 2023 · 0 comments · Fixed by #2039
Labels
subsystem: crucible-mir Issues related to Rust verification with crucible-mir and/or mir-json type: enhancement Issues describing an improvement to an existing feature or capability

Comments

@RyanGlScott
Copy link
Contributor

RyanGlScott commented Dec 19, 2023

Motivation: Currently, it is not possible to embed MIR struct or enum values into Cryptol. This makes it awkward or impossible to write certain SAW specifications. For instance, consider this Rust function:

pub fn increment(count: u32) -> Result<u32, Error> {
    if count < MAX {
        Ok(count+1)
    } else {
        Err(Overflow)
    }
}

How would you write a SAW spec for increment that works for all possible values of count? Sadly, you can't. There is no way to construct mir_return mv statement such that mv properly takes the count < MAX condition into account. The only way to do make this work would be to write two separate specs for increment: one where count < MAX and the spec always returns Ok, and another where count == MAX and the spec always returns Err. Not terribly satisfying.

We do want to support embedding structs (#1976) and enums (GaloisInc/cryptol#1588) into Cryptol someday. This will require a fair bit of work to achieve, however. In the mean time, it would be helpful to have some kind of solution to the problem above, even if it isn't as generic as Cryptol would be.

Solution: I propose adding the following command to SAW:

mir_mux_values : Term -> MIRValue -> MIRValue -> MIRSetup MIRValue

This command can be thought of as a particular form of if expression. If the condition (represented by the Term) holds, then return the first MIRValue argument. Otherwise, return the second MIRValue argument. The reason that the word "mux" is in the command's name is because the Term might conceivably be symbolic, in which case it would be necessary to perform a symbolic branch (i.e., a mux) of the two MIRValue arguments.

Using mir_mux_value, one could write a comprehensive spec for increment above like so:

let error_adt = mir_find_adt m "Error" [];
let result_adt = mir_find_adt m "Result" [mir_u32, error_adt];

let increment_spec = do {
  count <- mir_fresh_var "count" mir_u32;
  
  mir_execute_func [mir_term count];
  
  let ok  = mir_enum_value result_adt "Ok" [mir_term {{ count + 1 }}];
  let err = mir_enum_value result_adt "Err" [mir_enum_value error_adt "Overflow" []];
  res <- mir_mux_values {{ count < (2^^32 - 1) }} ok err;
  mir_return res;
};

This should be relatively straightforward to implement under the hood, as a use of mir_mux_value would translate to something akin to Crucible's muxRegForType function.

@RyanGlScott RyanGlScott added type: enhancement Issues describing an improvement to an existing feature or capability subsystem: crucible-mir Issues related to Rust verification with crucible-mir and/or mir-json labels Dec 19, 2023
@RyanGlScott RyanGlScott changed the title Add mir_merge_values command for merging two MIR values together Add mir_mux_values command for muxing two MIR values Mar 6, 2024
RyanGlScott added a commit that referenced this issue Mar 6, 2024
RyanGlScott added a commit that referenced this issue Mar 19, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
subsystem: crucible-mir Issues related to Rust verification with crucible-mir and/or mir-json type: enhancement Issues describing an improvement to an existing feature or capability
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant