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

SAW handles calls to the same unint function as separate functions #192

Closed
TomMD opened this issue Apr 21, 2017 · 2 comments
Closed

SAW handles calls to the same unint function as separate functions #192

TomMD opened this issue Apr 21, 2017 · 2 comments

Comments

@TomMD
Copy link
Contributor

TomMD commented Apr 21, 2017

Consider the C code that says g(x)-g(x) == 0. (N.B. simpler claims such as g x = g x also exhibit the same issue as shown below)

extern int g(int);
int test(int x) { return ((g(x) - g(x)) == 0); }

Using the saw script:

v1 <- llvm_load_module "the.bc";
let v2 =
    do {
        v3 <- llvm_var "args[0]" (llvm_int 32);
        llvm_return_arbitrary;
        llvm_no_simulate;
    };
v4 <- llvm_verify v1 "g" [] v2;
let v5 =
    do {
        v6 <- llvm_var "args[0]" (llvm_int 32);
        llvm_verify_tactic abc;
        llvm_return {{1 : [32]}};
    };
v7 <- llvm_verify v1 "test" [v4] v5;

The clang and saw commands:

clang -c -emit-llvm the.c -o the.bc && saw the.saw

The result:

Loading module Cryptol
Loading file "/private/tmp/the.saw"
WARNING: skipping simulation of @g
When verifying @test:
Proof of return value failed.
Counterexample:
  lss__return_g: 4294967295
  lss__return_g: 0
return value
Encountered:  0
Expected:     1
saw: user error ("llvm_verify" (/private/tmp/the.saw:15:7):
Proof failed.)

As the title says, I believe the two separate calls to g are being treated as separate uninterpreted functions. I have not examined what is being delivered to the solver (is there a flag for that?).

@atomb
Copy link
Contributor

atomb commented Apr 24, 2017

Perhaps it's something that needs to be better documented, but the behavior of llvm_return_arbitrary isn't exactly the same as an uninterpreted function. It's intended especially to be used in cases where we don't know, don't care, or can't even refer to the mechanism by which the return value is derived (as might be the case for I/O functions). So we don't require that the user has specified all possible inputs to the function, and therefore we can't guarantee that the real code will always return the same result given the same actual parameters.

To treat g as being modeled by an uninterpreted function of its argument, you could use llvm_return {{ f v3 }}, where f is some function that either has no definition or an ignored definition. Then you can use unint_z3 ["f"] as the verification tactic to indicate that f should be treated as uninterpreted.

@TomMD
Copy link
Contributor Author

TomMD commented Apr 24, 2017

Thanks!

@TomMD TomMD closed this as completed Apr 24, 2017
brianhuffman pushed a commit that referenced this issue Apr 26, 2021
In the previous setup, the additional imports to append to the preamble were
added manually and not part of the translation configuration.  This makes it so
that those can be specified in the configuration.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants