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

314 adding the abstract numeric domains of the apron library as smt solver #346

Open
wants to merge 135 commits into
base: master
Choose a base branch
from

Conversation

winnieros
Copy link

@winnieros winnieros commented Dec 20, 2023

Integration of the APRON Numeric Abstract Domain Library as a quasi SMT solver supporting Integer, Rational and Boolean.
Problems with the implementation:

  • Apron doesn't support UFs, no evaluation with CPAchecker possible;
  • limited functionalities of Boolean;
  • Abstract interpretation uses overapproximation of the value set which leads to unsound results; that does not go in line with SMT; no possibility was found to inform the user about possible overapproximation;
  • Model is not trustworthy; ex.: x = 3, y = 1/2 gives ]-infinity, infinity[ as value set for x = y +3 for both x and y;
  • Prover can only guarantee for isUnsat(); !isUnsat() can mean SAT or UNKNOWN but it is not possible to further specify such result;

winnieros and others added 13 commits November 20, 2023 20:52
Merge branch '314-adding-the-abstract-numeric-domains-of-the-apron-library-as-smt-solver' of github.com:sosy-lab/java-smt into 314-adding-the-abstract-numeric-domains-of-the-apron-library-as-smt-solver
Copy link
Collaborator

@baierd baierd left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Some minor points to address before we can merge.

build/build-publish-solvers.xml Outdated Show resolved Hide resolved

public class ApronApiTest {

public static Manager manager = new PolkaEq();
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Can you add a small description as to what PolkaEQ is for people not fimilar with abstract numeric domains?

src/org/sosy_lab/java_smt/solvers/apron/ApronApiTest.java Outdated Show resolved Hide resolved

@Override
protected ApronNode not(ApronNode pParam1) {
throw new UnsupportedOperationException("Apron does not support not() operations.");
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

You could add a comment about the possibility of transforming the formula into negation normal form, as discussed in your talk.

src/org/sosy_lab/java_smt/solvers/apron/ApronModel.java Outdated Show resolved Hide resolved
}
}

private ApronNode getComplexValue(ApronNode pNode) {
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The method is quite big, maybe it would be good to split it up.

src/org/sosy_lab/java_smt/solvers/apron/ApronModel.java Outdated Show resolved Hide resolved
}
return first;
}
return null;
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Is null the correct return here?
Maybe throw an exception instead?

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm returning 0 now.

…ding-the-abstract-numeric-domains-of-the-apron-library-as-smt-solver

# Conflicts:
#	.gitignore
#	build/build-publish-solvers.xml
#	lib/ivy.xml
#	src/org/sosy_lab/java_smt/test/BooleanFormulaSubjectTest.java
#	src/org/sosy_lab/java_smt/test/FormulaManagerTest.java
#	src/org/sosy_lab/java_smt/test/ModelEvaluationTest.java
#	src/org/sosy_lab/java_smt/test/NonLinearArithmeticTest.java
#	src/org/sosy_lab/java_smt/test/ProverEnvironmentTest.java
#	src/org/sosy_lab/java_smt/test/RationalFormulaManagerTest.java
#	src/org/sosy_lab/java_smt/test/SolverBasedTest0.java
#	src/org/sosy_lab/java_smt/test/SolverConcurrencyTest.java
#	src/org/sosy_lab/java_smt/test/SolverStackTest.java
#	src/org/sosy_lab/java_smt/test/TranslateFormulaTest.java
@daniel-raffler
Copy link
Contributor

@baierd The code looks good so far. Can you upload the solver backend to Ivy? (Note that the binaries will depend on system supplied MPFR and GMP libraries. If this is a problem we can probably still change our build script to include them with the installation.)

This is what I used to build the binaries:
ant publish-apron -Dapron.path=/home/daniel/workspace/apron-JavaSMT -Dapron.customRev=0.9.14

(We need the apron version from your fork for this: git clone git@github.com:baierd/apron-JavaSMT.git)

@daniel-raffler
Copy link
Contributor

(We need the apron version from your fork for this: git clone git@github.com:baierd/apron-JavaSMT.git)

I could also create a patch from your changes and include it with JavaSMT. This is probably easier to maintain than keeping the fork updated?

…ot match any of the special cases. This is necessary as default values don't work properly and the argument may not have been fully substituted. In that case it's not a value at all and we need to return 'null'.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Development

Successfully merging this pull request may close these issues.

Adding the Abstract Numeric Domain(s) of the Apron Library as SMT solver
3 participants