yices proof fails with "Unexpected non-success response"

[brianhuffman]

This example below is from GaloisInc/cryptol#444. (Sorry I haven't converted it to a Haskell/SBV example.) Basically, yices fails if you send it a value raised to an exponent greater than 2^31-1, and SBV doesn't handle the failure in a nice way.

Cryptol> :set prover=yices
Cryptol> :prove \(x:[32]) -> x!0 ==> x * (x ^^ -1) == 1

SBV error:

*** Data.SBV: Unexpected non-success response from Yices:
***
***    Sent      : (define-fun s64 () (_ BitVec 32) (bvmul s63 s63))
***    Expected  : success
***    Received  : (error "at line 71, column 35: in bvmul: maximal polynomial degree exceeded")
***    Exit code : ExitSuccess
***
***    Executable: /Users/huffman/.bin/yices-smt2
***    Options   : --incremental
***
*** Failed to establish solver context. Running in debug mode might provide
*** more information. Please report this as an issue!

[LeventErkok]

It feels to me like SBV is handling the failure in quite a nice way actually :-)

What would you have SBV do in this case? I'm not sure how to recover from something like this.

[brianhuffman]

I wouldn't call it "nice": it calls the Haskell error function with a message that says "Please report this as an issue!"

It would be nicer if instead of calling error, it returned an Unknown response, like it does with z3:

Cryptol> :set prover=z3
Cryptol> :prove \(x:[26]) -> x!0 ==> x * (x ^^ -1) == 1
Unknown.
  Reason: Overflow encountered when expanding vector
(Total Elapsed Time: 34.737s, using Z3)

[LeventErkok]

I see. Currently, SBV will say Unknown if it gets to issue check-sat and the solver actually does return an unknown result. This seems safe.

