Symbooglix missing a bug

[zvonimir]

We identified this as an example that it seems causes for Symbooglix to miss a bug:
array2_free_fail.zip

No bugs are reported when Symbooglix is executed on this bpl file like this:

symbooglix array2_free_fail.bpl --file-logging=0 --entry-points=main --timeout=1200 --max-loop-depth=1

On the other hand, Corral does report a bug as expected:

corral array2_free_fail.bpl /noTraceOnDisk /k:1 /timeLimit:1200 /cex:1 /maxStaticLoopBound:1 /recursionBound:1

This is a fairly simple example, and I do have to wonder if this problem is due to our usage of quantifiers.

[delcypher]

@zvonimir

No bugs are reported when Symbooglix is executed on this bpl file like this:

That is because symbooglix is timing out. Symbooglix is not claiming the program is bug free.

This is a fairly simple example, and I do have to wonder if this problem is due to our usage of quantifiers.

It looks that way. Symbooglix gets stuck in the implementation of $global_allocations() trying to check one of the calls to $galloc().

If I use a very recent build of Z3, Symbooglix eventually gives up because Z3 returns unknown (due to the default 120 second query timeout per call) while trying to check one of the calls to $galloc().

array2_free_fail.bpl:95: [Cmd] call $galloc(__SMACK_nondet_signed_long, 8);                                                                                                                   
Solver returned UNKNOWN!                                                                                                                                                                      
Not executing a speculative Execution State!                                                                                                                                                  
State 0:(Speculative) Disallowed speculative path. Starting at [Ensures] (forall q: ref :: { $Alloc[q] } q != base_addr ==> ($Alloc[q] <==> old($Alloc)[q]))

It is very likely that the problem here is the use of quantifiers.

Attached is a log of the queries Symbooglix issued to Z3
z3_in_log.txt. Maybe there's something that can be done to make Z3 handle the queries faster?

[zvonimir]

Ok, I attempted to reproduce this, and here is what I get. The end of the output I get from symbooglix is as follows:

Cancelled reading stderr
Cancelled reading stdout
killed process
Disposed of process
Exiting with NO_ERRORS_NO_TIMEOUT_BUT_FOUND_SPECULATIVE_PATHS

What does that actually mean?
I thought this output means that symbooglix found no bugs, but I guess I am not really sure what speculative paths imply.
Btw, I am using Z3 release 4.5.0.

[delcypher]

What does that actually mean?
I thought this output means that symbooglix found no bugs,

That's not what it means.

but I guess I am not really sure what speculative paths imply.

A speculative path is a path that Symbooglix could not prove is feasible. A path becomes "speculative" in Symbooglix at branch points (goto, assume, assert, etc.) if the solver fails to confirm feasibility (i.e. the solver times out or it reports unknown).

The current implementation of Symbooglix immediately terminates paths marked as "speculative". So having speculative paths implies path exploration might be non-exhaustive.

Therefore if

• Path exploration does not timeout
• speculative paths are reported
• No bugs are reported

then we cannot conclude the program is bug free.

[ccadar]

It would be useful to have a more human-friendly message here, essentially informing users that paths, and thus bugs, might have been missed.

[zvonimir]

@delcypher : Ok, got it, this makes sense now. Btw, could you send me the query on which Z3 times out? I am having trouble isolating it from the txt file you attached. Thx.

[delcypher]

@ccadar Good suggestion. I've added that in d4751f5

[delcypher]

@zvonimir Sorry I completely missed your request. I only just saw it now. I've run again and I've attached the query that hits the 120 second solver timeout.
slow.zip