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-47db877 [2018-01-23 14:29:33,896 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-23 14:29:33,924 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-23 14:29:33,938 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-23 14:29:33,939 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-23 14:29:33,940 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-23 14:29:33,941 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-23 14:29:33,942 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-23 14:29:33,944 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-23 14:29:33,945 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-23 14:29:33,946 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-23 14:29:33,946 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-23 14:29:33,947 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-23 14:29:33,949 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-23 14:29:33,949 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-23 14:29:33,952 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-23 14:29:33,954 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-23 14:29:33,956 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-23 14:29:33,957 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-23 14:29:33,958 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-23 14:29:33,960 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-23 14:29:33,961 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-23 14:29:33,961 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-23 14:29:33,962 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-23 14:29:33,963 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-23 14:29:33,964 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-23 14:29:33,964 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-23 14:29:33,965 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-23 14:29:33,965 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-23 14:29:33,965 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-23 14:29:33,966 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-23 14:29:33,966 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-23 14:29:33,975 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-23 14:29:33,975 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-23 14:29:33,976 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-23 14:29:33,976 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-23 14:29:33,976 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-23 14:29:33,977 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-23 14:29:33,977 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-23 14:29:33,977 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-23 14:29:33,977 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-23 14:29:33,977 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-23 14:29:33,977 INFO L133 SettingsManager]: * Check allocation purity=true [2018-01-23 14:29:33,978 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-23 14:29:33,978 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-23 14:29:33,978 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-23 14:29:33,978 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-01-23 14:29:33,978 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-23 14:29:33,978 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-01-23 14:29:33,978 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-23 14:29:33,978 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-01-23 14:29:33,979 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-01-23 14:29:33,979 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-23 14:29:33,979 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-01-23 14:29:33,979 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-23 14:29:33,979 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-23 14:29:33,980 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-23 14:29:33,980 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-23 14:29:33,980 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-23 14:29:33,980 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-23 14:29:33,980 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-23 14:29:33,980 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-23 14:29:33,980 INFO L133 SettingsManager]: * Stop after first violation was found=false [2018-01-23 14:29:33,981 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-01-23 14:29:33,981 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-23 14:29:33,981 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-23 14:29:33,981 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-23 14:29:33,982 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-23 14:29:33,982 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-23 14:29:34,015 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-23 14:29:34,026 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-23 14:29:34,029 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-23 14:29:34,031 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-23 14:29:34,031 INFO L276 PluginConnector]: CDTParser initialized [2018-01-23 14:29:34,032 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-23 14:29:34,216 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-23 14:29:34,220 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-23 14:29:34,221 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-23 14:29:34,221 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-23 14:29:34,227 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-23 14:29:34,227 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.01 02:29:34" (1/1) ... [2018-01-23 14:29:34,230 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 23.01 02:29:34, skipping insertion in model container [2018-01-23 14:29:34,230 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.01 02:29:34" (1/1) ... [2018-01-23 14:29:34,244 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-23 14:29:34,286 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-23 14:29:34,418 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-23 14:29:34,445 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-23 14:29:34,456 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:29:34 WrapperNode [2018-01-23 14:29:34,456 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-23 14:29:34,458 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-23 14:29:34,458 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-23 14:29:34,458 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-23 14:29:34,475 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:29:34" (1/1) ... [2018-01-23 14:29:34,475 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:29:34" (1/1) ... [2018-01-23 14:29:34,491 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:29:34" (1/1) ... [2018-01-23 14:29:34,492 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:29:34" (1/1) ... [2018-01-23 14:29:34,501 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:29:34" (1/1) ... [2018-01-23 14:29:34,506 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:29:34" (1/1) ... [2018-01-23 14:29:34,508 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:29:34" (1/1) ... [2018-01-23 14:29:34,511 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-23 14:29:34,511 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-23 14:29:34,511 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-23 14:29:34,512 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-23 14:29:34,513 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:29:34" (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-23 14:29:34,565 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-23 14:29:34,565 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-23 14:29:34,565 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-23 14:29:34,565 INFO L128 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2018-01-23 14:29:34,566 INFO L128 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2018-01-23 14:29:34,566 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-23 14:29:34,566 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-23 14:29:34,566 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-23 14:29:34,566 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-23 14:29:34,566 INFO L128 BoogieDeclarations]: Found specification of procedure malloc [2018-01-23 14:29:34,567 INFO L128 BoogieDeclarations]: Found specification of procedure free [2018-01-23 14:29:34,567 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-23 14:29:34,567 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-23 14:29:34,567 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-23 14:29:34,979 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-23 14:29:34,979 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.01 02:29:34 BoogieIcfgContainer [2018-01-23 14:29:34,980 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-23 14:29:34,981 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-23 14:29:34,983 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-23 14:29:34,985 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-23 14:29:34,985 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 23.01 02:29:34" (1/3) ... [2018-01-23 14:29:34,986 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 23.01 02:29:34, skipping insertion in model container [2018-01-23 14:29:34,987 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:29:34" (2/3) ... [2018-01-23 14:29:34,987 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 23.01 02:29:34, skipping insertion in model container [2018-01-23 14:29:34,987 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.01 02:29:34" (3/3) ... [2018-01-23 14:29:34,989 INFO L105 eAbstractionObserver]: Analyzing ICFG tree_dsw_true-valid-memsafety_false-termination.i [2018-01-23 14:29:34,998 INFO L130 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-23 14:29:35,006 INFO L142 ceAbstractionStarter]: Appying trace abstraction to program that has 3 error locations. [2018-01-23 14:29:35,054 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-23 14:29:35,055 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-23 14:29:35,055 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-23 14:29:35,055 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-23 14:29:35,055 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-23 14:29:35,055 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-23 14:29:35,055 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-23 14:29:35,056 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.initErr0EnsuresViolation======== [2018-01-23 14:29:35,056 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-23 14:29:35,078 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states. [2018-01-23 14:29:35,083 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2018-01-23 14:29:35,083 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:29:35,084 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1] [2018-01-23 14:29:35,084 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.initErr0EnsuresViolation]=== [2018-01-23 14:29:35,089 INFO L82 PathProgramCache]: Analyzing trace with hash 214305, now seen corresponding path program 1 times [2018-01-23 14:29:35,091 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:29:35,091 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:29:35,131 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:35,132 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:35,132 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:35,165 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-23 14:29:35,172 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-23 14:29:35,192 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-23 14:29:35,198 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-23 14:29:35,204 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-23 14:29:35,204 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-23 14:29:35,204 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-23 14:29:35,204 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-23 14:29:35,204 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-23 14:29:35,204 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-23 14:29:35,204 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-23 14:29:35,204 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.startErr0EnsuresViolation======== [2018-01-23 14:29:35,204 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-23 14:29:35,207 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states. [2018-01-23 14:29:35,209 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2018-01-23 14:29:35,209 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:29:35,209 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-23 14:29:35,209 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:29:35,209 INFO L82 PathProgramCache]: Analyzing trace with hash 210929596, now seen corresponding path program 1 times [2018-01-23 14:29:35,209 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:29:35,210 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:29:35,210 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:35,210 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:35,211 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:35,229 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:35,238 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:29:35,279 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-23 14:29:35,281 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:29:35,281 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-23 14:29:35,283 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-23 14:29:35,376 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-23 14:29:35,377 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-23 14:29:35,379 INFO L87 Difference]: Start difference. First operand 101 states. Second operand 2 states. [2018-01-23 14:29:35,407 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:29:35,408 INFO L93 Difference]: Finished difference Result 192 states and 226 transitions. [2018-01-23 14:29:35,408 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-23 14:29:35,409 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 26 [2018-01-23 14:29:35,410 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:29:35,419 INFO L225 Difference]: With dead ends: 192 [2018-01-23 14:29:35,419 INFO L226 Difference]: Without dead ends: 98 [2018-01-23 14:29:35,421 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-23 14:29:35,439 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2018-01-23 14:29:35,458 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 98. [2018-01-23 14:29:35,459 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 98 states. [2018-01-23 14:29:35,461 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 111 transitions. [2018-01-23 14:29:35,462 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 111 transitions. Word has length 26 [2018-01-23 14:29:35,462 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:29:35,463 INFO L432 AbstractCegarLoop]: Abstraction has 98 states and 111 transitions. [2018-01-23 14:29:35,463 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-23 14:29:35,463 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 111 transitions. [2018-01-23 14:29:35,464 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-01-23 14:29:35,464 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:29:35,464 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-23 14:29:35,464 INFO L371 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:29:35,464 INFO L82 PathProgramCache]: Analyzing trace with hash -615979456, now seen corresponding path program 1 times [2018-01-23 14:29:35,464 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:29:35,464 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:29:35,465 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:35,465 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:35,465 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:35,490 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:35,491 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:29:35,563 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-23 14:29:35,563 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:29:35,564 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-23 14:29:35,565 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-23 14:29:35,566 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-23 14:29:35,566 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-23 14:29:35,566 INFO L87 Difference]: Start difference. First operand 98 states and 111 transitions. Second operand 4 states. [2018-01-23 14:29:35,606 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:29:35,606 INFO L93 Difference]: Finished difference Result 109 states and 122 transitions. [2018-01-23 14:29:35,606 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-23 14:29:35,607 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 30 [2018-01-23 14:29:35,607 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:29:35,609 INFO L225 Difference]: With dead ends: 109 [2018-01-23 14:29:35,609 INFO L226 Difference]: Without dead ends: 102 [2018-01-23 14:29:35,610 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-23 14:29:35,610 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2018-01-23 14:29:35,617 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 100. [2018-01-23 14:29:35,618 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 100 states. [2018-01-23 14:29:35,620 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 113 transitions. [2018-01-23 14:29:35,620 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 113 transitions. Word has length 30 [2018-01-23 14:29:35,621 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:29:35,621 INFO L432 AbstractCegarLoop]: Abstraction has 100 states and 113 transitions. [2018-01-23 14:29:35,621 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-23 14:29:35,621 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 113 transitions. [2018-01-23 14:29:35,623 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2018-01-23 14:29:35,623 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:29:35,623 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-23 14:29:35,623 INFO L371 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:29:35,623 INFO L82 PathProgramCache]: Analyzing trace with hash -298055667, now seen corresponding path program 1 times [2018-01-23 14:29:35,623 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:29:35,623 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:29:35,624 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:35,624 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:35,625 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:35,645 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:35,646 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:29:35,717 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-23 14:29:35,717 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:29:35,718 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-01-23 14:29:35,718 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-23 14:29:35,718 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-23 14:29:35,719 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-23 14:29:35,719 INFO L87 Difference]: Start difference. First operand 100 states and 113 transitions. Second operand 6 states. [2018-01-23 14:29:35,927 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:29:35,927 INFO L93 Difference]: Finished difference Result 154 states and 171 transitions. [2018-01-23 14:29:35,928 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-01-23 14:29:35,928 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 42 [2018-01-23 14:29:35,928 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:29:35,929 INFO L225 Difference]: With dead ends: 154 [2018-01-23 14:29:35,930 INFO L226 Difference]: Without dead ends: 114 [2018-01-23 14:29:35,930 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-23 14:29:35,931 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2018-01-23 14:29:35,938 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 102. [2018-01-23 14:29:35,938 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 102 states. [2018-01-23 14:29:35,940 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 115 transitions. [2018-01-23 14:29:35,940 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 115 transitions. Word has length 42 [2018-01-23 14:29:35,941 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:29:35,941 INFO L432 AbstractCegarLoop]: Abstraction has 102 states and 115 transitions. [2018-01-23 14:29:35,941 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-23 14:29:35,941 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 115 transitions. [2018-01-23 14:29:35,943 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2018-01-23 14:29:35,943 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:29:35,943 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-23 14:29:35,943 INFO L371 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:29:35,944 INFO L82 PathProgramCache]: Analyzing trace with hash 1908754361, now seen corresponding path program 1 times [2018-01-23 14:29:35,944 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:29:35,944 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:29:35,945 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:35,945 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:35,945 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:35,961 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:35,962 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:29:36,028 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-23 14:29:36,028 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:29:36,028 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-23 14:29:36,048 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:36,092 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:36,097 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:29:36,171 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-23 14:29:36,191 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-23 14:29:36,191 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [8] total 11 [2018-01-23 14:29:36,191 INFO L409 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-01-23 14:29:36,192 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-01-23 14:29:36,192 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=90, Unknown=0, NotChecked=0, Total=110 [2018-01-23 14:29:36,192 INFO L87 Difference]: Start difference. First operand 102 states and 115 transitions. Second operand 11 states. [2018-01-23 14:29:36,621 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:29:36,621 INFO L93 Difference]: Finished difference Result 251 states and 279 transitions. [2018-01-23 14:29:36,621 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-01-23 14:29:36,621 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 52 [2018-01-23 14:29:36,622 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:29:36,626 INFO L225 Difference]: With dead ends: 251 [2018-01-23 14:29:36,626 INFO L226 Difference]: Without dead ends: 211 [2018-01-23 14:29:36,627 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 71 GetRequests, 51 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=139, Invalid=323, Unknown=0, NotChecked=0, Total=462 [2018-01-23 14:29:36,628 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 211 states. [2018-01-23 14:29:36,638 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 211 to 113. [2018-01-23 14:29:36,638 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 113 states. [2018-01-23 14:29:36,639 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 128 transitions. [2018-01-23 14:29:36,640 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 128 transitions. Word has length 52 [2018-01-23 14:29:36,640 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:29:36,640 INFO L432 AbstractCegarLoop]: Abstraction has 113 states and 128 transitions. [2018-01-23 14:29:36,640 INFO L433 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-01-23 14:29:36,640 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 128 transitions. [2018-01-23 14:29:36,642 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2018-01-23 14:29:36,642 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:29:36,642 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-23 14:29:36,643 INFO L371 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:29:36,644 INFO L82 PathProgramCache]: Analyzing trace with hash -1000009541, now seen corresponding path program 1 times [2018-01-23 14:29:36,644 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:29:36,644 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:29:36,645 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:36,645 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:36,645 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:36,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:36,663 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:29:36,791 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-23 14:29:36,791 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:29:36,791 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-23 14:29:36,804 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:36,846 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:36,850 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:29:36,883 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-23 14:29:36,886 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-23 14:29:36,886 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:36,888 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:36,890 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:36,890 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:11, output treesize:7 [2018-01-23 14:29:36,900 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-23 14:29:36,909 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:29:36,912 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-23 14:29:36,913 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:36,917 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:36,921 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:36,921 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:26, output treesize:17 [2018-01-23 14:29:36,986 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-23 14:29:36,989 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:29:36,989 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-23 14:29:36,990 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:36,993 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:36,995 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-23 14:29:36,996 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:27, output treesize:7 [2018-01-23 14:29:37,042 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-23 14:29:37,062 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:29:37,062 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 10] total 15 [2018-01-23 14:29:37,062 INFO L409 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-01-23 14:29:37,062 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-01-23 14:29:37,063 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=180, Unknown=0, NotChecked=0, Total=210 [2018-01-23 14:29:37,063 INFO L87 Difference]: Start difference. First operand 113 states and 128 transitions. Second operand 15 states. [2018-01-23 14:29:37,580 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:29:37,580 INFO L93 Difference]: Finished difference Result 205 states and 233 transitions. [2018-01-23 14:29:37,581 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-01-23 14:29:37,581 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 52 [2018-01-23 14:29:37,581 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:29:37,582 INFO L225 Difference]: With dead ends: 205 [2018-01-23 14:29:37,583 INFO L226 Difference]: Without dead ends: 165 [2018-01-23 14:29:37,583 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-23 14:29:37,584 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 165 states. [2018-01-23 14:29:37,596 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 165 to 150. [2018-01-23 14:29:37,597 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 150 states. [2018-01-23 14:29:37,598 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 150 states to 150 states and 174 transitions. [2018-01-23 14:29:37,598 INFO L78 Accepts]: Start accepts. Automaton has 150 states and 174 transitions. Word has length 52 [2018-01-23 14:29:37,599 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:29:37,599 INFO L432 AbstractCegarLoop]: Abstraction has 150 states and 174 transitions. [2018-01-23 14:29:37,599 INFO L433 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-01-23 14:29:37,599 INFO L276 IsEmpty]: Start isEmpty. Operand 150 states and 174 transitions. [2018-01-23 14:29:37,601 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2018-01-23 14:29:37,602 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:29:37,602 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-23 14:29:37,602 INFO L371 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:29:37,602 INFO L82 PathProgramCache]: Analyzing trace with hash -2108446361, now seen corresponding path program 1 times [2018-01-23 14:29:37,602 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:29:37,603 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:29:37,604 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:37,604 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:37,604 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:37,635 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:37,637 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:29:37,825 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-23 14:29:37,825 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:29:37,825 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-23 14:29:37,830 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:37,869 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:37,874 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:29:37,888 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-23 14:29:37,893 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-23 14:29:37,894 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:37,895 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:37,896 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:37,896 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:13, output treesize:9 [2018-01-23 14:29:37,958 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-23 14:29:37,960 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:29:37,961 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-23 14:29:37,961 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:37,985 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:37,994 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:37,994 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:30, output treesize:26 [2018-01-23 14:29:38,018 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-23 14:29:38,021 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:29:38,023 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-23 14:29:38,023 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:38,027 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:38,035 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-23 14:29:38,035 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:39, output treesize:11 [2018-01-23 14:29:38,131 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-23 14:29:38,147 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-23 14:29:38,148 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:38,164 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:38,167 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-23 14:29:38,168 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:18, output treesize:7 [2018-01-23 14:29:38,228 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-23 14:29:38,248 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:29:38,248 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13] total 22 [2018-01-23 14:29:38,249 INFO L409 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-01-23 14:29:38,249 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-01-23 14:29:38,249 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=415, Unknown=0, NotChecked=0, Total=462 [2018-01-23 14:29:38,249 INFO L87 Difference]: Start difference. First operand 150 states and 174 transitions. Second operand 22 states. [2018-01-23 14:29:39,015 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:29:39,015 INFO L93 Difference]: Finished difference Result 221 states and 250 transitions. [2018-01-23 14:29:39,046 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-01-23 14:29:39,046 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 62 [2018-01-23 14:29:39,046 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:29:39,047 INFO L225 Difference]: With dead ends: 221 [2018-01-23 14:29:39,047 INFO L226 Difference]: Without dead ends: 181 [2018-01-23 14:29:39,048 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-23 14:29:39,048 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 181 states. [2018-01-23 14:29:39,060 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 181 to 160. [2018-01-23 14:29:39,060 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 160 states. [2018-01-23 14:29:39,061 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 160 states to 160 states and 185 transitions. [2018-01-23 14:29:39,062 INFO L78 Accepts]: Start accepts. Automaton has 160 states and 185 transitions. Word has length 62 [2018-01-23 14:29:39,062 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:29:39,062 INFO L432 AbstractCegarLoop]: Abstraction has 160 states and 185 transitions. [2018-01-23 14:29:39,062 INFO L433 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-01-23 14:29:39,062 INFO L276 IsEmpty]: Start isEmpty. Operand 160 states and 185 transitions. [2018-01-23 14:29:39,063 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2018-01-23 14:29:39,063 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:29:39,064 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-23 14:29:39,064 INFO L371 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:29:39,064 INFO L82 PathProgramCache]: Analyzing trace with hash 341153769, now seen corresponding path program 2 times [2018-01-23 14:29:39,064 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:29:39,064 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:29:39,065 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:39,065 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:39,065 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:39,073 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:39,074 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:29:39,218 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-23 14:29:39,219 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:29:39,219 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-23 14:29:39,219 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-23 14:29:39,219 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-23 14:29:39,219 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-01-23 14:29:39,220 INFO L87 Difference]: Start difference. First operand 160 states and 185 transitions. Second operand 7 states. [2018-01-23 14:29:39,497 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:29:39,497 INFO L93 Difference]: Finished difference Result 267 states and 307 transitions. [2018-01-23 14:29:39,498 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-23 14:29:39,498 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 62 [2018-01-23 14:29:39,498 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:29:39,500 INFO L225 Difference]: With dead ends: 267 [2018-01-23 14:29:39,500 INFO L226 Difference]: Without dead ends: 212 [2018-01-23 14:29:39,501 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-23 14:29:39,501 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 212 states. [2018-01-23 14:29:39,511 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 212 to 160. [2018-01-23 14:29:39,511 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 160 states. [2018-01-23 14:29:39,512 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 160 states to 160 states and 184 transitions. [2018-01-23 14:29:39,512 INFO L78 Accepts]: Start accepts. Automaton has 160 states and 184 transitions. Word has length 62 [2018-01-23 14:29:39,512 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:29:39,512 INFO L432 AbstractCegarLoop]: Abstraction has 160 states and 184 transitions. [2018-01-23 14:29:39,512 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-23 14:29:39,513 INFO L276 IsEmpty]: Start isEmpty. Operand 160 states and 184 transitions. [2018-01-23 14:29:39,513 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2018-01-23 14:29:39,514 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:29:39,514 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-23 14:29:39,514 INFO L371 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:29:39,514 INFO L82 PathProgramCache]: Analyzing trace with hash 42752787, now seen corresponding path program 2 times [2018-01-23 14:29:39,514 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:29:39,514 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:29:39,515 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:39,515 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-23 14:29:39,515 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:39,542 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-23 14:29:39,575 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-23 14:29:39,591 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-23 14:29:39,607 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-23 14:29:39,625 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-23 14:29:39,626 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-23 14:29:39,652 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-23 14:29:39,653 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-23 14:29:39,653 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-23 14:29:39,653 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-23 14:29:39,653 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-23 14:29:39,653 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-23 14:29:39,653 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-23 14:29:39,653 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == mainErr0EnsuresViolation======== [2018-01-23 14:29:39,654 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-23 14:29:39,656 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states. [2018-01-23 14:29:39,656 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-01-23 14:29:39,657 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:29:39,657 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-23 14:29:39,657 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr0EnsuresViolation]=== [2018-01-23 14:29:39,657 INFO L82 PathProgramCache]: Analyzing trace with hash -495869350, now seen corresponding path program 1 times [2018-01-23 14:29:39,657 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:29:39,657 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:29:39,658 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:39,658 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:39,658 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:39,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:39,663 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:29:39,669 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-23 14:29:39,669 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:29:39,669 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-23 14:29:39,669 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-23 14:29:39,670 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-23 14:29:39,670 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-23 14:29:39,670 INFO L87 Difference]: Start difference. First operand 101 states. Second operand 2 states. [2018-01-23 14:29:39,673 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:29:39,673 INFO L93 Difference]: Finished difference Result 192 states and 226 transitions. [2018-01-23 14:29:39,673 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-23 14:29:39,673 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 24 [2018-01-23 14:29:39,673 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:29:39,673 INFO L225 Difference]: With dead ends: 192 [2018-01-23 14:29:39,674 INFO L226 Difference]: Without dead ends: 96 [2018-01-23 14:29:39,674 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-23 14:29:39,674 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2018-01-23 14:29:39,677 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 96. [2018-01-23 14:29:39,678 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 96 states. [2018-01-23 14:29:39,678 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 109 transitions. [2018-01-23 14:29:39,678 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 109 transitions. Word has length 24 [2018-01-23 14:29:39,678 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:29:39,678 INFO L432 AbstractCegarLoop]: Abstraction has 96 states and 109 transitions. [2018-01-23 14:29:39,678 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-23 14:29:39,679 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 109 transitions. [2018-01-23 14:29:39,679 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2018-01-23 14:29:39,679 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:29:39,679 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-23 14:29:39,679 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr0EnsuresViolation]=== [2018-01-23 14:29:39,679 INFO L82 PathProgramCache]: Analyzing trace with hash 1635111390, now seen corresponding path program 1 times [2018-01-23 14:29:39,679 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:29:39,679 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:29:39,680 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:39,680 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:39,680 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:39,686 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:39,686 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:29:39,705 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-23 14:29:39,705 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:29:39,705 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-23 14:29:39,705 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-23 14:29:39,705 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-23 14:29:39,706 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-23 14:29:39,706 INFO L87 Difference]: Start difference. First operand 96 states and 109 transitions. Second operand 4 states. [2018-01-23 14:29:39,805 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:29:39,805 INFO L93 Difference]: Finished difference Result 105 states and 118 transitions. [2018-01-23 14:29:39,806 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-23 14:29:39,806 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 28 [2018-01-23 14:29:39,806 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:29:39,807 INFO L225 Difference]: With dead ends: 105 [2018-01-23 14:29:39,807 INFO L226 Difference]: Without dead ends: 100 [2018-01-23 14:29:39,807 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-23 14:29:39,807 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2018-01-23 14:29:39,809 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 98. [2018-01-23 14:29:39,810 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 98 states. [2018-01-23 14:29:39,810 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 111 transitions. [2018-01-23 14:29:39,810 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 111 transitions. Word has length 28 [2018-01-23 14:29:39,811 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:29:39,811 INFO L432 AbstractCegarLoop]: Abstraction has 98 states and 111 transitions. [2018-01-23 14:29:39,811 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-23 14:29:39,811 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 111 transitions. [2018-01-23 14:29:39,811 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2018-01-23 14:29:39,812 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:29:39,812 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-23 14:29:39,812 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr0EnsuresViolation]=== [2018-01-23 14:29:39,812 INFO L82 PathProgramCache]: Analyzing trace with hash -965672213, now seen corresponding path program 1 times [2018-01-23 14:29:39,812 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:29:39,812 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:29:39,813 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:39,813 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:39,813 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:39,818 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:39,819 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:29:39,899 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-23 14:29:39,899 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:29:39,899 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-01-23 14:29:39,899 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-23 14:29:39,900 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-23 14:29:39,900 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-23 14:29:39,900 INFO L87 Difference]: Start difference. First operand 98 states and 111 transitions. Second operand 6 states. [2018-01-23 14:29:40,038 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:29:40,039 INFO L93 Difference]: Finished difference Result 150 states and 167 transitions. [2018-01-23 14:29:40,039 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-01-23 14:29:40,039 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 40 [2018-01-23 14:29:40,039 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:29:40,040 INFO L225 Difference]: With dead ends: 150 [2018-01-23 14:29:40,040 INFO L226 Difference]: Without dead ends: 112 [2018-01-23 14:29:40,040 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-23 14:29:40,040 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 112 states. [2018-01-23 14:29:40,042 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 112 to 100. [2018-01-23 14:29:40,043 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 100 states. [2018-01-23 14:29:40,043 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 113 transitions. [2018-01-23 14:29:40,043 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 113 transitions. Word has length 40 [2018-01-23 14:29:40,043 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:29:40,044 INFO L432 AbstractCegarLoop]: Abstraction has 100 states and 113 transitions. [2018-01-23 14:29:40,044 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-23 14:29:40,044 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 113 transitions. [2018-01-23 14:29:40,044 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-01-23 14:29:40,044 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:29:40,044 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-23 14:29:40,044 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr0EnsuresViolation]=== [2018-01-23 14:29:40,044 INFO L82 PathProgramCache]: Analyzing trace with hash 274611607, now seen corresponding path program 1 times [2018-01-23 14:29:40,045 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:29:40,045 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:29:40,045 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:40,045 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:40,045 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:40,050 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:40,051 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:29:40,135 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-23 14:29:40,136 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:29:40,136 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-23 14:29:40,146 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:40,169 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:40,172 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:29:40,222 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-23 14:29:40,256 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-23 14:29:40,256 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [8] total 11 [2018-01-23 14:29:40,256 INFO L409 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-01-23 14:29:40,256 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-01-23 14:29:40,256 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=90, Unknown=0, NotChecked=0, Total=110 [2018-01-23 14:29:40,257 INFO L87 Difference]: Start difference. First operand 100 states and 113 transitions. Second operand 11 states. [2018-01-23 14:29:40,465 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:29:40,465 INFO L93 Difference]: Finished difference Result 247 states and 274 transitions. [2018-01-23 14:29:40,465 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-01-23 14:29:40,465 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 50 [2018-01-23 14:29:40,466 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:29:40,466 INFO L225 Difference]: With dead ends: 247 [2018-01-23 14:29:40,466 INFO L226 Difference]: Without dead ends: 209 [2018-01-23 14:29:40,467 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 49 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=139, Invalid=323, Unknown=0, NotChecked=0, Total=462 [2018-01-23 14:29:40,467 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 209 states. [2018-01-23 14:29:40,472 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 209 to 111. [2018-01-23 14:29:40,472 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 111 states. [2018-01-23 14:29:40,473 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 126 transitions. [2018-01-23 14:29:40,473 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 126 transitions. Word has length 50 [2018-01-23 14:29:40,473 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:29:40,473 INFO L432 AbstractCegarLoop]: Abstraction has 111 states and 126 transitions. [2018-01-23 14:29:40,473 INFO L433 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-01-23 14:29:40,473 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 126 transitions. [2018-01-23 14:29:40,474 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-01-23 14:29:40,474 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:29:40,474 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-23 14:29:40,474 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr0EnsuresViolation]=== [2018-01-23 14:29:40,475 INFO L82 PathProgramCache]: Analyzing trace with hash -2097127655, now seen corresponding path program 1 times [2018-01-23 14:29:40,475 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:29:40,475 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:29:40,476 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:40,476 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:40,476 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:40,483 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:40,484 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:29:40,545 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-23 14:29:40,545 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:29:40,545 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-23 14:29:40,553 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:40,575 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:40,578 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:29:40,590 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-23 14:29:40,603 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-23 14:29:40,604 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:40,618 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:40,634 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:40,634 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:11, output treesize:7 [2018-01-23 14:29:40,645 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-23 14:29:40,664 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:29:40,665 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-23 14:29:40,666 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:40,671 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:40,674 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:40,674 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:26, output treesize:17 [2018-01-23 14:29:40,712 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-23 14:29:40,714 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:29:40,715 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-23 14:29:40,715 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:40,718 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:40,720 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-23 14:29:40,720 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:27, output treesize:7 [2018-01-23 14:29:40,773 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-23 14:29:40,805 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:29:40,805 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 10] total 15 [2018-01-23 14:29:40,806 INFO L409 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-01-23 14:29:40,806 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-01-23 14:29:40,806 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=180, Unknown=0, NotChecked=0, Total=210 [2018-01-23 14:29:40,806 INFO L87 Difference]: Start difference. First operand 111 states and 126 transitions. Second operand 15 states. [2018-01-23 14:29:41,205 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:29:41,206 INFO L93 Difference]: Finished difference Result 201 states and 229 transitions. [2018-01-23 14:29:41,206 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-01-23 14:29:41,206 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 50 [2018-01-23 14:29:41,206 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:29:41,207 INFO L225 Difference]: With dead ends: 201 [2018-01-23 14:29:41,207 INFO L226 Difference]: Without dead ends: 163 [2018-01-23 14:29:41,208 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-23 14:29:41,208 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 163 states. [2018-01-23 14:29:41,212 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 163 to 148. [2018-01-23 14:29:41,212 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 148 states. [2018-01-23 14:29:41,213 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 172 transitions. [2018-01-23 14:29:41,213 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 172 transitions. Word has length 50 [2018-01-23 14:29:41,213 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:29:41,213 INFO L432 AbstractCegarLoop]: Abstraction has 148 states and 172 transitions. [2018-01-23 14:29:41,213 INFO L433 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-01-23 14:29:41,213 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 172 transitions. [2018-01-23 14:29:41,214 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2018-01-23 14:29:41,214 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:29:41,214 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-23 14:29:41,214 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr0EnsuresViolation]=== [2018-01-23 14:29:41,214 INFO L82 PathProgramCache]: Analyzing trace with hash -489344315, now seen corresponding path program 1 times [2018-01-23 14:29:41,214 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:29:41,214 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:29:41,215 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:41,215 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:41,215 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:41,225 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:41,226 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:29:41,586 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-23 14:29:41,586 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:29:41,586 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-23 14:29:41,596 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:41,620 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:41,624 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:29:41,627 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-23 14:29:41,629 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-23 14:29:41,629 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:41,639 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:41,641 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:41,641 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:13, output treesize:9 [2018-01-23 14:29:41,769 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-23 14:29:41,771 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:29:41,772 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 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-23 14:29:41,772 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:41,776 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:41,780 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:41,780 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:30, output treesize:26 [2018-01-23 14:29:41,834 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-23 14:29:41,841 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:29:41,843 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-23 14:29:41,843 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:41,848 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:41,852 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-23 14:29:41,852 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:39, output treesize:11 [2018-01-23 14:29:41,880 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-23 14:29:41,881 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-23 14:29:41,881 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:41,882 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:41,884 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-23 14:29:41,884 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:18, output treesize:7 [2018-01-23 14:29:41,953 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-23 14:29:41,982 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:29:41,982 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13] total 22 [2018-01-23 14:29:41,982 INFO L409 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-01-23 14:29:41,983 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-01-23 14:29:41,983 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=415, Unknown=0, NotChecked=0, Total=462 [2018-01-23 14:29:41,983 INFO L87 Difference]: Start difference. First operand 148 states and 172 transitions. Second operand 22 states. [2018-01-23 14:29:42,661 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:29:42,661 INFO L93 Difference]: Finished difference Result 217 states and 246 transitions. [2018-01-23 14:29:42,662 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-01-23 14:29:42,662 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 60 [2018-01-23 14:29:42,662 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:29:42,662 INFO L225 Difference]: With dead ends: 217 [2018-01-23 14:29:42,663 INFO L226 Difference]: Without dead ends: 179 [2018-01-23 14:29:42,663 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 52 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 186 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=172, Invalid=1160, Unknown=0, NotChecked=0, Total=1332 [2018-01-23 14:29:42,663 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 179 states. [2018-01-23 14:29:42,670 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 179 to 158. [2018-01-23 14:29:42,670 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 158 states. [2018-01-23 14:29:42,671 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 158 states to 158 states and 183 transitions. [2018-01-23 14:29:42,671 INFO L78 Accepts]: Start accepts. Automaton has 158 states and 183 transitions. Word has length 60 [2018-01-23 14:29:42,672 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:29:42,672 INFO L432 AbstractCegarLoop]: Abstraction has 158 states and 183 transitions. [2018-01-23 14:29:42,672 INFO L433 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-01-23 14:29:42,672 INFO L276 IsEmpty]: Start isEmpty. Operand 158 states and 183 transitions. [2018-01-23 14:29:42,673 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2018-01-23 14:29:42,673 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:29:42,673 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-23 14:29:42,673 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr0EnsuresViolation]=== [2018-01-23 14:29:42,674 INFO L82 PathProgramCache]: Analyzing trace with hash 170187207, now seen corresponding path program 2 times [2018-01-23 14:29:42,674 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:29:42,674 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:29:42,674 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:42,675 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:42,675 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:42,682 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:42,683 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:29:42,832 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-23 14:29:42,833 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:29:42,833 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-23 14:29:42,833 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-23 14:29:42,833 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-23 14:29:42,834 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-01-23 14:29:42,834 INFO L87 Difference]: Start difference. First operand 158 states and 183 transitions. Second operand 7 states. [2018-01-23 14:29:43,015 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:29:43,015 INFO L93 Difference]: Finished difference Result 263 states and 303 transitions. [2018-01-23 14:29:43,015 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-23 14:29:43,015 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 60 [2018-01-23 14:29:43,016 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:29:43,016 INFO L225 Difference]: With dead ends: 263 [2018-01-23 14:29:43,016 INFO L226 Difference]: Without dead ends: 210 [2018-01-23 14:29:43,017 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-23 14:29:43,017 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 210 states. [2018-01-23 14:29:43,022 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 210 to 158. [2018-01-23 14:29:43,022 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 158 states. [2018-01-23 14:29:43,022 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 158 states to 158 states and 182 transitions. [2018-01-23 14:29:43,023 INFO L78 Accepts]: Start accepts. Automaton has 158 states and 182 transitions. Word has length 60 [2018-01-23 14:29:43,023 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:29:43,023 INFO L432 AbstractCegarLoop]: Abstraction has 158 states and 182 transitions. [2018-01-23 14:29:43,023 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-23 14:29:43,023 INFO L276 IsEmpty]: Start isEmpty. Operand 158 states and 182 transitions. [2018-01-23 14:29:43,023 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2018-01-23 14:29:43,023 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:29:43,024 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-23 14:29:43,024 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr0EnsuresViolation]=== [2018-01-23 14:29:43,024 INFO L82 PathProgramCache]: Analyzing trace with hash 312893297, now seen corresponding path program 2 times [2018-01-23 14:29:43,024 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:29:43,024 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:29:43,024 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:43,024 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-23 14:29:43,025 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:43,046 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:43,047 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:29:43,778 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-23 14:29:43,779 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:29:43,779 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-23 14:29:43,784 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-23 14:29:43,796 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-23 14:29:43,809 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-23 14:29:43,815 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-23 14:29:43,819 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:29:43,987 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-23 14:29:43,990 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-23 14:29:43,991 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:43,994 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:44,008 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-23 14:29:44,008 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:57, output treesize:74 [2018-01-23 14:29:44,095 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-23 14:29:44,103 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-23 14:29:44,114 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-23 14:29:44,139 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-23 14:29:44,163 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-23 14:29:44,164 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:74, output treesize:97 [2018-01-23 14:29:44,398 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-23 14:29:44,409 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-23 14:29:44,444 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-23 14:29:44,464 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:29:44,464 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 14] total 28 [2018-01-23 14:29:44,464 INFO L409 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-01-23 14:29:44,465 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-01-23 14:29:44,465 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=648, Unknown=3, NotChecked=102, Total=812 [2018-01-23 14:29:44,465 INFO L87 Difference]: Start difference. First operand 158 states and 182 transitions. Second operand 29 states. [2018-01-23 14:29:45,692 WARN L146 SmtUtils]: Spent 216ms on a formula simplification. DAG size of input: 104 DAG size of output 50 [2018-01-23 14:29:46,633 WARN L146 SmtUtils]: Spent 103ms on a formula simplification. DAG size of input: 70 DAG size of output 63 [2018-01-23 14:29:46,938 WARN L146 SmtUtils]: Spent 115ms on a formula simplification. DAG size of input: 73 DAG size of output 64 [2018-01-23 14:29:47,226 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:29:47,226 INFO L93 Difference]: Finished difference Result 216 states and 247 transitions. [2018-01-23 14:29:47,226 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-01-23 14:29:47,227 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 70 [2018-01-23 14:29:47,227 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:29:47,228 INFO L225 Difference]: With dead ends: 216 [2018-01-23 14:29:47,228 INFO L226 Difference]: Without dead ends: 211 [2018-01-23 14:29:47,229 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-23 14:29:47,229 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 211 states. [2018-01-23 14:29:47,247 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 211 to 200. [2018-01-23 14:29:47,247 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 200 states. [2018-01-23 14:29:47,248 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 200 states to 200 states and 231 transitions. [2018-01-23 14:29:47,249 INFO L78 Accepts]: Start accepts. Automaton has 200 states and 231 transitions. Word has length 70 [2018-01-23 14:29:47,249 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:29:47,249 INFO L432 AbstractCegarLoop]: Abstraction has 200 states and 231 transitions. [2018-01-23 14:29:47,249 INFO L433 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-01-23 14:29:47,249 INFO L276 IsEmpty]: Start isEmpty. Operand 200 states and 231 transitions. [2018-01-23 14:29:47,250 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2018-01-23 14:29:47,250 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:29:47,250 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-23 14:29:47,250 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr0EnsuresViolation]=== [2018-01-23 14:29:47,251 INFO L82 PathProgramCache]: Analyzing trace with hash -29771918, now seen corresponding path program 1 times [2018-01-23 14:29:47,251 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:29:47,251 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:29:47,252 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:47,252 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-23 14:29:47,252 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:29:47,267 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:47,268 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:29:47,451 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-23 14:29:47,451 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:29:47,451 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-23 14:29:47,462 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:29:47,505 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:29:47,509 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:29:47,512 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-23 14:29:47,513 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:47,516 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:47,516 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:10, output treesize:9 [2018-01-23 14:29:47,568 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:29:47,569 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:29:47,570 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-23 14:29:47,570 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:47,581 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:47,582 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:26, output treesize:24 [2018-01-23 14:29:47,626 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-23 14:29:47,628 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-23 14:29:47,629 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:47,630 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:47,638 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-23 14:29:47,638 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:35, output treesize:32 [2018-01-23 14:29:47,691 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-23 14:29:47,693 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-23 14:29:47,693 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:47,698 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:47,706 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-23 14:29:47,706 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:51, output treesize:43 [2018-01-23 14:29:47,760 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-23 14:29:47,763 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-23 14:29:47,763 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:47,767 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:47,774 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-23 14:29:47,774 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:58, output treesize:50 [2018-01-23 14:29:51,819 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:29:51,819 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:29:51,820 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:29:51,821 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-23 14:29:51,821 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:51,827 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-23 14:29:51,828 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:47, output treesize:40 [2018-01-23 14:29:51,882 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-23 14:29:51,884 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-23 14:29:51,884 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:51,890 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-23 14:29:51,890 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-23 14:29:51,892 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:29:51,896 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-23 14:29:51,896 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 3 variables, input treesize:44, output treesize:8 [2018-01-23 14:29:51,974 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-23 14:29:51,994 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:29:51,994 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 17] total 31 [2018-01-23 14:29:51,994 INFO L409 AbstractCegarLoop]: Interpolant automaton has 31 states [2018-01-23 14:29:51,995 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2018-01-23 14:29:51,995 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=112, Invalid=816, Unknown=2, NotChecked=0, Total=930 [2018-01-23 14:29:51,995 INFO L87 Difference]: Start difference. First operand 200 states and 231 transitions. Second operand 31 states. [2018-01-23 14:30:24,827 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:30:24,827 INFO L93 Difference]: Finished difference Result 503 states and 587 transitions. [2018-01-23 14:30:24,853 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-01-23 14:30:24,853 INFO L78 Accepts]: Start accepts. Automaton has 31 states. Word has length 74 [2018-01-23 14:30:24,853 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:30:24,855 INFO L225 Difference]: With dead ends: 503 [2018-01-23 14:30:24,855 INFO L226 Difference]: Without dead ends: 465 [2018-01-23 14:30:24,856 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 61 SyntacticMatches, 0 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 696 ImplicationChecksByTransitivity, 30.4s TimeCoverageRelationStatistics Valid=630, Invalid=2661, Unknown=15, NotChecked=0, Total=3306 [2018-01-23 14:30:24,856 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 465 states. [2018-01-23 14:30:24,866 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 465 to 278. [2018-01-23 14:30:24,867 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 278 states. [2018-01-23 14:30:24,868 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 278 states to 278 states and 330 transitions. [2018-01-23 14:30:24,868 INFO L78 Accepts]: Start accepts. Automaton has 278 states and 330 transitions. Word has length 74 [2018-01-23 14:30:24,868 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:30:24,868 INFO L432 AbstractCegarLoop]: Abstraction has 278 states and 330 transitions. [2018-01-23 14:30:24,868 INFO L433 AbstractCegarLoop]: Interpolant automaton has 31 states. [2018-01-23 14:30:24,868 INFO L276 IsEmpty]: Start isEmpty. Operand 278 states and 330 transitions. [2018-01-23 14:30:24,869 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2018-01-23 14:30:24,869 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:30:24,869 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-23 14:30:24,869 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr0EnsuresViolation]=== [2018-01-23 14:30:24,869 INFO L82 PathProgramCache]: Analyzing trace with hash -556285838, now seen corresponding path program 1 times [2018-01-23 14:30:24,869 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:30:24,869 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:30:24,870 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:30:24,870 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:30:24,870 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:30:24,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:30:24,883 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:30:25,415 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-23 14:30:25,415 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:30:25,415 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-23 14:30:25,420 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:30:25,459 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:30:25,463 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:30:25,466 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-23 14:30:25,467 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:30:25,475 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:30:25,475 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:6, output treesize:5 [2018-01-23 14:30:25,552 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:30:25,553 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:30:25,554 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-23 14:30:25,555 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:30:25,565 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:30:25,566 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:30, output treesize:28 [2018-01-23 14:30:25,592 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-23 14:30:25,595 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:30:25,596 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-23 14:30:25,596 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:30:25,601 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:30:25,610 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-23 14:30:25,610 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:40 [2018-01-23 14:30:25,666 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-23 14:30:25,668 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-23 14:30:25,669 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:30:25,674 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:30:25,684 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-23 14:30:25,684 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:63, output treesize:53 [2018-01-23 14:30:25,761 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 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-23 14:30:25,763 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-23 14:30:25,764 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:30:25,770 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:30:25,778 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-23 14:30:25,779 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:72, output treesize:62 [2018-01-23 14:30:29,834 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:30:29,835 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:30:29,871 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:30:29,871 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-23 14:30:29,872 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:30:29,879 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-23 14:30:29,879 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:57, output treesize:50 [2018-01-23 14:30:29,948 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-23 14:30:29,950 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:30:29,951 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-23 14:30:29,952 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:30:29,956 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-23 14:30:29,956 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-23 14:30:29,957 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:30:29,960 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-23 14:30:29,960 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:57, output treesize:7 [2018-01-23 14:30:30,046 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-23 14:30:30,066 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:30:30,066 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 20] total 31 [2018-01-23 14:30:30,066 INFO L409 AbstractCegarLoop]: Interpolant automaton has 31 states [2018-01-23 14:30:30,066 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2018-01-23 14:30:30,066 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=124, Invalid=804, Unknown=2, NotChecked=0, Total=930 [2018-01-23 14:30:30,067 INFO L87 Difference]: Start difference. First operand 278 states and 330 transitions. Second operand 31 states. Received shutdown request... [2018-01-23 14:30:38,824 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-01-23 14:30:38,825 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-23 14:30:38,826 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 23.01 02:30:38 BoogieIcfgContainer [2018-01-23 14:30:38,827 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-23 14:30:38,828 INFO L168 Benchmark]: Toolchain (without parser) took 64611.06 ms. Allocated memory was 306.7 MB in the beginning and 652.7 MB in the end (delta: 346.0 MB). Free memory was 265.0 MB in the beginning and 303.3 MB in the end (delta: -38.3 MB). Peak memory consumption was 307.8 MB. Max. memory is 5.3 GB. [2018-01-23 14:30:38,829 INFO L168 Benchmark]: CDTParser took 0.16 ms. Allocated memory is still 306.7 MB. Free memory is still 271.0 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-23 14:30:38,829 INFO L168 Benchmark]: CACSL2BoogieTranslator took 236.08 ms. Allocated memory is still 306.7 MB. Free memory was 264.0 MB in the beginning and 253.0 MB in the end (delta: 11.0 MB). Peak memory consumption was 11.0 MB. Max. memory is 5.3 GB. [2018-01-23 14:30:38,830 INFO L168 Benchmark]: Boogie Preprocessor took 53.28 ms. Allocated memory is still 306.7 MB. Free memory was 253.0 MB in the beginning and 251.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-01-23 14:30:38,830 INFO L168 Benchmark]: RCFGBuilder took 468.47 ms. Allocated memory is still 306.7 MB. Free memory was 251.0 MB in the beginning and 220.2 MB in the end (delta: 30.8 MB). Peak memory consumption was 30.8 MB. Max. memory is 5.3 GB. [2018-01-23 14:30:38,830 INFO L168 Benchmark]: TraceAbstraction took 63845.91 ms. Allocated memory was 306.7 MB in the beginning and 652.7 MB in the end (delta: 346.0 MB). Free memory was 220.2 MB in the beginning and 303.3 MB in the end (delta: -83.1 MB). Peak memory consumption was 262.9 MB. Max. memory is 5.3 GB. [2018-01-23 14:30:38,832 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.16 ms. Allocated memory is still 306.7 MB. Free memory is still 271.0 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 236.08 ms. Allocated memory is still 306.7 MB. Free memory was 264.0 MB in the beginning and 253.0 MB in the end (delta: 11.0 MB). Peak memory consumption was 11.0 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 53.28 ms. Allocated memory is still 306.7 MB. Free memory was 253.0 MB in the beginning and 251.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 468.47 ms. Allocated memory is still 306.7 MB. Free memory was 251.0 MB in the beginning and 220.2 MB in the end (delta: 30.8 MB). Peak memory consumption was 30.8 MB. Max. memory is 5.3 GB. * TraceAbstraction took 63845.91 ms. Allocated memory was 306.7 MB in the beginning and 652.7 MB in the end (delta: 346.0 MB). Free memory was 220.2 MB in the beginning and 303.3 MB in the end (delta: -83.1 MB). Peak memory consumption was 262.9 MB. Max. memory is 5.3 GB. * Results from de.uni_freiburg.informatik.ultimate.boogie.preprocessor: - GenericResult: Unfinished Backtranslation Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) - GenericResult: Unfinished Backtranslation Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) - GenericResult: Unfinished Backtranslation Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) - GenericResult: Unfinished Backtranslation Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - CounterExampleResult [Line: 1]: not all allocated memory was freed not all allocated memory was freed We found a FailurePath: - StatisticsResult: Ultimate Automizer benchmark data for error location: ULTIMATE.initErr0EnsuresViolation CFG has 3 procedures, 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.4s OverallTime, 8 OverallIterations, 4 TraceHistogramMax, 2.4s 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.2s 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 20 states, 31 states before enhancement), while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 48 known predicates. - StatisticsResult: Ultimate Automizer benchmark data for error location: mainErr0EnsuresViolation CFG has 3 procedures, 101 locations, 3 error locations. TIMEOUT Result, 59.1s OverallTime, 10 OverallIterations, 4 TraceHistogramMax, 46.1s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 965 SDtfs, 2736 SDslu, 6963 SDs, 0 SdLazy, 5215 SolverSat, 272 SolverUnsat, 15 SolverUnknown, 0 SolverNotchecked, 12.8s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 585 GetRequests, 336 SyntacticMatches, 8 SemanticMatches, 240 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 1596 ImplicationChecksByTransitivity, 41.7s 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.1s SatisfiabilityAnalysisTime, 12.4s 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-23_14-30-38-841.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-23_14-30-38-841.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-23_14-30-38-841.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-23_14-30-38-841.csv Completed graceful shutdown