sosy-lab / java-smt

JavaSMT - Unified Java API for SMT solvers.
Apache License 2.0
187 stars 45 forks source link

SMTInterpol regression: AssertionError in close #405

Open PhilippWendler opened 4 weeks ago

PhilippWendler commented 4 weeks ago

With JavaSMT 5.0.0 and SMTInterpol 2.5-1242-g5c50fb6d we get the following crash:

Exception in thread "main" java.lang.AssertionError
        at de.uni_freiburg.informatik.ultimate.smtinterpol.theory.cclosure.CCTerm.unshare(CCTerm.java:292)
        at de.uni_freiburg.informatik.ultimate.smtinterpol.convert.Clausifier.pop(Clausifier.java:2343)
        at de.uni_freiburg.informatik.ultimate.smtinterpol.smtlib2.SMTInterpol.pop(SMTInterpol.java:406)
        at org.sosy_lab.java_smt.solvers.smtinterpol.SmtInterpolAbstractProver.close(SmtInterpolAbstractProver.java:220)
        at org.sosy_lab.java_smt.basicimpl.withAssumptionsWrapper.BasicProverWithAssumptionsWrapper.close(BasicProverWithAssumptionsWrapper.java:117)
        at org.sosy_lab.cpachecker.util.predicates.smt.BasicProverEnvironmentView.close(BasicProverEnvironmentView.java:85)
        at org.sosy_lab.cpachecker.cpa.predicate.PredicateAbstractionManager.computeAbstraction(PredicateAbstractionManager.java:798)
        at org.sosy_lab.cpachecker.cpa.predicate.PredicateAbstractionManager.buildAbstraction(PredicateAbstractionManager.java:405)
        at org.sosy_lab.cpachecker.cpa.predicate.PredicatePrecisionAdjustment.computeAbstraction(PredicatePrecisionAdjustment.java:185)
        at org.sosy_lab.cpachecker.cpa.predicate.PredicatePrecisionAdjustment.prec(PredicatePrecisionAdjustment.java:96)
        at org.sosy_lab.cpachecker.cpa.composite.CompositePrecisionAdjustment.prec(CompositePrecisionAdjustment.java:68)
        at org.sosy_lab.cpachecker.cpa.arg.ARGPrecisionAdjustment.prec(ARGPrecisionAdjustment.java:88)
        at org.sosy_lab.cpachecker.cpa.arg.ARGPrecisionAdjustment.prec(ARGPrecisionAdjustment.java:58)
        at org.sosy_lab.cpachecker.core.algorithm.CPAAlgorithm.handleState(CPAAlgorithm.java:356)
        at org.sosy_lab.cpachecker.core.algorithm.CPAAlgorithm.run0(CPAAlgorithm.java:289)
        at org.sosy_lab.cpachecker.core.algorithm.CPAAlgorithm.run(CPAAlgorithm.java:260)
        at org.sosy_lab.cpachecker.core.algorithm.CEGARAlgorithm.run(CEGARAlgorithm.java:241)
        at org.sosy_lab.cpachecker.core.algorithm.CounterexampleStoreAlgorithm.run(CounterexampleStoreAlgorithm.java:58)
        at org.sosy_lab.cpachecker.core.CPAchecker.runAlgorithm(CPAchecker.java:489)
        at org.sosy_lab.cpachecker.core.CPAchecker.run(CPAchecker.java:357)
        at org.sosy_lab.cpachecker.cmdline.CPAMain.main(CPAMain.java:171)

This does not appear always, but in many hundred cases: 1,category(notIn())))&sort=0_cputime_1,asc), 2,category(notIn())))&sort=0_cputime_1,asc), 3,category(notIn())))) It seems to be deterministic.

Given that our code just calls close() as part of a try-with-resources block, this should be a bug in either JavaSMT or SMTInterpol.

baierd commented 4 weeks ago

So the problem is in line 220 in the SmtInterpolAbstractProver. I can not tell what the underlying problem is at this moment however. Removing this line avoids the error and the analysis returns True.

