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/memsafety-ext/tree_dsw_true-valid-memsafety_false-termination.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-2f49842 [2018-01-20 22:03:30,088 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-20 22:03:30,089 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-20 22:03:30,104 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-20 22:03:30,104 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-20 22:03:30,105 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-20 22:03:30,106 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-20 22:03:30,108 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-20 22:03:30,109 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-20 22:03:30,110 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-20 22:03:30,110 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-20 22:03:30,110 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-20 22:03:30,111 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-20 22:03:30,112 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-20 22:03:30,113 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-20 22:03:30,115 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-20 22:03:30,117 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-20 22:03:30,119 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-20 22:03:30,121 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-20 22:03:30,122 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-20 22:03:30,124 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-20 22:03:30,124 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-20 22:03:30,124 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-20 22:03:30,125 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-20 22:03:30,126 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-20 22:03:30,127 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-20 22:03:30,127 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-20 22:03:30,128 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-20 22:03:30,128 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-20 22:03:30,128 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-20 22:03:30,129 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-20 22:03:30,129 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:03:30,139 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-20 22:03:30,139 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-20 22:03:30,140 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-20 22:03:30,140 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-20 22:03:30,140 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-20 22:03:30,140 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-20 22:03:30,140 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-20 22:03:30,141 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-20 22:03:30,141 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-20 22:03:30,141 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-20 22:03:30,142 INFO L133 SettingsManager]: * Check allocation purity=true [2018-01-20 22:03:30,142 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-20 22:03:30,142 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-20 22:03:30,142 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-20 22:03:30,142 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-01-20 22:03:30,143 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-20 22:03:30,143 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-01-20 22:03:30,143 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-20 22:03:30,143 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-01-20 22:03:30,143 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-01-20 22:03:30,144 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-20 22:03:30,144 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-01-20 22:03:30,144 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-20 22:03:30,144 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-20 22:03:30,144 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-20 22:03:30,144 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-20 22:03:30,145 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-20 22:03:30,145 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-20 22:03:30,145 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-20 22:03:30,145 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-20 22:03:30,146 INFO L133 SettingsManager]: * Stop after first violation was found=false [2018-01-20 22:03:30,146 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-01-20 22:03:30,146 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-20 22:03:30,146 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-20 22:03:30,146 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-20 22:03:30,147 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-20 22:03:30,147 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-20 22:03:30,180 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-20 22:03:30,189 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-20 22:03:30,192 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-20 22:03:30,193 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-20 22:03:30,193 INFO L276 PluginConnector]: CDTParser initialized [2018-01-20 22:03:30,193 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/memsafety-ext/tree_dsw_true-valid-memsafety_false-termination.i [2018-01-20 22:03:30,348 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-20 22:03:30,353 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-20 22:03:30,354 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-20 22:03:30,354 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-20 22:03:30,359 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-20 22:03:30,359 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.01 10:03:30" (1/1) ... [2018-01-20 22:03:30,362 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7feccdb9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:03:30, skipping insertion in model container [2018-01-20 22:03:30,362 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.01 10:03:30" (1/1) ... [2018-01-20 22:03:30,374 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-20 22:03:30,410 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-20 22:03:30,524 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-20 22:03:30,546 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-20 22:03:30,556 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:03:30 WrapperNode [2018-01-20 22:03:30,556 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-20 22:03:30,557 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-20 22:03:30,557 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-20 22:03:30,557 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-20 22:03:30,570 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:03:30" (1/1) ... [2018-01-20 22:03:30,570 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:03:30" (1/1) ... [2018-01-20 22:03:30,579 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:03:30" (1/1) ... [2018-01-20 22:03:30,579 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:03:30" (1/1) ... [2018-01-20 22:03:30,585 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:03:30" (1/1) ... [2018-01-20 22:03:30,589 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:03:30" (1/1) ... [2018-01-20 22:03:30,590 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:03:30" (1/1) ... [2018-01-20 22:03:30,592 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-20 22:03:30,592 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-20 22:03:30,592 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-20 22:03:30,593 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-20 22:03:30,593 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:03:30" (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:03:30,637 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-20 22:03:30,637 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-20 22:03:30,637 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-20 22:03:30,637 INFO L128 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2018-01-20 22:03:30,637 INFO L128 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2018-01-20 22:03:30,637 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-20 22:03:30,638 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-20 22:03:30,638 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-20 22:03:30,638 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-20 22:03:30,638 INFO L128 BoogieDeclarations]: Found specification of procedure malloc [2018-01-20 22:03:30,638 INFO L128 BoogieDeclarations]: Found specification of procedure free [2018-01-20 22:03:30,638 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-20 22:03:30,639 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-20 22:03:30,639 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-20 22:03:31,029 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-20 22:03:31,029 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.01 10:03:31 BoogieIcfgContainer [2018-01-20 22:03:31,064 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-20 22:03:31,066 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-20 22:03:31,066 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-20 22:03:31,068 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-20 22:03:31,068 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.01 10:03:30" (1/3) ... [2018-01-20 22:03:31,069 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@63e82a2a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.01 10:03:31, skipping insertion in model container [2018-01-20 22:03:31,069 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:03:30" (2/3) ... [2018-01-20 22:03:31,070 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@63e82a2a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.01 10:03:31, skipping insertion in model container [2018-01-20 22:03:31,070 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.01 10:03:31" (3/3) ... [2018-01-20 22:03:31,072 INFO L105 eAbstractionObserver]: Analyzing ICFG tree_dsw_true-valid-memsafety_false-termination.i [2018-01-20 22:03:31,078 INFO L130 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-20 22:03:31,085 INFO L142 ceAbstractionStarter]: Appying trace abstraction to program that has 3 error locations. [2018-01-20 22:03:31,123 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 22:03:31,123 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 22:03:31,123 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 22:03:31,123 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 22:03:31,123 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 22:03:31,123 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 22:03:31,123 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 22:03:31,123 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.initErr0EnsuresViolation======== [2018-01-20 22:03:31,124 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 22:03:31,140 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states. [2018-01-20 22:03:31,145 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2018-01-20 22:03:31,145 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:03:31,146 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1] [2018-01-20 22:03:31,146 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.initErr0EnsuresViolation]=== [2018-01-20 22:03:31,150 INFO L82 PathProgramCache]: Analyzing trace with hash 214305, now seen corresponding path program 1 times [2018-01-20 22:03:31,151 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:03:31,152 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:03:31,193 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:31,193 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:31,193 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:31,219 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 22:03:31,225 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 22:03:31,240 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-20 22:03:31,246 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 22:03:31,254 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 22:03:31,255 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 22:03:31,255 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 22:03:31,255 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 22:03:31,255 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 22:03:31,255 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 22:03:31,256 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 22:03:31,256 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.startErr0EnsuresViolation======== [2018-01-20 22:03:31,256 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 22:03:31,259 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states. [2018-01-20 22:03:31,262 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2018-01-20 22:03:31,262 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:03:31,263 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] [2018-01-20 22:03:31,263 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:03:31,263 INFO L82 PathProgramCache]: Analyzing trace with hash 210929596, now seen corresponding path program 1 times [2018-01-20 22:03:31,263 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:03:31,263 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:03:31,264 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:31,264 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:31,264 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:31,282 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:31,288 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:03:31,325 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:03:31,327 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:03:31,327 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-20 22:03:31,329 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-20 22:03:31,431 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-20 22:03:31,431 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 22:03:31,433 INFO L87 Difference]: Start difference. First operand 101 states. Second operand 2 states. [2018-01-20 22:03:31,460 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:03:31,460 INFO L93 Difference]: Finished difference Result 192 states and 226 transitions. [2018-01-20 22:03:31,461 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-20 22:03:31,462 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 26 [2018-01-20 22:03:31,462 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:03:31,473 INFO L225 Difference]: With dead ends: 192 [2018-01-20 22:03:31,473 INFO L226 Difference]: Without dead ends: 98 [2018-01-20 22:03:31,476 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:03:31,490 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2018-01-20 22:03:31,508 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 98. [2018-01-20 22:03:31,509 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 98 states. [2018-01-20 22:03:31,511 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 111 transitions. [2018-01-20 22:03:31,512 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 111 transitions. Word has length 26 [2018-01-20 22:03:31,513 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:03:31,513 INFO L432 AbstractCegarLoop]: Abstraction has 98 states and 111 transitions. [2018-01-20 22:03:31,513 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-20 22:03:31,513 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 111 transitions. [2018-01-20 22:03:31,514 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-01-20 22:03:31,514 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:03:31,515 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] [2018-01-20 22:03:31,515 INFO L371 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:03:31,515 INFO L82 PathProgramCache]: Analyzing trace with hash -615979456, now seen corresponding path program 1 times [2018-01-20 22:03:31,515 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:03:31,515 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:03:31,516 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:31,516 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:31,517 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:31,545 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:31,546 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:03:31,618 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:03:31,619 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:03:31,619 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-20 22:03:31,621 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-20 22:03:31,621 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-20 22:03:31,621 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-20 22:03:31,621 INFO L87 Difference]: Start difference. First operand 98 states and 111 transitions. Second operand 4 states. [2018-01-20 22:03:31,659 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:03:31,659 INFO L93 Difference]: Finished difference Result 109 states and 122 transitions. [2018-01-20 22:03:31,659 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-20 22:03:31,659 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 30 [2018-01-20 22:03:31,660 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:03:31,662 INFO L225 Difference]: With dead ends: 109 [2018-01-20 22:03:31,662 INFO L226 Difference]: Without dead ends: 102 [2018-01-20 22:03:31,663 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-20 22:03:31,663 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2018-01-20 22:03:31,668 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 100. [2018-01-20 22:03:31,668 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 100 states. [2018-01-20 22:03:31,670 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 113 transitions. [2018-01-20 22:03:31,671 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 113 transitions. Word has length 30 [2018-01-20 22:03:31,671 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:03:31,671 INFO L432 AbstractCegarLoop]: Abstraction has 100 states and 113 transitions. [2018-01-20 22:03:31,671 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-20 22:03:31,671 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 113 transitions. [2018-01-20 22:03:31,673 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2018-01-20 22:03:31,673 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:03:31,673 INFO L322 BasicCegarLoop]: trace histogram [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] [2018-01-20 22:03:31,673 INFO L371 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:03:31,674 INFO L82 PathProgramCache]: Analyzing trace with hash -298055667, now seen corresponding path program 1 times [2018-01-20 22:03:31,674 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:03:31,674 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:03:31,675 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:31,675 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:31,675 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:31,695 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:31,696 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:03:31,766 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-20 22:03:31,767 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:03:31,767 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-01-20 22:03:31,767 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-20 22:03:31,768 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-20 22:03:31,768 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-20 22:03:31,768 INFO L87 Difference]: Start difference. First operand 100 states and 113 transitions. Second operand 6 states. [2018-01-20 22:03:31,929 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:03:31,930 INFO L93 Difference]: Finished difference Result 154 states and 171 transitions. [2018-01-20 22:03:31,930 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-01-20 22:03:31,930 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 42 [2018-01-20 22:03:31,930 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:03:31,931 INFO L225 Difference]: With dead ends: 154 [2018-01-20 22:03:31,931 INFO L226 Difference]: Without dead ends: 114 [2018-01-20 22:03:31,932 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2018-01-20 22:03:31,932 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2018-01-20 22:03:31,937 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 102. [2018-01-20 22:03:31,937 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 102 states. [2018-01-20 22:03:31,938 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 115 transitions. [2018-01-20 22:03:31,938 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 115 transitions. Word has length 42 [2018-01-20 22:03:31,939 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:03:31,939 INFO L432 AbstractCegarLoop]: Abstraction has 102 states and 115 transitions. [2018-01-20 22:03:31,939 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-20 22:03:31,939 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 115 transitions. [2018-01-20 22:03:31,940 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2018-01-20 22:03:31,940 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:03:31,940 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] [2018-01-20 22:03:31,940 INFO L371 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:03:31,940 INFO L82 PathProgramCache]: Analyzing trace with hash 1908754361, now seen corresponding path program 1 times [2018-01-20 22:03:31,940 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:03:31,941 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:03:31,941 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:31,941 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:31,941 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:31,957 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:31,958 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:03:32,038 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:03:32,038 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:03:32,038 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:03:32,055 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:32,101 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:32,108 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:03:32,173 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:03:32,207 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-20 22:03:32,208 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [8] total 11 [2018-01-20 22:03:32,208 INFO L409 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-01-20 22:03:32,208 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-01-20 22:03:32,209 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=90, Unknown=0, NotChecked=0, Total=110 [2018-01-20 22:03:32,209 INFO L87 Difference]: Start difference. First operand 102 states and 115 transitions. Second operand 11 states. [2018-01-20 22:03:32,782 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:03:32,782 INFO L93 Difference]: Finished difference Result 251 states and 279 transitions. [2018-01-20 22:03:32,782 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-01-20 22:03:32,782 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 52 [2018-01-20 22:03:32,783 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:03:32,787 INFO L225 Difference]: With dead ends: 251 [2018-01-20 22:03:32,788 INFO L226 Difference]: Without dead ends: 211 [2018-01-20 22:03:32,789 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 71 GetRequests, 51 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=139, Invalid=323, Unknown=0, NotChecked=0, Total=462 [2018-01-20 22:03:32,789 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 211 states. [2018-01-20 22:03:32,800 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 211 to 113. [2018-01-20 22:03:32,800 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 113 states. [2018-01-20 22:03:32,802 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 128 transitions. [2018-01-20 22:03:32,802 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 128 transitions. Word has length 52 [2018-01-20 22:03:32,802 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:03:32,803 INFO L432 AbstractCegarLoop]: Abstraction has 113 states and 128 transitions. [2018-01-20 22:03:32,803 INFO L433 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-01-20 22:03:32,803 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 128 transitions. [2018-01-20 22:03:32,805 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2018-01-20 22:03:32,805 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:03:32,805 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] [2018-01-20 22:03:32,806 INFO L371 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:03:32,807 INFO L82 PathProgramCache]: Analyzing trace with hash -1000009541, now seen corresponding path program 1 times [2018-01-20 22:03:32,807 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:03:32,807 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:03:32,808 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:32,808 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:32,808 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:32,826 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:32,828 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:03:32,984 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:03:32,985 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:03:32,985 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:03:32,995 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:33,032 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:33,036 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:03:33,080 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:03:33,081 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:03:33,082 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:33,083 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:33,084 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:33,085 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:11, output treesize:7 [2018-01-20 22:03:33,093 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 26 treesize of output 21 [2018-01-20 22:03:33,100 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:03:33,103 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 16 treesize of output 23 [2018-01-20 22:03:33,103 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:33,108 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:33,112 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:33,113 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:26, output treesize:17 [2018-01-20 22:03:33,164 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 24 treesize of output 18 [2018-01-20 22:03:33,166 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:03:33,167 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 18 treesize of output 10 [2018-01-20 22:03:33,167 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:33,169 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:33,172 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:33,172 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:27, output treesize:7 [2018-01-20 22:03:33,227 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:03:33,246 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:03:33,247 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 10] total 15 [2018-01-20 22:03:33,247 INFO L409 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-01-20 22:03:33,247 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-01-20 22:03:33,247 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=180, Unknown=0, NotChecked=0, Total=210 [2018-01-20 22:03:33,248 INFO L87 Difference]: Start difference. First operand 113 states and 128 transitions. Second operand 15 states. [2018-01-20 22:03:33,653 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:03:33,653 INFO L93 Difference]: Finished difference Result 205 states and 233 transitions. [2018-01-20 22:03:33,654 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-01-20 22:03:33,654 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 52 [2018-01-20 22:03:33,654 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:03:33,656 INFO L225 Difference]: With dead ends: 205 [2018-01-20 22:03:33,656 INFO L226 Difference]: Without dead ends: 165 [2018-01-20 22:03:33,657 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 46 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=89, Invalid=373, Unknown=0, NotChecked=0, Total=462 [2018-01-20 22:03:33,657 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 165 states. [2018-01-20 22:03:33,669 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 165 to 150. [2018-01-20 22:03:33,669 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 150 states. [2018-01-20 22:03:33,671 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 150 states to 150 states and 174 transitions. [2018-01-20 22:03:33,671 INFO L78 Accepts]: Start accepts. Automaton has 150 states and 174 transitions. Word has length 52 [2018-01-20 22:03:33,671 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:03:33,671 INFO L432 AbstractCegarLoop]: Abstraction has 150 states and 174 transitions. [2018-01-20 22:03:33,671 INFO L433 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-01-20 22:03:33,671 INFO L276 IsEmpty]: Start isEmpty. Operand 150 states and 174 transitions. [2018-01-20 22:03:33,673 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2018-01-20 22:03:33,673 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:03:33,673 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] [2018-01-20 22:03:33,673 INFO L371 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:03:33,674 INFO L82 PathProgramCache]: Analyzing trace with hash -2108446361, now seen corresponding path program 1 times [2018-01-20 22:03:33,674 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:03:33,674 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:03:33,675 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:33,675 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:33,675 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:33,704 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:33,705 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:03:33,905 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-20 22:03:33,906 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:03:33,906 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:03:33,914 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:33,952 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:33,957 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:03:33,962 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 13 treesize of output 10 [2018-01-20 22:03:33,963 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 10 treesize of output 9 [2018-01-20 22:03:33,964 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:33,965 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:33,966 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:33,966 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:13, output treesize:9 [2018-01-20 22:03:34,040 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 27 treesize of output 20 [2018-01-20 22:03:34,043 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:03:34,044 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 29 [2018-01-20 22:03:34,044 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:34,050 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:34,061 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:34,061 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:30, output treesize:26 [2018-01-20 22:03:34,101 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 36 treesize of output 27 [2018-01-20 22:03:34,104 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:03:34,106 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 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 27 treesize of output 23 [2018-01-20 22:03:34,107 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:34,111 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:34,118 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:03:34,118 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:39, output treesize:11 [2018-01-20 22:03:34,170 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:03:34,186 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:03:34,187 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:34,201 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:34,216 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:34,216 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:18, output treesize:7 [2018-01-20 22:03:34,291 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-20 22:03:34,310 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:03:34,310 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13] total 22 [2018-01-20 22:03:34,311 INFO L409 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-01-20 22:03:34,311 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-01-20 22:03:34,311 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=415, Unknown=0, NotChecked=0, Total=462 [2018-01-20 22:03:34,311 INFO L87 Difference]: Start difference. First operand 150 states and 174 transitions. Second operand 22 states. [2018-01-20 22:03:35,085 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:03:35,085 INFO L93 Difference]: Finished difference Result 221 states and 250 transitions. [2018-01-20 22:03:35,086 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-01-20 22:03:35,086 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 62 [2018-01-20 22:03:35,086 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:03:35,087 INFO L225 Difference]: With dead ends: 221 [2018-01-20 22:03:35,087 INFO L226 Difference]: Without dead ends: 181 [2018-01-20 22:03:35,087 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 54 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 186 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=172, Invalid=1160, Unknown=0, NotChecked=0, Total=1332 [2018-01-20 22:03:35,088 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 181 states. [2018-01-20 22:03:35,097 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 181 to 160. [2018-01-20 22:03:35,097 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 160 states. [2018-01-20 22:03:35,098 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 160 states to 160 states and 185 transitions. [2018-01-20 22:03:35,098 INFO L78 Accepts]: Start accepts. Automaton has 160 states and 185 transitions. Word has length 62 [2018-01-20 22:03:35,098 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:03:35,099 INFO L432 AbstractCegarLoop]: Abstraction has 160 states and 185 transitions. [2018-01-20 22:03:35,099 INFO L433 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-01-20 22:03:35,099 INFO L276 IsEmpty]: Start isEmpty. Operand 160 states and 185 transitions. [2018-01-20 22:03:35,099 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2018-01-20 22:03:35,099 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:03:35,100 INFO L322 BasicCegarLoop]: trace histogram [3, 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] [2018-01-20 22:03:35,100 INFO L371 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:03:35,100 INFO L82 PathProgramCache]: Analyzing trace with hash 341153769, now seen corresponding path program 2 times [2018-01-20 22:03:35,100 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:03:35,100 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:03:35,101 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:35,101 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:35,101 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:35,109 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:35,110 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:03:35,226 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-01-20 22:03:35,226 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:03:35,226 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-20 22:03:35,227 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-20 22:03:35,227 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-20 22:03:35,227 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-01-20 22:03:35,227 INFO L87 Difference]: Start difference. First operand 160 states and 185 transitions. Second operand 7 states. [2018-01-20 22:03:35,450 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:03:35,450 INFO L93 Difference]: Finished difference Result 267 states and 307 transitions. [2018-01-20 22:03:35,450 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-20 22:03:35,450 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 62 [2018-01-20 22:03:35,450 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:03:35,452 INFO L225 Difference]: With dead ends: 267 [2018-01-20 22:03:35,452 INFO L226 Difference]: Without dead ends: 212 [2018-01-20 22:03:35,453 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 3 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2018-01-20 22:03:35,453 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 212 states. [2018-01-20 22:03:35,460 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 212 to 160. [2018-01-20 22:03:35,460 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 160 states. [2018-01-20 22:03:35,461 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 160 states to 160 states and 184 transitions. [2018-01-20 22:03:35,462 INFO L78 Accepts]: Start accepts. Automaton has 160 states and 184 transitions. Word has length 62 [2018-01-20 22:03:35,462 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:03:35,462 INFO L432 AbstractCegarLoop]: Abstraction has 160 states and 184 transitions. [2018-01-20 22:03:35,462 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-20 22:03:35,462 INFO L276 IsEmpty]: Start isEmpty. Operand 160 states and 184 transitions. [2018-01-20 22:03:35,463 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2018-01-20 22:03:35,463 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:03:35,463 INFO L322 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2018-01-20 22:03:35,463 INFO L371 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:03:35,463 INFO L82 PathProgramCache]: Analyzing trace with hash 42752787, now seen corresponding path program 2 times [2018-01-20 22:03:35,463 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:03:35,463 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:03:35,464 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:35,464 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-20 22:03:35,464 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:35,491 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 22:03:35,521 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 22:03:35,539 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-20 22:03:35,555 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 22:03:35,571 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 22:03:35,572 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 22:03:35,597 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 22:03:35,597 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 22:03:35,597 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 22:03:35,598 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 22:03:35,598 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 22:03:35,598 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 22:03:35,598 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 22:03:35,598 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == mainErr0EnsuresViolation======== [2018-01-20 22:03:35,598 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 22:03:35,600 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states. [2018-01-20 22:03:35,601 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-01-20 22:03:35,601 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:03:35,601 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:03:35,601 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr0EnsuresViolation]=== [2018-01-20 22:03:35,601 INFO L82 PathProgramCache]: Analyzing trace with hash -495869350, now seen corresponding path program 1 times [2018-01-20 22:03:35,602 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:03:35,602 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:03:35,603 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:35,603 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:35,603 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:35,607 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:35,607 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:03:35,613 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:03:35,613 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:03:35,614 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-20 22:03:35,614 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-20 22:03:35,614 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-20 22:03:35,614 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 22:03:35,614 INFO L87 Difference]: Start difference. First operand 101 states. Second operand 2 states. [2018-01-20 22:03:35,619 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:03:35,619 INFO L93 Difference]: Finished difference Result 192 states and 226 transitions. [2018-01-20 22:03:35,620 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-20 22:03:35,620 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 24 [2018-01-20 22:03:35,620 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:03:35,621 INFO L225 Difference]: With dead ends: 192 [2018-01-20 22:03:35,621 INFO L226 Difference]: Without dead ends: 96 [2018-01-20 22:03:35,621 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:03:35,622 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2018-01-20 22:03:35,624 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 96. [2018-01-20 22:03:35,625 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 96 states. [2018-01-20 22:03:35,625 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 109 transitions. [2018-01-20 22:03:35,626 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 109 transitions. Word has length 24 [2018-01-20 22:03:35,626 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:03:35,626 INFO L432 AbstractCegarLoop]: Abstraction has 96 states and 109 transitions. [2018-01-20 22:03:35,626 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-20 22:03:35,626 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 109 transitions. [2018-01-20 22:03:35,627 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2018-01-20 22:03:35,627 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:03:35,627 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] [2018-01-20 22:03:35,627 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr0EnsuresViolation]=== [2018-01-20 22:03:35,627 INFO L82 PathProgramCache]: Analyzing trace with hash 1635111390, now seen corresponding path program 1 times [2018-01-20 22:03:35,627 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:03:35,627 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:03:35,628 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:35,628 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:35,628 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:35,635 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:35,636 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:03:35,661 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:03:35,662 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:03:35,662 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-20 22:03:35,662 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-20 22:03:35,662 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-20 22:03:35,662 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-20 22:03:35,662 INFO L87 Difference]: Start difference. First operand 96 states and 109 transitions. Second operand 4 states. [2018-01-20 22:03:35,677 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:03:35,678 INFO L93 Difference]: Finished difference Result 105 states and 118 transitions. [2018-01-20 22:03:35,678 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-20 22:03:35,678 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 28 [2018-01-20 22:03:35,678 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:03:35,679 INFO L225 Difference]: With dead ends: 105 [2018-01-20 22:03:35,679 INFO L226 Difference]: Without dead ends: 100 [2018-01-20 22:03:35,679 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-20 22:03:35,679 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2018-01-20 22:03:35,681 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 98. [2018-01-20 22:03:35,681 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 98 states. [2018-01-20 22:03:35,682 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 111 transitions. [2018-01-20 22:03:35,683 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 111 transitions. Word has length 28 [2018-01-20 22:03:35,683 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:03:35,683 INFO L432 AbstractCegarLoop]: Abstraction has 98 states and 111 transitions. [2018-01-20 22:03:35,683 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-20 22:03:35,683 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 111 transitions. [2018-01-20 22:03:35,684 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2018-01-20 22:03:35,684 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:03:35,684 INFO L322 BasicCegarLoop]: trace histogram [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] [2018-01-20 22:03:35,684 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr0EnsuresViolation]=== [2018-01-20 22:03:35,684 INFO L82 PathProgramCache]: Analyzing trace with hash -965672213, now seen corresponding path program 1 times [2018-01-20 22:03:35,685 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:03:35,685 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:03:35,685 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:35,686 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:35,686 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:35,693 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:35,694 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:03:35,741 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-20 22:03:35,742 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:03:35,742 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-01-20 22:03:35,742 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-20 22:03:35,742 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-20 22:03:35,742 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-20 22:03:35,743 INFO L87 Difference]: Start difference. First operand 98 states and 111 transitions. Second operand 6 states. [2018-01-20 22:03:35,947 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:03:35,947 INFO L93 Difference]: Finished difference Result 150 states and 167 transitions. [2018-01-20 22:03:35,947 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-01-20 22:03:35,947 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 40 [2018-01-20 22:03:35,947 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:03:35,948 INFO L225 Difference]: With dead ends: 150 [2018-01-20 22:03:35,948 INFO L226 Difference]: Without dead ends: 112 [2018-01-20 22:03:35,949 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2018-01-20 22:03:35,949 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 112 states. [2018-01-20 22:03:35,952 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 112 to 100. [2018-01-20 22:03:35,953 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 100 states. [2018-01-20 22:03:35,953 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 113 transitions. [2018-01-20 22:03:35,953 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 113 transitions. Word has length 40 [2018-01-20 22:03:35,954 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:03:35,954 INFO L432 AbstractCegarLoop]: Abstraction has 100 states and 113 transitions. [2018-01-20 22:03:35,954 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-20 22:03:35,954 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 113 transitions. [2018-01-20 22:03:35,955 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-01-20 22:03:35,955 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:03:35,955 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] [2018-01-20 22:03:35,955 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr0EnsuresViolation]=== [2018-01-20 22:03:35,955 INFO L82 PathProgramCache]: Analyzing trace with hash 274611607, now seen corresponding path program 1 times [2018-01-20 22:03:35,955 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:03:35,956 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:03:35,956 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:35,956 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:35,957 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:35,963 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:35,964 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:03:36,022 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:03:36,022 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:03:36,022 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:03:36,027 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:36,046 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:36,049 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:03:36,120 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:03:36,140 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-20 22:03:36,140 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [8] total 11 [2018-01-20 22:03:36,141 INFO L409 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-01-20 22:03:36,141 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-01-20 22:03:36,141 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=90, Unknown=0, NotChecked=0, Total=110 [2018-01-20 22:03:36,141 INFO L87 Difference]: Start difference. First operand 100 states and 113 transitions. Second operand 11 states. [2018-01-20 22:03:36,353 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:03:36,353 INFO L93 Difference]: Finished difference Result 247 states and 274 transitions. [2018-01-20 22:03:36,353 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-01-20 22:03:36,353 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 50 [2018-01-20 22:03:36,353 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:03:36,354 INFO L225 Difference]: With dead ends: 247 [2018-01-20 22:03:36,354 INFO L226 Difference]: Without dead ends: 209 [2018-01-20 22:03:36,355 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 49 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=139, Invalid=323, Unknown=0, NotChecked=0, Total=462 [2018-01-20 22:03:36,355 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 209 states. [2018-01-20 22:03:36,361 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 209 to 111. [2018-01-20 22:03:36,361 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 111 states. [2018-01-20 22:03:36,362 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 126 transitions. [2018-01-20 22:03:36,362 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 126 transitions. Word has length 50 [2018-01-20 22:03:36,363 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:03:36,363 INFO L432 AbstractCegarLoop]: Abstraction has 111 states and 126 transitions. [2018-01-20 22:03:36,363 INFO L433 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-01-20 22:03:36,363 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 126 transitions. [2018-01-20 22:03:36,364 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-01-20 22:03:36,364 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:03:36,364 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] [2018-01-20 22:03:36,364 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr0EnsuresViolation]=== [2018-01-20 22:03:36,365 INFO L82 PathProgramCache]: Analyzing trace with hash -2097127655, now seen corresponding path program 1 times [2018-01-20 22:03:36,365 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:03:36,365 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:03:36,366 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:36,366 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:36,366 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:36,374 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:36,375 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:03:36,458 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:03:36,459 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:03:36,459 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:03:36,464 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:36,483 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:36,485 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:03:36,498 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:03:36,500 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:03:36,500 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:36,501 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:36,505 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:36,505 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:11, output treesize:7 [2018-01-20 22:03:36,511 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 26 treesize of output 21 [2018-01-20 22:03:36,519 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:03:36,520 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 16 treesize of output 23 [2018-01-20 22:03:36,521 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:36,527 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:36,531 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:36,531 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:26, output treesize:17 [2018-01-20 22:03:36,572 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 24 treesize of output 18 [2018-01-20 22:03:36,575 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:03:36,576 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 18 treesize of output 10 [2018-01-20 22:03:36,576 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:36,579 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:36,581 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:36,582 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:27, output treesize:7 [2018-01-20 22:03:36,635 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:03:36,659 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:03:36,659 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 10] total 15 [2018-01-20 22:03:36,660 INFO L409 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-01-20 22:03:36,660 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-01-20 22:03:36,660 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=180, Unknown=0, NotChecked=0, Total=210 [2018-01-20 22:03:36,660 INFO L87 Difference]: Start difference. First operand 111 states and 126 transitions. Second operand 15 states. [2018-01-20 22:03:37,098 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:03:37,098 INFO L93 Difference]: Finished difference Result 201 states and 229 transitions. [2018-01-20 22:03:37,098 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-01-20 22:03:37,098 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 50 [2018-01-20 22:03:37,099 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:03:37,099 INFO L225 Difference]: With dead ends: 201 [2018-01-20 22:03:37,099 INFO L226 Difference]: Without dead ends: 163 [2018-01-20 22:03:37,100 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 44 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=89, Invalid=373, Unknown=0, NotChecked=0, Total=462 [2018-01-20 22:03:37,100 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 163 states. [2018-01-20 22:03:37,106 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 163 to 148. [2018-01-20 22:03:37,107 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 148 states. [2018-01-20 22:03:37,108 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 172 transitions. [2018-01-20 22:03:37,108 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 172 transitions. Word has length 50 [2018-01-20 22:03:37,108 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:03:37,108 INFO L432 AbstractCegarLoop]: Abstraction has 148 states and 172 transitions. [2018-01-20 22:03:37,108 INFO L433 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-01-20 22:03:37,109 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 172 transitions. [2018-01-20 22:03:37,109 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2018-01-20 22:03:37,109 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:03:37,110 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] [2018-01-20 22:03:37,110 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr0EnsuresViolation]=== [2018-01-20 22:03:37,110 INFO L82 PathProgramCache]: Analyzing trace with hash -489344315, now seen corresponding path program 1 times [2018-01-20 22:03:37,110 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:03:37,110 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:03:37,111 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:37,111 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:37,111 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:37,126 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:37,127 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:03:37,310 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-20 22:03:37,310 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:03:37,310 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:03:37,317 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:37,340 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:37,344 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:03:37,348 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 13 treesize of output 10 [2018-01-20 22:03:37,353 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 10 treesize of output 9 [2018-01-20 22:03:37,354 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:37,355 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:37,356 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:37,356 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:13, output treesize:9 [2018-01-20 22:03:37,432 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 27 treesize of output 20 [2018-01-20 22:03:37,435 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:03:37,436 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 29 [2018-01-20 22:03:37,436 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:37,443 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:37,448 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:37,448 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:30, output treesize:26 [2018-01-20 22:03:37,492 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 36 treesize of output 27 [2018-01-20 22:03:37,496 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:03:37,499 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 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 27 treesize of output 23 [2018-01-20 22:03:37,499 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:37,507 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:37,512 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:03:37,512 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:39, output treesize:11 [2018-01-20 22:03:37,549 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:03:37,551 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:03:37,551 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:37,552 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:37,555 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:37,556 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:18, output treesize:7 [2018-01-20 22:03:37,653 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-20 22:03:37,678 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:03:37,679 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13] total 22 [2018-01-20 22:03:37,679 INFO L409 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-01-20 22:03:37,680 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-01-20 22:03:37,680 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=415, Unknown=0, NotChecked=0, Total=462 [2018-01-20 22:03:37,680 INFO L87 Difference]: Start difference. First operand 148 states and 172 transitions. Second operand 22 states. [2018-01-20 22:03:38,347 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:03:38,348 INFO L93 Difference]: Finished difference Result 217 states and 246 transitions. [2018-01-20 22:03:38,348 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-01-20 22:03:38,348 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 60 [2018-01-20 22:03:38,348 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:03:38,349 INFO L225 Difference]: With dead ends: 217 [2018-01-20 22:03:38,349 INFO L226 Difference]: Without dead ends: 179 [2018-01-20 22:03:38,350 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 52 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 186 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=172, Invalid=1160, Unknown=0, NotChecked=0, Total=1332 [2018-01-20 22:03:38,350 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 179 states. [2018-01-20 22:03:38,356 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 179 to 158. [2018-01-20 22:03:38,356 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 158 states. [2018-01-20 22:03:38,358 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 158 states to 158 states and 183 transitions. [2018-01-20 22:03:38,358 INFO L78 Accepts]: Start accepts. Automaton has 158 states and 183 transitions. Word has length 60 [2018-01-20 22:03:38,358 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:03:38,358 INFO L432 AbstractCegarLoop]: Abstraction has 158 states and 183 transitions. [2018-01-20 22:03:38,358 INFO L433 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-01-20 22:03:38,358 INFO L276 IsEmpty]: Start isEmpty. Operand 158 states and 183 transitions. [2018-01-20 22:03:38,359 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2018-01-20 22:03:38,359 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:03:38,359 INFO L322 BasicCegarLoop]: trace histogram [3, 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] [2018-01-20 22:03:38,360 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr0EnsuresViolation]=== [2018-01-20 22:03:38,360 INFO L82 PathProgramCache]: Analyzing trace with hash 170187207, now seen corresponding path program 2 times [2018-01-20 22:03:38,360 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:03:38,360 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:03:38,361 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:38,361 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:38,361 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:38,369 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:38,370 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:03:38,552 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-01-20 22:03:38,552 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:03:38,552 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-20 22:03:38,553 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-20 22:03:38,553 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-20 22:03:38,553 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-01-20 22:03:38,553 INFO L87 Difference]: Start difference. First operand 158 states and 183 transitions. Second operand 7 states. [2018-01-20 22:03:38,728 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:03:38,728 INFO L93 Difference]: Finished difference Result 263 states and 303 transitions. [2018-01-20 22:03:38,728 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-20 22:03:38,728 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 60 [2018-01-20 22:03:38,728 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:03:38,729 INFO L225 Difference]: With dead ends: 263 [2018-01-20 22:03:38,729 INFO L226 Difference]: Without dead ends: 210 [2018-01-20 22:03:38,729 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 3 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2018-01-20 22:03:38,730 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 210 states. [2018-01-20 22:03:38,736 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 210 to 158. [2018-01-20 22:03:38,736 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 158 states. [2018-01-20 22:03:38,737 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 158 states to 158 states and 182 transitions. [2018-01-20 22:03:38,737 INFO L78 Accepts]: Start accepts. Automaton has 158 states and 182 transitions. Word has length 60 [2018-01-20 22:03:38,737 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:03:38,738 INFO L432 AbstractCegarLoop]: Abstraction has 158 states and 182 transitions. [2018-01-20 22:03:38,738 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-20 22:03:38,738 INFO L276 IsEmpty]: Start isEmpty. Operand 158 states and 182 transitions. [2018-01-20 22:03:38,738 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2018-01-20 22:03:38,739 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:03:38,739 INFO L322 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2018-01-20 22:03:38,739 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr0EnsuresViolation]=== [2018-01-20 22:03:38,739 INFO L82 PathProgramCache]: Analyzing trace with hash 312893297, now seen corresponding path program 2 times [2018-01-20 22:03:38,739 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:03:38,739 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:03:38,740 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:38,740 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-20 22:03:38,740 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:38,761 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:38,762 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:03:39,513 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2018-01-20 22:03:39,513 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:03:39,513 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:03:39,518 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-20 22:03:39,531 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-20 22:03:39,545 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-20 22:03:39,550 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-20 22:03:39,554 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:03:39,726 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 13 treesize of output 10 [2018-01-20 22:03:39,730 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 10 treesize of output 9 [2018-01-20 22:03:39,730 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:39,732 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:39,742 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:03:39,743 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:57, output treesize:74 [2018-01-20 22:03:39,821 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 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 70 treesize of output 58 [2018-01-20 22:03:39,828 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 1 new quantified variables, introduced 1 case distinctions, treesize of input 58 treesize of output 51 [2018-01-20 22:03:39,830 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-01-20 22:03:39,873 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-01-20 22:03:39,899 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-01-20 22:03:39,899 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:74, output treesize:97 [2018-01-20 22:03:40,119 WARN L1029 $PredicateComparison]: unable to prove that (exists ((main_~n~4.base Int) (main_~st~4.base Int)) (let ((.cse0 (store |c_old(#valid)| main_~n~4.base 1))) (let ((.cse1 (store .cse0 |c_main_~#sentinel~4.base| 1))) (and (= 0 (select .cse0 |c_main_~#sentinel~4.base|)) (not (= 0 main_~n~4.base)) (= (select .cse1 main_~st~4.base) 0) (= |c_#valid| (store (store .cse1 main_~st~4.base 0) main_~n~4.base 0)) (not (= main_~st~4.base 0)) (= 0 (select |c_old(#valid)| main_~n~4.base)))))) is different from true [2018-01-20 22:03:40,138 WARN L1029 $PredicateComparison]: unable to prove that (exists ((|main_~#sentinel~4.base| Int) (main_~n~4.base Int) (main_~st~4.base Int)) (let ((.cse0 (store |c_old(#valid)| main_~n~4.base 1))) (let ((.cse1 (store .cse0 |main_~#sentinel~4.base| 1))) (and (= 0 (select .cse0 |main_~#sentinel~4.base|)) (not (= 0 main_~n~4.base)) (= (select .cse1 main_~st~4.base) 0) (not (= main_~st~4.base 0)) (= |c_#valid| (store (store (store .cse1 main_~st~4.base 0) main_~n~4.base 0) |main_~#sentinel~4.base| 0)) (= 0 (select |c_old(#valid)| main_~n~4.base)))))) is different from true [2018-01-20 22:03:40,168 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 2 not checked. [2018-01-20 22:03:40,188 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:03:40,188 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 14] total 28 [2018-01-20 22:03:40,188 INFO L409 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-01-20 22:03:40,189 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-01-20 22:03:40,189 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=648, Unknown=3, NotChecked=102, Total=812 [2018-01-20 22:03:40,189 INFO L87 Difference]: Start difference. First operand 158 states and 182 transitions. Second operand 29 states. [2018-01-20 22:03:41,373 WARN L146 SmtUtils]: Spent 161ms on a formula simplification. DAG size of input: 104 DAG size of output 50 [2018-01-20 22:03:42,297 WARN L146 SmtUtils]: Spent 100ms on a formula simplification. DAG size of input: 70 DAG size of output 63 [2018-01-20 22:03:42,600 WARN L146 SmtUtils]: Spent 115ms on a formula simplification. DAG size of input: 73 DAG size of output 64 [2018-01-20 22:03:42,784 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:03:42,785 INFO L93 Difference]: Finished difference Result 216 states and 247 transitions. [2018-01-20 22:03:42,785 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-01-20 22:03:42,785 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 70 [2018-01-20 22:03:42,785 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:03:42,786 INFO L225 Difference]: With dead ends: 216 [2018-01-20 22:03:42,786 INFO L226 Difference]: Without dead ends: 211 [2018-01-20 22:03:42,787 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 106 GetRequests, 62 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 190 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=198, Invalid=1691, Unknown=11, NotChecked=170, Total=2070 [2018-01-20 22:03:42,788 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 211 states. [2018-01-20 22:03:42,805 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 211 to 200. [2018-01-20 22:03:42,805 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 200 states. [2018-01-20 22:03:42,806 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 200 states to 200 states and 231 transitions. [2018-01-20 22:03:42,807 INFO L78 Accepts]: Start accepts. Automaton has 200 states and 231 transitions. Word has length 70 [2018-01-20 22:03:42,807 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:03:42,807 INFO L432 AbstractCegarLoop]: Abstraction has 200 states and 231 transitions. [2018-01-20 22:03:42,807 INFO L433 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-01-20 22:03:42,807 INFO L276 IsEmpty]: Start isEmpty. Operand 200 states and 231 transitions. [2018-01-20 22:03:42,808 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2018-01-20 22:03:42,808 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:03:42,808 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] [2018-01-20 22:03:42,808 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr0EnsuresViolation]=== [2018-01-20 22:03:42,809 INFO L82 PathProgramCache]: Analyzing trace with hash -29771918, now seen corresponding path program 1 times [2018-01-20 22:03:42,809 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:03:42,809 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:03:42,810 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:42,810 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-20 22:03:42,810 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:03:42,826 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:42,827 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:03:43,047 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:03:43,048 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:03:43,048 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 22:03:43,054 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:03:43,085 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:03:43,089 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:03:43,093 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:03:43,094 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:43,099 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:43,099 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:10, output treesize:9 [2018-01-20 22:03:43,137 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:03:43,138 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:03:43,140 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:03:43,141 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:43,148 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:43,149 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:26, output treesize:24 [2018-01-20 22:03:43,170 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:03:43,172 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:03:43,172 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:43,173 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:43,180 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:03:43,180 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:35, output treesize:32 [2018-01-20 22:03:43,226 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 37 treesize of output 41 [2018-01-20 22:03:43,228 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 11 [2018-01-20 22:03:43,228 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:43,232 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:43,240 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:03:43,240 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:51, output treesize:43 [2018-01-20 22:03:43,306 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 50 treesize of output 40 [2018-01-20 22:03:43,308 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 20 treesize of output 25 [2018-01-20 22:03:43,308 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:43,314 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:43,320 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:03:43,320 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:58, output treesize:50 [2018-01-20 22:03:47,365 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:03:47,366 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:03:47,410 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:03:47,410 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 4 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:03:47,411 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:47,417 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:03:47,417 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:47, output treesize:40 [2018-01-20 22:03:47,472 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 25 [2018-01-20 22:03:47,474 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:03:47,475 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:47,479 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:03:47,479 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-20 22:03:47,481 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:47,485 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:03:47,485 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 3 variables, input treesize:44, output treesize:8 [2018-01-20 22:03:47,561 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 3 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-20 22:03:47,581 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:03:47,581 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 17] total 31 [2018-01-20 22:03:47,581 INFO L409 AbstractCegarLoop]: Interpolant automaton has 31 states [2018-01-20 22:03:47,581 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2018-01-20 22:03:47,581 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=112, Invalid=816, Unknown=2, NotChecked=0, Total=930 [2018-01-20 22:03:47,582 INFO L87 Difference]: Start difference. First operand 200 states and 231 transitions. Second operand 31 states. [2018-01-20 22:04:20,687 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:04:20,687 INFO L93 Difference]: Finished difference Result 503 states and 587 transitions. [2018-01-20 22:04:20,688 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-01-20 22:04:20,688 INFO L78 Accepts]: Start accepts. Automaton has 31 states. Word has length 74 [2018-01-20 22:04:20,688 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:04:20,689 INFO L225 Difference]: With dead ends: 503 [2018-01-20 22:04:20,689 INFO L226 Difference]: Without dead ends: 465 [2018-01-20 22:04:20,690 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 61 SyntacticMatches, 0 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 696 ImplicationChecksByTransitivity, 30.5s TimeCoverageRelationStatistics Valid=630, Invalid=2661, Unknown=15, NotChecked=0, Total=3306 [2018-01-20 22:04:20,691 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 465 states. [2018-01-20 22:04:20,708 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 465 to 278. [2018-01-20 22:04:20,708 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 278 states. [2018-01-20 22:04:20,710 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 278 states to 278 states and 330 transitions. [2018-01-20 22:04:20,710 INFO L78 Accepts]: Start accepts. Automaton has 278 states and 330 transitions. Word has length 74 [2018-01-20 22:04:20,710 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:04:20,710 INFO L432 AbstractCegarLoop]: Abstraction has 278 states and 330 transitions. [2018-01-20 22:04:20,710 INFO L433 AbstractCegarLoop]: Interpolant automaton has 31 states. [2018-01-20 22:04:20,710 INFO L276 IsEmpty]: Start isEmpty. Operand 278 states and 330 transitions. [2018-01-20 22:04:20,712 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2018-01-20 22:04:20,712 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:04:20,712 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] [2018-01-20 22:04:20,712 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr0EnsuresViolation]=== [2018-01-20 22:04:20,712 INFO L82 PathProgramCache]: Analyzing trace with hash -556285838, now seen corresponding path program 1 times [2018-01-20 22:04:20,712 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:04:20,712 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:04:20,713 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:04:20,713 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:04:20,713 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:04:20,728 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:04:20,729 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:04:21,090 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:04:21,091 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:04:21,091 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 22:04:21,104 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:04:21,141 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:04:21,145 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:04:21,148 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:04:21,148 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:04:21,152 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:04:21,152 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:6, output treesize:5 [2018-01-20 22:04:21,208 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:04:21,209 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:04:21,210 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:04:21,210 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:04:21,218 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:04:21,218 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:30, output treesize:28 [2018-01-20 22:04:21,245 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 21 treesize of output 16 [2018-01-20 22:04:21,248 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:04:21,254 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 16 treesize of output 23 [2018-01-20 22:04:21,255 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:04:21,270 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:04:21,290 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:04:21,290 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:40 [2018-01-20 22:04:21,349 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 46 [2018-01-20 22:04:21,351 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:04:21,352 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:04:21,357 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:04:21,394 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:04:21,395 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:63, output treesize:53 [2018-01-20 22:04:21,473 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 53 [2018-01-20 22:04:21,475 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:04:21,476 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:04:21,481 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:04:21,490 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:04:21,490 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:72, output treesize:62 [2018-01-20 22:04:25,546 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:04:25,547 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:04:25,547 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:04:25,548 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 25 [2018-01-20 22:04:25,548 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:04:25,555 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:04:25,555 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:57, output treesize:50 [2018-01-20 22:04:25,623 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 50 treesize of output 41 [2018-01-20 22:04:25,625 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:04:25,626 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 27 treesize of output 18 [2018-01-20 22:04:25,626 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:04:25,630 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:04:25,631 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-20 22:04:25,632 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:04:25,634 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:04:25,634 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:57, output treesize:7 [2018-01-20 22:04:25,719 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 3 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-20 22:04:25,739 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:04:25,739 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 20] total 31 [2018-01-20 22:04:25,739 INFO L409 AbstractCegarLoop]: Interpolant automaton has 31 states [2018-01-20 22:04:25,740 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2018-01-20 22:04:25,740 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=124, Invalid=804, Unknown=2, NotChecked=0, Total=930 [2018-01-20 22:04:25,740 INFO L87 Difference]: Start difference. First operand 278 states and 330 transitions. Second operand 31 states. Received shutdown request... [2018-01-20 22:04:37,843 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-01-20 22:04:37,843 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-20 22:04:37,845 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.01 10:04:37 BoogieIcfgContainer [2018-01-20 22:04:37,845 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-20 22:04:37,846 INFO L168 Benchmark]: Toolchain (without parser) took 67498.08 ms. Allocated memory was 306.2 MB in the beginning and 632.8 MB in the end (delta: 326.6 MB). Free memory was 264.5 MB in the beginning and 552.5 MB in the end (delta: -288.0 MB). Peak memory consumption was 38.6 MB. Max. memory is 5.3 GB. [2018-01-20 22:04:37,848 INFO L168 Benchmark]: CDTParser took 0.13 ms. Allocated memory is still 306.2 MB. Free memory is still 270.5 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-20 22:04:37,848 INFO L168 Benchmark]: CACSL2BoogieTranslator took 202.96 ms. Allocated memory is still 306.2 MB. Free memory was 263.5 MB in the beginning and 252.4 MB in the end (delta: 11.1 MB). Peak memory consumption was 11.1 MB. Max. memory is 5.3 GB. [2018-01-20 22:04:37,848 INFO L168 Benchmark]: Boogie Preprocessor took 35.22 ms. Allocated memory is still 306.2 MB. Free memory was 252.4 MB in the beginning and 250.3 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:04:37,849 INFO L168 Benchmark]: RCFGBuilder took 472.33 ms. Allocated memory is still 306.2 MB. Free memory was 250.3 MB in the beginning and 219.7 MB in the end (delta: 30.6 MB). Peak memory consumption was 30.6 MB. Max. memory is 5.3 GB. [2018-01-20 22:04:37,849 INFO L168 Benchmark]: TraceAbstraction took 66779.87 ms. Allocated memory was 306.2 MB in the beginning and 632.8 MB in the end (delta: 326.6 MB). Free memory was 219.7 MB in the beginning and 552.5 MB in the end (delta: -332.8 MB). There was no memory consumed. Max. memory is 5.3 GB. [2018-01-20 22:04:37,851 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.13 ms. Allocated memory is still 306.2 MB. Free memory is still 270.5 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 202.96 ms. Allocated memory is still 306.2 MB. Free memory was 263.5 MB in the beginning and 252.4 MB in the end (delta: 11.1 MB). Peak memory consumption was 11.1 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 35.22 ms. Allocated memory is still 306.2 MB. Free memory was 252.4 MB in the beginning and 250.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 472.33 ms. Allocated memory is still 306.2 MB. Free memory was 250.3 MB in the beginning and 219.7 MB in the end (delta: 30.6 MB). Peak memory consumption was 30.6 MB. Max. memory is 5.3 GB. * TraceAbstraction took 66779.87 ms. Allocated memory was 306.2 MB in the beginning and 632.8 MB in the end (delta: 326.6 MB). Free memory was 219.7 MB in the beginning and 552.5 MB in the end (delta: -332.8 MB). There was no memory consumed. 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, 101 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=101occurred 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: [L629] EXPR, FCALL malloc(sizeof(*root)) VAL [malloc(sizeof(*root))={11:0}] [L629] struct TreeNode* root = malloc(sizeof(*root)), *n; VAL [malloc(sizeof(*root))={11:0}, root={11:0}] [L630] FCALL root->left = ((void *)0) VAL [malloc(sizeof(*root))={11:0}, root={11:0}] [L631] FCALL root->right = ((void *)0) VAL [malloc(sizeof(*root))={11:0}, root={11:0}] [L632] COND FALSE !(__VERIFIER_nondet_int()) [L651] FCALL struct TreeNode sentinel; VAL [malloc(sizeof(*root))={11:0}, root={11:0}, sentinel={10:0}] [L652] n = root [L653] struct TreeNode* pred = &sentinel; [L654] struct TreeNode* succ = ((void *)0); VAL [malloc(sizeof(*root))={11:0}, n={11:0}, pred={10:0}, root={11:0}, sentinel={10:0}, succ={0:0}] [L655] COND TRUE n != &sentinel VAL [malloc(sizeof(*root))={11:0}, n={11:0}, pred={10:0}, root={11:0}, sentinel={10:0}, succ={0:0}] [L656] EXPR, FCALL n->left VAL [malloc(sizeof(*root))={11:0}, n={11:0}, n->left={0:0}, pred={10:0}, root={11:0}, sentinel={10:0}, succ={0:0}] [L656] succ = n->left [L657] EXPR, FCALL n->right VAL [malloc(sizeof(*root))={11:0}, n={11:0}, n->right={0:0}, pred={10:0}, root={11:0}, sentinel={10:0}, succ={0:0}] [L657] FCALL n->left = n->right VAL [malloc(sizeof(*root))={11:0}, n={11:0}, n->right={0:0}, pred={10:0}, root={11:0}, sentinel={10:0}, succ={0:0}] [L658] FCALL n->right = pred VAL [malloc(sizeof(*root))={11:0}, n={11:0}, pred={10:0}, root={11:0}, sentinel={10:0}, succ={0:0}] [L659] pred = n [L660] n = succ VAL [malloc(sizeof(*root))={11:0}, n={0:0}, pred={11:0}, root={11:0}, sentinel={10:0}, succ={0:0}] [L661] COND TRUE !n [L662] n = pred [L663] pred = ((void *)0) VAL [malloc(sizeof(*root))={11:0}, n={11:0}, pred={0:0}, root={11:0}, sentinel={10:0}, succ={0:0}] [L655] COND TRUE n != &sentinel VAL [malloc(sizeof(*root))={11:0}, n={11:0}, pred={0:0}, root={11:0}, sentinel={10:0}, succ={0:0}] [L656] EXPR, FCALL n->left VAL [malloc(sizeof(*root))={11:0}, n={11:0}, n->left={0:0}, pred={0:0}, root={11:0}, sentinel={10:0}, succ={0:0}] [L656] succ = n->left [L657] EXPR, FCALL n->right VAL [malloc(sizeof(*root))={11:0}, n={11:0}, n->right={10:0}, pred={0:0}, root={11:0}, sentinel={10:0}, succ={0:0}] [L657] FCALL n->left = n->right VAL [malloc(sizeof(*root))={11:0}, n={11:0}, n->right={10:0}, pred={0:0}, root={11:0}, sentinel={10:0}, succ={0:0}] [L658] FCALL n->right = pred VAL [malloc(sizeof(*root))={11:0}, n={11:0}, pred={0:0}, root={11:0}, sentinel={10:0}, succ={0:0}] [L659] pred = n [L660] n = succ VAL [malloc(sizeof(*root))={11:0}, n={0:0}, pred={11:0}, root={11:0}, sentinel={10:0}, succ={0:0}] [L661] COND TRUE !n [L662] n = pred [L663] pred = ((void *)0) VAL [malloc(sizeof(*root))={11:0}, n={11:0}, pred={0:0}, root={11:0}, sentinel={10:0}, succ={0:0}] [L655] COND TRUE n != &sentinel VAL [malloc(sizeof(*root))={11:0}, n={11:0}, pred={0:0}, root={11:0}, sentinel={10:0}, succ={0:0}] [L656] EXPR, FCALL n->left VAL [malloc(sizeof(*root))={11:0}, n={11:0}, n->left={10:0}, pred={0:0}, root={11:0}, sentinel={10:0}, succ={0:0}] [L656] succ = n->left [L657] EXPR, FCALL n->right VAL [malloc(sizeof(*root))={11:0}, n={11:0}, n->right={0:0}, pred={0:0}, root={11:0}, sentinel={10:0}, succ={10:0}] [L657] FCALL n->left = n->right VAL [malloc(sizeof(*root))={11:0}, n={11:0}, n->right={0:0}, pred={0:0}, root={11:0}, sentinel={10:0}, succ={10:0}] [L658] FCALL n->right = pred VAL [malloc(sizeof(*root))={11:0}, n={11:0}, pred={0:0}, root={11:0}, sentinel={10:0}, succ={10:0}] [L659] pred = n [L660] n = succ VAL [malloc(sizeof(*root))={11:0}, n={10:0}, pred={11:0}, root={11:0}, sentinel={10:0}, succ={10:0}] [L661] COND FALSE !(!n) VAL [malloc(sizeof(*root))={11:0}, n={10:0}, pred={11:0}, root={11:0}, sentinel={10:0}, succ={10:0}] [L655] COND FALSE !(n != &sentinel) VAL [malloc(sizeof(*root))={11:0}, n={10:0}, pred={11:0}, root={11:0}, sentinel={10:0}, succ={10:0}] [L666] COND FALSE !(pred != root) VAL [malloc(sizeof(*root))={11:0}, n={10:0}, pred={11:0}, root={11:0}, sentinel={10:0}, succ={10:0}] [L668] n = ((void *)0) VAL [malloc(sizeof(*root))={11:0}, n={0:0}, pred={11:0}, root={11:0}, sentinel={10:0}, succ={10:0}] [L669] EXPR, FCALL malloc(sizeof(*s)) VAL [malloc(sizeof(*root))={11:0}, malloc(sizeof(*s))={12:0}, n={0:0}, pred={11:0}, root={11:0}, sentinel={10:0}, succ={10:0}] [L669] struct StackItem* s = malloc(sizeof(*s)), *st; VAL [malloc(sizeof(*root))={11:0}, malloc(sizeof(*s))={12:0}, n={0:0}, pred={11:0}, root={11:0}, s={12:0}, sentinel={10:0}, succ={10:0}] [L670] FCALL s->next = ((void *)0) VAL [malloc(sizeof(*root))={11:0}, malloc(sizeof(*s))={12:0}, n={0:0}, pred={11:0}, root={11:0}, s={12:0}, sentinel={10:0}, succ={10:0}] [L671] FCALL s->node = root VAL [malloc(sizeof(*root))={11:0}, malloc(sizeof(*s))={12:0}, n={0:0}, pred={11:0}, root={11:0}, s={12:0}, sentinel={10:0}, succ={10:0}] [L672] COND TRUE s != ((void *)0) [L673] st = s VAL [malloc(sizeof(*root))={11:0}, malloc(sizeof(*s))={12:0}, n={0:0}, pred={11:0}, root={11:0}, s={12:0}, s={12:0}, sentinel={10:0}, succ={10:0}] [L674] EXPR, FCALL s->next VAL [malloc(sizeof(*root))={11:0}, malloc(sizeof(*s))={12:0}, n={0:0}, pred={11:0}, root={11:0}, s={12:0}, s={12:0}, s->next={0:0}, sentinel={10:0}, succ={10:0}] [L674] s = s->next [L675] EXPR, FCALL st->node VAL [malloc(sizeof(*root))={11:0}, malloc(sizeof(*s))={12:0}, n={0:0}, pred={11:0}, root={11:0}, s={0:0}, s={12:0}, sentinel={10:0}, st->node={11:0}, succ={10:0}] [L675] n = st->node [L676] FCALL free(st) VAL [malloc(sizeof(*root))={11:0}, malloc(sizeof(*s))={12:0}, n={11:0}, pred={11:0}, root={11:0}, s={12:0}, s={0:0}, sentinel={10:0}, succ={10:0}] [L677] FCALL n->left VAL [malloc(sizeof(*root))={11:0}, malloc(sizeof(*s))={12:0}, n={11:0}, n->left={0:0}, pred={11:0}, root={11:0}, s={12:0}, s={0:0}, sentinel={10:0}, succ={10:0}] [L677] COND FALSE !(n->left) [L683] FCALL n->right VAL [malloc(sizeof(*root))={11:0}, malloc(sizeof(*s))={12:0}, n={11:0}, n->right={0:0}, pred={11:0}, root={11:0}, s={0:0}, s={12:0}, sentinel={10:0}, succ={10:0}] [L683] COND FALSE !(n->right) [L689] FCALL free(n) VAL [malloc(sizeof(*root))={11:0}, malloc(sizeof(*s))={12:0}, n={11:0}, pred={11:0}, root={11:0}, s={12:0}, s={0:0}, sentinel={10:0}, succ={10:0}] [L672] COND FALSE !(s != ((void *)0)) VAL [malloc(sizeof(*root))={11:0}, malloc(sizeof(*s))={12:0}, n={11:0}, pred={11:0}, root={11:0}, s={0:0}, s={12:0}, sentinel={10:0}, succ={10:0}] [L691] return 0; VAL [\result=0, malloc(sizeof(*root))={11:0}, malloc(sizeof(*s))={12:0}, n={11:0}, pred={11:0}, root={11:0}, s={0:0}, s={12:0}, sentinel={10:0}, succ={10:0}] [L691] return 0; - StatisticsResult: Ultimate Automizer benchmark data for error location: ULTIMATE.startErr0EnsuresViolation CFG has 3 procedures, 101 locations, 3 error locations. UNSAFE Result, 4.3s OverallTime, 8 OverallIterations, 4 TraceHistogramMax, 2.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 741 SDtfs, 1538 SDslu, 3471 SDs, 0 SdLazy, 1971 SolverSat, 66 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 258 GetRequests, 160 SyntacticMatches, 4 SemanticMatches, 94 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 249 ImplicationChecksByTransitivity, 1.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=160occurred in iteration=6, 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, 7 MinimizatonAttempts, 200 StatesRemovedByMinimization, 6 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.2s SatisfiabilityAnalysisTime, 1.3s InterpolantComputationTime, 564 NumberOfCodeBlocks, 564 NumberOfCodeBlocksAsserted, 11 NumberOfCheckSat, 482 ConstructedInterpolants, 0 QuantifiedInterpolants, 94348 SizeOfPredicates, 23 NumberOfNonLiveVariables, 605 ConjunctsInSsa, 52 ConjunctsInUnsatCore, 10 InterpolantComputations, 5 PerfectInterpolantSequences, 32/66 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available - TimeoutResultAtElement [Line: 620]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 620). Cancelled while BasicCegarLoop was constructing difference of abstraction (278states) and interpolant automaton (currently 21 states, 31 states before enhancement), while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - StatisticsResult: Ultimate Automizer benchmark data for error location: mainErr0EnsuresViolation CFG has 3 procedures, 101 locations, 3 error locations. TIMEOUT Result, 62.2s OverallTime, 10 OverallIterations, 4 TraceHistogramMax, 49.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 966 SDtfs, 2753 SDslu, 6978 SDs, 0 SdLazy, 5232 SolverSat, 276 SolverUnsat, 16 SolverUnknown, 0 SolverNotchecked, 14.9s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 586 GetRequests, 336 SyntacticMatches, 8 SemanticMatches, 241 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 1611 ImplicationChecksByTransitivity, 42.6s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=278occurred in iteration=9, 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, 9 MinimizatonAttempts, 398 StatesRemovedByMinimization, 8 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.2s SatisfiabilityAnalysisTime, 12.0s InterpolantComputationTime, 908 NumberOfCodeBlocks, 908 NumberOfCodeBlocksAsserted, 17 NumberOfCheckSat, 892 ConstructedInterpolants, 41 QuantifiedInterpolants, 584426 SizeOfPredicates, 74 NumberOfNonLiveVariables, 1338 ConjunctsInSsa, 173 ConjunctsInUnsatCore, 16 InterpolantComputations, 5 PerfectInterpolantSequences, 112/170 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/tree_dsw_true-valid-memsafety_false-termination.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-20_22-04-37-860.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/tree_dsw_true-valid-memsafety_false-termination.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-20_22-04-37-860.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/tree_dsw_true-valid-memsafety_false-termination.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-1-2018-01-20_22-04-37-860.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/tree_dsw_true-valid-memsafety_false-termination.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-2-2018-01-20_22-04-37-860.csv Completed graceful shutdown