When the solver actually returns error in response to anything we send (regardless whether it's a check-sat or not), then we throw an exception. Because we really don't know what happened. For instance, SBV can be sending down complete garbage (i.e., syntactically incorrect line); and we would like to know that.

This is what's happening here. Z3 is nice enough to wait and tell you unknown; but yices is eager and simply chokes. I don't think either behavior is wrong, though obviously they are different.

It seems only way to distinguish would be to actually read the "error" message sent back and do some analysis on whether it can be turned into "unknown". But that seems fragile at best, and really not in the spirit of the interface. If we get an error, then it's something to worry about.

I'm not sure how else to proceed here; if we start assigning semantics to error messages from individual solvers, that'll likely lead to a whole can of worms down the road.

[brianhuffman]

Ok, I see now that we shouldn't conflate "error" and "unknown" responses; they mean different things.

But I would really prefer the error response to be handled by some means other than the Haskell error function. I see that the SMTResult datatype actually has a ProofError constructor; why don't you use that?

With error, I have to install an exception handler in the IO monad to catch it, and it's hard to be sure I won't accidentally catch panics or other uses of error that come from different sources.

[LeventErkok]

That is a good point; we should be able to make better use of ProofError.

Can you create a direct test case in SBV to exhibit this behavior? I'll see what I can do!

[LeventErkok]

@brianhuffman On second thought, this unfortunately doesn't really work.

Ever since we moved to the "query" mode of operation, the user is allowed to send arbitrary commands down to the solver. And the solver can respond back error for any of them. ProofError can only reliably be returned after a check-sat call, to make the types work out as they currently are. We would have to change the return type of every operation to allow for the solver responding with error and have the user peel out this explicitly.

That sounds very onerous, and I'm not sure if it's worth the complexity.

Maybe there's another solution to tell Cryptol it was the solver returning an error instead of some other source. I'm open to ideas.

[LeventErkok]

Perhaps a compromise would be to throw a specific exception if we get an "error" back from the solver, instead of calling error. Something like SMTSolverError or some such. That way Cryptol can catch that particular exception and ignore others to percolate. Would that serve the purpose?

[brianhuffman]

Yes, that would be perfect. You should make sure to use Control.Exception.throwIO rather than throw, as suggested by the documentation: "The throwIO variant should be used in preference to throw to raise an exception within the IO monad because it guarantees ordering with respect to other IO operations, whereas throw does not." (afaik error s is basically throw (ErrorCall s))

[LeventErkok]

@brianhuffman I was just looking at this again, and I'm actually getting a segmentation-fault from Z3 with this query. (My Z3 version is quite fresh.) I'm guessing you must be using a rather old version of Z3? Perhaps that should be reported to the Z3 folks separately.

[brianhuffman]

I'm using z3 version 4.5.0, which I understand is the latest release.

For reference, here is the generated smt file, which produces an "unknown" response when I give it to z3:

; Automatically created by SBV on 2017-11-22 09:57:46.80188 PST
(set-option :smtlib2_compliant true)
(set-option :diagnostic-output-channel "stdout")
(set-option :produce-models true)
(set-logic QF_BV)
; --- uninterpreted sorts ---
; --- literal constants ---
(define-fun s_2 () Bool false)
(define-fun s_1 () Bool true)
(define-fun s2 () (_ BitVec 1) #b0)
(define-fun s55 () (_ BitVec 26) #b00000000000000000000000001)
; --- skolem constants ---
(declare-fun s0 () (_ BitVec 26))
; --- constant tables ---
; --- skolemized tables ---
; --- arrays ---
; --- uninterpreted constants ---
; --- user given axioms ---
; --- formula ---
(define-fun s1 () (_ BitVec 1) ((_ extract 0 0) s0))
(define-fun s3 () Bool (distinct s1 s2))
(define-fun s4 () (_ BitVec 26) (bvmul s0 s0))
(define-fun s5 () (_ BitVec 26) (bvmul s0 s4))
(define-fun s6 () (_ BitVec 26) (bvmul s5 s5))
(define-fun s7 () (_ BitVec 26) (bvmul s0 s6))
(define-fun s8 () (_ BitVec 26) (bvmul s7 s7))
(define-fun s9 () (_ BitVec 26) (bvmul s0 s8))
(define-fun s10 () (_ BitVec 26) (bvmul s9 s9))
(define-fun s11 () (_ BitVec 26) (bvmul s0 s10))
(define-fun s12 () (_ BitVec 26) (bvmul s11 s11))
(define-fun s13 () (_ BitVec 26) (bvmul s0 s12))
(define-fun s14 () (_ BitVec 26) (bvmul s13 s13))
(define-fun s15 () (_ BitVec 26) (bvmul s0 s14))
(define-fun s16 () (_ BitVec 26) (bvmul s15 s15))
(define-fun s17 () (_ BitVec 26) (bvmul s0 s16))
(define-fun s18 () (_ BitVec 26) (bvmul s17 s17))
(define-fun s19 () (_ BitVec 26) (bvmul s0 s18))
(define-fun s20 () (_ BitVec 26) (bvmul s19 s19))
(define-fun s21 () (_ BitVec 26) (bvmul s0 s20))
(define-fun s22 () (_ BitVec 26) (bvmul s21 s21))
(define-fun s23 () (_ BitVec 26) (bvmul s0 s22))
(define-fun s24 () (_ BitVec 26) (bvmul s23 s23))
(define-fun s25 () (_ BitVec 26) (bvmul s0 s24))
(define-fun s26 () (_ BitVec 26) (bvmul s25 s25))
(define-fun s27 () (_ BitVec 26) (bvmul s0 s26))
(define-fun s28 () (_ BitVec 26) (bvmul s27 s27))
(define-fun s29 () (_ BitVec 26) (bvmul s0 s28))
(define-fun s30 () (_ BitVec 26) (bvmul s29 s29))
(define-fun s31 () (_ BitVec 26) (bvmul s0 s30))
(define-fun s32 () (_ BitVec 26) (bvmul s31 s31))
(define-fun s33 () (_ BitVec 26) (bvmul s0 s32))
(define-fun s34 () (_ BitVec 26) (bvmul s33 s33))
(define-fun s35 () (_ BitVec 26) (bvmul s0 s34))
(define-fun s36 () (_ BitVec 26) (bvmul s35 s35))
(define-fun s37 () (_ BitVec 26) (bvmul s0 s36))
(define-fun s38 () (_ BitVec 26) (bvmul s37 s37))
(define-fun s39 () (_ BitVec 26) (bvmul s0 s38))
(define-fun s40 () (_ BitVec 26) (bvmul s39 s39))
(define-fun s41 () (_ BitVec 26) (bvmul s0 s40))
(define-fun s42 () (_ BitVec 26) (bvmul s41 s41))
(define-fun s43 () (_ BitVec 26) (bvmul s0 s42))
(define-fun s44 () (_ BitVec 26) (bvmul s43 s43))
(define-fun s45 () (_ BitVec 26) (bvmul s0 s44))
(define-fun s46 () (_ BitVec 26) (bvmul s45 s45))
(define-fun s47 () (_ BitVec 26) (bvmul s0 s46))
(define-fun s48 () (_ BitVec 26) (bvmul s47 s47))
(define-fun s49 () (_ BitVec 26) (bvmul s0 s48))
(define-fun s50 () (_ BitVec 26) (bvmul s49 s49))
(define-fun s51 () (_ BitVec 26) (bvmul s0 s50))
(define-fun s52 () (_ BitVec 26) (bvmul s51 s51))
(define-fun s53 () (_ BitVec 26) (bvmul s0 s52))
(define-fun s54 () (_ BitVec 26) (bvmul s0 s53))
(define-fun s56 () Bool (= s54 s55))
(define-fun s57 () Bool (ite s3 s56 s_1))
(assert (not s57))
(check-sat)

[LeventErkok]

@brianhuffman Interesting. By looking at the generated SMT-Lib, this one seems to be using 26-bits only. (Not 32 as in the original.)

What happens if you try with 32-bits?

[brianhuffman]

26 bits is the smallest size at which z3 fails, and it is the same size I used in my original z3 example.

I just tried z3 with 32 bits; in Cryptol I get

Cryptol> :prove \(x:[32]) -> x!0 ==> x * (x ^^ -1) == 1

SBV error:

*** Error     : fd:15: hGetLine: end of file
*** Executable: /Users/huffman/.bin/z3
*** Options   : -nw -in -smt2
*** Request   : (check-sat)
***
*** Giving up!

Up to size 28 I get an "unknown" response just like with size 26, but with 29 and above I get the "Giving up!" response (which I guess signifies a segfault).

[LeventErkok]

That makes sense. The fd:15: hGetLine: end of file is the tell-tale sign of seg-fault: The pipe disappears when the solver crashes.

[LeventErkok]

@brianhuffman Finally got around to implementing this. SBV will now throwIO if the solver ever responds with error. It'll throw SMTException, defined thusly:

sbv/Data/SBV/SMT/Utils.hs

Lines 135 to 146 in 190fa05

	data SMTException = SMTException {
	smtExceptionDescription :: String
	, smtExceptionSent :: String
	, smtExceptionExpected :: String
	, smtExceptionReceived :: String
	, smtExceptionStdOut :: String
	, smtExceptionStdErr :: Maybe String
	, smtExceptionExitCode :: Maybe ExitCode
	, smtExceptionConfig :: SMTConfig
	, smtExceptionReason :: Maybe [String]
	, smtExceptionHint :: Maybe [String]
	}

There's a nice Show instance for this type; so if you catch \(e :: SMTException) and display the show'd value to the user it would provide enough info. Then you can go back to the Crytol REPL. Of course, if you want to inspect the fields of this data type and take further action, that's possible too. Note that if you ever catch this exception, the solver is no longer alive at that point; i.e., Query mode users would have lost the access to the pipe at that point. I guess that part doesn't really matter for Cryptol.

Exceptions are tricky to deal with, so I'll keep this ticket open and refrain from making a release till you get a chance to test this out and make sure it works as expected. Let me know what you find out!

[LeventErkok]

@brianhuffman Did you get a chance to test this out? Would like to close the ticket if we have some confirmation that it works as expected.

[LeventErkok]

@brianhuffman I'm intending to make a new SBV release in about a week or so. I don't know if you got a chance to test this out. Would like to close this ticket before the release.

[LeventErkok]

SBV 7.5 will be released soon; I'm closing this ticket as I think this release addresses it. If not, please feel free to reopen!