GaloisInc / crucible

Crucible is a library for symbolic simulation of imperative programs
629 stars 42 forks source link

`crucible-mir`: Allow any value to be partially initialized #1109

Open RyanGlScott opened 11 months ago

RyanGlScott commented 11 months ago

Currently, crucible-mir uses the following conventions for translating structs and tuples into RegValues:

Despite the fact that tuples and structs are conceptually quite similar, they use rather different StructRepr conventions. I propose to simplify things by making both tuples and structs use the StructRepr [MaybeRepr t_1, ..., MaybeRepr t_n]—that is, we should no longer use canInitialize. I have two motivations for this:

  1. This makes the treatment of tuples and structs much more uniform throughout the code.
  2. In SAW, it is convenient to be able to have tuple and struct values with uninitialized fields. Notably, this is convenient to use for SAW overrides, as we want to invalidate mutable allocations used in an override after it has been applied to ensure that they are used in a sound manner. With the StructRepr [MaybeRepr t_1, ..., MaybeRepr t_n] convention, created one of these structs is as simple as Empty :> Unassigned :> ... :> Unassigned.

    An alternative would be to create fresh symbolic values for fields that canInitialize returns True on. (This is the approach taken by crucible-mir-comp here.) I'm not as fond of this approach, however, as it has the disadvantage that if a user underspecifies the value that a mutable allocation points to, their mistake will likely go unnoticed until simulation is finished. On the other hand, reading from an Unassigned value will immediately error during simulation, which means that a user is more likely to notice the mistake.

RyanGlScott commented 10 months ago

Upon further discussion with @spernsteiner and @andreistefanescu, we've come to the conclusion that in the long-term, it would be convenient to allow partial initialization of any value, not just struct fields. This would allow us to do the following:

  1. Partial initialization of static items.
  2. Invalidating memory of any type in a SAW compositional override.
  3. Verifying unsafe code involving MaybeUninit.

This would likely require the same plan as above: use MaybeRepr in more places. I'll edit the title of this issue to reflect the more general goal.