I could not yet determine a way of testing this. @daniel-raffler do you want to try and find a test and possibly a program to send to the SMTInterpol devs if we are not causing this?

@PhilippWendler do we need a hotfix version for this?

Based on debugging i found that:

PhilippWendler commented 4 weeks ago

So the problem is in line 220 in the SmtInterpolAbstractProver. I can not tell what the underlying problem is at this moment however. Removing this line avoids the error and the analysis returns True.

But that leaks all the memory, wouldn't it? So it only confirms the problem but is not a fix.

I could not yet determine a way of testing this. @daniel-raffler do you want to try and find a test and possibly a program to send to the SMTInterpol devs if we are not causing this?

If your assumption below about empty pushes is correct, this should be easy to replicate, shouldn't it?

@PhilippWendler do we need a hotfix version for this?

Well, depends. It would certainly be nice if SMTInterpol would be usable in CPAchecker without having to wait for several months or so.

baierd commented 4 weeks ago

So the problem is in line 220 in the SmtInterpolAbstractProver. I can not tell what the underlying problem is at this moment however. Removing this line avoids the error and the analysis returns True.

But that leaks all the memory, wouldn't it? So it only confirms the problem but is not a fix.

Yes. But there is API in SMTInterpol for that with exit() to close a solver completely or reset() and resetAssertions() to reset it and clean up the references. But i need to take a look at how we implemented the prover for SMTInterpol. This might actually be a proper solution compared to what we do currently.

I could not yet determine a way of testing this. @daniel-raffler do you want to try and find a test and possibly a program to send to the SMTInterpol devs if we are not causing this?

If your assumption below about empty pushes is correct, this should be easy to replicate, shouldn't it?

I of course tried this, but it is not that trivial ;D

@PhilippWendler do we need a hotfix version for this?

Well, depends. It would certainly be nice if SMTInterpol would be usable in CPAchecker without having to wait for several months or so.

I guess we can do a release once we sorted this and #406 out.

daniel-raffler commented 4 weeks ago

@daniel-raffler do you want to try and find a test and possibly a program to send to the SMTInterpol devs if we are not causing this?

I've had a look at it and it seems that the issue has been around for some time. It was introduced in 999c8d59cc54feb64117db3a62c8f37201c0bf6c, which moved a lot of the bookkeeping for the assertion stack from the solver backends to their base class AbstractProver. The commit also changed close() in SMTInterpolAbstractProver from its old version:

public void close() {
  if (!closed) {
    assertedFormulas.clear();
    annotatedTerms.clear();
    env.pop(assertedFormulas.size());
  }
  super.close();
}

to

@Override
public void close() {
  if (!closed) {
    annotatedTerms.clear();
    env.pop(size());
  }
  super.close();
}

Note that the old version is actually broken as env.pop(assertedFormulas.size()); is called after assertedFormulas was just cleared. Because of this pop would only ever get called with 0 as its argument. If we change the order and call pop first the crash can be replicated even with the old version.

I think it should be safe to simply remove the line for now as this will just gets us back to the behavior of JavaSMT 4.0.2 before the version was updated in CPAchecker. There might still be a SMTInterpol bug here, but this will need some more work: The line env.pop(assertedFormulas.size()); was last changed in cd14da11f383d300c7d2767ddd5c4e1263e1fcf0 which is about adding support for multiple prover stacks to SMTInterpol. Before that only one prover would be allowed at a time and the assertion stack would have to be cleared before another prover is opened (internally the stack would simply be reused). It's possible that there are still some problems when formulas are shared across prover stacks, and those provers are then closed in the "wrong" order. I'll see if I can find a test case for that.

baierd commented 4 weeks ago

I fixed it using the proper cleanup API of SMTInterpol in 72b06914cf9bd126930d32d37161a8895683abba.

I also tested this with CPAchecker and it works fine now.

@daniel-raffler if you want to find a minimal example to use as a test you can try. But don't spend to much time on it as it should be fixed for good now.