java -Xmx6000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data ./data --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/ai/eq-bench/mempurity-32bit-Automizer_Camel+AI_EQ.epf -i ../../../trunk/examples/svcomp/forester-heap/dll-01_true-unreach-call_true-valid-memsafety.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-2f49842 [2018-01-20 22:26:24,982 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-20 22:26:24,984 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-20 22:26:24,997 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-20 22:26:24,997 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-20 22:26:24,998 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-20 22:26:24,999 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-20 22:26:25,000 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-20 22:26:25,002 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-20 22:26:25,002 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-20 22:26:25,003 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-20 22:26:25,004 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-20 22:26:25,005 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-20 22:26:25,006 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-20 22:26:25,007 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-20 22:26:25,009 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-20 22:26:25,011 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-20 22:26:25,013 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-20 22:26:25,014 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-20 22:26:25,015 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-20 22:26:25,017 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-20 22:26:25,018 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-20 22:26:25,018 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-20 22:26:25,019 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-20 22:26:25,020 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-20 22:26:25,021 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-20 22:26:25,021 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-20 22:26:25,022 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-20 22:26:25,022 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-20 22:26:25,022 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-20 22:26:25,023 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-20 22:26:25,023 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/ai/eq-bench/mempurity-32bit-Automizer_Camel+AI_EQ.epf [2018-01-20 22:26:25,033 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-20 22:26:25,033 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-20 22:26:25,034 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-20 22:26:25,034 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-20 22:26:25,034 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-20 22:26:25,034 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-20 22:26:25,035 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-20 22:26:25,035 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-20 22:26:25,035 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-20 22:26:25,036 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-20 22:26:25,036 INFO L133 SettingsManager]: * Check allocation purity=true [2018-01-20 22:26:25,036 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-20 22:26:25,036 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-20 22:26:25,036 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-20 22:26:25,037 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-01-20 22:26:25,037 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-20 22:26:25,037 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-01-20 22:26:25,037 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-20 22:26:25,037 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-01-20 22:26:25,038 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-01-20 22:26:25,038 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-20 22:26:25,038 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-01-20 22:26:25,038 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-20 22:26:25,038 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-20 22:26:25,039 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-20 22:26:25,039 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-20 22:26:25,039 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-20 22:26:25,039 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-20 22:26:25,040 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-20 22:26:25,040 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-20 22:26:25,040 INFO L133 SettingsManager]: * Stop after first violation was found=false [2018-01-20 22:26:25,040 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-01-20 22:26:25,040 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-20 22:26:25,041 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-20 22:26:25,041 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-20 22:26:25,042 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-20 22:26:25,042 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-20 22:26:25,078 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-20 22:26:25,091 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-20 22:26:25,095 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-20 22:26:25,096 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-20 22:26:25,097 INFO L276 PluginConnector]: CDTParser initialized [2018-01-20 22:26:25,098 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/forester-heap/dll-01_true-unreach-call_true-valid-memsafety.i [2018-01-20 22:26:25,280 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-20 22:26:25,285 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-20 22:26:25,286 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-20 22:26:25,286 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-20 22:26:25,291 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-20 22:26:25,292 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.01 10:26:25" (1/1) ... [2018-01-20 22:26:25,295 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6b83b4c1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25, skipping insertion in model container [2018-01-20 22:26:25,295 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.01 10:26:25" (1/1) ... [2018-01-20 22:26:25,309 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-20 22:26:25,350 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-20 22:26:25,472 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-20 22:26:25,499 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-20 22:26:25,509 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25 WrapperNode [2018-01-20 22:26:25,509 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-20 22:26:25,510 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-20 22:26:25,510 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-20 22:26:25,510 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-20 22:26:25,524 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25" (1/1) ... [2018-01-20 22:26:25,524 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25" (1/1) ... [2018-01-20 22:26:25,534 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25" (1/1) ... [2018-01-20 22:26:25,534 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25" (1/1) ... [2018-01-20 22:26:25,539 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25" (1/1) ... [2018-01-20 22:26:25,545 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25" (1/1) ... [2018-01-20 22:26:25,547 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25" (1/1) ... [2018-01-20 22:26:25,549 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-20 22:26:25,549 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-20 22:26:25,550 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-20 22:26:25,550 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-20 22:26:25,551 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-20 22:26:25,597 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-20 22:26:25,597 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-20 22:26:25,597 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-20 22:26:25,597 INFO L128 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2018-01-20 22:26:25,598 INFO L128 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2018-01-20 22:26:25,598 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-20 22:26:25,598 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-20 22:26:25,598 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-20 22:26:25,598 INFO L128 BoogieDeclarations]: Found specification of procedure malloc [2018-01-20 22:26:25,599 INFO L128 BoogieDeclarations]: Found specification of procedure free [2018-01-20 22:26:25,599 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-20 22:26:25,599 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_error [2018-01-20 22:26:25,599 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-20 22:26:25,599 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-20 22:26:25,599 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-20 22:26:26,045 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-20 22:26:26,045 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.01 10:26:26 BoogieIcfgContainer [2018-01-20 22:26:26,046 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-20 22:26:26,047 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-20 22:26:26,047 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-20 22:26:26,048 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-20 22:26:26,049 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.01 10:26:25" (1/3) ... [2018-01-20 22:26:26,049 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@37f8562f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.01 10:26:26, skipping insertion in model container [2018-01-20 22:26:26,050 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25" (2/3) ... [2018-01-20 22:26:26,050 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@37f8562f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.01 10:26:26, skipping insertion in model container [2018-01-20 22:26:26,050 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.01 10:26:26" (3/3) ... [2018-01-20 22:26:26,051 INFO L105 eAbstractionObserver]: Analyzing ICFG dll-01_true-unreach-call_true-valid-memsafety.i [2018-01-20 22:26:26,058 INFO L130 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-20 22:26:26,065 INFO L142 ceAbstractionStarter]: Appying trace abstraction to program that has 3 error locations. [2018-01-20 22:26:26,106 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 22:26:26,106 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 22:26:26,106 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 22:26:26,106 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 22:26:26,107 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 22:26:26,107 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 22:26:26,107 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 22:26:26,107 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.initErr0EnsuresViolation======== [2018-01-20 22:26:26,107 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 22:26:26,125 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states. [2018-01-20 22:26:26,130 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2018-01-20 22:26:26,130 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:26,131 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1] [2018-01-20 22:26:26,131 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.initErr0EnsuresViolation]=== [2018-01-20 22:26:26,135 INFO L82 PathProgramCache]: Analyzing trace with hash 396895, now seen corresponding path program 1 times [2018-01-20 22:26:26,136 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:26,137 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:26,178 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:26,178 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:26,178 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:26,206 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 22:26:26,212 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 22:26:26,229 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-20 22:26:26,235 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 22:26:26,244 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 22:26:26,244 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 22:26:26,244 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 22:26:26,244 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 22:26:26,244 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 22:26:26,245 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 22:26:26,245 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 22:26:26,245 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.startErr0EnsuresViolation======== [2018-01-20 22:26:26,245 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 22:26:26,249 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states. [2018-01-20 22:26:26,252 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-01-20 22:26:26,252 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:26,252 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:26,252 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:26:26,253 INFO L82 PathProgramCache]: Analyzing trace with hash -1539010196, now seen corresponding path program 1 times [2018-01-20 22:26:26,253 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:26,253 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:26,254 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:26,254 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:26,254 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:26,273 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:26,284 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:26,427 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:26:26,429 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:26:26,430 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-20 22:26:26,431 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-20 22:26:26,441 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-20 22:26:26,442 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 22:26:26,444 INFO L87 Difference]: Start difference. First operand 127 states. Second operand 2 states. [2018-01-20 22:26:26,475 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:26,475 INFO L93 Difference]: Finished difference Result 244 states and 348 transitions. [2018-01-20 22:26:26,475 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-20 22:26:26,476 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 24 [2018-01-20 22:26:26,477 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:26,487 INFO L225 Difference]: With dead ends: 244 [2018-01-20 22:26:26,488 INFO L226 Difference]: Without dead ends: 124 [2018-01-20 22:26:26,491 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 22:26:26,504 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2018-01-20 22:26:26,526 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 124. [2018-01-20 22:26:26,527 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 124 states. [2018-01-20 22:26:26,529 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 124 states to 124 states and 133 transitions. [2018-01-20 22:26:26,531 INFO L78 Accepts]: Start accepts. Automaton has 124 states and 133 transitions. Word has length 24 [2018-01-20 22:26:26,532 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:26,532 INFO L432 AbstractCegarLoop]: Abstraction has 124 states and 133 transitions. [2018-01-20 22:26:26,532 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-20 22:26:26,532 INFO L276 IsEmpty]: Start isEmpty. Operand 124 states and 133 transitions. [2018-01-20 22:26:26,534 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2018-01-20 22:26:26,534 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:26,534 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:26,534 INFO L371 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:26:26,534 INFO L82 PathProgramCache]: Analyzing trace with hash 849242386, now seen corresponding path program 1 times [2018-01-20 22:26:26,535 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:26,535 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:26,536 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:26,536 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:26,536 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:26,563 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:26,564 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:26,698 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:26:26,699 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:26:26,699 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-20 22:26:26,701 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-20 22:26:26,701 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-20 22:26:26,701 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-20 22:26:26,702 INFO L87 Difference]: Start difference. First operand 124 states and 133 transitions. Second operand 5 states. [2018-01-20 22:26:27,083 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:27,083 INFO L93 Difference]: Finished difference Result 287 states and 310 transitions. [2018-01-20 22:26:27,084 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-20 22:26:27,084 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 37 [2018-01-20 22:26:27,084 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:27,090 INFO L225 Difference]: With dead ends: 287 [2018-01-20 22:26:27,090 INFO L226 Difference]: Without dead ends: 192 [2018-01-20 22:26:27,091 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2018-01-20 22:26:27,092 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 192 states. [2018-01-20 22:26:27,102 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 192 to 128. [2018-01-20 22:26:27,102 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 128 states. [2018-01-20 22:26:27,104 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 128 states to 128 states and 137 transitions. [2018-01-20 22:26:27,104 INFO L78 Accepts]: Start accepts. Automaton has 128 states and 137 transitions. Word has length 37 [2018-01-20 22:26:27,105 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:27,105 INFO L432 AbstractCegarLoop]: Abstraction has 128 states and 137 transitions. [2018-01-20 22:26:27,105 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-20 22:26:27,105 INFO L276 IsEmpty]: Start isEmpty. Operand 128 states and 137 transitions. [2018-01-20 22:26:27,106 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2018-01-20 22:26:27,106 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:27,107 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:27,107 INFO L371 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:26:27,107 INFO L82 PathProgramCache]: Analyzing trace with hash -1513386891, now seen corresponding path program 1 times [2018-01-20 22:26:27,107 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:27,107 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:27,108 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:27,108 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:27,109 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:27,128 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:27,128 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:27,203 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:26:27,203 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:26:27,203 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-20 22:26:27,204 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-20 22:26:27,204 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-20 22:26:27,204 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-20 22:26:27,205 INFO L87 Difference]: Start difference. First operand 128 states and 137 transitions. Second operand 5 states. [2018-01-20 22:26:27,348 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:27,348 INFO L93 Difference]: Finished difference Result 213 states and 229 transitions. [2018-01-20 22:26:27,348 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-20 22:26:27,349 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 39 [2018-01-20 22:26:27,349 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:27,352 INFO L225 Difference]: With dead ends: 213 [2018-01-20 22:26:27,352 INFO L226 Difference]: Without dead ends: 186 [2018-01-20 22:26:27,353 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2018-01-20 22:26:27,353 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 186 states. [2018-01-20 22:26:27,363 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 186 to 132. [2018-01-20 22:26:27,363 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 132 states. [2018-01-20 22:26:27,365 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 132 states to 132 states and 141 transitions. [2018-01-20 22:26:27,365 INFO L78 Accepts]: Start accepts. Automaton has 132 states and 141 transitions. Word has length 39 [2018-01-20 22:26:27,365 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:27,365 INFO L432 AbstractCegarLoop]: Abstraction has 132 states and 141 transitions. [2018-01-20 22:26:27,366 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-20 22:26:27,366 INFO L276 IsEmpty]: Start isEmpty. Operand 132 states and 141 transitions. [2018-01-20 22:26:27,368 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2018-01-20 22:26:27,368 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:27,368 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:27,368 INFO L371 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:26:27,369 INFO L82 PathProgramCache]: Analyzing trace with hash 1547435689, now seen corresponding path program 1 times [2018-01-20 22:26:27,369 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:27,369 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:27,370 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:27,370 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:27,370 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:27,394 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 22:26:27,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 22:26:27,432 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-20 22:26:27,443 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 22:26:27,451 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 22:26:27,452 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 22:26:27,470 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 22:26:27,470 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 22:26:27,470 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 22:26:27,470 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 22:26:27,471 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 22:26:27,471 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 22:26:27,471 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 22:26:27,471 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == mainErr0EnsuresViolation======== [2018-01-20 22:26:27,471 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 22:26:27,473 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states. [2018-01-20 22:26:27,474 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2018-01-20 22:26:27,474 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:27,474 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:27,475 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr0EnsuresViolation]=== [2018-01-20 22:26:27,475 INFO L82 PathProgramCache]: Analyzing trace with hash 565995656, now seen corresponding path program 1 times [2018-01-20 22:26:27,475 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:27,475 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:27,476 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:27,476 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:27,476 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:27,482 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:27,483 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:27,491 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:26:27,491 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:26:27,492 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-20 22:26:27,492 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-20 22:26:27,492 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-20 22:26:27,492 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 22:26:27,492 INFO L87 Difference]: Start difference. First operand 127 states. Second operand 2 states. [2018-01-20 22:26:27,498 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:27,499 INFO L93 Difference]: Finished difference Result 244 states and 348 transitions. [2018-01-20 22:26:27,499 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-20 22:26:27,499 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 22 [2018-01-20 22:26:27,499 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:27,500 INFO L225 Difference]: With dead ends: 244 [2018-01-20 22:26:27,501 INFO L226 Difference]: Without dead ends: 122 [2018-01-20 22:26:27,501 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 22:26:27,502 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2018-01-20 22:26:27,508 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 122. [2018-01-20 22:26:27,508 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 122 states. [2018-01-20 22:26:27,509 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 131 transitions. [2018-01-20 22:26:27,510 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 131 transitions. Word has length 22 [2018-01-20 22:26:27,510 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:27,510 INFO L432 AbstractCegarLoop]: Abstraction has 122 states and 131 transitions. [2018-01-20 22:26:27,510 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-20 22:26:27,510 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 131 transitions. [2018-01-20 22:26:27,511 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2018-01-20 22:26:27,511 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:27,512 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:27,512 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr0EnsuresViolation]=== [2018-01-20 22:26:27,512 INFO L82 PathProgramCache]: Analyzing trace with hash -673975890, now seen corresponding path program 1 times [2018-01-20 22:26:27,512 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:27,512 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:27,513 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:27,513 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:27,514 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:27,524 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:27,525 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:27,579 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:26:27,579 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:26:27,579 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-20 22:26:27,579 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-20 22:26:27,579 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-20 22:26:27,579 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-20 22:26:27,580 INFO L87 Difference]: Start difference. First operand 122 states and 131 transitions. Second operand 5 states. [2018-01-20 22:26:27,753 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:27,753 INFO L93 Difference]: Finished difference Result 283 states and 305 transitions. [2018-01-20 22:26:27,754 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-20 22:26:27,754 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 35 [2018-01-20 22:26:27,754 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:27,755 INFO L225 Difference]: With dead ends: 283 [2018-01-20 22:26:27,755 INFO L226 Difference]: Without dead ends: 190 [2018-01-20 22:26:27,756 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2018-01-20 22:26:27,756 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 190 states. [2018-01-20 22:26:27,761 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 190 to 126. [2018-01-20 22:26:27,761 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 126 states. [2018-01-20 22:26:27,763 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 126 states to 126 states and 135 transitions. [2018-01-20 22:26:27,763 INFO L78 Accepts]: Start accepts. Automaton has 126 states and 135 transitions. Word has length 35 [2018-01-20 22:26:27,763 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:27,764 INFO L432 AbstractCegarLoop]: Abstraction has 126 states and 135 transitions. [2018-01-20 22:26:27,764 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-20 22:26:27,764 INFO L276 IsEmpty]: Start isEmpty. Operand 126 states and 135 transitions. [2018-01-20 22:26:27,765 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2018-01-20 22:26:27,766 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:27,766 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:27,766 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr0EnsuresViolation]=== [2018-01-20 22:26:27,766 INFO L82 PathProgramCache]: Analyzing trace with hash 1839763921, now seen corresponding path program 1 times [2018-01-20 22:26:27,767 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:27,767 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:27,768 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:27,768 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:27,768 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:27,780 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:27,781 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:27,833 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:26:27,833 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:26:27,834 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-20 22:26:27,834 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-20 22:26:27,834 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-20 22:26:27,834 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-20 22:26:27,835 INFO L87 Difference]: Start difference. First operand 126 states and 135 transitions. Second operand 5 states. [2018-01-20 22:26:28,022 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:28,022 INFO L93 Difference]: Finished difference Result 209 states and 225 transitions. [2018-01-20 22:26:28,023 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-20 22:26:28,023 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 37 [2018-01-20 22:26:28,023 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:28,024 INFO L225 Difference]: With dead ends: 209 [2018-01-20 22:26:28,025 INFO L226 Difference]: Without dead ends: 184 [2018-01-20 22:26:28,025 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2018-01-20 22:26:28,026 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2018-01-20 22:26:28,032 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 130. [2018-01-20 22:26:28,032 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 130 states. [2018-01-20 22:26:28,033 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 130 states to 130 states and 139 transitions. [2018-01-20 22:26:28,033 INFO L78 Accepts]: Start accepts. Automaton has 130 states and 139 transitions. Word has length 37 [2018-01-20 22:26:28,034 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:28,034 INFO L432 AbstractCegarLoop]: Abstraction has 130 states and 139 transitions. [2018-01-20 22:26:28,034 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-20 22:26:28,034 INFO L276 IsEmpty]: Start isEmpty. Operand 130 states and 139 transitions. [2018-01-20 22:26:28,035 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2018-01-20 22:26:28,035 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:28,035 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:28,035 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr0EnsuresViolation]=== [2018-01-20 22:26:28,036 INFO L82 PathProgramCache]: Analyzing trace with hash 171442437, now seen corresponding path program 1 times [2018-01-20 22:26:28,036 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:28,036 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:28,037 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:28,037 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:28,037 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:28,054 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:28,054 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:28,209 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-20 22:26:28,210 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:26:28,210 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 22:26:28,219 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:28,255 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:28,262 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:26:28,384 WARN L1029 $PredicateComparison]: unable to prove that (exists ((main_~list~5.base Int)) (and (= 0 (select |c_old(#valid)| main_~list~5.base)) (= |c_#valid| (store |c_old(#valid)| main_~list~5.base 0)) (not (= 0 main_~list~5.base)))) is different from true [2018-01-20 22:26:28,418 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 2 not checked. [2018-01-20 22:26:28,453 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:26:28,453 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 6] total 8 [2018-01-20 22:26:28,454 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-20 22:26:28,454 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-20 22:26:28,454 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=43, Unknown=1, NotChecked=12, Total=72 [2018-01-20 22:26:28,455 INFO L87 Difference]: Start difference. First operand 130 states and 139 transitions. Second operand 9 states. [2018-01-20 22:26:28,830 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:28,830 INFO L93 Difference]: Finished difference Result 214 states and 229 transitions. [2018-01-20 22:26:28,831 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-01-20 22:26:28,831 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 57 [2018-01-20 22:26:28,831 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:28,833 INFO L225 Difference]: With dead ends: 214 [2018-01-20 22:26:28,833 INFO L226 Difference]: Without dead ends: 211 [2018-01-20 22:26:28,833 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 56 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 1 IntricatePredicates, 1 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=45, Invalid=114, Unknown=1, NotChecked=22, Total=182 [2018-01-20 22:26:28,834 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 211 states. [2018-01-20 22:26:28,843 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 211 to 178. [2018-01-20 22:26:28,843 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 178 states. [2018-01-20 22:26:28,844 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 178 states to 178 states and 192 transitions. [2018-01-20 22:26:28,845 INFO L78 Accepts]: Start accepts. Automaton has 178 states and 192 transitions. Word has length 57 [2018-01-20 22:26:28,845 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:28,845 INFO L432 AbstractCegarLoop]: Abstraction has 178 states and 192 transitions. [2018-01-20 22:26:28,845 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-20 22:26:28,846 INFO L276 IsEmpty]: Start isEmpty. Operand 178 states and 192 transitions. [2018-01-20 22:26:28,847 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2018-01-20 22:26:28,847 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:28,847 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:28,848 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr0EnsuresViolation]=== [2018-01-20 22:26:28,848 INFO L82 PathProgramCache]: Analyzing trace with hash -1525904848, now seen corresponding path program 1 times [2018-01-20 22:26:28,848 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:28,848 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:28,849 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:28,849 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:28,850 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:28,875 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:28,876 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:28,998 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-20 22:26:28,998 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:26:28,998 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-20 22:26:28,999 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-20 22:26:28,999 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-20 22:26:28,999 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2018-01-20 22:26:28,999 INFO L87 Difference]: Start difference. First operand 178 states and 192 transitions. Second operand 7 states. [2018-01-20 22:26:29,252 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:29,253 INFO L93 Difference]: Finished difference Result 273 states and 294 transitions. [2018-01-20 22:26:29,253 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-20 22:26:29,253 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 62 [2018-01-20 22:26:29,253 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:29,254 INFO L225 Difference]: With dead ends: 273 [2018-01-20 22:26:29,254 INFO L226 Difference]: Without dead ends: 248 [2018-01-20 22:26:29,255 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=32, Invalid=78, Unknown=0, NotChecked=0, Total=110 [2018-01-20 22:26:29,255 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 248 states. [2018-01-20 22:26:29,263 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 248 to 220. [2018-01-20 22:26:29,263 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 220 states. [2018-01-20 22:26:29,264 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 220 states to 220 states and 238 transitions. [2018-01-20 22:26:29,265 INFO L78 Accepts]: Start accepts. Automaton has 220 states and 238 transitions. Word has length 62 [2018-01-20 22:26:29,265 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:29,265 INFO L432 AbstractCegarLoop]: Abstraction has 220 states and 238 transitions. [2018-01-20 22:26:29,265 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-20 22:26:29,265 INFO L276 IsEmpty]: Start isEmpty. Operand 220 states and 238 transitions. [2018-01-20 22:26:29,266 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2018-01-20 22:26:29,266 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:29,266 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:29,266 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr0EnsuresViolation]=== [2018-01-20 22:26:29,267 INFO L82 PathProgramCache]: Analyzing trace with hash 628326227, now seen corresponding path program 1 times [2018-01-20 22:26:29,267 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:29,267 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:29,268 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:29,268 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:29,268 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:29,286 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:29,287 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:29,519 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-01-20 22:26:29,519 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:26:29,520 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2018-01-20 22:26:29,520 INFO L409 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-01-20 22:26:29,520 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-01-20 22:26:29,520 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2018-01-20 22:26:29,521 INFO L87 Difference]: Start difference. First operand 220 states and 238 transitions. Second operand 11 states. [2018-01-20 22:26:30,142 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:30,143 INFO L93 Difference]: Finished difference Result 441 states and 474 transitions. [2018-01-20 22:26:30,143 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-01-20 22:26:30,143 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 64 [2018-01-20 22:26:30,143 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:30,145 INFO L225 Difference]: With dead ends: 441 [2018-01-20 22:26:30,145 INFO L226 Difference]: Without dead ends: 342 [2018-01-20 22:26:30,146 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=98, Invalid=244, Unknown=0, NotChecked=0, Total=342 [2018-01-20 22:26:30,146 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 342 states. [2018-01-20 22:26:30,158 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 342 to 215. [2018-01-20 22:26:30,158 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 215 states. [2018-01-20 22:26:30,159 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 215 states to 215 states and 232 transitions. [2018-01-20 22:26:30,159 INFO L78 Accepts]: Start accepts. Automaton has 215 states and 232 transitions. Word has length 64 [2018-01-20 22:26:30,159 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:30,159 INFO L432 AbstractCegarLoop]: Abstraction has 215 states and 232 transitions. [2018-01-20 22:26:30,159 INFO L433 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-01-20 22:26:30,160 INFO L276 IsEmpty]: Start isEmpty. Operand 215 states and 232 transitions. [2018-01-20 22:26:30,160 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2018-01-20 22:26:30,160 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:30,160 INFO L322 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:30,161 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr0EnsuresViolation]=== [2018-01-20 22:26:30,161 INFO L82 PathProgramCache]: Analyzing trace with hash -135358828, now seen corresponding path program 2 times [2018-01-20 22:26:30,161 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:30,161 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:30,162 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:30,162 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:30,162 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:30,172 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:30,173 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:30,356 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 11 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:26:30,356 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:26:30,357 INFO L209 onRefinementStrategy]: 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-01-20 22:26:30,367 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-20 22:26:30,383 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-20 22:26:30,395 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-20 22:26:30,398 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-20 22:26:30,402 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:26:30,477 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2018-01-20 22:26:30,480 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 3 [2018-01-20 22:26:30,481 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:30,482 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:30,483 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:30,483 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:15, output treesize:3 [2018-01-20 22:26:30,524 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 5 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:26:30,546 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:26:30,546 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2018-01-20 22:26:30,547 INFO L409 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-01-20 22:26:30,547 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-01-20 22:26:30,547 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=227, Unknown=0, NotChecked=0, Total=272 [2018-01-20 22:26:30,548 INFO L87 Difference]: Start difference. First operand 215 states and 232 transitions. Second operand 17 states. [2018-01-20 22:26:30,974 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:30,974 INFO L93 Difference]: Finished difference Result 393 states and 425 transitions. [2018-01-20 22:26:30,975 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-01-20 22:26:30,975 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 66 [2018-01-20 22:26:30,975 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:30,976 INFO L225 Difference]: With dead ends: 393 [2018-01-20 22:26:30,976 INFO L226 Difference]: Without dead ends: 296 [2018-01-20 22:26:30,977 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 60 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 62 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=82, Invalid=380, Unknown=0, NotChecked=0, Total=462 [2018-01-20 22:26:30,977 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 296 states. [2018-01-20 22:26:30,987 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 296 to 218. [2018-01-20 22:26:30,987 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 218 states. [2018-01-20 22:26:30,988 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 218 states to 218 states and 233 transitions. [2018-01-20 22:26:30,988 INFO L78 Accepts]: Start accepts. Automaton has 218 states and 233 transitions. Word has length 66 [2018-01-20 22:26:30,989 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:30,989 INFO L432 AbstractCegarLoop]: Abstraction has 218 states and 233 transitions. [2018-01-20 22:26:30,989 INFO L433 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-01-20 22:26:30,989 INFO L276 IsEmpty]: Start isEmpty. Operand 218 states and 233 transitions. [2018-01-20 22:26:30,990 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2018-01-20 22:26:30,990 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:30,990 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:30,990 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr0EnsuresViolation]=== [2018-01-20 22:26:30,991 INFO L82 PathProgramCache]: Analyzing trace with hash -1992096144, now seen corresponding path program 1 times [2018-01-20 22:26:30,991 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:30,991 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:30,992 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:30,992 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-20 22:26:30,992 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:31,000 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:31,002 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:31,169 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-20 22:26:31,169 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:26:31,169 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-20 22:26:31,170 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-20 22:26:31,170 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-20 22:26:31,170 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2018-01-20 22:26:31,170 INFO L87 Difference]: Start difference. First operand 218 states and 233 transitions. Second operand 7 states. [2018-01-20 22:26:31,343 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:31,343 INFO L93 Difference]: Finished difference Result 294 states and 311 transitions. [2018-01-20 22:26:31,343 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-20 22:26:31,343 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 70 [2018-01-20 22:26:31,344 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:31,345 INFO L225 Difference]: With dead ends: 294 [2018-01-20 22:26:31,345 INFO L226 Difference]: Without dead ends: 236 [2018-01-20 22:26:31,346 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=76, Unknown=0, NotChecked=0, Total=110 [2018-01-20 22:26:31,346 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 236 states. [2018-01-20 22:26:31,359 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 236 to 224. [2018-01-20 22:26:31,359 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 224 states. [2018-01-20 22:26:31,361 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 224 states to 224 states and 239 transitions. [2018-01-20 22:26:31,361 INFO L78 Accepts]: Start accepts. Automaton has 224 states and 239 transitions. Word has length 70 [2018-01-20 22:26:31,361 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:31,361 INFO L432 AbstractCegarLoop]: Abstraction has 224 states and 239 transitions. [2018-01-20 22:26:31,362 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-20 22:26:31,362 INFO L276 IsEmpty]: Start isEmpty. Operand 224 states and 239 transitions. [2018-01-20 22:26:31,363 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2018-01-20 22:26:31,363 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:31,363 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:31,363 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr0EnsuresViolation]=== [2018-01-20 22:26:31,363 INFO L82 PathProgramCache]: Analyzing trace with hash -938083547, now seen corresponding path program 1 times [2018-01-20 22:26:31,364 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:31,364 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:31,365 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:31,365 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:31,365 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:31,383 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:31,384 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:32,263 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-20 22:26:32,264 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:26:32,264 INFO L209 onRefinementStrategy]: 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-01-20 22:26:32,269 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:32,288 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:32,292 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:26:32,399 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 15 [2018-01-20 22:26:32,401 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 3 [2018-01-20 22:26:32,401 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:32,402 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:32,403 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:32,403 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:19, output treesize:3 [2018-01-20 22:26:32,459 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:26:32,479 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:26:32,479 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 9] total 22 [2018-01-20 22:26:32,480 INFO L409 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-01-20 22:26:32,480 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-01-20 22:26:32,480 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=417, Unknown=0, NotChecked=0, Total=462 [2018-01-20 22:26:32,480 INFO L87 Difference]: Start difference. First operand 224 states and 239 transitions. Second operand 22 states. [2018-01-20 22:26:34,664 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:34,665 INFO L93 Difference]: Finished difference Result 428 states and 454 transitions. [2018-01-20 22:26:34,665 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-01-20 22:26:34,665 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 75 [2018-01-20 22:26:34,665 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:34,666 INFO L225 Difference]: With dead ends: 428 [2018-01-20 22:26:34,666 INFO L226 Difference]: Without dead ends: 275 [2018-01-20 22:26:34,667 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 77 SyntacticMatches, 3 SemanticMatches, 57 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 673 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=366, Invalid=3056, Unknown=0, NotChecked=0, Total=3422 [2018-01-20 22:26:34,668 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 275 states. [2018-01-20 22:26:34,675 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 275 to 226. [2018-01-20 22:26:34,675 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 226 states. [2018-01-20 22:26:34,676 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 226 states to 226 states and 243 transitions. [2018-01-20 22:26:34,676 INFO L78 Accepts]: Start accepts. Automaton has 226 states and 243 transitions. Word has length 75 [2018-01-20 22:26:34,676 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:34,676 INFO L432 AbstractCegarLoop]: Abstraction has 226 states and 243 transitions. [2018-01-20 22:26:34,676 INFO L433 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-01-20 22:26:34,677 INFO L276 IsEmpty]: Start isEmpty. Operand 226 states and 243 transitions. [2018-01-20 22:26:34,677 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2018-01-20 22:26:34,677 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:34,677 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:34,677 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr0EnsuresViolation]=== [2018-01-20 22:26:34,678 INFO L82 PathProgramCache]: Analyzing trace with hash -670239325, now seen corresponding path program 1 times [2018-01-20 22:26:34,678 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:34,678 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:34,678 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:34,678 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:34,678 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:34,687 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:34,688 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:34,763 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-01-20 22:26:34,764 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:26:34,764 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-20 22:26:34,764 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-20 22:26:34,764 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-20 22:26:34,764 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-20 22:26:34,764 INFO L87 Difference]: Start difference. First operand 226 states and 243 transitions. Second operand 5 states. [2018-01-20 22:26:34,897 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:34,897 INFO L93 Difference]: Finished difference Result 429 states and 464 transitions. [2018-01-20 22:26:34,897 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-20 22:26:34,897 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 83 [2018-01-20 22:26:34,898 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:34,899 INFO L225 Difference]: With dead ends: 429 [2018-01-20 22:26:34,899 INFO L226 Difference]: Without dead ends: 242 [2018-01-20 22:26:34,900 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2018-01-20 22:26:34,900 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 242 states. [2018-01-20 22:26:34,907 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 242 to 230. [2018-01-20 22:26:34,907 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 230 states. [2018-01-20 22:26:34,909 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 230 states to 230 states and 247 transitions. [2018-01-20 22:26:34,909 INFO L78 Accepts]: Start accepts. Automaton has 230 states and 247 transitions. Word has length 83 [2018-01-20 22:26:34,909 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:34,909 INFO L432 AbstractCegarLoop]: Abstraction has 230 states and 247 transitions. [2018-01-20 22:26:34,909 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-20 22:26:34,910 INFO L276 IsEmpty]: Start isEmpty. Operand 230 states and 247 transitions. [2018-01-20 22:26:34,910 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 86 [2018-01-20 22:26:34,911 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:34,911 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:34,911 INFO L371 AbstractCegarLoop]: === Iteration 11 === [mainErr0EnsuresViolation]=== [2018-01-20 22:26:34,911 INFO L82 PathProgramCache]: Analyzing trace with hash 1776602016, now seen corresponding path program 1 times [2018-01-20 22:26:34,911 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:34,911 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:34,912 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:34,912 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:34,912 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:34,928 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:34,929 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:35,243 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-20 22:26:35,243 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:26:35,243 INFO L209 onRefinementStrategy]: 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-01-20 22:26:35,248 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:35,278 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:35,284 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:26:35,288 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-20 22:26:35,288 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:35,296 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:35,296 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:6, output treesize:5 [2018-01-20 22:26:35,337 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:35,338 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:35,341 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-20 22:26:35,342 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:35,348 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:35,348 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:17, output treesize:11 [2018-01-20 22:26:35,386 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:26:35,388 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:26:35,388 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:35,390 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:35,395 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:35,395 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:22, output treesize:15 [2018-01-20 22:26:35,432 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:35,435 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 34 [2018-01-20 22:26:35,439 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-01-20 22:26:35,439 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:35,449 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:35,456 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:26:35,457 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:28 [2018-01-20 22:26:35,563 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:35,568 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 24 [2018-01-20 22:26:35,571 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 15 [2018-01-20 22:26:35,572 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:35,588 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:35,620 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 55 treesize of output 46 [2018-01-20 22:26:35,636 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 16 treesize of output 31 [2018-01-20 22:26:35,638 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 2 xjuncts. [2018-01-20 22:26:35,654 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:26:35,672 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-01-20 22:26:35,673 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:58, output treesize:108 [2018-01-20 22:26:35,767 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 97 treesize of output 84 [2018-01-20 22:26:35,771 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:35,772 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 47 [2018-01-20 22:26:35,773 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:35,792 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:35,831 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 89 treesize of output 79 [2018-01-20 22:26:35,834 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:35,835 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 47 [2018-01-20 22:26:35,835 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:35,845 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:35,876 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 97 treesize of output 87 [2018-01-20 22:26:35,879 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:35,880 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 47 [2018-01-20 22:26:35,880 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:35,891 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:35,918 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 89 treesize of output 76 [2018-01-20 22:26:35,921 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:35,922 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 47 [2018-01-20 22:26:35,922 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:35,930 INFO L267 ElimStorePlain]: Start of recursive call 8: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:35,949 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:26:35,950 INFO L202 ElimStorePlain]: Needed 9 recursive calls to eliminate 4 variables, input treesize:195, output treesize:163 [2018-01-20 22:26:36,009 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 95 treesize of output 75 [2018-01-20 22:26:36,015 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 29 [2018-01-20 22:26:36,056 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,066 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:36,066 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 14 [2018-01-20 22:26:36,066 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,073 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,092 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 44 treesize of output 32 [2018-01-20 22:26:36,096 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:36,097 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 10 [2018-01-20 22:26:36,097 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,102 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 4 [2018-01-20 22:26:36,102 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,104 INFO L267 ElimStorePlain]: Start of recursive call 5: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,120 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 95 treesize of output 73 [2018-01-20 22:26:36,124 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 46 treesize of output 33 [2018-01-20 22:26:36,125 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,138 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:36,139 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 14 [2018-01-20 22:26:36,139 INFO L267 ElimStorePlain]: Start of recursive call 10: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,146 INFO L267 ElimStorePlain]: Start of recursive call 8: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,157 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 30 [2018-01-20 22:26:36,159 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 13 [2018-01-20 22:26:36,159 INFO L267 ElimStorePlain]: Start of recursive call 12: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,165 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:36,165 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 6 [2018-01-20 22:26:36,165 INFO L267 ElimStorePlain]: Start of recursive call 13: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,169 INFO L267 ElimStorePlain]: Start of recursive call 11: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,174 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 4 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:26:36,174 INFO L202 ElimStorePlain]: Needed 13 recursive calls to eliminate 6 variables, input treesize:191, output treesize:9 [2018-01-20 22:26:36,269 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-20 22:26:36,290 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:26:36,290 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 29 [2018-01-20 22:26:36,291 INFO L409 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-01-20 22:26:36,291 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-01-20 22:26:36,291 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=740, Unknown=0, NotChecked=0, Total=812 [2018-01-20 22:26:36,291 INFO L87 Difference]: Start difference. First operand 230 states and 247 transitions. Second operand 29 states. [2018-01-20 22:26:38,390 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:38,391 INFO L93 Difference]: Finished difference Result 518 states and 557 transitions. [2018-01-20 22:26:38,391 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2018-01-20 22:26:38,391 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 85 [2018-01-20 22:26:38,391 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:38,393 INFO L225 Difference]: With dead ends: 518 [2018-01-20 22:26:38,393 INFO L226 Difference]: Without dead ends: 486 [2018-01-20 22:26:38,394 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 72 SyntacticMatches, 3 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 575 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=471, Invalid=2721, Unknown=0, NotChecked=0, Total=3192 [2018-01-20 22:26:38,394 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 486 states. [2018-01-20 22:26:38,413 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 486 to 375. [2018-01-20 22:26:38,413 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 375 states. [2018-01-20 22:26:38,414 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 375 states to 375 states and 404 transitions. [2018-01-20 22:26:38,414 INFO L78 Accepts]: Start accepts. Automaton has 375 states and 404 transitions. Word has length 85 [2018-01-20 22:26:38,414 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:38,414 INFO L432 AbstractCegarLoop]: Abstraction has 375 states and 404 transitions. [2018-01-20 22:26:38,414 INFO L433 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-01-20 22:26:38,414 INFO L276 IsEmpty]: Start isEmpty. Operand 375 states and 404 transitions. [2018-01-20 22:26:38,416 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2018-01-20 22:26:38,416 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:38,416 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:38,416 INFO L371 AbstractCegarLoop]: === Iteration 12 === [mainErr0EnsuresViolation]=== [2018-01-20 22:26:38,416 INFO L82 PathProgramCache]: Analyzing trace with hash 2030876237, now seen corresponding path program 1 times [2018-01-20 22:26:38,416 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:38,416 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:38,417 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:38,417 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:38,418 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:38,455 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:38,456 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:39,503 WARN L146 SmtUtils]: Spent 210ms on a formula simplification. DAG size of input: 99 DAG size of output 57 [2018-01-20 22:26:39,802 WARN L146 SmtUtils]: Spent 137ms on a formula simplification. DAG size of input: 68 DAG size of output 57 [2018-01-20 22:26:40,069 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-20 22:26:40,070 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:26:40,070 INFO L209 onRefinementStrategy]: 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-01-20 22:26:40,075 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:40,104 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:40,108 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:26:40,113 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-20 22:26:40,114 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,116 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,116 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:6, output treesize:5 [2018-01-20 22:26:40,174 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:40,175 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:40,176 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 21 [2018-01-20 22:26:40,176 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,183 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,183 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:27, output treesize:25 [2018-01-20 22:26:40,212 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:26:40,214 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:26:40,214 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,215 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,222 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,222 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:37 [2018-01-20 22:26:40,282 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:40,285 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 47 treesize of output 51 [2018-01-20 22:26:40,287 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-01-20 22:26:40,287 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,293 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,301 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:26:40,301 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:58, output treesize:50 [2018-01-20 22:26:40,415 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 57 treesize of output 52 [2018-01-20 22:26:40,425 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 16 treesize of output 23 [2018-01-20 22:26:40,425 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-20 22:26:40,443 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:26:40,464 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-01-20 22:26:40,464 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:62, output treesize:100 [2018-01-20 22:26:40,519 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:40,519 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:40,520 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:40,520 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 5 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 21 [2018-01-20 22:26:40,521 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,527 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,527 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:50, output treesize:43 [2018-01-20 22:26:40,560 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:40,563 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 52 treesize of output 51 [2018-01-20 22:26:40,566 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:40,567 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 23 [2018-01-20 22:26:40,568 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,578 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,587 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,587 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:56, output treesize:55 [2018-01-20 22:26:40,656 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:40,663 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 78 treesize of output 86 [2018-01-20 22:26:40,675 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-01-20 22:26:40,676 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,723 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,732 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:26:40,732 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:78, output treesize:68 [2018-01-20 22:26:40,836 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 110 treesize of output 79 [2018-01-20 22:26:40,842 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 37 [2018-01-20 22:26:40,842 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,856 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,866 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 3 dim-0 vars, and 1 xjuncts. [2018-01-20 22:26:40,866 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:110, output treesize:96 [2018-01-20 22:26:44,980 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 103 treesize of output 60 [2018-01-20 22:26:44,984 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:44,987 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 17 [2018-01-20 22:26:44,987 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:45,001 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 1 [2018-01-20 22:26:45,002 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:45,009 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 9 [2018-01-20 22:26:45,010 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:45,022 INFO L267 ElimStorePlain]: Start of recursive call 2: 3 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:45,026 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:45,026 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 5 variables, input treesize:103, output treesize:4 [2018-01-20 22:26:45,174 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-20 22:26:45,196 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:26:45,197 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 21] total 44 [2018-01-20 22:26:45,197 INFO L409 AbstractCegarLoop]: Interpolant automaton has 44 states [2018-01-20 22:26:45,197 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 44 interpolants. [2018-01-20 22:26:45,198 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=220, Invalid=1670, Unknown=2, NotChecked=0, Total=1892 [2018-01-20 22:26:45,198 INFO L87 Difference]: Start difference. First operand 375 states and 404 transitions. Second operand 44 states. [2018-01-20 22:26:46,696 WARN L146 SmtUtils]: Spent 107ms on a formula simplification. DAG size of input: 109 DAG size of output 58 [2018-01-20 22:26:46,846 WARN L146 SmtUtils]: Spent 109ms on a formula simplification. DAG size of input: 87 DAG size of output 58 [2018-01-20 22:26:47,012 WARN L146 SmtUtils]: Spent 124ms on a formula simplification. DAG size of input: 144 DAG size of output 60 [2018-01-20 22:26:53,327 WARN L146 SmtUtils]: Spent 6173ms on a formula simplification. DAG size of input: 165 DAG size of output 82 [2018-01-20 22:26:59,512 WARN L146 SmtUtils]: Spent 6144ms on a formula simplification. DAG size of input: 131 DAG size of output 80 [2018-01-20 22:27:05,752 WARN L146 SmtUtils]: Spent 6177ms on a formula simplification. DAG size of input: 174 DAG size of output 84 [2018-01-20 22:27:11,998 WARN L146 SmtUtils]: Spent 6176ms on a formula simplification. DAG size of input: 137 DAG size of output 87 [2018-01-20 22:27:14,325 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:27:14,326 INFO L93 Difference]: Finished difference Result 627 states and 674 transitions. [2018-01-20 22:27:14,326 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 52 states. [2018-01-20 22:27:14,326 INFO L78 Accepts]: Start accepts. Automaton has 44 states. Word has length 90 [2018-01-20 22:27:14,326 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:27:14,328 INFO L225 Difference]: With dead ends: 627 [2018-01-20 22:27:14,328 INFO L226 Difference]: Without dead ends: 592 [2018-01-20 22:27:14,329 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 162 GetRequests, 72 SyntacticMatches, 1 SemanticMatches, 89 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2466 ImplicationChecksByTransitivity, 33.1s TimeCoverageRelationStatistics Valid=1425, Invalid=6750, Unknown=15, NotChecked=0, Total=8190 [2018-01-20 22:27:14,330 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 592 states. [2018-01-20 22:27:14,350 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 592 to 387. [2018-01-20 22:27:14,350 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 387 states. [2018-01-20 22:27:14,352 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 387 states to 387 states and 417 transitions. [2018-01-20 22:27:14,352 INFO L78 Accepts]: Start accepts. Automaton has 387 states and 417 transitions. Word has length 90 [2018-01-20 22:27:14,352 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:27:14,352 INFO L432 AbstractCegarLoop]: Abstraction has 387 states and 417 transitions. [2018-01-20 22:27:14,352 INFO L433 AbstractCegarLoop]: Interpolant automaton has 44 states. [2018-01-20 22:27:14,352 INFO L276 IsEmpty]: Start isEmpty. Operand 387 states and 417 transitions. [2018-01-20 22:27:14,354 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2018-01-20 22:27:14,354 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:27:14,354 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:27:14,354 INFO L371 AbstractCegarLoop]: === Iteration 13 === [mainErr0EnsuresViolation]=== [2018-01-20 22:27:14,355 INFO L82 PathProgramCache]: Analyzing trace with hash -667837716, now seen corresponding path program 2 times [2018-01-20 22:27:14,355 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:27:14,355 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:27:14,356 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:27:14,356 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:27:14,356 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:27:14,377 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:27:14,379 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:27:15,986 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-01-20 22:27:15,986 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:27:15,986 INFO L209 onRefinementStrategy]: 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-01-20 22:27:15,991 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-20 22:27:16,003 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-20 22:27:16,015 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-20 22:27:16,018 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-20 22:27:16,022 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:27:16,143 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 44 treesize of output 41 [2018-01-20 22:27:16,145 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:27:16,145 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:16,152 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:16,155 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 44 treesize of output 41 [2018-01-20 22:27:16,156 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:27:16,156 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:16,164 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:16,185 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:27:16,185 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:89, output treesize:83 [2018-01-20 22:27:16,279 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:16,281 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 62 treesize of output 66 [2018-01-20 22:27:16,283 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-01-20 22:27:16,283 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:16,292 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:16,316 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:16,319 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 62 treesize of output 66 [2018-01-20 22:27:16,320 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-01-20 22:27:16,321 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:16,329 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:16,350 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-2 vars, End of recursive call: 2 dim-0 vars, and 2 xjuncts. [2018-01-20 22:27:16,351 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:125, output treesize:109 [2018-01-20 22:27:16,536 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:16,540 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 66 treesize of output 65 [2018-01-20 22:27:16,548 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 16 treesize of output 23 [2018-01-20 22:27:16,548 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-20 22:27:16,562 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:27:16,601 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:16,605 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 66 treesize of output 61 [2018-01-20 22:27:16,608 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:16,613 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 16 treesize of output 27 [2018-01-20 22:27:16,613 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 2 xjuncts. [2018-01-20 22:27:16,630 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:27:16,674 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-2 vars, End of recursive call: 2 dim-0 vars, and 4 xjuncts. [2018-01-20 22:27:16,675 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:133, output treesize:215 [2018-01-20 22:27:16,758 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:16,761 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 67 treesize of output 65 [2018-01-20 22:27:16,763 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:16,764 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 31 [2018-01-20 22:27:16,764 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:16,772 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:16,794 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:16,797 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 67 treesize of output 65 [2018-01-20 22:27:16,799 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:16,799 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 31 [2018-01-20 22:27:16,800 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:16,808 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:16,825 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-2 vars, End of recursive call: 2 dim-0 vars, and 2 xjuncts. [2018-01-20 22:27:16,826 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:135, output treesize:119 [2018-01-20 22:27:16,965 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:16,967 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 66 treesize of output 54 [2018-01-20 22:27:16,970 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 22 [2018-01-20 22:27:16,971 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:16,987 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:16,987 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 6 [2018-01-20 22:27:16,988 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:16,997 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:17,025 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:17,027 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 66 treesize of output 54 [2018-01-20 22:27:17,029 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:17,030 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 6 [2018-01-20 22:27:17,030 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:17,041 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 18 [2018-01-20 22:27:17,041 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:17,047 INFO L267 ElimStorePlain]: Start of recursive call 5: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:17,062 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:27:17,062 INFO L202 ElimStorePlain]: Needed 7 recursive calls to eliminate 4 variables, input treesize:133, output treesize:55 [2018-01-20 22:27:17,203 WARN L1029 $PredicateComparison]: unable to prove that (exists ((main_~list~5.base Int)) (let ((.cse0 (store |c_old(#valid)| main_~list~5.base 1))) (and (= (select .cse0 c_main_~end~5.base) 0) (= 0 (select |c_old(#valid)| main_~list~5.base)) (= |c_#valid| (store (store .cse0 c_main_~end~5.base 1) main_~list~5.base 0)) (not (= 0 main_~list~5.base))))) is different from true [2018-01-20 22:27:17,207 WARN L1029 $PredicateComparison]: unable to prove that (exists ((v_subst_1 Int)) (let ((.cse0 (store |c_old(#valid)| v_subst_1 1))) (and (= 0 (select |c_old(#valid)| v_subst_1)) (not (= 0 v_subst_1)) (= |c_#valid| (store (store .cse0 c_main_~list~5.base 1) v_subst_1 0)) (= (select .cse0 c_main_~list~5.base) 0)))) is different from true [2018-01-20 22:27:17,438 WARN L1029 $PredicateComparison]: unable to prove that (or (and (not (= c_main_~list~5.offset 0)) (exists ((v_prenex_15 Int)) (let ((.cse0 (store |c_old(#valid)| v_prenex_15 1))) (and (not (= 0 v_prenex_15)) (= 0 (select |c_old(#valid)| v_prenex_15)) (= |c_#valid| (store (store .cse0 c_main_~list~5.base 1) v_prenex_15 0)) (= (select .cse0 c_main_~list~5.base) 0))))) (and (exists ((v_subst_1 Int)) (let ((.cse1 (store |c_old(#valid)| v_subst_1 1))) (and (= 0 (select |c_old(#valid)| v_subst_1)) (not (= 0 v_subst_1)) (= |c_#valid| (store (store .cse1 c_main_~list~5.base 1) v_subst_1 0)) (= (select .cse1 c_main_~list~5.base) 0)))) (not (= 0 c_main_~list~5.base)))) is different from true [2018-01-20 22:27:17,450 WARN L1029 $PredicateComparison]: unable to prove that (exists ((main_~list~5.base Int) (v_subst_1 Int)) (let ((.cse0 (store |c_old(#valid)| v_subst_1 1))) (and (= 0 (select |c_old(#valid)| v_subst_1)) (not (= 0 v_subst_1)) (= |c_#valid| (store (store (store .cse0 main_~list~5.base 1) v_subst_1 0) main_~list~5.base 0)) (= (select .cse0 main_~list~5.base) 0) (not (= 0 main_~list~5.base))))) is different from true [2018-01-20 22:27:17,561 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 11 not checked. [2018-01-20 22:27:17,582 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:27:17,582 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 21] total 43 [2018-01-20 22:27:17,582 INFO L409 AbstractCegarLoop]: Interpolant automaton has 44 states [2018-01-20 22:27:17,583 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 44 interpolants. [2018-01-20 22:27:17,583 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=143, Invalid=1412, Unknown=21, NotChecked=316, Total=1892 [2018-01-20 22:27:17,583 INFO L87 Difference]: Start difference. First operand 387 states and 417 transitions. Second operand 44 states. [2018-01-20 22:27:20,427 WARN L146 SmtUtils]: Spent 116ms on a formula simplification. DAG size of input: 97 DAG size of output 74 [2018-01-20 22:27:21,533 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:27:21,533 INFO L93 Difference]: Finished difference Result 595 states and 639 transitions. [2018-01-20 22:27:21,533 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-01-20 22:27:21,533 INFO L78 Accepts]: Start accepts. Automaton has 44 states. Word has length 105 [2018-01-20 22:27:21,534 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:27:21,536 INFO L225 Difference]: With dead ends: 595 [2018-01-20 22:27:21,536 INFO L226 Difference]: Without dead ends: 592 [2018-01-20 22:27:21,537 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 165 GetRequests, 93 SyntacticMatches, 4 SemanticMatches, 68 ConstructedPredicates, 4 IntricatePredicates, 0 DeprecatedPredicates, 985 ImplicationChecksByTransitivity, 4.0s TimeCoverageRelationStatistics Valid=460, Invalid=3824, Unknown=22, NotChecked=524, Total=4830 [2018-01-20 22:27:21,537 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 592 states. [2018-01-20 22:27:21,561 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 592 to 530. [2018-01-20 22:27:21,561 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 530 states. [2018-01-20 22:27:21,562 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 530 states to 530 states and 573 transitions. [2018-01-20 22:27:21,563 INFO L78 Accepts]: Start accepts. Automaton has 530 states and 573 transitions. Word has length 105 [2018-01-20 22:27:21,563 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:27:21,563 INFO L432 AbstractCegarLoop]: Abstraction has 530 states and 573 transitions. [2018-01-20 22:27:21,563 INFO L433 AbstractCegarLoop]: Interpolant automaton has 44 states. [2018-01-20 22:27:21,563 INFO L276 IsEmpty]: Start isEmpty. Operand 530 states and 573 transitions. [2018-01-20 22:27:21,564 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2018-01-20 22:27:21,564 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:27:21,564 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:27:21,564 INFO L371 AbstractCegarLoop]: === Iteration 14 === [mainErr0EnsuresViolation]=== [2018-01-20 22:27:21,565 INFO L82 PathProgramCache]: Analyzing trace with hash 564030745, now seen corresponding path program 2 times [2018-01-20 22:27:21,565 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:27:21,565 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:27:21,565 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:27:21,565 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-20 22:27:21,566 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:27:21,591 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:27:21,592 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:27:22,674 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 5 proven. 23 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-01-20 22:27:22,674 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:27:22,674 INFO L209 onRefinementStrategy]: 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-01-20 22:27:22,682 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-20 22:27:22,703 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-20 22:27:22,726 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-20 22:27:22,735 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-20 22:27:22,741 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:27:22,744 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-20 22:27:22,745 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:22,747 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:22,747 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:6, output treesize:5 [2018-01-20 22:27:22,825 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:22,826 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:22,827 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 21 [2018-01-20 22:27:22,828 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:22,840 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:22,840 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:26, output treesize:24 [2018-01-20 22:27:22,877 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:27:22,878 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:27:22,878 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:22,880 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:22,889 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:27:22,891 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:27:22,891 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:22,893 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:22,900 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:22,900 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:43, output treesize:36 [2018-01-20 22:27:22,969 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:22,973 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 30 [2018-01-20 22:27:22,975 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-01-20 22:27:22,975 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:22,979 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:22,990 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:22,993 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 52 treesize of output 56 [2018-01-20 22:27:22,995 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-01-20 22:27:22,995 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:23,002 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:23,011 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:27:23,011 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:78, output treesize:62 [2018-01-20 22:27:23,059 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 26 [2018-01-20 22:27:23,061 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 3 [2018-01-20 22:27:23,062 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:23,067 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 1 [2018-01-20 22:27:23,068 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:23,069 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:23,077 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:27:23,077 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:70, output treesize:46 [2018-01-20 22:27:23,161 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 49 treesize of output 44 [2018-01-20 22:27:23,169 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 16 treesize of output 23 [2018-01-20 22:27:23,170 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-20 22:27:23,182 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:27:23,200 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-01-20 22:27:23,201 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:57, output treesize:90 [2018-01-20 22:27:23,257 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:23,258 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:23,259 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:23,259 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 5 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 21 [2018-01-20 22:27:23,259 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:23,267 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:23,267 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:49, output treesize:42 [2018-01-20 22:27:23,305 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:23,308 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 44 treesize of output 43 [2018-01-20 22:27:23,311 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:23,311 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 4 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 23 [2018-01-20 22:27:23,311 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:23,318 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:23,327 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:23,327 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:55, output treesize:60 [2018-01-20 22:27:23,424 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:23,429 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 80 treesize of output 88 [2018-01-20 22:27:23,431 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-01-20 22:27:23,431 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:23,441 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:23,451 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:27:23,451 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:83, output treesize:73 [2018-01-20 22:27:23,565 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:23,571 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 95 treesize of output 95 [2018-01-20 22:27:23,575 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 29 [2018-01-20 22:27:23,575 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:23,587 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:23,599 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2018-01-20 22:27:23,599 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:98, output treesize:88 Received shutdown request... [2018-01-20 22:27:25,652 INFO L175 TraceCheckSpWp]: Timeout while computing interpolants [2018-01-20 22:27:25,652 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-20 22:27:25,654 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.01 10:27:25 BoogieIcfgContainer [2018-01-20 22:27:25,654 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-20 22:27:25,654 INFO L168 Benchmark]: Toolchain (without parser) took 60373.69 ms. Allocated memory was 307.2 MB in the beginning and 728.2 MB in the end (delta: 421.0 MB). Free memory was 264.2 MB in the beginning and 359.7 MB in the end (delta: -95.6 MB). Peak memory consumption was 325.4 MB. Max. memory is 5.3 GB. [2018-01-20 22:27:25,655 INFO L168 Benchmark]: CDTParser took 0.21 ms. Allocated memory is still 307.2 MB. Free memory is still 270.1 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-20 22:27:25,656 INFO L168 Benchmark]: CACSL2BoogieTranslator took 223.31 ms. Allocated memory is still 307.2 MB. Free memory was 264.2 MB in the beginning and 250.2 MB in the end (delta: 13.9 MB). Peak memory consumption was 13.9 MB. Max. memory is 5.3 GB. [2018-01-20 22:27:25,656 INFO L168 Benchmark]: Boogie Preprocessor took 39.29 ms. Allocated memory is still 307.2 MB. Free memory was 250.2 MB in the beginning and 248.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-01-20 22:27:25,656 INFO L168 Benchmark]: RCFGBuilder took 496.34 ms. Allocated memory is still 307.2 MB. Free memory was 248.2 MB in the beginning and 215.3 MB in the end (delta: 33.0 MB). Peak memory consumption was 33.0 MB. Max. memory is 5.3 GB. [2018-01-20 22:27:25,656 INFO L168 Benchmark]: TraceAbstraction took 59607.34 ms. Allocated memory was 307.2 MB in the beginning and 728.2 MB in the end (delta: 421.0 MB). Free memory was 215.3 MB in the beginning and 359.7 MB in the end (delta: -144.5 MB). Peak memory consumption was 276.5 MB. Max. memory is 5.3 GB. [2018-01-20 22:27:25,657 INFO L344 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.21 ms. Allocated memory is still 307.2 MB. Free memory is still 270.1 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 223.31 ms. Allocated memory is still 307.2 MB. Free memory was 264.2 MB in the beginning and 250.2 MB in the end (delta: 13.9 MB). Peak memory consumption was 13.9 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 39.29 ms. Allocated memory is still 307.2 MB. Free memory was 250.2 MB in the beginning and 248.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 496.34 ms. Allocated memory is still 307.2 MB. Free memory was 248.2 MB in the beginning and 215.3 MB in the end (delta: 33.0 MB). Peak memory consumption was 33.0 MB. Max. memory is 5.3 GB. * TraceAbstraction took 59607.34 ms. Allocated memory was 307.2 MB in the beginning and 728.2 MB in the end (delta: 421.0 MB). Free memory was 215.3 MB in the beginning and 359.7 MB in the end (delta: -144.5 MB). Peak memory consumption was 276.5 MB. Max. memory is 5.3 GB. * Results from de.uni_freiburg.informatik.ultimate.boogie.preprocessor: - GenericResult: Unfinished Backtranslation Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) - GenericResult: Unfinished Backtranslation Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) - GenericResult: Unfinished Backtranslation Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) - GenericResult: Unfinished Backtranslation Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - CounterExampleResult [Line: 1]: not all allocated memory was freed not all allocated memory was freed We found a FailurePath: - StatisticsResult: Ultimate Automizer benchmark data for error location: ULTIMATE.initErr0EnsuresViolation CFG has 3 procedures, 127 locations, 3 error locations. UNSAFE Result, 0.1s OverallTime, 1 OverallIterations, 1 TraceHistogramMax, 0.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: No data available, PredicateUnifierStatistics: No data available, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=127occurred in iteration=0, 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, AutomataMinimizationStatistics: No data available, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.0s SatisfiabilityAnalysisTime, 0.0s InterpolantComputationTime, 3 NumberOfCodeBlocks, 3 NumberOfCodeBlocksAsserted, 1 NumberOfCheckSat, 0 ConstructedInterpolants, 0 QuantifiedInterpolants, 0 SizeOfPredicates, 0 NumberOfNonLiveVariables, 0 ConjunctsInSsa, 0 ConjunctsInUnsatCore, 0 InterpolantComputations, 0 PerfectInterpolantSequences, 0/0 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available - CounterExampleResult [Line: 1]: not all allocated memory was freed not all allocated memory was freed We found a FailurePath: [L992] EXPR, FCALL malloc(sizeof(SLL)) VAL [malloc(sizeof(SLL))={14:0}] [L992] SLL* list = malloc(sizeof(SLL)); VAL [list={14:0}, malloc(sizeof(SLL))={14:0}] [L993] FCALL list->next = ((void*)0) VAL [list={14:0}, malloc(sizeof(SLL))={14:0}] [L994] FCALL list->prev = ((void*)0) VAL [list={14:0}, malloc(sizeof(SLL))={14:0}] [L995] COND FALSE !(!(list != ((void*)0))) VAL [list={14:0}, malloc(sizeof(SLL))={14:0}] [L995] COND FALSE !(0) VAL [list={14:0}, malloc(sizeof(SLL))={14:0}] [L995] COND TRUE __VERIFIER_nondet_int() [L995] FCALL list->inner = ((void*)0) VAL [list={14:0}, malloc(sizeof(SLL))={14:0}] [L995] EXPR, FCALL list->inner VAL [list={14:0}, list->inner={0:0}, malloc(sizeof(SLL))={14:0}] [L995] EXPR list->inner != ((void*)0) || list->inner == ((void*)0) VAL [list={14:0}, list->inner={0:0}, list->inner != ((void*)0) || list->inner == ((void*)0)=0, malloc(sizeof(SLL))={14:0}] [L995] EXPR, FCALL list->inner VAL [list={14:0}, list->inner={0:0}, list->inner={0:0}, list->inner != ((void*)0) || list->inner == ((void*)0)=0, malloc(sizeof(SLL))={14:0}] [L995] EXPR list->inner != ((void*)0) || list->inner == ((void*)0) VAL [list={14:0}, list->inner={0:0}, list->inner={0:0}, list->inner != ((void*)0) || list->inner == ((void*)0)=1, malloc(sizeof(SLL))={14:0}] [L995] COND FALSE !(!(list->inner != ((void*)0) || list->inner == ((void*)0))) [L995] COND FALSE !(0) VAL [list={14:0}, malloc(sizeof(SLL))={14:0}] [L997] SLL* end = list; VAL [end={14:0}, list={14:0}, malloc(sizeof(SLL))={14:0}] [L1000] COND FALSE !(__VERIFIER_nondet_int()) [L1011] end = ((void*)0) [L1012] end = list VAL [end={14:0}, list={14:0}, malloc(sizeof(SLL))={14:0}] [L1015] COND FALSE !(!(((void*)0) != end)) VAL [end={14:0}, list={14:0}, malloc(sizeof(SLL))={14:0}] [L1015] COND FALSE !(0) VAL [end={14:0}, list={14:0}, malloc(sizeof(SLL))={14:0}] [L1017] COND TRUE ((void*)0) != end [L1019] int len = 0; VAL [end={14:0}, len=0, list={14:0}, malloc(sizeof(SLL))={14:0}] [L1020] EXPR, FCALL end->inner VAL [end={14:0}, end->inner={0:0}, len=0, list={14:0}, malloc(sizeof(SLL))={14:0}] [L1020] SLL* inner = end->inner; [L1021] COND FALSE !(((void*)0) != inner) VAL [end={14:0}, inner={0:0}, len=0, list={14:0}, malloc(sizeof(SLL))={14:0}] [L1032] COND FALSE !(!(len <= 1)) VAL [end={14:0}, inner={0:0}, len=0, list={14:0}, malloc(sizeof(SLL))={14:0}] [L1032] COND FALSE !(0) VAL [end={14:0}, inner={0:0}, len=0, list={14:0}, malloc(sizeof(SLL))={14:0}] [L1034] EXPR, FCALL end->next VAL [end={14:0}, end->next={0:0}, inner={0:0}, len=0, list={14:0}, malloc(sizeof(SLL))={14:0}] [L1034] end = end->next [L1017] COND FALSE !(((void*)0) != end) VAL [end={0:0}, inner={0:0}, len=0, list={14:0}, malloc(sizeof(SLL))={14:0}] [L1038] COND TRUE ((void*)0) != list VAL [end={0:0}, inner={0:0}, len=0, list={14:0}, malloc(sizeof(SLL))={14:0}] [L1040] EXPR, FCALL list->inner VAL [end={0:0}, inner={0:0}, len=0, list={14:0}, list->inner={0:0}, malloc(sizeof(SLL))={14:0}] [L1040] end = list->inner [L1042] COND FALSE !(((void*)0) != end) VAL [end={0:0}, inner={0:0}, len=0, list={14:0}, malloc(sizeof(SLL))={14:0}] [L1050] EXPR, FCALL list->next VAL [end={0:0}, inner={0:0}, len=0, list={14:0}, list->next={0:0}, malloc(sizeof(SLL))={14:0}] [L1050] end = list->next [L1051] FCALL free(list) VAL [end={0:0}, inner={0:0}, len=0, list={14:0}, malloc(sizeof(SLL))={14:0}] [L1052] list = end VAL [end={0:0}, inner={0:0}, len=0, list={0:0}, malloc(sizeof(SLL))={14:0}] [L1038] COND FALSE !(((void*)0) != list) VAL [end={0:0}, inner={0:0}, len=0, list={0:0}, malloc(sizeof(SLL))={14:0}] [L1055] return 0; - StatisticsResult: Ultimate Automizer benchmark data for error location: ULTIMATE.startErr0EnsuresViolation CFG has 3 procedures, 127 locations, 3 error locations. UNSAFE Result, 1.2s OverallTime, 4 OverallIterations, 2 TraceHistogramMax, 0.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 357 SDtfs, 432 SDslu, 434 SDs, 0 SdLazy, 175 SolverSat, 7 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 16 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=132occurred in iteration=3, 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, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 3 MinimizatonAttempts, 118 StatesRemovedByMinimization, 2 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.0s SatisfiabilityAnalysisTime, 0.3s InterpolantComputationTime, 159 NumberOfCodeBlocks, 159 NumberOfCodeBlocksAsserted, 4 NumberOfCheckSat, 97 ConstructedInterpolants, 0 QuantifiedInterpolants, 7895 SizeOfPredicates, 0 NumberOfNonLiveVariables, 0 ConjunctsInSsa, 0 ConjunctsInUnsatCore, 3 InterpolantComputations, 3 PerfectInterpolantSequences, 0/0 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available - TimeoutResultAtElement [Line: 989]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 989). Cancelled while BasicCegarLoop was analyzing trace of length 111 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 43 known predicates. - StatisticsResult: Ultimate Automizer benchmark data for error location: mainErr0EnsuresViolation CFG has 3 procedures, 127 locations, 3 error locations. TIMEOUT Result, 58.1s OverallTime, 14 OverallIterations, 3 TraceHistogramMax, 39.7s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 1714 SDtfs, 5488 SDslu, 14386 SDs, 0 SdLazy, 9575 SolverSat, 548 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 6.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 808 GetRequests, 445 SyntacticMatches, 12 SemanticMatches, 351 ConstructedPredicates, 5 IntricatePredicates, 1 DeprecatedPredicates, 4812 ImplicationChecksByTransitivity, 42.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=530occurred in iteration=13, 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, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 13 MinimizatonAttempts, 835 StatesRemovedByMinimization, 12 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 13.3s InterpolantComputationTime, 1329 NumberOfCodeBlocks, 1329 NumberOfCodeBlocksAsserted, 21 NumberOfCheckSat, 1310 ConstructedInterpolants, 112 QuantifiedInterpolants, 2983681 SizeOfPredicates, 71 NumberOfNonLiveVariables, 1240 ConjunctsInSsa, 184 ConjunctsInUnsatCore, 19 InterpolantComputations, 7 PerfectInterpolantSequences, 69/155 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available RESULT: Ultimate proved your program to be incorrect! Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dll-01_true-unreach-call_true-valid-memsafety.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-20_22-27-25-663.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dll-01_true-unreach-call_true-valid-memsafety.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-20_22-27-25-663.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dll-01_true-unreach-call_true-valid-memsafety.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-1-2018-01-20_22-27-25-663.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dll-01_true-unreach-call_true-valid-memsafety.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-2-2018-01-20_22-27-25-663.csv Completed graceful shutdown