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/lockfree-3.3_false-valid-memtrack.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-47db877 [2018-01-23 14:24:44,228 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-23 14:24:44,230 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-23 14:24:44,246 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-23 14:24:44,246 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-23 14:24:44,247 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-23 14:24:44,249 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-23 14:24:44,250 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-23 14:24:44,253 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-23 14:24:44,254 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-23 14:24:44,255 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-23 14:24:44,255 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-23 14:24:44,256 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-23 14:24:44,257 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-23 14:24:44,258 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-23 14:24:44,261 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-23 14:24:44,263 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-23 14:24:44,264 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-23 14:24:44,266 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-23 14:24:44,267 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-23 14:24:44,269 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-23 14:24:44,269 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-23 14:24:44,269 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-23 14:24:44,270 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-23 14:24:44,271 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-23 14:24:44,272 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-23 14:24:44,273 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-23 14:24:44,273 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-23 14:24:44,274 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-23 14:24:44,274 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-23 14:24:44,275 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-23 14:24:44,275 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:24:44,285 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-23 14:24:44,286 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-23 14:24:44,287 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-23 14:24:44,287 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-23 14:24:44,287 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-23 14:24:44,287 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-23 14:24:44,287 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-23 14:24:44,288 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-23 14:24:44,288 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-23 14:24:44,289 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-23 14:24:44,289 INFO L133 SettingsManager]: * Check allocation purity=true [2018-01-23 14:24:44,289 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-23 14:24:44,289 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-23 14:24:44,289 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-23 14:24:44,290 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-01-23 14:24:44,290 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-23 14:24:44,290 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-01-23 14:24:44,290 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-23 14:24:44,290 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-01-23 14:24:44,290 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-01-23 14:24:44,291 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-23 14:24:44,291 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-01-23 14:24:44,291 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-23 14:24:44,291 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-23 14:24:44,291 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-23 14:24:44,292 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-23 14:24:44,292 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-23 14:24:44,292 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-23 14:24:44,292 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-23 14:24:44,292 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-23 14:24:44,293 INFO L133 SettingsManager]: * Stop after first violation was found=false [2018-01-23 14:24:44,293 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-01-23 14:24:44,293 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-23 14:24:44,293 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-23 14:24:44,293 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-23 14:24:44,294 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-23 14:24:44,294 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-23 14:24:44,331 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-23 14:24:44,344 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-23 14:24:44,349 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-23 14:24:44,351 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-23 14:24:44,351 INFO L276 PluginConnector]: CDTParser initialized [2018-01-23 14:24:44,352 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/memsafety/lockfree-3.3_false-valid-memtrack.i [2018-01-23 14:24:44,540 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-23 14:24:44,544 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-23 14:24:44,544 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-23 14:24:44,544 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-23 14:24:44,549 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-23 14:24:44,550 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.01 02:24:44" (1/1) ... [2018-01-23 14:24:44,552 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@11237bad and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:24:44, skipping insertion in model container [2018-01-23 14:24:44,553 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.01 02:24:44" (1/1) ... [2018-01-23 14:24:44,566 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-23 14:24:44,607 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-23 14:24:44,727 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-23 14:24:44,748 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-23 14:24:44,757 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:24:44 WrapperNode [2018-01-23 14:24:44,758 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-23 14:24:44,759 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-23 14:24:44,759 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-23 14:24:44,759 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-23 14:24:44,775 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:24:44" (1/1) ... [2018-01-23 14:24:44,775 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:24:44" (1/1) ... [2018-01-23 14:24:44,784 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:24:44" (1/1) ... [2018-01-23 14:24:44,784 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:24:44" (1/1) ... [2018-01-23 14:24:44,790 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:24:44" (1/1) ... [2018-01-23 14:24:44,794 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:24:44" (1/1) ... [2018-01-23 14:24:44,796 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:24:44" (1/1) ... [2018-01-23 14:24:44,798 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-23 14:24:44,799 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-23 14:24:44,799 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-23 14:24:44,799 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-23 14:24:44,801 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:24:44" (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:24:44,851 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-23 14:24:44,851 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-23 14:24:44,851 INFO L136 BoogieDeclarations]: Found implementation of procedure push [2018-01-23 14:24:44,851 INFO L136 BoogieDeclarations]: Found implementation of procedure pop [2018-01-23 14:24:44,851 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-23 14:24:44,852 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-01-23 14:24:44,852 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-01-23 14:24:44,852 INFO L128 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2018-01-23 14:24:44,852 INFO L128 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2018-01-23 14:24:44,852 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-23 14:24:44,852 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-23 14:24:44,852 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-23 14:24:44,852 INFO L128 BoogieDeclarations]: Found specification of procedure malloc [2018-01-23 14:24:44,852 INFO L128 BoogieDeclarations]: Found specification of procedure free [2018-01-23 14:24:44,853 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-23 14:24:44,853 INFO L128 BoogieDeclarations]: Found specification of procedure push [2018-01-23 14:24:44,853 INFO L128 BoogieDeclarations]: Found specification of procedure pop [2018-01-23 14:24:44,853 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-23 14:24:44,853 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-23 14:24:44,853 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-23 14:24:45,152 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-23 14:24:45,153 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.01 02:24:45 BoogieIcfgContainer [2018-01-23 14:24:45,153 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-23 14:24:45,154 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-23 14:24:45,154 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-23 14:24:45,156 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-23 14:24:45,156 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 23.01 02:24:44" (1/3) ... [2018-01-23 14:24:45,157 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@66ff790d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.01 02:24:45, skipping insertion in model container [2018-01-23 14:24:45,157 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:24:44" (2/3) ... [2018-01-23 14:24:45,158 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@66ff790d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.01 02:24:45, skipping insertion in model container [2018-01-23 14:24:45,158 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.01 02:24:45" (3/3) ... [2018-01-23 14:24:45,160 INFO L105 eAbstractionObserver]: Analyzing ICFG lockfree-3.3_false-valid-memtrack.i [2018-01-23 14:24:45,170 INFO L130 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-23 14:24:45,180 INFO L142 ceAbstractionStarter]: Appying trace abstraction to program that has 5 error locations. [2018-01-23 14:24:45,230 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-23 14:24:45,230 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-23 14:24:45,230 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-23 14:24:45,230 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-23 14:24:45,231 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-23 14:24:45,231 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-23 14:24:45,231 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-23 14:24:45,231 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == popErr0EnsuresViolation======== [2018-01-23 14:24:45,232 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-23 14:24:45,255 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states. [2018-01-23 14:24:45,263 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2018-01-23 14:24:45,263 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:45,264 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:24:45,264 INFO L371 AbstractCegarLoop]: === Iteration 1 === [popErr0EnsuresViolation]=== [2018-01-23 14:24:45,269 INFO L82 PathProgramCache]: Analyzing trace with hash 816843792, now seen corresponding path program 1 times [2018-01-23 14:24:45,272 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:45,272 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:45,318 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:45,319 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:45,319 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:45,401 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:45,411 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:45,474 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:24:45,476 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:24:45,477 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2018-01-23 14:24:45,478 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-23 14:24:45,489 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-23 14:24:45,489 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-23 14:24:45,492 INFO L87 Difference]: Start difference. First operand 62 states. Second operand 2 states. [2018-01-23 14:24:45,601 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:45,601 INFO L93 Difference]: Finished difference Result 75 states and 95 transitions. [2018-01-23 14:24:45,601 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-23 14:24:45,603 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 14 [2018-01-23 14:24:45,604 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:45,609 INFO L225 Difference]: With dead ends: 75 [2018-01-23 14:24:45,610 INFO L226 Difference]: Without dead ends: 0 [2018-01-23 14:24:45,613 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 1 GetRequests, 1 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:24:45,626 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2018-01-23 14:24:45,630 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2018-01-23 14:24:45,631 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 0 states. [2018-01-23 14:24:45,632 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2018-01-23 14:24:45,633 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 14 [2018-01-23 14:24:45,633 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:45,633 INFO L432 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2018-01-23 14:24:45,633 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-23 14:24:45,633 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2018-01-23 14:24:45,633 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2018-01-23 14:24:45,639 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2018-01-23 14:24:45,667 INFO L401 ceAbstractionStarter]: For program point L681(line 681) no Hoare annotation was computed. [2018-01-23 14:24:45,667 INFO L401 ceAbstractionStarter]: For program point L680(line 680) no Hoare annotation was computed. [2018-01-23 14:24:45,667 INFO L401 ceAbstractionStarter]: For program point popEXIT(lines 660 687) no Hoare annotation was computed. [2018-01-23 14:24:45,667 INFO L401 ceAbstractionStarter]: For program point L663(lines 663 686) no Hoare annotation was computed. [2018-01-23 14:24:45,668 INFO L404 ceAbstractionStarter]: At program point popENTRY(lines 660 687) the Hoare annotation is: true [2018-01-23 14:24:45,668 INFO L401 ceAbstractionStarter]: For program point L682(line 682) no Hoare annotation was computed. [2018-01-23 14:24:45,668 INFO L401 ceAbstractionStarter]: For program point L667(line 667) no Hoare annotation was computed. [2018-01-23 14:24:45,668 INFO L401 ceAbstractionStarter]: For program point L672'(line 672) no Hoare annotation was computed. [2018-01-23 14:24:45,668 INFO L401 ceAbstractionStarter]: For program point L664(line 664) no Hoare annotation was computed. [2018-01-23 14:24:45,668 INFO L401 ceAbstractionStarter]: For program point L682'(line 682) no Hoare annotation was computed. [2018-01-23 14:24:45,669 INFO L401 ceAbstractionStarter]: For program point L668(lines 668 669) no Hoare annotation was computed. [2018-01-23 14:24:45,669 INFO L401 ceAbstractionStarter]: For program point L674(line 674) no Hoare annotation was computed. [2018-01-23 14:24:45,669 INFO L401 ceAbstractionStarter]: For program point L672(line 672) no Hoare annotation was computed. [2018-01-23 14:24:45,669 INFO L401 ceAbstractionStarter]: For program point L671(line 671) no Hoare annotation was computed. [2018-01-23 14:24:45,669 INFO L401 ceAbstractionStarter]: For program point L675(lines 675 678) no Hoare annotation was computed. [2018-01-23 14:24:45,669 INFO L401 ceAbstractionStarter]: For program point L675''(lines 675 678) no Hoare annotation was computed. [2018-01-23 14:24:45,669 INFO L401 ceAbstractionStarter]: For program point L681'(line 681) no Hoare annotation was computed. [2018-01-23 14:24:45,670 INFO L401 ceAbstractionStarter]: For program point popErr0EnsuresViolation(lines 660 687) no Hoare annotation was computed. [2018-01-23 14:24:45,670 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.initErr0EnsuresViolation(lines 1 707) no Hoare annotation was computed. [2018-01-23 14:24:45,670 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.initEXIT(lines 1 707) no Hoare annotation was computed. [2018-01-23 14:24:45,670 INFO L404 ceAbstractionStarter]: At program point ULTIMATE.initENTRY(lines 1 707) the Hoare annotation is: true [2018-01-23 14:24:45,670 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.initFINAL(lines 1 707) no Hoare annotation was computed. [2018-01-23 14:24:45,670 INFO L404 ceAbstractionStarter]: At program point ULTIMATE.startENTRY(lines 1 707) the Hoare annotation is: true [2018-01-23 14:24:45,670 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.startFINAL(lines 1 707) no Hoare annotation was computed. [2018-01-23 14:24:45,671 INFO L404 ceAbstractionStarter]: At program point L1(lines 1 707) the Hoare annotation is: true [2018-01-23 14:24:45,671 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.startErr0EnsuresViolation(lines 1 707) no Hoare annotation was computed. [2018-01-23 14:24:45,671 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.startEXIT(lines 1 707) no Hoare annotation was computed. [2018-01-23 14:24:45,671 INFO L404 ceAbstractionStarter]: At program point L694'(line 694) the Hoare annotation is: true [2018-01-23 14:24:45,671 INFO L401 ceAbstractionStarter]: For program point L690'(line 690) no Hoare annotation was computed. [2018-01-23 14:24:45,671 INFO L401 ceAbstractionStarter]: For program point L697'(line 697) no Hoare annotation was computed. [2018-01-23 14:24:45,671 INFO L401 ceAbstractionStarter]: For program point L696'''(lines 696 700) no Hoare annotation was computed. [2018-01-23 14:24:45,672 INFO L401 ceAbstractionStarter]: For program point L690'''(line 690) no Hoare annotation was computed. [2018-01-23 14:24:45,672 INFO L401 ceAbstractionStarter]: For program point mainErr0EnsuresViolation(lines 688 707) no Hoare annotation was computed. [2018-01-23 14:24:45,672 INFO L404 ceAbstractionStarter]: At program point L692(line 692) the Hoare annotation is: true [2018-01-23 14:24:45,672 INFO L401 ceAbstractionStarter]: For program point L691(lines 691 694) no Hoare annotation was computed. [2018-01-23 14:24:45,672 INFO L401 ceAbstractionStarter]: For program point L690(lines 690 695) no Hoare annotation was computed. [2018-01-23 14:24:45,672 INFO L401 ceAbstractionStarter]: For program point L696(lines 696 700) no Hoare annotation was computed. [2018-01-23 14:24:45,672 INFO L401 ceAbstractionStarter]: For program point L696''(lines 696 700) no Hoare annotation was computed. [2018-01-23 14:24:45,673 INFO L404 ceAbstractionStarter]: At program point L694(line 694) the Hoare annotation is: true [2018-01-23 14:24:45,673 INFO L401 ceAbstractionStarter]: For program point mainFINAL(lines 688 707) no Hoare annotation was computed. [2018-01-23 14:24:45,673 INFO L401 ceAbstractionStarter]: For program point L698(line 698) no Hoare annotation was computed. [2018-01-23 14:24:45,673 INFO L401 ceAbstractionStarter]: For program point L697(line 697) no Hoare annotation was computed. [2018-01-23 14:24:45,673 INFO L401 ceAbstractionStarter]: For program point mainEXIT(lines 688 707) no Hoare annotation was computed. [2018-01-23 14:24:45,673 INFO L401 ceAbstractionStarter]: For program point L698'(line 698) no Hoare annotation was computed. [2018-01-23 14:24:45,673 INFO L401 ceAbstractionStarter]: For program point L640(line 640) no Hoare annotation was computed. [2018-01-23 14:24:45,674 INFO L401 ceAbstractionStarter]: For program point L644(line 644) no Hoare annotation was computed. [2018-01-23 14:24:45,674 INFO L401 ceAbstractionStarter]: For program point L643(line 643) no Hoare annotation was computed. [2018-01-23 14:24:45,674 INFO L401 ceAbstractionStarter]: For program point L647''(lines 647 650) no Hoare annotation was computed. [2018-01-23 14:24:45,674 INFO L401 ceAbstractionStarter]: For program point L647(lines 647 650) no Hoare annotation was computed. [2018-01-23 14:24:45,674 INFO L401 ceAbstractionStarter]: For program point L646(line 646) no Hoare annotation was computed. [2018-01-23 14:24:45,674 INFO L401 ceAbstractionStarter]: For program point L633'(line 633) no Hoare annotation was computed. [2018-01-23 14:24:45,674 INFO L404 ceAbstractionStarter]: At program point pushENTRY(lines 629 656) the Hoare annotation is: true [2018-01-23 14:24:45,675 INFO L401 ceAbstractionStarter]: For program point L652(line 652) no Hoare annotation was computed. [2018-01-23 14:24:45,675 INFO L401 ceAbstractionStarter]: For program point pushErr0EnsuresViolation(lines 629 656) no Hoare annotation was computed. [2018-01-23 14:24:45,675 INFO L401 ceAbstractionStarter]: For program point L634(line 634) no Hoare annotation was computed. [2018-01-23 14:24:45,675 INFO L401 ceAbstractionStarter]: For program point L633(line 633) no Hoare annotation was computed. [2018-01-23 14:24:45,675 INFO L401 ceAbstractionStarter]: For program point L632(line 632) no Hoare annotation was computed. [2018-01-23 14:24:45,675 INFO L401 ceAbstractionStarter]: For program point L631(lines 631 655) no Hoare annotation was computed. [2018-01-23 14:24:45,675 INFO L401 ceAbstractionStarter]: For program point L638(line 638) no Hoare annotation was computed. [2018-01-23 14:24:45,675 INFO L401 ceAbstractionStarter]: For program point pushEXIT(lines 629 656) no Hoare annotation was computed. [2018-01-23 14:24:45,676 INFO L401 ceAbstractionStarter]: For program point L637(line 637) no Hoare annotation was computed. [2018-01-23 14:24:45,676 INFO L401 ceAbstractionStarter]: For program point L634'(line 634) no Hoare annotation was computed. [2018-01-23 14:24:45,678 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-23 14:24:45,678 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-23 14:24:45,678 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-23 14:24:45,679 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-23 14:24:45,679 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-23 14:24:45,679 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-23 14:24:45,679 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-23 14:24:45,679 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.initErr0EnsuresViolation======== [2018-01-23 14:24:45,679 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-23 14:24:45,681 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states. [2018-01-23 14:24:45,681 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2018-01-23 14:24:45,681 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:45,681 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1] [2018-01-23 14:24:45,682 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.initErr0EnsuresViolation]=== [2018-01-23 14:24:45,682 INFO L82 PathProgramCache]: Analyzing trace with hash 169454, now seen corresponding path program 1 times [2018-01-23 14:24:45,682 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:45,682 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:45,683 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:45,683 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:45,684 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:45,698 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-23 14:24:45,709 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-23 14:24:45,733 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-23 14:24:45,742 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-23 14:24:45,755 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-23 14:24:45,755 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-23 14:24:45,755 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-23 14:24:45,755 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-23 14:24:45,755 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-23 14:24:45,755 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-23 14:24:45,755 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-23 14:24:45,756 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.startErr0EnsuresViolation======== [2018-01-23 14:24:45,756 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-23 14:24:45,758 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states. [2018-01-23 14:24:45,759 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-01-23 14:24:45,759 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:45,759 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:24:45,759 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:24:45,760 INFO L82 PathProgramCache]: Analyzing trace with hash 1316586551, now seen corresponding path program 1 times [2018-01-23 14:24:45,760 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:45,760 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:45,761 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:45,761 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:45,761 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:45,777 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:45,778 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:45,794 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:24:45,794 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:24:45,795 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-23 14:24:45,795 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-23 14:24:45,795 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-23 14:24:45,795 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-23 14:24:45,795 INFO L87 Difference]: Start difference. First operand 62 states. Second operand 2 states. [2018-01-23 14:24:45,802 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:45,802 INFO L93 Difference]: Finished difference Result 75 states and 95 transitions. [2018-01-23 14:24:45,802 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-23 14:24:45,802 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 11 [2018-01-23 14:24:45,802 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:45,809 INFO L225 Difference]: With dead ends: 75 [2018-01-23 14:24:45,809 INFO L226 Difference]: Without dead ends: 57 [2018-01-23 14:24:45,810 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:24:45,810 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2018-01-23 14:24:45,822 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 57. [2018-01-23 14:24:45,822 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 57 states. [2018-01-23 14:24:45,823 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 74 transitions. [2018-01-23 14:24:45,823 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 74 transitions. Word has length 11 [2018-01-23 14:24:45,823 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:45,823 INFO L432 AbstractCegarLoop]: Abstraction has 57 states and 74 transitions. [2018-01-23 14:24:45,824 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-23 14:24:45,824 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 74 transitions. [2018-01-23 14:24:45,824 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-23 14:24:45,824 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:45,824 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:24:45,825 INFO L371 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:24:45,825 INFO L82 PathProgramCache]: Analyzing trace with hash -2092868013, now seen corresponding path program 1 times [2018-01-23 14:24:45,825 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:45,825 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:45,826 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:45,826 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:45,826 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:45,842 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:45,844 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:45,879 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:24:45,879 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:24:45,879 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-23 14:24:45,881 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-23 14:24:45,881 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-23 14:24:45,881 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-23 14:24:45,882 INFO L87 Difference]: Start difference. First operand 57 states and 74 transitions. Second operand 3 states. [2018-01-23 14:24:45,901 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:45,901 INFO L93 Difference]: Finished difference Result 69 states and 87 transitions. [2018-01-23 14:24:45,902 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-23 14:24:45,902 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 15 [2018-01-23 14:24:45,902 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:45,903 INFO L225 Difference]: With dead ends: 69 [2018-01-23 14:24:45,903 INFO L226 Difference]: Without dead ends: 58 [2018-01-23 14:24:45,904 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-23 14:24:45,905 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2018-01-23 14:24:45,911 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 58. [2018-01-23 14:24:45,911 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 58 states. [2018-01-23 14:24:45,913 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 75 transitions. [2018-01-23 14:24:45,913 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 75 transitions. Word has length 15 [2018-01-23 14:24:45,913 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:45,913 INFO L432 AbstractCegarLoop]: Abstraction has 58 states and 75 transitions. [2018-01-23 14:24:45,913 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-23 14:24:45,914 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 75 transitions. [2018-01-23 14:24:45,914 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-23 14:24:45,915 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:45,915 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:24:45,915 INFO L371 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:24:45,915 INFO L82 PathProgramCache]: Analyzing trace with hash 1392752657, now seen corresponding path program 1 times [2018-01-23 14:24:45,915 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:45,916 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:45,917 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:45,917 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:45,917 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:45,941 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-23 14:24:45,962 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-23 14:24:45,973 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-23 14:24:45,983 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-23 14:24:45,990 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-23 14:24:45,991 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-23 14:24:46,002 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-23 14:24:46,002 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-23 14:24:46,003 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-23 14:24:46,003 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-23 14:24:46,003 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-23 14:24:46,003 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-23 14:24:46,003 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-23 14:24:46,003 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == mainErr0EnsuresViolation======== [2018-01-23 14:24:46,003 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-23 14:24:46,005 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states. [2018-01-23 14:24:46,005 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2018-01-23 14:24:46,005 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:46,005 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:24:46,006 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr0EnsuresViolation]=== [2018-01-23 14:24:46,006 INFO L82 PathProgramCache]: Analyzing trace with hash 1784608256, now seen corresponding path program 1 times [2018-01-23 14:24:46,006 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:46,006 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:46,007 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:46,007 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:46,008 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:46,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:46,017 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:46,027 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:24:46,027 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:24:46,027 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-23 14:24:46,028 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-23 14:24:46,028 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-23 14:24:46,028 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-23 14:24:46,028 INFO L87 Difference]: Start difference. First operand 62 states. Second operand 2 states. [2018-01-23 14:24:46,033 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:46,033 INFO L93 Difference]: Finished difference Result 75 states and 95 transitions. [2018-01-23 14:24:46,034 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-23 14:24:46,034 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 9 [2018-01-23 14:24:46,034 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:46,035 INFO L225 Difference]: With dead ends: 75 [2018-01-23 14:24:46,035 INFO L226 Difference]: Without dead ends: 55 [2018-01-23 14:24:46,036 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:24:46,036 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2018-01-23 14:24:46,041 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2018-01-23 14:24:46,041 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-01-23 14:24:46,042 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 72 transitions. [2018-01-23 14:24:46,043 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 72 transitions. Word has length 9 [2018-01-23 14:24:46,043 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:46,043 INFO L432 AbstractCegarLoop]: Abstraction has 55 states and 72 transitions. [2018-01-23 14:24:46,043 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-23 14:24:46,043 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 72 transitions. [2018-01-23 14:24:46,044 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-01-23 14:24:46,044 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:46,044 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:24:46,044 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr0EnsuresViolation]=== [2018-01-23 14:24:46,045 INFO L82 PathProgramCache]: Analyzing trace with hash 1548658460, now seen corresponding path program 1 times [2018-01-23 14:24:46,045 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:46,045 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:46,046 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:46,046 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:46,047 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:46,055 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:46,056 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:46,088 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:24:46,088 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:24:46,088 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-23 14:24:46,089 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-23 14:24:46,089 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-23 14:24:46,089 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-23 14:24:46,089 INFO L87 Difference]: Start difference. First operand 55 states and 72 transitions. Second operand 3 states. [2018-01-23 14:24:46,110 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:46,110 INFO L93 Difference]: Finished difference Result 65 states and 83 transitions. [2018-01-23 14:24:46,110 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-23 14:24:46,111 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 13 [2018-01-23 14:24:46,111 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:46,112 INFO L225 Difference]: With dead ends: 65 [2018-01-23 14:24:46,112 INFO L226 Difference]: Without dead ends: 56 [2018-01-23 14:24:46,113 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-23 14:24:46,113 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2018-01-23 14:24:46,118 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 56. [2018-01-23 14:24:46,118 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 56 states. [2018-01-23 14:24:46,119 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 73 transitions. [2018-01-23 14:24:46,119 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 73 transitions. Word has length 13 [2018-01-23 14:24:46,120 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:46,120 INFO L432 AbstractCegarLoop]: Abstraction has 56 states and 73 transitions. [2018-01-23 14:24:46,120 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-23 14:24:46,120 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 73 transitions. [2018-01-23 14:24:46,121 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-01-23 14:24:46,121 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:46,121 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:24:46,122 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr0EnsuresViolation]=== [2018-01-23 14:24:46,122 INFO L82 PathProgramCache]: Analyzing trace with hash 1605916762, now seen corresponding path program 1 times [2018-01-23 14:24:46,122 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:46,122 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:46,123 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:46,123 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:46,123 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:46,134 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:46,135 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:46,158 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:24:46,158 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:24:46,158 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-23 14:24:46,158 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-23 14:24:46,159 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-23 14:24:46,159 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-23 14:24:46,159 INFO L87 Difference]: Start difference. First operand 56 states and 73 transitions. Second operand 3 states. [2018-01-23 14:24:46,213 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:46,214 INFO L93 Difference]: Finished difference Result 65 states and 82 transitions. [2018-01-23 14:24:46,214 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-23 14:24:46,214 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 13 [2018-01-23 14:24:46,215 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:46,216 INFO L225 Difference]: With dead ends: 65 [2018-01-23 14:24:46,216 INFO L226 Difference]: Without dead ends: 62 [2018-01-23 14:24:46,216 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-23 14:24:46,216 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2018-01-23 14:24:46,222 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 58. [2018-01-23 14:24:46,222 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 58 states. [2018-01-23 14:24:46,223 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 75 transitions. [2018-01-23 14:24:46,223 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 75 transitions. Word has length 13 [2018-01-23 14:24:46,224 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:46,224 INFO L432 AbstractCegarLoop]: Abstraction has 58 states and 75 transitions. [2018-01-23 14:24:46,224 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-23 14:24:46,224 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 75 transitions. [2018-01-23 14:24:46,225 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2018-01-23 14:24:46,225 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:46,225 INFO L322 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:24:46,225 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr0EnsuresViolation]=== [2018-01-23 14:24:46,225 INFO L82 PathProgramCache]: Analyzing trace with hash 1614897922, now seen corresponding path program 1 times [2018-01-23 14:24:46,226 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:46,226 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:46,227 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:46,227 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:46,227 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:46,237 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:46,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:24:46,291 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-23 14:24:46,291 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:24:46,291 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-23 14:24:46,292 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-23 14:24:46,292 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-23 14:24:46,292 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-23 14:24:46,292 INFO L87 Difference]: Start difference. First operand 58 states and 75 transitions. Second operand 4 states. [2018-01-23 14:24:46,339 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:46,340 INFO L93 Difference]: Finished difference Result 114 states and 149 transitions. [2018-01-23 14:24:46,340 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-23 14:24:46,340 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 19 [2018-01-23 14:24:46,341 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:46,342 INFO L225 Difference]: With dead ends: 114 [2018-01-23 14:24:46,343 INFO L226 Difference]: Without dead ends: 100 [2018-01-23 14:24:46,343 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 3 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:24:46,344 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2018-01-23 14:24:46,357 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 95. [2018-01-23 14:24:46,358 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 95 states. [2018-01-23 14:24:46,359 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 129 transitions. [2018-01-23 14:24:46,359 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 129 transitions. Word has length 19 [2018-01-23 14:24:46,360 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:46,360 INFO L432 AbstractCegarLoop]: Abstraction has 95 states and 129 transitions. [2018-01-23 14:24:46,360 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-23 14:24:46,360 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 129 transitions. [2018-01-23 14:24:46,363 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2018-01-23 14:24:46,363 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:46,363 INFO L322 BasicCegarLoop]: trace histogram [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] [2018-01-23 14:24:46,363 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr0EnsuresViolation]=== [2018-01-23 14:24:46,363 INFO L82 PathProgramCache]: Analyzing trace with hash -302614467, now seen corresponding path program 1 times [2018-01-23 14:24:46,364 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:46,364 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:46,365 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:46,365 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:46,365 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:46,378 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:46,379 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:46,556 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-23 14:24:46,556 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:24:46,556 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-23 14:24:46,557 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-23 14:24:46,557 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-23 14:24:46,557 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2018-01-23 14:24:46,557 INFO L87 Difference]: Start difference. First operand 95 states and 129 transitions. Second operand 7 states. [2018-01-23 14:24:46,892 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:46,902 INFO L93 Difference]: Finished difference Result 227 states and 312 transitions. [2018-01-23 14:24:46,902 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-23 14:24:46,902 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 37 [2018-01-23 14:24:46,903 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:46,905 INFO L225 Difference]: With dead ends: 227 [2018-01-23 14:24:46,906 INFO L226 Difference]: Without dead ends: 174 [2018-01-23 14:24:46,907 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=93, Unknown=0, NotChecked=0, Total=132 [2018-01-23 14:24:46,907 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 174 states. [2018-01-23 14:24:46,929 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 174 to 150. [2018-01-23 14:24:46,929 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 150 states. [2018-01-23 14:24:46,932 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 150 states to 150 states and 207 transitions. [2018-01-23 14:24:46,932 INFO L78 Accepts]: Start accepts. Automaton has 150 states and 207 transitions. Word has length 37 [2018-01-23 14:24:46,933 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:46,933 INFO L432 AbstractCegarLoop]: Abstraction has 150 states and 207 transitions. [2018-01-23 14:24:46,941 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-23 14:24:46,941 INFO L276 IsEmpty]: Start isEmpty. Operand 150 states and 207 transitions. [2018-01-23 14:24:46,943 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2018-01-23 14:24:46,943 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:46,944 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 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] [2018-01-23 14:24:46,944 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr0EnsuresViolation]=== [2018-01-23 14:24:46,944 INFO L82 PathProgramCache]: Analyzing trace with hash 1718063660, now seen corresponding path program 1 times [2018-01-23 14:24:46,944 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:46,945 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:46,946 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:46,946 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:46,946 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:46,968 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:46,969 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:47,094 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 2 proven. 18 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-23 14:24:47,094 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:24:47,094 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:24:47,122 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:47,194 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:47,203 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:24:47,471 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 15 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-23 14:24:47,512 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:24:47,513 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 8] total 16 [2018-01-23 14:24:47,513 INFO L409 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-01-23 14:24:47,513 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-01-23 14:24:47,514 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=209, Unknown=0, NotChecked=0, Total=240 [2018-01-23 14:24:47,514 INFO L87 Difference]: Start difference. First operand 150 states and 207 transitions. Second operand 16 states. [2018-01-23 14:24:50,306 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:50,307 INFO L93 Difference]: Finished difference Result 1079 states and 1600 transitions. [2018-01-23 14:24:50,307 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 95 states. [2018-01-23 14:24:50,307 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 47 [2018-01-23 14:24:50,307 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:50,316 INFO L225 Difference]: With dead ends: 1079 [2018-01-23 14:24:50,316 INFO L226 Difference]: Without dead ends: 937 [2018-01-23 14:24:50,323 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 171 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 104 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4378 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=1600, Invalid=9530, Unknown=0, NotChecked=0, Total=11130 [2018-01-23 14:24:50,324 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 937 states. [2018-01-23 14:24:50,387 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 937 to 363. [2018-01-23 14:24:50,388 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 363 states. [2018-01-23 14:24:50,391 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 363 states to 363 states and 515 transitions. [2018-01-23 14:24:50,392 INFO L78 Accepts]: Start accepts. Automaton has 363 states and 515 transitions. Word has length 47 [2018-01-23 14:24:50,392 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:50,392 INFO L432 AbstractCegarLoop]: Abstraction has 363 states and 515 transitions. [2018-01-23 14:24:50,392 INFO L433 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-01-23 14:24:50,392 INFO L276 IsEmpty]: Start isEmpty. Operand 363 states and 515 transitions. [2018-01-23 14:24:50,396 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2018-01-23 14:24:50,396 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:50,397 INFO L322 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 4, 3, 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] [2018-01-23 14:24:50,397 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr0EnsuresViolation]=== [2018-01-23 14:24:50,397 INFO L82 PathProgramCache]: Analyzing trace with hash -1650249222, now seen corresponding path program 1 times [2018-01-23 14:24:50,397 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:50,397 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:50,398 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:50,398 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:50,399 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:50,415 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:50,416 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:50,525 INFO L134 CoverageAnalysis]: Checked inductivity of 83 backedges. 22 proven. 16 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-01-23 14:24:50,525 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:24:50,525 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:24:50,534 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:50,598 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:50,604 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:24:50,673 INFO L134 CoverageAnalysis]: Checked inductivity of 83 backedges. 38 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-01-23 14:24:50,695 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-23 14:24:50,695 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 9 [2018-01-23 14:24:50,695 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-23 14:24:50,696 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-23 14:24:50,696 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-01-23 14:24:50,696 INFO L87 Difference]: Start difference. First operand 363 states and 515 transitions. Second operand 9 states. [2018-01-23 14:24:50,993 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:50,993 INFO L93 Difference]: Finished difference Result 876 states and 1273 transitions. [2018-01-23 14:24:50,993 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-23 14:24:50,993 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 73 [2018-01-23 14:24:50,993 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:50,997 INFO L225 Difference]: With dead ends: 876 [2018-01-23 14:24:50,997 INFO L226 Difference]: Without dead ends: 518 [2018-01-23 14:24:50,999 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 76 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=51, Invalid=131, Unknown=0, NotChecked=0, Total=182 [2018-01-23 14:24:51,000 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 518 states. [2018-01-23 14:24:51,035 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 518 to 478. [2018-01-23 14:24:51,036 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 478 states. [2018-01-23 14:24:51,039 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 478 states to 478 states and 685 transitions. [2018-01-23 14:24:51,039 INFO L78 Accepts]: Start accepts. Automaton has 478 states and 685 transitions. Word has length 73 [2018-01-23 14:24:51,039 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:51,039 INFO L432 AbstractCegarLoop]: Abstraction has 478 states and 685 transitions. [2018-01-23 14:24:51,039 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-23 14:24:51,040 INFO L276 IsEmpty]: Start isEmpty. Operand 478 states and 685 transitions. [2018-01-23 14:24:51,042 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2018-01-23 14:24:51,043 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:51,043 INFO L322 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 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] [2018-01-23 14:24:51,043 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr0EnsuresViolation]=== [2018-01-23 14:24:51,043 INFO L82 PathProgramCache]: Analyzing trace with hash -1980963244, now seen corresponding path program 1 times [2018-01-23 14:24:51,043 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:51,043 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:51,044 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:51,045 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:51,045 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:51,056 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:51,057 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:51,136 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 19 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-01-23 14:24:51,137 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:24:51,137 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-23 14:24:51,137 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-23 14:24:51,137 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-23 14:24:51,137 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2018-01-23 14:24:51,137 INFO L87 Difference]: Start difference. First operand 478 states and 685 transitions. Second operand 7 states. [2018-01-23 14:24:51,422 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:51,423 INFO L93 Difference]: Finished difference Result 1385 states and 2113 transitions. [2018-01-23 14:24:51,423 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-23 14:24:51,423 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 74 [2018-01-23 14:24:51,424 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:51,431 INFO L225 Difference]: With dead ends: 1385 [2018-01-23 14:24:51,431 INFO L226 Difference]: Without dead ends: 912 [2018-01-23 14:24:51,434 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=34, Invalid=76, Unknown=0, NotChecked=0, Total=110 [2018-01-23 14:24:51,435 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 912 states. [2018-01-23 14:24:51,517 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 912 to 752. [2018-01-23 14:24:51,517 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 752 states. [2018-01-23 14:24:51,524 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 752 states to 752 states and 1082 transitions. [2018-01-23 14:24:51,524 INFO L78 Accepts]: Start accepts. Automaton has 752 states and 1082 transitions. Word has length 74 [2018-01-23 14:24:51,524 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:51,524 INFO L432 AbstractCegarLoop]: Abstraction has 752 states and 1082 transitions. [2018-01-23 14:24:51,524 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-23 14:24:51,525 INFO L276 IsEmpty]: Start isEmpty. Operand 752 states and 1082 transitions. [2018-01-23 14:24:51,528 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2018-01-23 14:24:51,528 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:51,528 INFO L322 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 5, 5, 5, 5, 5, 3, 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] [2018-01-23 14:24:51,528 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr0EnsuresViolation]=== [2018-01-23 14:24:51,529 INFO L82 PathProgramCache]: Analyzing trace with hash 787103849, now seen corresponding path program 2 times [2018-01-23 14:24:51,529 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:51,529 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:51,530 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:51,530 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:51,530 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:51,547 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:51,548 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:51,869 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 40 proven. 73 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2018-01-23 14:24:51,869 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:24:51,870 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:24:51,876 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-23 14:24:51,935 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-23 14:24:51,976 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-23 14:24:51,985 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-23 14:24:51,992 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:24:52,141 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 79 proven. 3 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-01-23 14:24:52,165 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:24:52,165 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 17 [2018-01-23 14:24:52,166 INFO L409 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-01-23 14:24:52,166 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-01-23 14:24:52,166 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=239, Unknown=0, NotChecked=0, Total=272 [2018-01-23 14:24:52,166 INFO L87 Difference]: Start difference. First operand 752 states and 1082 transitions. Second operand 17 states. [2018-01-23 14:24:59,113 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:59,113 INFO L93 Difference]: Finished difference Result 5302 states and 8432 transitions. [2018-01-23 14:24:59,114 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 135 states. [2018-01-23 14:24:59,114 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 83 [2018-01-23 14:24:59,115 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:59,148 INFO L225 Difference]: With dead ends: 5302 [2018-01-23 14:24:59,148 INFO L226 Difference]: Without dead ends: 4555 [2018-01-23 14:24:59,162 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 316 GetRequests, 170 SyntacticMatches, 0 SemanticMatches, 146 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8914 ImplicationChecksByTransitivity, 4.6s TimeCoverageRelationStatistics Valid=2873, Invalid=18883, Unknown=0, NotChecked=0, Total=21756 [2018-01-23 14:24:59,166 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4555 states. [2018-01-23 14:24:59,492 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4555 to 3144. [2018-01-23 14:24:59,492 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3144 states. [2018-01-23 14:24:59,509 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3144 states to 3144 states and 4486 transitions. [2018-01-23 14:24:59,509 INFO L78 Accepts]: Start accepts. Automaton has 3144 states and 4486 transitions. Word has length 83 [2018-01-23 14:24:59,510 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:59,510 INFO L432 AbstractCegarLoop]: Abstraction has 3144 states and 4486 transitions. [2018-01-23 14:24:59,510 INFO L433 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-01-23 14:24:59,510 INFO L276 IsEmpty]: Start isEmpty. Operand 3144 states and 4486 transitions. [2018-01-23 14:24:59,518 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2018-01-23 14:24:59,518 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:59,519 INFO L322 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 3, 3, 3, 3, 3, 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] [2018-01-23 14:24:59,519 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr0EnsuresViolation]=== [2018-01-23 14:24:59,519 INFO L82 PathProgramCache]: Analyzing trace with hash 1494721301, now seen corresponding path program 1 times [2018-01-23 14:24:59,519 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:59,519 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:59,520 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:59,520 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-23 14:24:59,520 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:59,532 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:59,534 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:59,650 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 25 proven. 5 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2018-01-23 14:24:59,651 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:24:59,651 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:24:59,658 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:59,740 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:59,746 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:24:59,820 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2018-01-23 14:24:59,852 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-23 14:24:59,852 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 9 [2018-01-23 14:24:59,853 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-23 14:24:59,853 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-23 14:24:59,853 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-01-23 14:24:59,853 INFO L87 Difference]: Start difference. First operand 3144 states and 4486 transitions. Second operand 9 states. [2018-01-23 14:25:00,191 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:25:00,191 INFO L93 Difference]: Finished difference Result 6836 states and 9969 transitions. [2018-01-23 14:25:00,192 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-23 14:25:00,192 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 86 [2018-01-23 14:25:00,192 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:25:00,208 INFO L225 Difference]: With dead ends: 6836 [2018-01-23 14:25:00,208 INFO L226 Difference]: Without dead ends: 3697 [2018-01-23 14:25:00,218 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 89 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=45, Invalid=111, Unknown=0, NotChecked=0, Total=156 [2018-01-23 14:25:00,220 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3697 states. [2018-01-23 14:25:00,401 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3697 to 3144. [2018-01-23 14:25:00,402 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3144 states. [2018-01-23 14:25:00,408 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3144 states to 3144 states and 4486 transitions. [2018-01-23 14:25:00,409 INFO L78 Accepts]: Start accepts. Automaton has 3144 states and 4486 transitions. Word has length 86 [2018-01-23 14:25:00,409 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:25:00,409 INFO L432 AbstractCegarLoop]: Abstraction has 3144 states and 4486 transitions. [2018-01-23 14:25:00,409 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-23 14:25:00,409 INFO L276 IsEmpty]: Start isEmpty. Operand 3144 states and 4486 transitions. [2018-01-23 14:25:00,415 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2018-01-23 14:25:00,415 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:25:00,415 INFO L322 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 5, 5, 5, 5, 5, 4, 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] [2018-01-23 14:25:00,415 INFO L371 AbstractCegarLoop]: === Iteration 11 === [mainErr0EnsuresViolation]=== [2018-01-23 14:25:00,416 INFO L82 PathProgramCache]: Analyzing trace with hash 1024435374, now seen corresponding path program 1 times [2018-01-23 14:25:00,416 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:25:00,416 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:25:00,417 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:25:00,418 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:25:00,418 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:25:00,426 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:25:00,427 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:25:00,563 INFO L134 CoverageAnalysis]: Checked inductivity of 132 backedges. 28 proven. 21 refuted. 0 times theorem prover too weak. 83 trivial. 0 not checked. [2018-01-23 14:25:00,563 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:25:00,563 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:25:00,584 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:25:00,646 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:25:00,651 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:25:00,835 INFO L134 CoverageAnalysis]: Checked inductivity of 132 backedges. 49 proven. 0 refuted. 0 times theorem prover too weak. 83 trivial. 0 not checked. [2018-01-23 14:25:00,864 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-23 14:25:00,864 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 9 [2018-01-23 14:25:00,864 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-23 14:25:00,864 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-23 14:25:00,865 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-01-23 14:25:00,865 INFO L87 Difference]: Start difference. First operand 3144 states and 4486 transitions. Second operand 9 states. [2018-01-23 14:25:01,193 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:25:01,193 INFO L93 Difference]: Finished difference Result 5258 states and 7573 transitions. [2018-01-23 14:25:01,193 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-23 14:25:01,194 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 87 [2018-01-23 14:25:01,194 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:25:01,214 INFO L225 Difference]: With dead ends: 5258 [2018-01-23 14:25:01,214 INFO L226 Difference]: Without dead ends: 3673 [2018-01-23 14:25:01,223 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 90 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=51, Invalid=131, Unknown=0, NotChecked=0, Total=182 [2018-01-23 14:25:01,226 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3673 states. [2018-01-23 14:25:01,554 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3673 to 3550. [2018-01-23 14:25:01,554 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3550 states. [2018-01-23 14:25:01,568 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3550 states to 3550 states and 5100 transitions. [2018-01-23 14:25:01,569 INFO L78 Accepts]: Start accepts. Automaton has 3550 states and 5100 transitions. Word has length 87 [2018-01-23 14:25:01,569 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:25:01,569 INFO L432 AbstractCegarLoop]: Abstraction has 3550 states and 5100 transitions. [2018-01-23 14:25:01,570 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-23 14:25:01,570 INFO L276 IsEmpty]: Start isEmpty. Operand 3550 states and 5100 transitions. [2018-01-23 14:25:01,584 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2018-01-23 14:25:01,584 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:25:01,585 INFO L322 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 3, 3, 3, 3, 3, 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:25:01,585 INFO L371 AbstractCegarLoop]: === Iteration 12 === [mainErr0EnsuresViolation]=== [2018-01-23 14:25:01,585 INFO L82 PathProgramCache]: Analyzing trace with hash 160797049, now seen corresponding path program 1 times [2018-01-23 14:25:01,585 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:25:01,585 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:25:01,586 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:25:01,586 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:25:01,586 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:25:01,607 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:25:01,608 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:25:01,800 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 25 proven. 4 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2018-01-23 14:25:01,800 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:25:01,800 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:25:01,810 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:25:01,864 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:25:01,869 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:25:01,886 WARN L1029 $PredicateComparison]: unable to prove that (exists ((|push_#t~malloc2.base| Int)) (and (<= (select |c_old(#valid)| |push_#t~malloc2.base|) 0) (= |c_#valid| (store |c_old(#valid)| |push_#t~malloc2.base| 1)))) is different from true [2018-01-23 14:25:01,899 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 28 proven. 0 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2018-01-23 14:25:01,921 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-23 14:25:01,921 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [8] total 10 [2018-01-23 14:25:01,922 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-01-23 14:25:01,922 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-01-23 14:25:01,922 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=54, Unknown=1, NotChecked=14, Total=90 [2018-01-23 14:25:01,922 INFO L87 Difference]: Start difference. First operand 3550 states and 5100 transitions. Second operand 10 states. [2018-01-23 14:25:02,556 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:25:02,556 INFO L93 Difference]: Finished difference Result 8706 states and 13158 transitions. [2018-01-23 14:25:02,557 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-01-23 14:25:02,557 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 88 [2018-01-23 14:25:02,557 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:25:02,586 INFO L225 Difference]: With dead ends: 8706 [2018-01-23 14:25:02,586 INFO L226 Difference]: Without dead ends: 4831 [2018-01-23 14:25:02,607 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 104 GetRequests, 91 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=43, Invalid=140, Unknown=3, NotChecked=24, Total=210 [2018-01-23 14:25:02,610 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4831 states. [2018-01-23 14:25:03,093 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4831 to 4394. [2018-01-23 14:25:03,093 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4394 states. [2018-01-23 14:25:03,107 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4394 states to 4394 states and 6385 transitions. [2018-01-23 14:25:03,108 INFO L78 Accepts]: Start accepts. Automaton has 4394 states and 6385 transitions. Word has length 88 [2018-01-23 14:25:03,108 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:25:03,108 INFO L432 AbstractCegarLoop]: Abstraction has 4394 states and 6385 transitions. [2018-01-23 14:25:03,108 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-01-23 14:25:03,108 INFO L276 IsEmpty]: Start isEmpty. Operand 4394 states and 6385 transitions. [2018-01-23 14:25:03,120 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2018-01-23 14:25:03,120 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:25:03,120 INFO L322 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:25:03,120 INFO L371 AbstractCegarLoop]: === Iteration 13 === [mainErr0EnsuresViolation]=== [2018-01-23 14:25:03,120 INFO L82 PathProgramCache]: Analyzing trace with hash -2024113882, now seen corresponding path program 1 times [2018-01-23 14:25:03,121 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:25:03,121 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:25:03,122 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:25:03,122 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:25:03,122 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:25:03,146 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:25:03,147 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:25:03,404 INFO L134 CoverageAnalysis]: Checked inductivity of 97 backedges. 38 proven. 41 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2018-01-23 14:25:03,404 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:25:03,404 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:25:03,418 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:25:03,502 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:25:03,507 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:25:03,642 INFO L134 CoverageAnalysis]: Checked inductivity of 97 backedges. 48 proven. 3 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2018-01-23 14:25:03,673 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:25:03,673 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 6] total 15 [2018-01-23 14:25:03,673 INFO L409 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-01-23 14:25:03,674 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-01-23 14:25:03,674 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=182, Unknown=0, NotChecked=0, Total=210 [2018-01-23 14:25:03,674 INFO L87 Difference]: Start difference. First operand 4394 states and 6385 transitions. Second operand 15 states. [2018-01-23 14:25:06,542 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:25:06,543 INFO L93 Difference]: Finished difference Result 16377 states and 25815 transitions. [2018-01-23 14:25:06,543 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 58 states. [2018-01-23 14:25:06,543 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 90 [2018-01-23 14:25:06,543 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:25:06,606 INFO L225 Difference]: With dead ends: 16377 [2018-01-23 14:25:06,606 INFO L226 Difference]: Without dead ends: 12378 [2018-01-23 14:25:06,631 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 197 GetRequests, 128 SyntacticMatches, 0 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1474 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=937, Invalid=4033, Unknown=0, NotChecked=0, Total=4970 [2018-01-23 14:25:06,639 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 12378 states. [2018-01-23 14:25:07,651 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 12378 to 10054. [2018-01-23 14:25:07,651 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 10054 states. [2018-01-23 14:25:07,673 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10054 states to 10054 states and 14764 transitions. [2018-01-23 14:25:07,674 INFO L78 Accepts]: Start accepts. Automaton has 10054 states and 14764 transitions. Word has length 90 [2018-01-23 14:25:07,674 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:25:07,674 INFO L432 AbstractCegarLoop]: Abstraction has 10054 states and 14764 transitions. [2018-01-23 14:25:07,674 INFO L433 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-01-23 14:25:07,674 INFO L276 IsEmpty]: Start isEmpty. Operand 10054 states and 14764 transitions. [2018-01-23 14:25:07,682 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2018-01-23 14:25:07,682 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:25:07,682 INFO L322 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 5, 5, 5, 5, 5, 4, 4, 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] [2018-01-23 14:25:07,682 INFO L371 AbstractCegarLoop]: === Iteration 14 === [mainErr0EnsuresViolation]=== [2018-01-23 14:25:07,682 INFO L82 PathProgramCache]: Analyzing trace with hash 507171894, now seen corresponding path program 1 times [2018-01-23 14:25:07,683 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:25:07,683 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:25:07,683 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:25:07,683 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:25:07,683 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:25:07,695 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:25:07,696 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:25:07,935 INFO L134 CoverageAnalysis]: Checked inductivity of 138 backedges. 71 proven. 22 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-01-23 14:25:07,936 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:25:07,936 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:25:07,943 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:25:07,998 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:25:08,001 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:25:08,063 INFO L134 CoverageAnalysis]: Checked inductivity of 138 backedges. 79 proven. 12 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2018-01-23 14:25:08,084 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:25:08,084 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 9] total 15 [2018-01-23 14:25:08,085 INFO L409 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-01-23 14:25:08,085 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-01-23 14:25:08,085 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=175, Unknown=0, NotChecked=0, Total=210 [2018-01-23 14:25:08,085 INFO L87 Difference]: Start difference. First operand 10054 states and 14764 transitions. Second operand 15 states. [2018-01-23 14:25:10,580 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:25:10,580 INFO L93 Difference]: Finished difference Result 34700 states and 57428 transitions. [2018-01-23 14:25:10,580 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-01-23 14:25:10,580 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 90 [2018-01-23 14:25:10,581 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:25:10,661 INFO L225 Difference]: With dead ends: 34700 [2018-01-23 14:25:10,661 INFO L226 Difference]: Without dead ends: 23471 [2018-01-23 14:25:10,690 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 101 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 366 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=292, Invalid=1268, Unknown=0, NotChecked=0, Total=1560 [2018-01-23 14:25:10,703 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23471 states. [2018-01-23 14:25:11,796 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23471 to 14718. [2018-01-23 14:25:11,796 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 14718 states. [2018-01-23 14:25:11,826 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14718 states to 14718 states and 21754 transitions. [2018-01-23 14:25:11,827 INFO L78 Accepts]: Start accepts. Automaton has 14718 states and 21754 transitions. Word has length 90 [2018-01-23 14:25:11,827 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:25:11,827 INFO L432 AbstractCegarLoop]: Abstraction has 14718 states and 21754 transitions. [2018-01-23 14:25:11,827 INFO L433 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-01-23 14:25:11,827 INFO L276 IsEmpty]: Start isEmpty. Operand 14718 states and 21754 transitions. [2018-01-23 14:25:11,836 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2018-01-23 14:25:11,837 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:25:11,837 INFO L322 BasicCegarLoop]: trace histogram [7, 7, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2018-01-23 14:25:11,837 INFO L371 AbstractCegarLoop]: === Iteration 15 === [mainErr0EnsuresViolation]=== [2018-01-23 14:25:11,837 INFO L82 PathProgramCache]: Analyzing trace with hash 671709488, now seen corresponding path program 1 times [2018-01-23 14:25:11,837 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:25:11,837 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:25:11,838 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:25:11,838 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:25:11,838 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:25:11,850 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:25:11,851 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:25:12,108 INFO L134 CoverageAnalysis]: Checked inductivity of 146 backedges. 57 proven. 31 refuted. 0 times theorem prover too weak. 58 trivial. 0 not checked. [2018-01-23 14:25:12,108 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:25:12,108 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:25:12,207 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:25:12,269 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:25:12,272 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:25:12,299 INFO L134 CoverageAnalysis]: Checked inductivity of 146 backedges. 64 proven. 3 refuted. 0 times theorem prover too weak. 79 trivial. 0 not checked. [2018-01-23 14:25:12,331 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:25:12,332 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 4] total 10 [2018-01-23 14:25:12,332 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-01-23 14:25:12,332 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-01-23 14:25:12,332 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=73, Unknown=0, NotChecked=0, Total=90 [2018-01-23 14:25:12,332 INFO L87 Difference]: Start difference. First operand 14718 states and 21754 transitions. Second operand 10 states. [2018-01-23 14:25:17,078 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:25:17,078 INFO L93 Difference]: Finished difference Result 89092 states and 133872 transitions. [2018-01-23 14:25:17,102 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-01-23 14:25:17,102 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 107 [2018-01-23 14:25:17,103 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:25:17,349 INFO L225 Difference]: With dead ends: 89092 [2018-01-23 14:25:17,349 INFO L226 Difference]: Without dead ends: 74379 [2018-01-23 14:25:17,416 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 161 GetRequests, 126 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 280 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=272, Invalid=1060, Unknown=0, NotChecked=0, Total=1332 [2018-01-23 14:25:17,457 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74379 states. [2018-01-23 14:25:22,390 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74379 to 71089. [2018-01-23 14:25:22,390 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 71089 states. [2018-01-23 14:25:22,594 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71089 states to 71089 states and 105835 transitions. [2018-01-23 14:25:22,595 INFO L78 Accepts]: Start accepts. Automaton has 71089 states and 105835 transitions. Word has length 107 [2018-01-23 14:25:22,595 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:25:22,595 INFO L432 AbstractCegarLoop]: Abstraction has 71089 states and 105835 transitions. [2018-01-23 14:25:22,596 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-01-23 14:25:22,596 INFO L276 IsEmpty]: Start isEmpty. Operand 71089 states and 105835 transitions. [2018-01-23 14:25:22,609 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2018-01-23 14:25:22,609 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:25:22,609 INFO L322 BasicCegarLoop]: trace histogram [7, 7, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2018-01-23 14:25:22,609 INFO L371 AbstractCegarLoop]: === Iteration 16 === [mainErr0EnsuresViolation]=== [2018-01-23 14:25:22,609 INFO L82 PathProgramCache]: Analyzing trace with hash -1515124594, now seen corresponding path program 1 times [2018-01-23 14:25:22,609 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:25:22,609 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:25:22,610 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:25:22,610 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:25:22,610 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:25:22,630 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:25:22,631 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:25:22,987 INFO L134 CoverageAnalysis]: Checked inductivity of 146 backedges. 2 proven. 117 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2018-01-23 14:25:22,988 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:25:22,988 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:25:22,995 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:25:23,073 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:25:23,077 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:25:23,199 INFO L134 CoverageAnalysis]: Checked inductivity of 146 backedges. 67 proven. 13 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2018-01-23 14:25:23,220 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:25:23,220 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9] total 19 [2018-01-23 14:25:23,220 INFO L409 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-01-23 14:25:23,220 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-01-23 14:25:23,221 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=304, Unknown=0, NotChecked=0, Total=342 [2018-01-23 14:25:23,221 INFO L87 Difference]: Start difference. First operand 71089 states and 105835 transitions. Second operand 19 states. Received shutdown request... [2018-01-23 14:25:25,703 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-01-23 14:25:25,703 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-23 14:25:25,705 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-23 14:25:25,705 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-23 14:25:25,705 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-23 14:25:25,705 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-23 14:25:25,705 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-23 14:25:25,706 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-23 14:25:25,706 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-23 14:25:25,706 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == pushErr0EnsuresViolation======== [2018-01-23 14:25:25,706 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-23 14:25:25,708 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states. [2018-01-23 14:25:25,708 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-23 14:25:25,709 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 23.01 02:25:25 BoogieIcfgContainer [2018-01-23 14:25:25,709 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-23 14:25:25,710 INFO L168 Benchmark]: Toolchain (without parser) took 41169.63 ms. Allocated memory was 308.3 MB in the beginning and 1.9 GB in the end (delta: 1.6 GB). Free memory was 267.0 MB in the beginning and 1.6 GB in the end (delta: -1.4 GB). Peak memory consumption was 229.2 MB. Max. memory is 5.3 GB. [2018-01-23 14:25:25,712 INFO L168 Benchmark]: CDTParser took 0.19 ms. Allocated memory is still 308.3 MB. Free memory is still 273.0 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-23 14:25:25,712 INFO L168 Benchmark]: CACSL2BoogieTranslator took 214.05 ms. Allocated memory is still 308.3 MB. Free memory was 267.0 MB in the beginning and 255.1 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 5.3 GB. [2018-01-23 14:25:25,713 INFO L168 Benchmark]: Boogie Preprocessor took 39.97 ms. Allocated memory is still 308.3 MB. Free memory was 255.1 MB in the beginning and 253.1 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:25:25,713 INFO L168 Benchmark]: RCFGBuilder took 354.21 ms. Allocated memory is still 308.3 MB. Free memory was 253.1 MB in the beginning and 230.1 MB in the end (delta: 23.0 MB). Peak memory consumption was 23.0 MB. Max. memory is 5.3 GB. [2018-01-23 14:25:25,713 INFO L168 Benchmark]: TraceAbstraction took 40555.46 ms. Allocated memory was 308.3 MB in the beginning and 1.9 GB in the end (delta: 1.6 GB). Free memory was 230.1 MB in the beginning and 1.6 GB in the end (delta: -1.4 GB). Peak memory consumption was 192.3 MB. Max. memory is 5.3 GB. [2018-01-23 14:25:25,715 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.19 ms. Allocated memory is still 308.3 MB. Free memory is still 273.0 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 214.05 ms. Allocated memory is still 308.3 MB. Free memory was 267.0 MB in the beginning and 255.1 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 39.97 ms. Allocated memory is still 308.3 MB. Free memory was 255.1 MB in the beginning and 253.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 354.21 ms. Allocated memory is still 308.3 MB. Free memory was 253.1 MB in the beginning and 230.1 MB in the end (delta: 23.0 MB). Peak memory consumption was 23.0 MB. Max. memory is 5.3 GB. * TraceAbstraction took 40555.46 ms. Allocated memory was 308.3 MB in the beginning and 1.9 GB in the end (delta: 1.6 GB). Free memory was 230.1 MB in the beginning and 1.6 GB in the end (delta: -1.4 GB). Peak memory consumption was 192.3 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: - PositiveResult [Line: 660]: all allocated memory was freed For all program executions holds that all allocated memory was freed at this location - StatisticsResult: Ultimate Automizer benchmark data for error location: popErr0EnsuresViolation CFG has 5 procedures, 62 locations, 5 error locations. SAFE Result, 0.4s OverallTime, 1 OverallIterations, 1 TraceHistogramMax, 0.1s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 78 SDtfs, 0 SDslu, 0 SDs, 0 SdLazy, 0 SolverSat, 0 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=62occurred 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: 0.0s AutomataMinimizationTime, 1 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 8 LocationsWithAnnotation, 8 PreInvPairs, 8 NumberOfFragments, 8 HoareAnnotationTreeSize, 8 FomulaSimplifications, 0 FormulaSimplificationTreeSizeReduction, 0.0s HoareSimplificationTime, 8 FomulaSimplificationsInter, 0 FormulaSimplificationTreeSizeReductionInter, 0.0s HoareSimplificationTimeInter, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.0s SatisfiabilityAnalysisTime, 0.0s InterpolantComputationTime, 14 NumberOfCodeBlocks, 14 NumberOfCodeBlocksAsserted, 1 NumberOfCheckSat, 13 ConstructedInterpolants, 0 QuantifiedInterpolants, 169 SizeOfPredicates, 0 NumberOfNonLiveVariables, 0 ConjunctsInSsa, 0 ConjunctsInUnsatCore, 1 InterpolantComputations, 1 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: [L625] int pc1 = 1; [L626] int pc4 = 1; [L624] struct cell *S; [L627] static struct cell *t1 = ((void *)0); [L628] static struct cell *x1 = ((void *)0); [L657] struct cell* garbage; [L658] static struct cell *t4 = ((void *)0); [L659] static struct cell *x4 = ((void *)0); [L662] static int res4; VAL [\old(garbage)=15, \old(garbage)=17, \old(pc1)=7, \old(pc4)=11, \old(res4)=5, \old(S)=9, \old(S)=3, \old(t1)=12, \old(t1)=8, \old(t4)=4, \old(t4)=16, \old(x1)=14, \old(x1)=1, \old(x4)=13, \old(x4)=6, garbage={0:0}, pc1=1, pc4=1, res4=0, S={0:0}, t1={0:0}, t4={0:0}, x1={0:0}, x4={0:0}] - StatisticsResult: Ultimate Automizer benchmark data for error location: ULTIMATE.initErr0EnsuresViolation CFG has 5 procedures, 62 locations, 5 error locations. UNSAFE Result, 0.0s 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=62occurred 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: [L625] int pc1 = 1; [L626] int pc4 = 1; [L624] struct cell *S; [L627] static struct cell *t1 = ((void *)0); [L628] static struct cell *x1 = ((void *)0); [L657] struct cell* garbage; [L658] static struct cell *t4 = ((void *)0); [L659] static struct cell *x4 = ((void *)0); [L662] static int res4; VAL [\old(garbage)=0, \old(garbage)=0, \old(pc1)=1, \old(pc4)=1, \old(res4)=0, \old(S)=0, \old(S)=0, \old(t1)=0, \old(t1)=0, \old(t4)=0, \old(t4)=0, \old(x1)=0, \old(x1)=0, \old(x4)=0, \old(x4)=0, garbage={0:0}, pc1=1, pc4=1, res4=0, S={0:0}, t1={0:0}, t4={0:0}, x1={0:0}, x4={0:0}] [L690] S || 1 != pc1 || __VERIFIER_nondet_int() [L690] S || 1 != pc1 || __VERIFIER_nondet_int() VAL [\old(garbage)=0, \old(garbage)=0, \old(pc1)=1, \old(pc4)=1, \old(res4)=0, \old(S)=0, \old(S)=0, \old(t1)=0, \old(t1)=0, \old(t4)=0, \old(t4)=0, \old(x1)=0, \old(x1)=0, \old(x4)=0, \old(x4)=0, __VERIFIER_nondet_int()=0, garbage={0:0}, pc1=1, pc4=1, res4=0, S={0:0}, S || 1 != pc1 || __VERIFIER_nondet_int()=0, t1={0:0}, t4={0:0}, x1={0:0}, x4={0:0}] [L690] COND FALSE !(S || 1 != pc1 || __VERIFIER_nondet_int()) [L696] COND FALSE !(\read(*garbage)) VAL [\old(garbage)=0, \old(garbage)=0, \old(pc1)=1, \old(pc4)=1, \old(res4)=0, \old(S)=0, \old(S)=0, \old(t1)=0, \old(t1)=0, \old(t4)=0, \old(t4)=0, \old(x1)=0, \old(x1)=0, \old(x4)=0, \old(x4)=0, garbage={0:0}, pc1=1, pc4=1, res4=0, S={0:0}, t1={0:0}, t4={0:0}, x1={0:0}, x4={0:0}] [L701] S = ((void *)0) [L702] t1 = ((void *)0) [L703] x1 = ((void *)0) [L704] t4 = ((void *)0) [L705] x4 = ((void *)0) [L706] return !!garbage; VAL [garbage={0:0}, pc1=1, pc4=1, res4=0, S={0:0}, t1={0:0}, t4={0:0}, x1={0:0}, x4={0:0}] - StatisticsResult: Ultimate Automizer benchmark data for error location: ULTIMATE.startErr0EnsuresViolation CFG has 5 procedures, 62 locations, 5 error locations. UNSAFE Result, 0.2s OverallTime, 3 OverallIterations, 1 TraceHistogramMax, 0.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 151 SDtfs, 0 SDslu, 69 SDs, 0 SdLazy, 5 SolverSat, 0 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 5 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=62occurred 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: 0.0s AutomataMinimizationTime, 2 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.0s SatisfiabilityAnalysisTime, 0.0s InterpolantComputationTime, 41 NumberOfCodeBlocks, 41 NumberOfCodeBlocksAsserted, 3 NumberOfCheckSat, 24 ConstructedInterpolants, 0 QuantifiedInterpolants, 296 SizeOfPredicates, 0 NumberOfNonLiveVariables, 0 ConjunctsInSsa, 0 ConjunctsInUnsatCore, 2 InterpolantComputations, 2 PerfectInterpolantSequences, 0/0 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available - TimeoutResultAtElement [Line: 688]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 688). Cancelled while BasicCegarLoop was constructing difference of abstraction (71089states) and interpolant automaton (currently 30 states, 19 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 35. - StatisticsResult: Ultimate Automizer benchmark data for error location: mainErr0EnsuresViolation CFG has 5 procedures, 62 locations, 5 error locations. TIMEOUT Result, 39.7s OverallTime, 16 OverallIterations, 7 TraceHistogramMax, 25.4s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 1302 SDtfs, 9176 SDslu, 4075 SDs, 0 SdLazy, 8004 SolverSat, 2943 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 6.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1574 GetRequests, 1061 SyntacticMatches, 3 SemanticMatches, 509 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 15927 ImplicationChecksByTransitivity, 11.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=71089occurred in iteration=15, 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: 8.9s AutomataMinimizationTime, 15 MinimizatonAttempts, 17698 StatesRemovedByMinimization, 13 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 3.6s InterpolantComputationTime, 1881 NumberOfCodeBlocks, 1881 NumberOfCodeBlocksAsserted, 27 NumberOfCheckSat, 1855 ConstructedInterpolants, 4 QuantifiedInterpolants, 406877 SizeOfPredicates, 36 NumberOfNonLiveVariables, 5809 ConjunctsInSsa, 84 ConjunctsInUnsatCore, 26 InterpolantComputations, 10 PerfectInterpolantSequences, 1839/2224 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available - TimeoutResultAtElement [Line: 629]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 629). Cancelled while IsEmpty was searching accepting run (input had 62 states). - StatisticsResult: Ultimate Automizer benchmark data for error location: pushErr0EnsuresViolation CFG has 5 procedures, 62 locations, 5 error locations. TIMEOUT Result, 0.0s OverallTime, 0 OverallIterations, 0 TraceHistogramMax, 0.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: No data available, PredicateUnifierStatistics: No data available, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=62occurred 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: 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/lockfree-3.3_false-valid-memtrack.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-23_14-25-25-725.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/lockfree-3.3_false-valid-memtrack.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-23_14-25-25-725.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/lockfree-3.3_false-valid-memtrack.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-1-2018-01-23_14-25-25-725.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/lockfree-3.3_false-valid-memtrack.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-2-2018-01-23_14-25-25-725.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/lockfree-3.3_false-valid-memtrack.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-3-2018-01-23_14-25-25-725.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/lockfree-3.3_false-valid-memtrack.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-4-2018-01-23_14-25-25-725.csv Completed graceful shutdown