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

Make summarize_verification report whether definitions depend on unsafe primitives or axioms (e.g., fix) #2088

Open
RyanGlScott opened this issue Aug 13, 2024 · 0 comments
Labels
type: feature request Issues requesting a new feature or capability unsoundness Issues that can lead to unsoundness or false verification
Milestone

Comments

@RyanGlScott
Copy link
Contributor

RyanGlScott commented Aug 13, 2024

I propose that we extend the summarize_verification command such that it lists any unsafe primitives or axioms that a proof uses. The particular use case I have in mind is reporting whether any proofs depend on the SAWCore fix function, which has the potential to introduce unsoundness if wielded improperly. For example, here is an example of a proof of False (relying on fix), as well a use of summarize_verification afterwards:

// test.saw
enable_experimental;

let f = parse_core "fix (EqTrue False) (id (EqTrue False))";
f_thm <- prove_core (goal_exact f) "EqTrue False";

summarize_verification;

SAW's current output is:

$ ~/Software/saw-1.1/bin/saw test.saw
[13:32:51.593] Loading file "/home/ryanscott/Documents/Hacking/SAW/test.saw"


# Theorems Proved or Assumed

* Theorem:
~~~~
  EqTrue False
~~~~

This shows a proof of False, but it doesn't include the very important caveat that it relies on the unsafe fix primitive. This is especially important when you consider that one can introduce fix implicitly by writing recursive Cryptol definitions. (For example, let {{ r = ~r : Bit }}; gets translated to a SAWCore definition involving fix behind the scenes.) Inspired by Coq's Print Assumptions command, I propose that we extend the output so that it looks something like this:

# Theorems Proved or Assumed

* Theorem:
~~~~
  EqTrue False

Depends on the following unsafe primitives or axioms:
* fix
~~~~

Another axiom that would be worth reporting here is unsafeAssert.

We will need to think a bit about which primitives or axioms should count as "unsafe" in this context. The SAWCore prelude defines many primitives and axioms that aren't really unsafe, but rather left undefined so that they can be overridden with more efficient implementations (e.g., boolEq). It might be overwhelming to include every single primitive and axiom in the list of output, so perhaps we should omit things like boolEq (or only print them if the user specifically requests them).

@RyanGlScott RyanGlScott added type: enhancement Issues describing an improvement to an existing feature or capability type: feature request Issues requesting a new feature or capability labels Aug 13, 2024
@sauclovian-g sauclovian-g added unsoundness Issues that can lead to unsoundness or false verification and removed type: enhancement Issues describing an improvement to an existing feature or capability labels Nov 8, 2024
@sauclovian-g sauclovian-g added this to the 2025T1 milestone Nov 8, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
type: feature request Issues requesting a new feature or capability unsoundness Issues that can lead to unsoundness or false verification
Projects
None yet
Development

No branches or pull requests

2 participants