From b19c08997e15d2e42f61f1936fd60c5e34081d68 Mon Sep 17 00:00:00 2001 From: Andrew Reynolds Date: Mon, 17 Feb 2020 11:17:02 -0600 Subject: [PATCH] Fix soundness bug in reduction of integer div/mod (#3766) This was introduced 7 years ago in https://github.com/CVC4/CVC4/commit/9098391fe334d829ec4101f190b8f1fa21c30752. This impacted any case of integer div/mod of the form `(mod c t)` or `(div c t)` where c is a constant and `t` is not. Fixes #3765. Also improves `--dump=t-lemmas` trace to result in smt-lib compatible output, which was required for debugging this. --- src/theory/arith/theory_arith_private.cpp | 2 +- src/theory/theory_engine.cpp | 4 ++-- test/regress/CMakeLists.txt | 2 ++ .../quantifiers/issue3765-quant-dd.smt2 | 18 ++++++++++++++++++ .../regress1/quantifiers/issue3765.smt2 | 17 +++++++++++++++++ 5 files changed, 40 insertions(+), 3 deletions(-) create mode 100644 test/regress/regress1/quantifiers/issue3765-quant-dd.smt2 create mode 100644 test/regress/regress1/quantifiers/issue3765.smt2 diff --git a/src/theory/arith/theory_arith_private.cpp b/src/theory/arith/theory_arith_private.cpp index 76d8dbc01..0ddded6bf 100644 --- a/src/theory/arith/theory_arith_private.cpp +++ b/src/theory/arith/theory_arith_private.cpp @@ -1603,7 +1603,7 @@ Node TheoryArithPrivate::axiomIteForTotalIntDivision(Node int_div_like){ Polynomial rp = Polynomial::parsePolynomial(r); Polynomial qp = Polynomial::parsePolynomial(q); - Node abs_d = (n.isConstant()) ? + Node abs_d = (d.isConstant()) ? d.getHead().getConstant().abs().getNode() : mkIntSkolem("abs"); Node eq = Comparison::mkComparison(EQUAL, n, d * qp + rp).getNode(); diff --git a/src/theory/theory_engine.cpp b/src/theory/theory_engine.cpp index 7549bd973..b43e55364 100644 --- a/src/theory/theory_engine.cpp +++ b/src/theory/theory_engine.cpp @@ -1854,11 +1854,11 @@ theory::LemmaStatus TheoryEngine::lemma(TNode node, if(Dump.isOn("t-lemmas")) { Node n = node; - if (negated) { + if (!negated) { n = node.negate(); } Dump("t-lemmas") << CommentCommand("theory lemma: expect valid") - << QueryCommand(n.toExpr()); + << CheckSatCommand(n.toExpr()); } // Share with other portfolio threads diff --git a/test/regress/CMakeLists.txt b/test/regress/CMakeLists.txt index 42c145762..1437baae1 100644 --- a/test/regress/CMakeLists.txt +++ b/test/regress/CMakeLists.txt @@ -1446,6 +1446,8 @@ set(regress_1_tests regress1/quantifiers/issue3628.smt2 regress1/quantifiers/issue3664.smt2 regress1/quantifiers/issue3724-quant.smt2 + regress1/quantifiers/issue3765.smt2 + regress1/quantifiers/issue3765-quant-dd.smt2 regress1/quantifiers/issue993.smt2 regress1/quantifiers/javafe.ast.StmtVec.009.smt2 regress1/quantifiers/lra-vts-inf.smt2 diff --git a/test/regress/regress1/quantifiers/issue3765-quant-dd.smt2 b/test/regress/regress1/quantifiers/issue3765-quant-dd.smt2 new file mode 100644 index 000000000..624e5ddfa --- /dev/null +++ b/test/regress/regress1/quantifiers/issue3765-quant-dd.smt2 @@ -0,0 +1,18 @@ +; COMMAND-LINE: --finite-model-find --no-check-models +; EXPECT: sat + +(set-logic ALL) + +(declare-sort U 0) +(declare-fun g (U) Int) +(declare-sort V 0) +(declare-fun f (V) Int) +(assert (and +(forall ((?i U)) (not (forall ((?z V)) (not (= (f ?z) (div (- 1) (g ?i))))) )) +)) + +(declare-fun k () U) +(assert (= (g k) 22)) + + +(check-sat) diff --git a/test/regress/regress1/quantifiers/issue3765.smt2 b/test/regress/regress1/quantifiers/issue3765.smt2 new file mode 100644 index 000000000..97e106365 --- /dev/null +++ b/test/regress/regress1/quantifiers/issue3765.smt2 @@ -0,0 +1,17 @@ +; COMMAND-LINE: --fmf-fun --no-check-models +; EXPECT: sat + +(set-info :smt-lib-version 2.5) +(set-option :produce-models true) +(set-logic ALL) +(define-funs-rec ( +(f11((va9 Int))Int) +(f3((v1f Int))Int) +) +( (f3 (ite (= 0 va9) (- 1) (div (- 1) va9))) + (- (ite (= 0 v1f) 0 (mod 0 v1f))) +)) +(declare-fun v18d() Int) +(assert (= 0 (f11 v18d))) +(assert (= 22 v18d)) +(check-sat) -- 2.30.2