java -Xss4m -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/cav12/s3_clnt_4.cil.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 12:11:03,718 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 12:11:03,721 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 12:11:03,733 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 12:11:03,733 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 12:11:03,734 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 12:11:03,735 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 12:11:03,739 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 12:11:03,740 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 12:11:03,741 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 12:11:03,741 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 12:11:03,743 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 12:11:03,743 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 12:11:03,744 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 12:11:03,745 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 12:11:03,746 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 12:11:03,749 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 12:11:03,750 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 12:11:03,760 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 12:11:03,761 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 12:11:03,762 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 12:11:03,764 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 12:11:03,764 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 12:11:03,764 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 12:11:03,768 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 12:11:03,769 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 12:11:03,770 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 12:11:03,770 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 12:11:03,771 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 12:11:03,771 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 12:11:03,775 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 12:11:03,776 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 12:11:03,776 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 12:11:03,777 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 12:11:03,777 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 12:11:03,777 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-25 12:11:03,797 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 12:11:03,797 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 12:11:03,798 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 12:11:03,798 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 12:11:03,799 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 12:11:03,799 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 12:11:03,799 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 12:11:03,799 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 12:11:03,799 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 12:11:03,799 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 12:11:03,800 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 12:11:03,800 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 12:11:03,800 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 12:11:03,800 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 12:11:03,800 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 12:11:03,801 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 12:11:03,801 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 12:11:03,801 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 12:11:03,801 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 12:11:03,801 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 12:11:03,801 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 12:11:03,803 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 12:11:03,803 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 12:11:03,848 INFO ]: Repository-Root is: /tmp [2018-06-25 12:11:03,862 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 12:11:03,865 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 12:11:03,866 INFO ]: Initializing SmtParser... [2018-06-25 12:11:03,866 INFO ]: SmtParser initialized [2018-06-25 12:11:03,867 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/cav12/s3_clnt_4.cil.smt2 [2018-06-25 12:11:03,868 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-25 12:11:03,952 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/s3_clnt_4.cil.smt2 unknown [2018-06-25 12:11:04,473 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/s3_clnt_4.cil.smt2 [2018-06-25 12:11:04,479 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 12:11:04,493 INFO ]: Walking toolchain with 4 elements. [2018-06-25 12:11:04,494 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 12:11:04,494 INFO ]: Initializing ChcToBoogie... [2018-06-25 12:11:04,494 INFO ]: ChcToBoogie initialized [2018-06-25 12:11:04,500 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 12:11:04" (1/1) ... [2018-06-25 12:11:04,584 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:11:04 Unit [2018-06-25 12:11:04,584 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 12:11:04,585 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 12:11:04,585 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 12:11:04,585 INFO ]: Boogie Preprocessor initialized [2018-06-25 12:11:04,629 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:11:04" (1/1) ... [2018-06-25 12:11:04,629 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:11:04" (1/1) ... [2018-06-25 12:11:04,650 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:11:04" (1/1) ... [2018-06-25 12:11:04,650 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:11:04" (1/1) ... [2018-06-25 12:11:04,664 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:11:04" (1/1) ... [2018-06-25 12:11:04,665 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:11:04" (1/1) ... [2018-06-25 12:11:04,669 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:11:04" (1/1) ... [2018-06-25 12:11:04,673 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 12:11:04,674 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 12:11:04,674 INFO ]: Initializing RCFGBuilder... [2018-06-25 12:11:04,674 INFO ]: RCFGBuilder initialized [2018-06-25 12:11:04,674 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:11:04" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-25 12:11:04,687 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 12:11:04,687 INFO ]: Found specification of procedure gotoProc [2018-06-25 12:11:04,687 INFO ]: Found implementation of procedure gotoProc [2018-06-25 12:11:04,687 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 12:11:04,687 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 12:11:04,687 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 12:11:05,031 INFO ]: Using library mode [2018-06-25 12:11:05,032 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 12:11:05 BoogieIcfgContainer [2018-06-25 12:11:05,032 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 12:11:05,033 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 12:11:05,033 INFO ]: Initializing TraceAbstraction... [2018-06-25 12:11:05,036 INFO ]: TraceAbstraction initialized [2018-06-25 12:11:05,038 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 12:11:04" (1/3) ... [2018-06-25 12:11:05,039 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7541e1ba and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 12:11:05, skipping insertion in model container [2018-06-25 12:11:05,039 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:11:04" (2/3) ... [2018-06-25 12:11:05,039 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7541e1ba and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 12:11:05, skipping insertion in model container [2018-06-25 12:11:05,039 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 12:11:05" (3/3) ... [2018-06-25 12:11:05,041 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 12:11:05,051 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 12:11:05,060 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 12:11:05,106 INFO ]: Using default assertion order modulation [2018-06-25 12:11:05,107 INFO ]: Interprodecural is true [2018-06-25 12:11:05,107 INFO ]: Hoare is false [2018-06-25 12:11:05,107 INFO ]: Compute interpolants for FPandBP [2018-06-25 12:11:05,107 INFO ]: Backedges is TWOTRACK [2018-06-25 12:11:05,107 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 12:11:05,107 INFO ]: Difference is false [2018-06-25 12:11:05,107 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 12:11:05,107 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 12:11:05,121 INFO ]: Start isEmpty. Operand 10 states. [2018-06-25 12:11:05,135 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 12:11:05,135 INFO ]: Found error trace [2018-06-25 12:11:05,138 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:11:05,138 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:11:05,143 INFO ]: Analyzing trace with hash 1284994894, now seen corresponding path program 1 times [2018-06-25 12:11:05,145 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:11:05,145 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:11:05,177 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:11:05,177 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:11:05,177 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:11:05,246 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:11:05,377 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:11:05,379 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 12:11:05,379 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 12:11:05,381 INFO ]: Interpolant automaton has 3 states [2018-06-25 12:11:05,396 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 12:11:05,397 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 12:11:05,399 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-25 12:11:05,482 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:11:05,482 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 12:11:05,483 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 12:11:05,484 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-25 12:11:05,484 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:11:05,497 INFO ]: With dead ends: 9 [2018-06-25 12:11:05,497 INFO ]: Without dead ends: 9 [2018-06-25 12:11:05,498 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 12:11:05,514 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 12:11:05,529 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 12:11:05,531 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 12:11:05,531 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 12:11:05,532 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 12:11:05,533 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:11:05,533 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 12:11:05,533 INFO ]: Interpolant automaton has 3 states. [2018-06-25 12:11:05,533 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 12:11:05,533 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 12:11:05,533 INFO ]: Found error trace [2018-06-25 12:11:05,533 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:11:05,533 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:11:05,533 INFO ]: Analyzing trace with hash 1180964567, now seen corresponding path program 1 times [2018-06-25 12:11:05,533 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:11:05,533 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:11:05,534 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:11:05,535 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:11:05,535 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:11:05,646 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:11:05,884 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:11:05,884 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:11:05,884 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:11:05,894 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:11:06,029 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:11:06,043 INFO ]: Computing forward predicates... [2018-06-25 12:11:06,395 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:11:06,416 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:11:06,416 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 6 [2018-06-25 12:11:06,416 INFO ]: Interpolant automaton has 6 states [2018-06-25 12:11:06,416 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-25 12:11:06,416 INFO ]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-25 12:11:06,417 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 6 states. [2018-06-25 12:11:06,667 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:11:06,667 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-25 12:11:06,667 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-25 12:11:06,667 INFO ]: Start accepts. Automaton has 6 states. Word has length 8 [2018-06-25 12:11:06,667 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:11:06,667 INFO ]: With dead ends: 10 [2018-06-25 12:11:06,667 INFO ]: Without dead ends: 10 [2018-06-25 12:11:06,668 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=19, Invalid=23, Unknown=0, NotChecked=0, Total=42 [2018-06-25 12:11:06,668 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-25 12:11:06,669 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-25 12:11:06,669 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-25 12:11:06,670 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-25 12:11:06,670 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-25 12:11:06,670 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:11:06,670 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-25 12:11:06,670 INFO ]: Interpolant automaton has 6 states. [2018-06-25 12:11:06,670 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-25 12:11:06,670 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-25 12:11:06,670 INFO ]: Found error trace [2018-06-25 12:11:06,670 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:11:06,670 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:11:06,671 INFO ]: Analyzing trace with hash -2043975570, now seen corresponding path program 2 times [2018-06-25 12:11:06,671 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:11:06,671 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:11:06,674 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:11:06,674 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:11:06,674 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:11:06,792 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:11:06,995 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:11:06,995 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:11:06,996 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:11:07,002 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 12:11:07,124 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 12:11:07,124 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:11:07,133 INFO ]: Computing forward predicates... [2018-06-25 12:11:07,998 WARN ]: Spent 151.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-25 12:11:08,013 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:11:08,044 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:11:08,044 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2018-06-25 12:11:08,044 INFO ]: Interpolant automaton has 8 states [2018-06-25 12:11:08,044 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-25 12:11:08,044 INFO ]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2018-06-25 12:11:08,045 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 8 states. [2018-06-25 12:11:08,225 WARN ]: Spent 115.00 ms on a formula simplification. DAG size of input: 11 DAG size of output: 7 [2018-06-25 12:11:08,366 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:11:08,366 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-25 12:11:08,366 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-25 12:11:08,366 INFO ]: Start accepts. Automaton has 8 states. Word has length 9 [2018-06-25 12:11:08,367 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:11:08,367 INFO ]: With dead ends: 11 [2018-06-25 12:11:08,367 INFO ]: Without dead ends: 11 [2018-06-25 12:11:08,367 INFO ]: 0 DeclaredPredicates, 15 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=35, Invalid=55, Unknown=0, NotChecked=0, Total=90 [2018-06-25 12:11:08,367 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-25 12:11:08,368 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-25 12:11:08,368 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-25 12:11:08,368 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-25 12:11:08,368 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-25 12:11:08,368 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:11:08,368 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-25 12:11:08,368 INFO ]: Interpolant automaton has 8 states. [2018-06-25 12:11:08,368 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-25 12:11:08,368 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-25 12:11:08,368 INFO ]: Found error trace [2018-06-25 12:11:08,368 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:11:08,369 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:11:08,369 INFO ]: Analyzing trace with hash 1062095287, now seen corresponding path program 3 times [2018-06-25 12:11:08,369 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:11:08,369 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:11:08,369 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:11:08,369 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:11:08,369 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:11:08,465 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:11:08,820 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:11:08,820 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:11:08,820 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:11:08,833 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 12:11:08,971 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-25 12:11:08,971 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:11:08,981 INFO ]: Computing forward predicates... [2018-06-25 12:11:11,791 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:11:11,813 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:11:11,813 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2018-06-25 12:11:11,813 INFO ]: Interpolant automaton has 10 states [2018-06-25 12:11:11,813 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-25 12:11:11,814 INFO ]: CoverageRelationStatistics Valid=31, Invalid=59, Unknown=0, NotChecked=0, Total=90 [2018-06-25 12:11:11,814 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 10 states. [2018-06-25 12:11:11,984 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:11:11,984 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-25 12:11:11,985 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-25 12:11:11,986 INFO ]: Start accepts. Automaton has 10 states. Word has length 10 [2018-06-25 12:11:11,986 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:11:11,986 INFO ]: With dead ends: 12 [2018-06-25 12:11:11,986 INFO ]: Without dead ends: 12 [2018-06-25 12:11:11,986 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=58, Invalid=98, Unknown=0, NotChecked=0, Total=156 [2018-06-25 12:11:11,987 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-25 12:11:11,988 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-25 12:11:11,988 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-25 12:11:11,988 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-25 12:11:11,988 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-25 12:11:11,988 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:11:11,988 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-25 12:11:11,988 INFO ]: Interpolant automaton has 10 states. [2018-06-25 12:11:11,988 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-25 12:11:11,989 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-25 12:11:11,989 INFO ]: Found error trace [2018-06-25 12:11:11,989 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:11:11,989 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:11:11,989 INFO ]: Analyzing trace with hash -1433955954, now seen corresponding path program 4 times [2018-06-25 12:11:11,989 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:11:11,989 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:11:11,990 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:11:11,990 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:11:11,990 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:11:12,119 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:11:12,685 WARN ]: Spent 119.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-25 12:11:13,102 WARN ]: Spent 329.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 11 [2018-06-25 12:11:13,321 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:11:13,321 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:11:13,321 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:11:13,329 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-25 12:11:13,481 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-25 12:11:13,481 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:11:13,493 INFO ]: Computing forward predicates... [2018-06-25 12:11:15,269 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:11:15,289 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:11:15,289 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2018-06-25 12:11:15,289 INFO ]: Interpolant automaton has 12 states [2018-06-25 12:11:15,289 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-25 12:11:15,289 INFO ]: CoverageRelationStatistics Valid=41, Invalid=91, Unknown=0, NotChecked=0, Total=132 [2018-06-25 12:11:15,289 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 12 states. [2018-06-25 12:11:15,539 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:11:15,539 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-25 12:11:15,539 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-25 12:11:15,539 INFO ]: Start accepts. Automaton has 12 states. Word has length 11 [2018-06-25 12:11:15,539 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:11:15,540 INFO ]: With dead ends: 13 [2018-06-25 12:11:15,540 INFO ]: Without dead ends: 13 [2018-06-25 12:11:15,540 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 38 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=83, Invalid=157, Unknown=0, NotChecked=0, Total=240 [2018-06-25 12:11:15,540 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-25 12:11:15,541 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-25 12:11:15,541 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-25 12:11:15,542 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-25 12:11:15,542 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 11 [2018-06-25 12:11:15,542 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:11:15,542 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-25 12:11:15,542 INFO ]: Interpolant automaton has 12 states. [2018-06-25 12:11:15,542 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-25 12:11:15,542 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-25 12:11:15,542 INFO ]: Found error trace [2018-06-25 12:11:15,542 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:11:15,542 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:11:15,542 INFO ]: Analyzing trace with hash -1502133097, now seen corresponding path program 5 times [2018-06-25 12:11:15,542 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:11:15,542 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:11:15,543 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:11:15,543 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:11:15,543 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:11:15,684 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:11:15,961 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:11:15,961 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:11:15,961 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:11:15,971 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-25 12:11:16,137 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-25 12:11:16,138 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:11:16,149 INFO ]: Computing forward predicates... [2018-06-25 12:11:17,423 WARN ]: Spent 518.00 ms on a formula simplification. DAG size of input: 28 DAG size of output: 8 [2018-06-25 12:11:22,606 WARN ]: Spent 4.06 s on a formula simplification. DAG size of input: 351 DAG size of output: 143 [2018-06-25 12:11:23,476 WARN ]: Spent 384.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-25 12:11:23,491 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:11:23,525 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:11:23,525 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2018-06-25 12:11:23,525 INFO ]: Interpolant automaton has 14 states [2018-06-25 12:11:23,525 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-25 12:11:23,525 INFO ]: CoverageRelationStatistics Valid=54, Invalid=128, Unknown=0, NotChecked=0, Total=182 [2018-06-25 12:11:23,526 INFO ]: Start difference. First operand 13 states and 13 transitions. Second operand 14 states. [2018-06-25 12:11:24,086 WARN ]: Spent 389.00 ms on a formula simplification. DAG size of input: 151 DAG size of output: 81 [2018-06-25 12:11:24,632 WARN ]: Spent 523.00 ms on a formula simplification. DAG size of input: 158 DAG size of output: 90 [2018-06-25 12:11:25,586 WARN ]: Spent 918.00 ms on a formula simplification. DAG size of input: 154 DAG size of output: 152 [2018-06-25 12:11:25,611 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:11:25,611 INFO ]: Finished difference Result 14 states and 14 transitions. [2018-06-25 12:11:25,612 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-25 12:11:25,612 INFO ]: Start accepts. Automaton has 14 states. Word has length 12 [2018-06-25 12:11:25,612 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:11:25,612 INFO ]: With dead ends: 14 [2018-06-25 12:11:25,612 INFO ]: Without dead ends: 14 [2018-06-25 12:11:25,613 INFO ]: 0 DeclaredPredicates, 24 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 65 ImplicationChecksByTransitivity, 7.6s TimeCoverageRelationStatistics Valid=114, Invalid=228, Unknown=0, NotChecked=0, Total=342 [2018-06-25 12:11:25,613 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-25 12:11:25,614 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-25 12:11:25,614 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-25 12:11:25,614 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-06-25 12:11:25,614 INFO ]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 12 [2018-06-25 12:11:25,614 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:11:25,614 INFO ]: Abstraction has 14 states and 14 transitions. [2018-06-25 12:11:25,614 INFO ]: Interpolant automaton has 14 states. [2018-06-25 12:11:25,615 INFO ]: Start isEmpty. Operand 14 states and 14 transitions. [2018-06-25 12:11:25,615 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-25 12:11:25,615 INFO ]: Found error trace [2018-06-25 12:11:25,615 INFO ]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:11:25,615 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:11:25,615 INFO ]: Analyzing trace with hash 679342766, now seen corresponding path program 6 times [2018-06-25 12:11:25,615 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:11:25,615 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:11:25,616 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:11:25,616 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:11:25,616 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:11:25,792 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:11:26,386 WARN ]: Spent 130.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 11 [2018-06-25 12:11:26,454 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:11:26,454 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:11:26,454 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:11:26,460 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-25 12:11:26,663 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2018-06-25 12:11:26,663 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:11:26,680 INFO ]: Computing forward predicates... [2018-06-25 12:11:27,949 WARN ]: Spent 415.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 6 [2018-06-25 12:11:28,953 WARN ]: Spent 121.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 8 [2018-06-25 12:11:29,599 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:11:29,623 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:11:29,623 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 16 [2018-06-25 12:11:29,623 INFO ]: Interpolant automaton has 16 states [2018-06-25 12:11:29,624 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-25 12:11:29,624 INFO ]: CoverageRelationStatistics Valid=73, Invalid=167, Unknown=0, NotChecked=0, Total=240 [2018-06-25 12:11:29,624 INFO ]: Start difference. First operand 14 states and 14 transitions. Second operand 16 states. [2018-06-25 12:11:29,993 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:11:29,994 INFO ]: Finished difference Result 17 states and 17 transitions. [2018-06-25 12:11:29,994 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-25 12:11:29,994 INFO ]: Start accepts. Automaton has 16 states. Word has length 13 [2018-06-25 12:11:29,994 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:11:29,994 INFO ]: With dead ends: 17 [2018-06-25 12:11:29,994 INFO ]: Without dead ends: 17 [2018-06-25 12:11:29,995 INFO ]: 0 DeclaredPredicates, 29 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 120 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=179, Invalid=373, Unknown=0, NotChecked=0, Total=552 [2018-06-25 12:11:29,995 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-25 12:11:29,996 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-25 12:11:29,996 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-25 12:11:29,997 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 17 transitions. [2018-06-25 12:11:29,997 INFO ]: Start accepts. Automaton has 17 states and 17 transitions. Word has length 13 [2018-06-25 12:11:29,997 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:11:29,997 INFO ]: Abstraction has 17 states and 17 transitions. [2018-06-25 12:11:29,997 INFO ]: Interpolant automaton has 16 states. [2018-06-25 12:11:29,997 INFO ]: Start isEmpty. Operand 17 states and 17 transitions. [2018-06-25 12:11:29,997 INFO ]: Finished isEmpty. Found accepting run of length 17 [2018-06-25 12:11:29,997 INFO ]: Found error trace [2018-06-25 12:11:29,997 INFO ]: trace histogram [9, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:11:29,997 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:11:29,997 INFO ]: Analyzing trace with hash 1237160535, now seen corresponding path program 7 times [2018-06-25 12:11:29,997 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:11:29,997 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:11:29,998 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:11:29,998 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:11:29,998 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:11:30,409 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:11:31,376 WARN ]: Spent 398.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 14 [2018-06-25 12:11:31,587 INFO ]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:11:31,587 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:11:31,587 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:11:31,594 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:11:31,850 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:11:31,870 INFO ]: Computing forward predicates... [2018-06-25 12:11:34,735 WARN ]: Spent 1.59 s on a formula simplification. DAG size of input: 252 DAG size of output: 112 [2018-06-25 12:11:41,664 WARN ]: Spent 2.35 s on a formula simplification. DAG size of input: 322 DAG size of output: 124 [2018-06-25 12:11:47,503 WARN ]: Spent 3.56 s on a formula simplification. DAG size of input: 370 DAG size of output: 141 [2018-06-25 12:11:51,361 INFO ]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:11:51,383 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:11:51,384 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 22 [2018-06-25 12:11:51,384 INFO ]: Interpolant automaton has 22 states [2018-06-25 12:11:51,384 INFO ]: Constructing interpolant automaton starting with 22 interpolants. [2018-06-25 12:11:51,384 INFO ]: CoverageRelationStatistics Valid=139, Invalid=323, Unknown=0, NotChecked=0, Total=462 [2018-06-25 12:11:51,384 INFO ]: Start difference. First operand 17 states and 17 transitions. Second operand 22 states. [2018-06-25 12:11:52,099 WARN ]: Spent 489.00 ms on a formula simplification. DAG size of input: 162 DAG size of output: 85 [2018-06-25 12:11:52,857 WARN ]: Spent 717.00 ms on a formula simplification. DAG size of input: 160 DAG size of output: 154 [2018-06-25 12:11:53,305 WARN ]: Spent 390.00 ms on a formula simplification. DAG size of input: 151 DAG size of output: 83 [2018-06-25 12:11:54,138 WARN ]: Spent 807.00 ms on a formula simplification. DAG size of input: 157 DAG size of output: 151 [2018-06-25 12:11:54,333 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:11:54,333 INFO ]: Finished difference Result 20 states and 20 transitions. [2018-06-25 12:11:54,333 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-25 12:11:54,333 INFO ]: Start accepts. Automaton has 22 states. Word has length 16 [2018-06-25 12:11:54,333 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:11:54,334 INFO ]: With dead ends: 20 [2018-06-25 12:11:54,334 INFO ]: Without dead ends: 20 [2018-06-25 12:11:54,334 INFO ]: 0 DeclaredPredicates, 37 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 287 ImplicationChecksByTransitivity, 11.9s TimeCoverageRelationStatistics Valid=326, Invalid=666, Unknown=0, NotChecked=0, Total=992 [2018-06-25 12:11:54,334 INFO ]: Start minimizeSevpa. Operand 20 states. [2018-06-25 12:11:54,336 INFO ]: Finished minimizeSevpa. Reduced states from 20 to 20. [2018-06-25 12:11:54,336 INFO ]: Start removeUnreachable. Operand 20 states. [2018-06-25 12:11:54,336 INFO ]: Finished removeUnreachable. Reduced from 20 states to 20 states and 20 transitions. [2018-06-25 12:11:54,336 INFO ]: Start accepts. Automaton has 20 states and 20 transitions. Word has length 16 [2018-06-25 12:11:54,336 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:11:54,336 INFO ]: Abstraction has 20 states and 20 transitions. [2018-06-25 12:11:54,336 INFO ]: Interpolant automaton has 22 states. [2018-06-25 12:11:54,336 INFO ]: Start isEmpty. Operand 20 states and 20 transitions. [2018-06-25 12:11:54,337 INFO ]: Finished isEmpty. Found accepting run of length 20 [2018-06-25 12:11:54,337 INFO ]: Found error trace [2018-06-25 12:11:54,337 INFO ]: trace histogram [12, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:11:54,337 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:11:54,337 INFO ]: Analyzing trace with hash 1957848590, now seen corresponding path program 8 times [2018-06-25 12:11:54,337 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:11:54,337 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:11:54,338 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:11:54,338 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:11:54,338 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:11:55,017 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:11:56,286 WARN ]: Spent 368.00 ms on a formula simplification. DAG size of input: 24 DAG size of output: 14 [2018-06-25 12:11:56,417 WARN ]: Spent 118.00 ms on a formula simplification. DAG size of input: 74 DAG size of output: 17 [2018-06-25 12:11:56,743 WARN ]: Spent 303.00 ms on a formula simplification. DAG size of input: 142 DAG size of output: 25 [2018-06-25 12:11:57,482 WARN ]: Spent 699.00 ms on a formula simplification. DAG size of input: 245 DAG size of output: 75 [2018-06-25 12:11:57,888 WARN ]: Spent 374.00 ms on a formula simplification. DAG size of input: 164 DAG size of output: 40 [2018-06-25 12:11:58,142 WARN ]: Spent 209.00 ms on a formula simplification. DAG size of input: 137 DAG size of output: 26 [2018-06-25 12:11:58,322 INFO ]: Checked inductivity of 78 backedges. 0 proven. 78 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:11:58,322 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:11:58,354 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:11:58,360 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 12:11:58,805 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 12:11:58,805 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:11:58,833 INFO ]: Computing forward predicates... [2018-06-25 12:11:59,194 WARN ]: Spent 138.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 19 Received shutdown request... [2018-06-25 12:12:01,517 INFO ]: Timeout while computing interpolants [2018-06-25 12:12:01,717 WARN ]: Destroyed unattended storables created during the last iteration: 10 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:12:01,717 WARN ]: Verification canceled [2018-06-25 12:12:01,722 WARN ]: Timeout [2018-06-25 12:12:01,722 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 12:12:01 BoogieIcfgContainer [2018-06-25 12:12:01,722 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 12:12:01,723 INFO ]: Toolchain (without parser) took 57243.56 ms. Allocated memory was 306.2 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 244.6 MB in the beginning and 735.2 MB in the end (delta: -490.6 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 12:12:01,723 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 306.2 MB. Free memory is still 271.7 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 12:12:01,723 INFO ]: ChcToBoogie took 91.22 ms. Allocated memory is still 306.2 MB. Free memory was 244.6 MB in the beginning and 241.5 MB in the end (delta: 3.1 MB). Peak memory consumption was 3.1 MB. Max. memory is 3.6 GB. [2018-06-25 12:12:01,724 INFO ]: Boogie Preprocessor took 87.95 ms. Allocated memory is still 306.2 MB. Free memory was 241.5 MB in the beginning and 239.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 12:12:01,724 INFO ]: RCFGBuilder took 358.49 ms. Allocated memory is still 306.2 MB. Free memory was 239.5 MB in the beginning and 212.4 MB in the end (delta: 27.1 MB). Peak memory consumption was 27.1 MB. Max. memory is 3.6 GB. [2018-06-25 12:12:01,724 INFO ]: TraceAbstraction took 56688.60 ms. Allocated memory was 306.2 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 212.4 MB in the beginning and 735.2 MB in the end (delta: -522.9 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-25 12:12:01,726 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 306.2 MB. Free memory is still 271.7 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 91.22 ms. Allocated memory is still 306.2 MB. Free memory was 244.6 MB in the beginning and 241.5 MB in the end (delta: 3.1 MB). Peak memory consumption was 3.1 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 87.95 ms. Allocated memory is still 306.2 MB. Free memory was 241.5 MB in the beginning and 239.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 358.49 ms. Allocated memory is still 306.2 MB. Free memory was 239.5 MB in the beginning and 212.4 MB in the end (delta: 27.1 MB). Peak memory consumption was 27.1 MB. Max. memory is 3.6 GB. * TraceAbstraction took 56688.60 ms. Allocated memory was 306.2 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 212.4 MB in the beginning and 735.2 MB in the end (delta: -522.9 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 20 with TraceHistMax 12, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while XnfDer was eliminating 175 quantified variables from 69 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 56.6s OverallTime, 9 OverallIterations, 12 TraceHistogramMax, 6.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 56 SDtfs, 13 SDslu, 193 SDs, 0 SdLazy, 96 SolverSat, 44 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.7s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 159 GetRequests, 51 SyntacticMatches, 0 SemanticMatches, 108 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 545 ImplicationChecksByTransitivity, 24.4s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=20occurred in iteration=8, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 8 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.4s SsaConstructionTime, 1.9s SatisfiabilityAnalysisTime, 39.9s InterpolantComputationTime, 165 NumberOfCodeBlocks, 165 NumberOfCodeBlocksAsserted, 25 NumberOfCheckSat, 150 ConstructedInterpolants, 0 QuantifiedInterpolants, 33965 SizeOfPredicates, 20 NumberOfNonLiveVariables, 3361 ConjunctsInSsa, 202 ConjunctsInUnsatCore, 15 InterpolantComputations, 1 PerfectInterpolantSequences, 0/202 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/s3_clnt_4.cil.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_12-12-01-736.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/s3_clnt_4.cil.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_12-12-01-736.csv Completed graceful shutdown