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.1_false-valid-memtrack.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-2f49842 [2018-01-20 21:57:52,652 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-20 21:57:52,654 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-20 21:57:52,667 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-20 21:57:52,667 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-20 21:57:52,668 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-20 21:57:52,669 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-20 21:57:52,670 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-20 21:57:52,672 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-20 21:57:52,672 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-20 21:57:52,673 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-20 21:57:52,673 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-20 21:57:52,674 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-20 21:57:52,675 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-20 21:57:52,676 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-20 21:57:52,678 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-20 21:57:52,681 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-20 21:57:52,683 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-20 21:57:52,684 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-20 21:57:52,685 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-20 21:57:52,687 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-20 21:57:52,687 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-20 21:57:52,688 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-20 21:57:52,689 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-20 21:57:52,689 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-20 21:57:52,691 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-20 21:57:52,691 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-20 21:57:52,692 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-20 21:57:52,692 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-20 21:57:52,692 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-20 21:57:52,692 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-20 21:57:52,693 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/ai/eq-bench/mempurity-32bit-Automizer_Camel+AI_EQ.epf [2018-01-20 21:57:52,703 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-20 21:57:52,703 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-20 21:57:52,704 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-20 21:57:52,704 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-20 21:57:52,704 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-20 21:57:52,705 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-20 21:57:52,705 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-20 21:57:52,705 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-20 21:57:52,706 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-20 21:57:52,706 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-20 21:57:52,706 INFO L133 SettingsManager]: * Check allocation purity=true [2018-01-20 21:57:52,706 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-20 21:57:52,706 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-20 21:57:52,707 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-20 21:57:52,707 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-01-20 21:57:52,707 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-20 21:57:52,707 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-01-20 21:57:52,707 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-20 21:57:52,708 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-01-20 21:57:52,708 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-01-20 21:57:52,708 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-20 21:57:52,708 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-01-20 21:57:52,708 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-20 21:57:52,709 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-20 21:57:52,709 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-20 21:57:52,709 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-20 21:57:52,709 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-20 21:57:52,710 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-20 21:57:52,710 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-20 21:57:52,710 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-20 21:57:52,710 INFO L133 SettingsManager]: * Stop after first violation was found=false [2018-01-20 21:57:52,710 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-01-20 21:57:52,711 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-20 21:57:52,711 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-20 21:57:52,711 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-20 21:57:52,712 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-20 21:57:52,712 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-20 21:57:52,747 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-20 21:57:52,759 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-20 21:57:52,764 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-20 21:57:52,765 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-20 21:57:52,766 INFO L276 PluginConnector]: CDTParser initialized [2018-01-20 21:57:52,766 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/memsafety/lockfree-3.1_false-valid-memtrack.i [2018-01-20 21:57:52,957 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-20 21:57:52,962 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-20 21:57:52,963 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-20 21:57:52,963 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-20 21:57:52,968 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-20 21:57:52,969 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.01 09:57:52" (1/1) ... [2018-01-20 21:57:52,971 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6479bd29 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:57:52, skipping insertion in model container [2018-01-20 21:57:52,971 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.01 09:57:52" (1/1) ... [2018-01-20 21:57:52,984 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-20 21:57:53,020 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-20 21:57:53,133 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-20 21:57:53,153 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-20 21:57:53,163 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:57:53 WrapperNode [2018-01-20 21:57:53,163 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-20 21:57:53,164 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-20 21:57:53,164 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-20 21:57:53,164 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-20 21:57:53,179 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:57:53" (1/1) ... [2018-01-20 21:57:53,179 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:57:53" (1/1) ... [2018-01-20 21:57:53,187 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:57:53" (1/1) ... [2018-01-20 21:57:53,187 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:57:53" (1/1) ... [2018-01-20 21:57:53,192 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:57:53" (1/1) ... [2018-01-20 21:57:53,195 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:57:53" (1/1) ... [2018-01-20 21:57:53,197 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:57:53" (1/1) ... [2018-01-20 21:57:53,199 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-20 21:57:53,199 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-20 21:57:53,199 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-20 21:57:53,199 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-20 21:57:53,200 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:57:53" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-20 21:57:53,249 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-20 21:57:53,249 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-20 21:57:53,250 INFO L136 BoogieDeclarations]: Found implementation of procedure push [2018-01-20 21:57:53,250 INFO L136 BoogieDeclarations]: Found implementation of procedure pop [2018-01-20 21:57:53,250 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-20 21:57:53,250 INFO L128 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2018-01-20 21:57:53,250 INFO L128 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2018-01-20 21:57:53,250 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-01-20 21:57:53,251 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-01-20 21:57:53,251 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-20 21:57:53,251 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-20 21:57:53,251 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-20 21:57:53,251 INFO L128 BoogieDeclarations]: Found specification of procedure malloc [2018-01-20 21:57:53,251 INFO L128 BoogieDeclarations]: Found specification of procedure free [2018-01-20 21:57:53,252 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-20 21:57:53,252 INFO L128 BoogieDeclarations]: Found specification of procedure push [2018-01-20 21:57:53,252 INFO L128 BoogieDeclarations]: Found specification of procedure pop [2018-01-20 21:57:53,252 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-20 21:57:53,252 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-20 21:57:53,252 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-20 21:57:53,531 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-20 21:57:53,532 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.01 09:57:53 BoogieIcfgContainer [2018-01-20 21:57:53,532 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-20 21:57:53,533 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-20 21:57:53,533 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-20 21:57:53,535 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-20 21:57:53,536 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.01 09:57:52" (1/3) ... [2018-01-20 21:57:53,537 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@20c4ca76 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.01 09:57:53, skipping insertion in model container [2018-01-20 21:57:53,537 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 09:57:53" (2/3) ... [2018-01-20 21:57:53,537 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@20c4ca76 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.01 09:57:53, skipping insertion in model container [2018-01-20 21:57:53,538 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.01 09:57:53" (3/3) ... [2018-01-20 21:57:53,539 INFO L105 eAbstractionObserver]: Analyzing ICFG lockfree-3.1_false-valid-memtrack.i [2018-01-20 21:57:53,546 INFO L130 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-20 21:57:53,553 INFO L142 ceAbstractionStarter]: Appying trace abstraction to program that has 5 error locations. [2018-01-20 21:57:53,590 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 21:57:53,591 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 21:57:53,591 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 21:57:53,591 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 21:57:53,591 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 21:57:53,591 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 21:57:53,591 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 21:57:53,591 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == popErr0EnsuresViolation======== [2018-01-20 21:57:53,592 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 21:57:53,608 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states. [2018-01-20 21:57:53,614 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2018-01-20 21:57:53,614 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:57:53,615 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:57:53,615 INFO L371 AbstractCegarLoop]: === Iteration 1 === [popErr0EnsuresViolation]=== [2018-01-20 21:57:53,619 INFO L82 PathProgramCache]: Analyzing trace with hash 816843792, now seen corresponding path program 1 times [2018-01-20 21:57:53,621 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:57:53,621 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:57:53,662 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:53,662 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:57:53,662 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:53,737 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:57:53,744 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:57:53,803 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 21:57:53,806 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 21:57:53,807 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2018-01-20 21:57:53,809 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-20 21:57:53,821 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-20 21:57:53,822 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 21:57:53,824 INFO L87 Difference]: Start difference. First operand 62 states. Second operand 2 states. [2018-01-20 21:57:53,928 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:57:53,928 INFO L93 Difference]: Finished difference Result 75 states and 95 transitions. [2018-01-20 21:57:53,929 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-20 21:57:53,930 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 14 [2018-01-20 21:57:53,930 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:57:53,936 INFO L225 Difference]: With dead ends: 75 [2018-01-20 21:57:53,936 INFO L226 Difference]: Without dead ends: 0 [2018-01-20 21:57:53,940 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-20 21:57:53,955 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2018-01-20 21:57:53,961 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2018-01-20 21:57:53,962 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 0 states. [2018-01-20 21:57:53,962 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2018-01-20 21:57:53,963 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 14 [2018-01-20 21:57:53,963 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:57:53,964 INFO L432 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2018-01-20 21:57:53,964 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-20 21:57:53,964 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2018-01-20 21:57:53,964 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2018-01-20 21:57:53,968 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2018-01-20 21:57:53,988 INFO L401 ceAbstractionStarter]: For program point L681(line 681) no Hoare annotation was computed. [2018-01-20 21:57:53,988 INFO L401 ceAbstractionStarter]: For program point L680(line 680) no Hoare annotation was computed. [2018-01-20 21:57:53,988 INFO L401 ceAbstractionStarter]: For program point popEXIT(lines 660 687) no Hoare annotation was computed. [2018-01-20 21:57:53,988 INFO L401 ceAbstractionStarter]: For program point L663(lines 663 686) no Hoare annotation was computed. [2018-01-20 21:57:53,989 INFO L404 ceAbstractionStarter]: At program point popENTRY(lines 660 687) the Hoare annotation is: true [2018-01-20 21:57:53,989 INFO L401 ceAbstractionStarter]: For program point L682(line 682) no Hoare annotation was computed. [2018-01-20 21:57:53,989 INFO L401 ceAbstractionStarter]: For program point L667(line 667) no Hoare annotation was computed. [2018-01-20 21:57:53,989 INFO L401 ceAbstractionStarter]: For program point L672'(line 672) no Hoare annotation was computed. [2018-01-20 21:57:53,990 INFO L401 ceAbstractionStarter]: For program point L664(line 664) no Hoare annotation was computed. [2018-01-20 21:57:53,990 INFO L401 ceAbstractionStarter]: For program point L682'(line 682) no Hoare annotation was computed. [2018-01-20 21:57:53,990 INFO L401 ceAbstractionStarter]: For program point L668(lines 668 669) no Hoare annotation was computed. [2018-01-20 21:57:53,990 INFO L401 ceAbstractionStarter]: For program point L674(line 674) no Hoare annotation was computed. [2018-01-20 21:57:53,990 INFO L401 ceAbstractionStarter]: For program point L672(line 672) no Hoare annotation was computed. [2018-01-20 21:57:53,990 INFO L401 ceAbstractionStarter]: For program point L671(line 671) no Hoare annotation was computed. [2018-01-20 21:57:53,990 INFO L401 ceAbstractionStarter]: For program point L675(lines 675 678) no Hoare annotation was computed. [2018-01-20 21:57:53,991 INFO L401 ceAbstractionStarter]: For program point L675''(lines 675 678) no Hoare annotation was computed. [2018-01-20 21:57:53,991 INFO L401 ceAbstractionStarter]: For program point L681'(line 681) no Hoare annotation was computed. [2018-01-20 21:57:53,991 INFO L401 ceAbstractionStarter]: For program point popErr0EnsuresViolation(lines 660 687) no Hoare annotation was computed. [2018-01-20 21:57:53,991 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.initErr0EnsuresViolation(lines 1 707) no Hoare annotation was computed. [2018-01-20 21:57:53,991 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.initEXIT(lines 1 707) no Hoare annotation was computed. [2018-01-20 21:57:53,991 INFO L404 ceAbstractionStarter]: At program point ULTIMATE.initENTRY(lines 1 707) the Hoare annotation is: true [2018-01-20 21:57:53,992 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.initFINAL(lines 1 707) no Hoare annotation was computed. [2018-01-20 21:57:53,992 INFO L404 ceAbstractionStarter]: At program point ULTIMATE.startENTRY(lines 1 707) the Hoare annotation is: true [2018-01-20 21:57:53,992 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.startFINAL(lines 1 707) no Hoare annotation was computed. [2018-01-20 21:57:53,992 INFO L404 ceAbstractionStarter]: At program point L1(lines 1 707) the Hoare annotation is: true [2018-01-20 21:57:53,992 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.startErr0EnsuresViolation(lines 1 707) no Hoare annotation was computed. [2018-01-20 21:57:53,992 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.startEXIT(lines 1 707) no Hoare annotation was computed. [2018-01-20 21:57:53,992 INFO L404 ceAbstractionStarter]: At program point L694'(line 694) the Hoare annotation is: true [2018-01-20 21:57:53,993 INFO L401 ceAbstractionStarter]: For program point L690'(line 690) no Hoare annotation was computed. [2018-01-20 21:57:53,993 INFO L401 ceAbstractionStarter]: For program point L697'(line 697) no Hoare annotation was computed. [2018-01-20 21:57:53,993 INFO L401 ceAbstractionStarter]: For program point L696'''(lines 696 700) no Hoare annotation was computed. [2018-01-20 21:57:53,993 INFO L401 ceAbstractionStarter]: For program point L690'''(line 690) no Hoare annotation was computed. [2018-01-20 21:57:53,993 INFO L401 ceAbstractionStarter]: For program point mainErr0EnsuresViolation(lines 688 707) no Hoare annotation was computed. [2018-01-20 21:57:53,993 INFO L404 ceAbstractionStarter]: At program point L692(line 692) the Hoare annotation is: true [2018-01-20 21:57:53,994 INFO L401 ceAbstractionStarter]: For program point L691(lines 691 694) no Hoare annotation was computed. [2018-01-20 21:57:53,994 INFO L401 ceAbstractionStarter]: For program point L690(lines 690 695) no Hoare annotation was computed. [2018-01-20 21:57:53,994 INFO L401 ceAbstractionStarter]: For program point L696(lines 696 700) no Hoare annotation was computed. [2018-01-20 21:57:53,994 INFO L401 ceAbstractionStarter]: For program point L696''(lines 696 700) no Hoare annotation was computed. [2018-01-20 21:57:53,994 INFO L404 ceAbstractionStarter]: At program point L694(line 694) the Hoare annotation is: true [2018-01-20 21:57:53,994 INFO L401 ceAbstractionStarter]: For program point mainFINAL(lines 688 707) no Hoare annotation was computed. [2018-01-20 21:57:53,994 INFO L401 ceAbstractionStarter]: For program point L698(line 698) no Hoare annotation was computed. [2018-01-20 21:57:53,995 INFO L401 ceAbstractionStarter]: For program point L697(line 697) no Hoare annotation was computed. [2018-01-20 21:57:53,995 INFO L401 ceAbstractionStarter]: For program point mainEXIT(lines 688 707) no Hoare annotation was computed. [2018-01-20 21:57:53,995 INFO L401 ceAbstractionStarter]: For program point L698'(line 698) no Hoare annotation was computed. [2018-01-20 21:57:53,995 INFO L401 ceAbstractionStarter]: For program point L640(line 640) no Hoare annotation was computed. [2018-01-20 21:57:53,995 INFO L401 ceAbstractionStarter]: For program point L644(line 644) no Hoare annotation was computed. [2018-01-20 21:57:53,995 INFO L401 ceAbstractionStarter]: For program point L643(line 643) no Hoare annotation was computed. [2018-01-20 21:57:53,995 INFO L401 ceAbstractionStarter]: For program point L647''(lines 647 650) no Hoare annotation was computed. [2018-01-20 21:57:53,996 INFO L401 ceAbstractionStarter]: For program point L647(lines 647 650) no Hoare annotation was computed. [2018-01-20 21:57:53,996 INFO L401 ceAbstractionStarter]: For program point L646(line 646) no Hoare annotation was computed. [2018-01-20 21:57:53,996 INFO L401 ceAbstractionStarter]: For program point L633'(line 633) no Hoare annotation was computed. [2018-01-20 21:57:53,996 INFO L404 ceAbstractionStarter]: At program point pushENTRY(lines 629 656) the Hoare annotation is: true [2018-01-20 21:57:53,996 INFO L401 ceAbstractionStarter]: For program point L652(line 652) no Hoare annotation was computed. [2018-01-20 21:57:53,996 INFO L401 ceAbstractionStarter]: For program point pushErr0EnsuresViolation(lines 629 656) no Hoare annotation was computed. [2018-01-20 21:57:53,997 INFO L401 ceAbstractionStarter]: For program point L634(line 634) no Hoare annotation was computed. [2018-01-20 21:57:53,997 INFO L401 ceAbstractionStarter]: For program point L633(line 633) no Hoare annotation was computed. [2018-01-20 21:57:53,997 INFO L401 ceAbstractionStarter]: For program point L632(line 632) no Hoare annotation was computed. [2018-01-20 21:57:53,997 INFO L401 ceAbstractionStarter]: For program point L631(lines 631 655) no Hoare annotation was computed. [2018-01-20 21:57:53,997 INFO L401 ceAbstractionStarter]: For program point L638(line 638) no Hoare annotation was computed. [2018-01-20 21:57:53,997 INFO L401 ceAbstractionStarter]: For program point pushEXIT(lines 629 656) no Hoare annotation was computed. [2018-01-20 21:57:53,997 INFO L401 ceAbstractionStarter]: For program point L637(line 637) no Hoare annotation was computed. [2018-01-20 21:57:53,998 INFO L401 ceAbstractionStarter]: For program point L634'(line 634) no Hoare annotation was computed. [2018-01-20 21:57:54,001 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 21:57:54,002 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 21:57:54,002 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 21:57:54,002 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 21:57:54,002 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 21:57:54,002 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 21:57:54,002 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 21:57:54,002 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.initErr0EnsuresViolation======== [2018-01-20 21:57:54,003 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 21:57:54,005 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states. [2018-01-20 21:57:54,005 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2018-01-20 21:57:54,005 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:57:54,006 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1] [2018-01-20 21:57:54,006 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.initErr0EnsuresViolation]=== [2018-01-20 21:57:54,006 INFO L82 PathProgramCache]: Analyzing trace with hash 169454, now seen corresponding path program 1 times [2018-01-20 21:57:54,006 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:57:54,006 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:57:54,008 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:54,008 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:57:54,008 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:54,021 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 21:57:54,034 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 21:57:54,059 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-20 21:57:54,068 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 21:57:54,078 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 21:57:54,078 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 21:57:54,078 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 21:57:54,078 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 21:57:54,078 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 21:57:54,078 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 21:57:54,078 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 21:57:54,078 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.startErr0EnsuresViolation======== [2018-01-20 21:57:54,078 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 21:57:54,080 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states. [2018-01-20 21:57:54,082 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-01-20 21:57:54,082 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:57:54,082 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:57:54,082 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 21:57:54,082 INFO L82 PathProgramCache]: Analyzing trace with hash 1316586551, now seen corresponding path program 1 times [2018-01-20 21:57:54,083 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:57:54,083 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:57:54,084 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:54,084 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:57:54,084 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:54,098 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:57:54,100 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:57:54,116 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 21:57:54,116 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 21:57:54,116 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-20 21:57:54,117 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-20 21:57:54,117 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-20 21:57:54,117 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 21:57:54,117 INFO L87 Difference]: Start difference. First operand 62 states. Second operand 2 states. [2018-01-20 21:57:54,124 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:57:54,124 INFO L93 Difference]: Finished difference Result 75 states and 95 transitions. [2018-01-20 21:57:54,124 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-20 21:57:54,124 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 11 [2018-01-20 21:57:54,124 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:57:54,132 INFO L225 Difference]: With dead ends: 75 [2018-01-20 21:57:54,132 INFO L226 Difference]: Without dead ends: 57 [2018-01-20 21:57:54,133 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 21:57:54,134 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2018-01-20 21:57:54,149 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 57. [2018-01-20 21:57:54,149 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 57 states. [2018-01-20 21:57:54,151 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 74 transitions. [2018-01-20 21:57:54,151 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 74 transitions. Word has length 11 [2018-01-20 21:57:54,151 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:57:54,151 INFO L432 AbstractCegarLoop]: Abstraction has 57 states and 74 transitions. [2018-01-20 21:57:54,152 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-20 21:57:54,152 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 74 transitions. [2018-01-20 21:57:54,153 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-20 21:57:54,153 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:57:54,153 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:57:54,153 INFO L371 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 21:57:54,153 INFO L82 PathProgramCache]: Analyzing trace with hash -2092868013, now seen corresponding path program 1 times [2018-01-20 21:57:54,153 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:57:54,154 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:57:54,155 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:54,155 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:57:54,155 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:54,169 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:57:54,170 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:57:54,201 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 21:57:54,201 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 21:57:54,201 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-20 21:57:54,203 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-20 21:57:54,203 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-20 21:57:54,203 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-20 21:57:54,204 INFO L87 Difference]: Start difference. First operand 57 states and 74 transitions. Second operand 3 states. [2018-01-20 21:57:54,226 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:57:54,227 INFO L93 Difference]: Finished difference Result 69 states and 87 transitions. [2018-01-20 21:57:54,227 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-20 21:57:54,227 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 15 [2018-01-20 21:57:54,227 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:57:54,228 INFO L225 Difference]: With dead ends: 69 [2018-01-20 21:57:54,228 INFO L226 Difference]: Without dead ends: 58 [2018-01-20 21:57:54,229 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-20 21:57:54,229 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2018-01-20 21:57:54,233 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 58. [2018-01-20 21:57:54,233 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 58 states. [2018-01-20 21:57:54,234 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 75 transitions. [2018-01-20 21:57:54,235 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 75 transitions. Word has length 15 [2018-01-20 21:57:54,235 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:57:54,235 INFO L432 AbstractCegarLoop]: Abstraction has 58 states and 75 transitions. [2018-01-20 21:57:54,235 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-20 21:57:54,235 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 75 transitions. [2018-01-20 21:57:54,236 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-20 21:57:54,236 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:57:54,236 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:57:54,236 INFO L371 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 21:57:54,236 INFO L82 PathProgramCache]: Analyzing trace with hash 1392752657, now seen corresponding path program 1 times [2018-01-20 21:57:54,236 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:57:54,236 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:57:54,237 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:54,237 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:57:54,237 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:54,255 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 21:57:54,272 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 21:57:54,282 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-20 21:57:54,291 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 21:57:54,298 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 21:57:54,299 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 21:57:54,309 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 21:57:54,309 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 21:57:54,309 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 21:57:54,309 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 21:57:54,310 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 21:57:54,310 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 21:57:54,310 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 21:57:54,310 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == mainErr0EnsuresViolation======== [2018-01-20 21:57:54,310 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 21:57:54,311 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states. [2018-01-20 21:57:54,311 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2018-01-20 21:57:54,311 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:57:54,311 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:57:54,312 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr0EnsuresViolation]=== [2018-01-20 21:57:54,312 INFO L82 PathProgramCache]: Analyzing trace with hash 1784608256, now seen corresponding path program 1 times [2018-01-20 21:57:54,312 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:57:54,312 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:57:54,313 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:54,313 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:57:54,313 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:54,321 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:57:54,322 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:57:54,333 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 21:57:54,333 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 21:57:54,333 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-20 21:57:54,333 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-20 21:57:54,334 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-20 21:57:54,334 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 21:57:54,334 INFO L87 Difference]: Start difference. First operand 62 states. Second operand 2 states. [2018-01-20 21:57:54,339 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:57:54,339 INFO L93 Difference]: Finished difference Result 75 states and 95 transitions. [2018-01-20 21:57:54,339 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-20 21:57:54,339 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 9 [2018-01-20 21:57:54,339 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:57:54,340 INFO L225 Difference]: With dead ends: 75 [2018-01-20 21:57:54,340 INFO L226 Difference]: Without dead ends: 55 [2018-01-20 21:57:54,341 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 21:57:54,341 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2018-01-20 21:57:54,346 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2018-01-20 21:57:54,346 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-01-20 21:57:54,347 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 72 transitions. [2018-01-20 21:57:54,347 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 72 transitions. Word has length 9 [2018-01-20 21:57:54,348 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:57:54,348 INFO L432 AbstractCegarLoop]: Abstraction has 55 states and 72 transitions. [2018-01-20 21:57:54,348 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-20 21:57:54,348 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 72 transitions. [2018-01-20 21:57:54,348 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-01-20 21:57:54,349 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:57:54,349 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:57:54,349 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr0EnsuresViolation]=== [2018-01-20 21:57:54,349 INFO L82 PathProgramCache]: Analyzing trace with hash 1548658460, now seen corresponding path program 1 times [2018-01-20 21:57:54,349 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:57:54,349 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:57:54,350 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:54,350 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:57:54,350 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:54,359 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:57:54,360 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:57:54,391 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 21:57:54,391 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 21:57:54,391 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-20 21:57:54,392 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-20 21:57:54,392 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-20 21:57:54,392 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-20 21:57:54,392 INFO L87 Difference]: Start difference. First operand 55 states and 72 transitions. Second operand 3 states. [2018-01-20 21:57:54,407 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:57:54,408 INFO L93 Difference]: Finished difference Result 65 states and 83 transitions. [2018-01-20 21:57:54,408 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-20 21:57:54,408 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 13 [2018-01-20 21:57:54,409 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:57:54,410 INFO L225 Difference]: With dead ends: 65 [2018-01-20 21:57:54,410 INFO L226 Difference]: Without dead ends: 56 [2018-01-20 21:57:54,410 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-20 21:57:54,411 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2018-01-20 21:57:54,415 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 56. [2018-01-20 21:57:54,415 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 56 states. [2018-01-20 21:57:54,416 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 73 transitions. [2018-01-20 21:57:54,416 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 73 transitions. Word has length 13 [2018-01-20 21:57:54,416 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:57:54,417 INFO L432 AbstractCegarLoop]: Abstraction has 56 states and 73 transitions. [2018-01-20 21:57:54,417 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-20 21:57:54,417 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 73 transitions. [2018-01-20 21:57:54,417 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-01-20 21:57:54,418 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:57:54,418 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 21:57:54,418 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr0EnsuresViolation]=== [2018-01-20 21:57:54,418 INFO L82 PathProgramCache]: Analyzing trace with hash 1605916762, now seen corresponding path program 1 times [2018-01-20 21:57:54,418 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:57:54,418 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:57:54,419 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:54,419 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:57:54,419 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:54,429 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:57:54,430 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:57:54,450 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 21:57:54,451 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 21:57:54,451 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-20 21:57:54,451 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-20 21:57:54,451 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-20 21:57:54,451 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-20 21:57:54,452 INFO L87 Difference]: Start difference. First operand 56 states and 73 transitions. Second operand 3 states. [2018-01-20 21:57:54,501 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:57:54,501 INFO L93 Difference]: Finished difference Result 65 states and 82 transitions. [2018-01-20 21:57:54,501 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-20 21:57:54,501 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 13 [2018-01-20 21:57:54,502 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:57:54,503 INFO L225 Difference]: With dead ends: 65 [2018-01-20 21:57:54,503 INFO L226 Difference]: Without dead ends: 62 [2018-01-20 21:57:54,503 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-20 21:57:54,503 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2018-01-20 21:57:54,508 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 58. [2018-01-20 21:57:54,508 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 58 states. [2018-01-20 21:57:54,509 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 75 transitions. [2018-01-20 21:57:54,509 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 75 transitions. Word has length 13 [2018-01-20 21:57:54,510 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:57:54,510 INFO L432 AbstractCegarLoop]: Abstraction has 58 states and 75 transitions. [2018-01-20 21:57:54,510 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-20 21:57:54,510 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 75 transitions. [2018-01-20 21:57:54,511 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2018-01-20 21:57:54,511 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:57:54,511 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-20 21:57:54,511 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr0EnsuresViolation]=== [2018-01-20 21:57:54,511 INFO L82 PathProgramCache]: Analyzing trace with hash 1614897922, now seen corresponding path program 1 times [2018-01-20 21:57:54,512 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:57:54,512 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:57:54,513 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:54,513 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:57:54,513 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:54,525 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:57:54,526 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:57:54,581 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-20 21:57:54,582 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 21:57:54,582 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-20 21:57:54,582 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-20 21:57:54,582 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-20 21:57:54,582 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-20 21:57:54,583 INFO L87 Difference]: Start difference. First operand 58 states and 75 transitions. Second operand 4 states. [2018-01-20 21:57:54,694 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:57:54,695 INFO L93 Difference]: Finished difference Result 114 states and 149 transitions. [2018-01-20 21:57:54,695 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-20 21:57:54,695 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 19 [2018-01-20 21:57:54,696 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:57:54,697 INFO L225 Difference]: With dead ends: 114 [2018-01-20 21:57:54,698 INFO L226 Difference]: Without dead ends: 100 [2018-01-20 21:57:54,698 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-20 21:57:54,698 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2018-01-20 21:57:54,712 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 95. [2018-01-20 21:57:54,712 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 95 states. [2018-01-20 21:57:54,714 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 129 transitions. [2018-01-20 21:57:54,714 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 129 transitions. Word has length 19 [2018-01-20 21:57:54,714 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:57:54,714 INFO L432 AbstractCegarLoop]: Abstraction has 95 states and 129 transitions. [2018-01-20 21:57:54,714 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-20 21:57:54,714 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 129 transitions. [2018-01-20 21:57:54,717 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2018-01-20 21:57:54,717 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:57:54,718 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-20 21:57:54,718 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr0EnsuresViolation]=== [2018-01-20 21:57:54,718 INFO L82 PathProgramCache]: Analyzing trace with hash -302614467, now seen corresponding path program 1 times [2018-01-20 21:57:54,718 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:57:54,718 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:57:54,719 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:54,719 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:57:54,719 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:54,733 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:57:54,734 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:57:54,925 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-20 21:57:54,926 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 21:57:54,926 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-20 21:57:54,926 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-20 21:57:54,926 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-20 21:57:54,926 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2018-01-20 21:57:54,927 INFO L87 Difference]: Start difference. First operand 95 states and 129 transitions. Second operand 7 states. [2018-01-20 21:57:55,321 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:57:55,321 INFO L93 Difference]: Finished difference Result 227 states and 312 transitions. [2018-01-20 21:57:55,322 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-20 21:57:55,322 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 37 [2018-01-20 21:57:55,322 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:57:55,325 INFO L225 Difference]: With dead ends: 227 [2018-01-20 21:57:55,325 INFO L226 Difference]: Without dead ends: 174 [2018-01-20 21:57:55,326 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-20 21:57:55,327 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 174 states. [2018-01-20 21:57:55,353 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 174 to 150. [2018-01-20 21:57:55,353 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 150 states. [2018-01-20 21:57:55,355 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 150 states to 150 states and 207 transitions. [2018-01-20 21:57:55,355 INFO L78 Accepts]: Start accepts. Automaton has 150 states and 207 transitions. Word has length 37 [2018-01-20 21:57:55,356 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:57:55,356 INFO L432 AbstractCegarLoop]: Abstraction has 150 states and 207 transitions. [2018-01-20 21:57:55,356 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-20 21:57:55,356 INFO L276 IsEmpty]: Start isEmpty. Operand 150 states and 207 transitions. [2018-01-20 21:57:55,358 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2018-01-20 21:57:55,358 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:57:55,358 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-20 21:57:55,359 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr0EnsuresViolation]=== [2018-01-20 21:57:55,359 INFO L82 PathProgramCache]: Analyzing trace with hash 1718063660, now seen corresponding path program 1 times [2018-01-20 21:57:55,360 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:57:55,360 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:57:55,361 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:55,361 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:57:55,361 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:55,380 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:57:55,381 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:57:55,530 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-20 21:57:55,530 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 21:57:55,530 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 21:57:55,543 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:57:55,617 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:57:55,625 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 21:57:55,814 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-20 21:57:55,849 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 21:57:55,849 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 15 [2018-01-20 21:57:55,849 INFO L409 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-01-20 21:57:55,850 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-01-20 21:57:55,850 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=181, Unknown=0, NotChecked=0, Total=210 [2018-01-20 21:57:55,850 INFO L87 Difference]: Start difference. First operand 150 states and 207 transitions. Second operand 15 states. [2018-01-20 21:57:58,983 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:57:58,983 INFO L93 Difference]: Finished difference Result 1106 states and 1684 transitions. [2018-01-20 21:57:58,983 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 83 states. [2018-01-20 21:57:58,983 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 47 [2018-01-20 21:57:58,984 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:57:58,992 INFO L225 Difference]: With dead ends: 1106 [2018-01-20 21:57:58,992 INFO L226 Difference]: Without dead ends: 937 [2018-01-20 21:57:58,998 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 158 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 91 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3345 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=1397, Invalid=7159, Unknown=0, NotChecked=0, Total=8556 [2018-01-20 21:57:58,999 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 937 states. [2018-01-20 21:57:59,062 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 937 to 363. [2018-01-20 21:57:59,063 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 363 states. [2018-01-20 21:57:59,066 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 363 states to 363 states and 511 transitions. [2018-01-20 21:57:59,066 INFO L78 Accepts]: Start accepts. Automaton has 363 states and 511 transitions. Word has length 47 [2018-01-20 21:57:59,067 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:57:59,067 INFO L432 AbstractCegarLoop]: Abstraction has 363 states and 511 transitions. [2018-01-20 21:57:59,067 INFO L433 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-01-20 21:57:59,067 INFO L276 IsEmpty]: Start isEmpty. Operand 363 states and 511 transitions. [2018-01-20 21:57:59,070 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2018-01-20 21:57:59,071 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:57:59,071 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-20 21:57:59,071 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr0EnsuresViolation]=== [2018-01-20 21:57:59,071 INFO L82 PathProgramCache]: Analyzing trace with hash -1650249222, now seen corresponding path program 1 times [2018-01-20 21:57:59,071 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:57:59,072 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:57:59,073 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:59,073 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:57:59,073 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:59,089 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:57:59,090 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:57:59,189 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-20 21:57:59,189 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 21:57:59,189 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 21:57:59,200 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:57:59,273 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:57:59,280 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 21:57:59,349 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-20 21:57:59,383 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-20 21:57:59,383 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 9 [2018-01-20 21:57:59,384 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-20 21:57:59,384 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-20 21:57:59,384 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-01-20 21:57:59,384 INFO L87 Difference]: Start difference. First operand 363 states and 511 transitions. Second operand 9 states. [2018-01-20 21:57:59,821 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:57:59,822 INFO L93 Difference]: Finished difference Result 801 states and 1160 transitions. [2018-01-20 21:57:59,822 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-20 21:57:59,822 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 73 [2018-01-20 21:57:59,823 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:57:59,825 INFO L225 Difference]: With dead ends: 801 [2018-01-20 21:57:59,826 INFO L226 Difference]: Without dead ends: 516 [2018-01-20 21:57:59,827 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-20 21:57:59,827 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 516 states. [2018-01-20 21:57:59,855 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 516 to 476. [2018-01-20 21:57:59,855 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 476 states. [2018-01-20 21:57:59,859 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 476 states to 476 states and 678 transitions. [2018-01-20 21:57:59,859 INFO L78 Accepts]: Start accepts. Automaton has 476 states and 678 transitions. Word has length 73 [2018-01-20 21:57:59,860 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:57:59,860 INFO L432 AbstractCegarLoop]: Abstraction has 476 states and 678 transitions. [2018-01-20 21:57:59,860 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-20 21:57:59,860 INFO L276 IsEmpty]: Start isEmpty. Operand 476 states and 678 transitions. [2018-01-20 21:57:59,863 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2018-01-20 21:57:59,863 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:57:59,863 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-20 21:57:59,863 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr0EnsuresViolation]=== [2018-01-20 21:57:59,864 INFO L82 PathProgramCache]: Analyzing trace with hash -1980963244, now seen corresponding path program 1 times [2018-01-20 21:57:59,864 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:57:59,864 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:57:59,865 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:59,865 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:57:59,865 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:57:59,874 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:57:59,876 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:57:59,953 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-20 21:57:59,954 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 21:57:59,954 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-20 21:57:59,954 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-20 21:57:59,954 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-20 21:57:59,954 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2018-01-20 21:57:59,955 INFO L87 Difference]: Start difference. First operand 476 states and 678 transitions. Second operand 7 states. [2018-01-20 21:58:00,176 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:00,176 INFO L93 Difference]: Finished difference Result 1379 states and 2090 transitions. [2018-01-20 21:58:00,176 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-20 21:58:00,176 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 74 [2018-01-20 21:58:00,177 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:00,184 INFO L225 Difference]: With dead ends: 1379 [2018-01-20 21:58:00,184 INFO L226 Difference]: Without dead ends: 908 [2018-01-20 21:58:00,187 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-20 21:58:00,187 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 908 states. [2018-01-20 21:58:00,271 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 908 to 748. [2018-01-20 21:58:00,272 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 748 states. [2018-01-20 21:58:00,278 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 748 states to 748 states and 1068 transitions. [2018-01-20 21:58:00,279 INFO L78 Accepts]: Start accepts. Automaton has 748 states and 1068 transitions. Word has length 74 [2018-01-20 21:58:00,279 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:00,279 INFO L432 AbstractCegarLoop]: Abstraction has 748 states and 1068 transitions. [2018-01-20 21:58:00,279 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-20 21:58:00,279 INFO L276 IsEmpty]: Start isEmpty. Operand 748 states and 1068 transitions. [2018-01-20 21:58:00,283 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2018-01-20 21:58:00,283 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:00,283 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-20 21:58:00,283 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr0EnsuresViolation]=== [2018-01-20 21:58:00,284 INFO L82 PathProgramCache]: Analyzing trace with hash 787103849, now seen corresponding path program 2 times [2018-01-20 21:58:00,284 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:00,284 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:00,285 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:00,285 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:00,285 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:00,302 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:00,303 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:00,569 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-20 21:58:00,569 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 21:58:00,569 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 21:58:00,576 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-20 21:58:00,613 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-20 21:58:00,640 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-20 21:58:00,645 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-20 21:58:00,652 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 21:58:00,778 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-20 21:58:00,799 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 21:58:00,799 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 17 [2018-01-20 21:58:00,799 INFO L409 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-01-20 21:58:00,800 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-01-20 21:58:00,800 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=239, Unknown=0, NotChecked=0, Total=272 [2018-01-20 21:58:00,800 INFO L87 Difference]: Start difference. First operand 748 states and 1068 transitions. Second operand 17 states. [2018-01-20 21:58:06,488 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:06,488 INFO L93 Difference]: Finished difference Result 5106 states and 8026 transitions. [2018-01-20 21:58:06,489 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 135 states. [2018-01-20 21:58:06,489 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 83 [2018-01-20 21:58:06,489 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:06,521 INFO L225 Difference]: With dead ends: 5106 [2018-01-20 21:58:06,522 INFO L226 Difference]: Without dead ends: 4555 [2018-01-20 21:58:06,534 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 316 GetRequests, 170 SyntacticMatches, 0 SemanticMatches, 146 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8914 ImplicationChecksByTransitivity, 3.6s TimeCoverageRelationStatistics Valid=2873, Invalid=18883, Unknown=0, NotChecked=0, Total=21756 [2018-01-20 21:58:06,537 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4555 states. [2018-01-20 21:58:06,847 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4555 to 3144. [2018-01-20 21:58:06,847 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3144 states. [2018-01-20 21:58:06,864 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3144 states to 3144 states and 4486 transitions. [2018-01-20 21:58:06,864 INFO L78 Accepts]: Start accepts. Automaton has 3144 states and 4486 transitions. Word has length 83 [2018-01-20 21:58:06,865 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:06,865 INFO L432 AbstractCegarLoop]: Abstraction has 3144 states and 4486 transitions. [2018-01-20 21:58:06,865 INFO L433 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-01-20 21:58:06,865 INFO L276 IsEmpty]: Start isEmpty. Operand 3144 states and 4486 transitions. [2018-01-20 21:58:06,873 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2018-01-20 21:58:06,873 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:06,873 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-20 21:58:06,873 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr0EnsuresViolation]=== [2018-01-20 21:58:06,873 INFO L82 PathProgramCache]: Analyzing trace with hash 1494721301, now seen corresponding path program 1 times [2018-01-20 21:58:06,873 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:06,874 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:06,874 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:06,875 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-20 21:58:06,875 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:06,886 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:06,887 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:06,972 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-20 21:58:06,973 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 21:58:06,973 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 21:58:06,980 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:07,039 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:07,045 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 21:58:07,104 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-20 21:58:07,138 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-20 21:58:07,138 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 9 [2018-01-20 21:58:07,139 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-20 21:58:07,139 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-20 21:58:07,139 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-01-20 21:58:07,139 INFO L87 Difference]: Start difference. First operand 3144 states and 4486 transitions. Second operand 9 states. [2018-01-20 21:58:07,477 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:07,478 INFO L93 Difference]: Finished difference Result 6836 states and 9969 transitions. [2018-01-20 21:58:07,478 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-20 21:58:07,478 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 86 [2018-01-20 21:58:07,478 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:07,503 INFO L225 Difference]: With dead ends: 6836 [2018-01-20 21:58:07,503 INFO L226 Difference]: Without dead ends: 3697 [2018-01-20 21:58:07,518 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 89 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=45, Invalid=111, Unknown=0, NotChecked=0, Total=156 [2018-01-20 21:58:07,521 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3697 states. [2018-01-20 21:58:07,802 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3697 to 3144. [2018-01-20 21:58:07,802 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3144 states. [2018-01-20 21:58:07,812 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3144 states to 3144 states and 4486 transitions. [2018-01-20 21:58:07,813 INFO L78 Accepts]: Start accepts. Automaton has 3144 states and 4486 transitions. Word has length 86 [2018-01-20 21:58:07,844 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:07,844 INFO L432 AbstractCegarLoop]: Abstraction has 3144 states and 4486 transitions. [2018-01-20 21:58:07,844 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-20 21:58:07,844 INFO L276 IsEmpty]: Start isEmpty. Operand 3144 states and 4486 transitions. [2018-01-20 21:58:07,852 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2018-01-20 21:58:07,852 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:07,852 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-20 21:58:07,853 INFO L371 AbstractCegarLoop]: === Iteration 11 === [mainErr0EnsuresViolation]=== [2018-01-20 21:58:07,853 INFO L82 PathProgramCache]: Analyzing trace with hash 1024435374, now seen corresponding path program 1 times [2018-01-20 21:58:07,853 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:07,853 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:07,854 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:07,854 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:07,854 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:07,865 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:07,866 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:07,946 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-20 21:58:07,946 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 21:58:07,947 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 21:58:07,953 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:08,020 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:08,025 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 21:58:08,221 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-20 21:58:08,242 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-20 21:58:08,242 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 9 [2018-01-20 21:58:08,243 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-20 21:58:08,243 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-20 21:58:08,243 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-01-20 21:58:08,243 INFO L87 Difference]: Start difference. First operand 3144 states and 4486 transitions. Second operand 9 states. [2018-01-20 21:58:08,757 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:08,758 INFO L93 Difference]: Finished difference Result 5258 states and 7573 transitions. [2018-01-20 21:58:08,758 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-20 21:58:08,758 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 87 [2018-01-20 21:58:08,758 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:08,773 INFO L225 Difference]: With dead ends: 5258 [2018-01-20 21:58:08,774 INFO L226 Difference]: Without dead ends: 3673 [2018-01-20 21:58:08,780 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-20 21:58:08,782 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3673 states. [2018-01-20 21:58:08,973 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3673 to 3550. [2018-01-20 21:58:08,973 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3550 states. [2018-01-20 21:58:08,980 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3550 states to 3550 states and 5100 transitions. [2018-01-20 21:58:08,980 INFO L78 Accepts]: Start accepts. Automaton has 3550 states and 5100 transitions. Word has length 87 [2018-01-20 21:58:08,981 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:08,981 INFO L432 AbstractCegarLoop]: Abstraction has 3550 states and 5100 transitions. [2018-01-20 21:58:08,981 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-20 21:58:08,981 INFO L276 IsEmpty]: Start isEmpty. Operand 3550 states and 5100 transitions. [2018-01-20 21:58:08,987 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2018-01-20 21:58:08,987 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:08,987 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-20 21:58:08,987 INFO L371 AbstractCegarLoop]: === Iteration 12 === [mainErr0EnsuresViolation]=== [2018-01-20 21:58:08,988 INFO L82 PathProgramCache]: Analyzing trace with hash 160797049, now seen corresponding path program 1 times [2018-01-20 21:58:08,988 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:08,988 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:08,989 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:08,989 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:08,989 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:08,999 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:09,000 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:09,227 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-20 21:58:09,227 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 21:58:09,227 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 21:58:09,245 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:09,312 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:09,317 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 21:58:09,448 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-20 21:58:09,478 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-20 21:58:09,500 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-20 21:58:09,500 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [8] total 10 [2018-01-20 21:58:09,500 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-01-20 21:58:09,500 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-01-20 21:58:09,501 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=54, Unknown=1, NotChecked=14, Total=90 [2018-01-20 21:58:09,501 INFO L87 Difference]: Start difference. First operand 3550 states and 5100 transitions. Second operand 10 states. [2018-01-20 21:58:10,181 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:10,181 INFO L93 Difference]: Finished difference Result 8706 states and 13158 transitions. [2018-01-20 21:58:10,181 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-01-20 21:58:10,181 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 88 [2018-01-20 21:58:10,182 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:10,204 INFO L225 Difference]: With dead ends: 8706 [2018-01-20 21:58:10,204 INFO L226 Difference]: Without dead ends: 4831 [2018-01-20 21:58:10,217 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 104 GetRequests, 91 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=43, Invalid=141, Unknown=2, NotChecked=24, Total=210 [2018-01-20 21:58:10,220 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4831 states. [2018-01-20 21:58:10,515 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4831 to 4394. [2018-01-20 21:58:10,515 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4394 states. [2018-01-20 21:58:10,524 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4394 states to 4394 states and 6385 transitions. [2018-01-20 21:58:10,524 INFO L78 Accepts]: Start accepts. Automaton has 4394 states and 6385 transitions. Word has length 88 [2018-01-20 21:58:10,525 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:10,525 INFO L432 AbstractCegarLoop]: Abstraction has 4394 states and 6385 transitions. [2018-01-20 21:58:10,525 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-01-20 21:58:10,525 INFO L276 IsEmpty]: Start isEmpty. Operand 4394 states and 6385 transitions. [2018-01-20 21:58:10,530 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2018-01-20 21:58:10,530 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:10,531 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-20 21:58:10,531 INFO L371 AbstractCegarLoop]: === Iteration 13 === [mainErr0EnsuresViolation]=== [2018-01-20 21:58:10,531 INFO L82 PathProgramCache]: Analyzing trace with hash -2024113882, now seen corresponding path program 1 times [2018-01-20 21:58:10,531 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:10,531 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:10,532 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:10,532 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:10,532 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:10,551 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:10,552 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:10,841 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-20 21:58:10,842 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 21:58:10,842 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 21:58:10,850 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:10,933 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:10,939 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 21:58:11,046 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-20 21:58:11,081 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 21:58:11,081 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 6] total 15 [2018-01-20 21:58:11,082 INFO L409 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-01-20 21:58:11,082 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-01-20 21:58:11,082 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=182, Unknown=0, NotChecked=0, Total=210 [2018-01-20 21:58:11,082 INFO L87 Difference]: Start difference. First operand 4394 states and 6385 transitions. Second operand 15 states. [2018-01-20 21:58:13,962 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:13,963 INFO L93 Difference]: Finished difference Result 16377 states and 25815 transitions. [2018-01-20 21:58:13,963 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 58 states. [2018-01-20 21:58:13,963 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 90 [2018-01-20 21:58:13,964 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:14,033 INFO L225 Difference]: With dead ends: 16377 [2018-01-20 21:58:14,033 INFO L226 Difference]: Without dead ends: 12378 [2018-01-20 21:58:14,061 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 197 GetRequests, 128 SyntacticMatches, 0 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1474 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=937, Invalid=4033, Unknown=0, NotChecked=0, Total=4970 [2018-01-20 21:58:14,071 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 12378 states. [2018-01-20 21:58:14,904 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 12378 to 10054. [2018-01-20 21:58:14,905 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 10054 states. [2018-01-20 21:58:14,931 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10054 states to 10054 states and 14764 transitions. [2018-01-20 21:58:14,931 INFO L78 Accepts]: Start accepts. Automaton has 10054 states and 14764 transitions. Word has length 90 [2018-01-20 21:58:14,932 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:14,932 INFO L432 AbstractCegarLoop]: Abstraction has 10054 states and 14764 transitions. [2018-01-20 21:58:14,932 INFO L433 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-01-20 21:58:14,932 INFO L276 IsEmpty]: Start isEmpty. Operand 10054 states and 14764 transitions. [2018-01-20 21:58:14,946 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2018-01-20 21:58:14,946 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:14,946 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-20 21:58:14,946 INFO L371 AbstractCegarLoop]: === Iteration 14 === [mainErr0EnsuresViolation]=== [2018-01-20 21:58:14,947 INFO L82 PathProgramCache]: Analyzing trace with hash 507171894, now seen corresponding path program 1 times [2018-01-20 21:58:14,947 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:14,947 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:14,948 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:14,948 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:14,948 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:14,965 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:14,966 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:15,146 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-20 21:58:15,147 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 21:58:15,147 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 21:58:15,156 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:15,238 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:15,243 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 21:58:15,315 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-20 21:58:15,336 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 21:58:15,336 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 16 [2018-01-20 21:58:15,336 INFO L409 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-01-20 21:58:15,336 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-01-20 21:58:15,336 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=203, Unknown=0, NotChecked=0, Total=240 [2018-01-20 21:58:15,336 INFO L87 Difference]: Start difference. First operand 10054 states and 14764 transitions. Second operand 16 states. [2018-01-20 21:58:17,644 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:17,644 INFO L93 Difference]: Finished difference Result 34479 states and 56881 transitions. [2018-01-20 21:58:17,644 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-01-20 21:58:17,644 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 90 [2018-01-20 21:58:17,645 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:17,717 INFO L225 Difference]: With dead ends: 34479 [2018-01-20 21:58:17,717 INFO L226 Difference]: Without dead ends: 24430 [2018-01-20 21:58:17,745 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 96 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 234 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=215, Invalid=975, Unknown=0, NotChecked=0, Total=1190 [2018-01-20 21:58:17,758 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24430 states. [2018-01-20 21:58:18,772 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24430 to 14850. [2018-01-20 21:58:18,772 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 14850 states. [2018-01-20 21:58:18,799 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14850 states to 14850 states and 21251 transitions. [2018-01-20 21:58:18,799 INFO L78 Accepts]: Start accepts. Automaton has 14850 states and 21251 transitions. Word has length 90 [2018-01-20 21:58:18,799 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:18,799 INFO L432 AbstractCegarLoop]: Abstraction has 14850 states and 21251 transitions. [2018-01-20 21:58:18,800 INFO L433 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-01-20 21:58:18,800 INFO L276 IsEmpty]: Start isEmpty. Operand 14850 states and 21251 transitions. [2018-01-20 21:58:18,809 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2018-01-20 21:58:18,810 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:18,810 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-20 21:58:18,810 INFO L371 AbstractCegarLoop]: === Iteration 15 === [mainErr0EnsuresViolation]=== [2018-01-20 21:58:18,810 INFO L82 PathProgramCache]: Analyzing trace with hash 671709488, now seen corresponding path program 1 times [2018-01-20 21:58:18,810 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:18,810 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:18,811 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:18,811 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:18,811 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:18,827 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:18,828 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:19,033 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-20 21:58:19,034 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 21:58:19,034 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 21:58:19,041 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:19,108 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:19,111 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 21:58:19,133 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-20 21:58:19,153 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 21:58:19,153 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 4] total 10 [2018-01-20 21:58:19,154 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-01-20 21:58:19,154 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-01-20 21:58:19,154 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=73, Unknown=0, NotChecked=0, Total=90 [2018-01-20 21:58:19,154 INFO L87 Difference]: Start difference. First operand 14850 states and 21251 transitions. Second operand 10 states. [2018-01-20 21:58:19,311 WARN L146 SmtUtils]: Spent 103ms on a formula simplification. DAG size of input: 26 DAG size of output 24 [2018-01-20 21:58:23,911 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 21:58:23,911 INFO L93 Difference]: Finished difference Result 90309 states and 131452 transitions. [2018-01-20 21:58:23,944 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-01-20 21:58:23,945 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 107 [2018-01-20 21:58:23,945 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 21:58:24,139 INFO L225 Difference]: With dead ends: 90309 [2018-01-20 21:58:24,139 INFO L226 Difference]: Without dead ends: 75464 [2018-01-20 21:58:24,176 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-20 21:58:24,214 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 75464 states. [2018-01-20 21:58:28,879 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 75464 to 71706. [2018-01-20 21:58:28,879 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 71706 states. [2018-01-20 21:58:29,031 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71706 states to 71706 states and 103461 transitions. [2018-01-20 21:58:29,032 INFO L78 Accepts]: Start accepts. Automaton has 71706 states and 103461 transitions. Word has length 107 [2018-01-20 21:58:29,032 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 21:58:29,032 INFO L432 AbstractCegarLoop]: Abstraction has 71706 states and 103461 transitions. [2018-01-20 21:58:29,032 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-01-20 21:58:29,033 INFO L276 IsEmpty]: Start isEmpty. Operand 71706 states and 103461 transitions. [2018-01-20 21:58:29,043 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2018-01-20 21:58:29,043 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 21:58:29,043 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-20 21:58:29,043 INFO L371 AbstractCegarLoop]: === Iteration 16 === [mainErr0EnsuresViolation]=== [2018-01-20 21:58:29,043 INFO L82 PathProgramCache]: Analyzing trace with hash -1515124594, now seen corresponding path program 1 times [2018-01-20 21:58:29,044 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 21:58:29,044 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 21:58:29,044 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:29,044 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:29,044 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 21:58:29,063 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:29,064 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 21:58:29,310 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-20 21:58:29,310 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 21:58:29,310 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-20 21:58:29,319 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 21:58:29,388 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 21:58:29,392 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 21:58:29,512 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-20 21:58:29,534 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 21:58:29,534 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9] total 19 [2018-01-20 21:58:29,534 INFO L409 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-01-20 21:58:29,535 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-01-20 21:58:29,535 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=304, Unknown=0, NotChecked=0, Total=342 [2018-01-20 21:58:29,535 INFO L87 Difference]: Start difference. First operand 71706 states and 103461 transitions. Second operand 19 states. [2018-01-20 21:58:31,124 WARN L146 SmtUtils]: Spent 211ms on a formula simplification. DAG size of input: 39 DAG size of output 36 [2018-01-20 21:58:35,116 WARN L146 SmtUtils]: Spent 884ms on a formula simplification. DAG size of input: 44 DAG size of output 42 Received shutdown request... [2018-01-20 21:58:37,161 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 131 states. [2018-01-20 21:58:37,162 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-20 21:58:37,166 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 21:58:37,166 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 21:58:37,166 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 21:58:37,166 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 21:58:37,166 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 21:58:37,166 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 21:58:37,166 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 21:58:37,166 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == pushErr0EnsuresViolation======== [2018-01-20 21:58:37,167 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 21:58:37,168 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states. [2018-01-20 21:58:37,168 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-20 21:58:37,169 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.01 09:58:37 BoogieIcfgContainer [2018-01-20 21:58:37,169 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-20 21:58:37,170 INFO L168 Benchmark]: Toolchain (without parser) took 44212.04 ms. Allocated memory was 310.4 MB in the beginning and 1.8 GB in the end (delta: 1.5 GB). Free memory was 268.7 MB in the beginning and 905.5 MB in the end (delta: -636.8 MB). Peak memory consumption was 881.5 MB. Max. memory is 5.3 GB. [2018-01-20 21:58:37,172 INFO L168 Benchmark]: CDTParser took 0.21 ms. Allocated memory is still 310.4 MB. Free memory is still 274.7 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-20 21:58:37,172 INFO L168 Benchmark]: CACSL2BoogieTranslator took 200.23 ms. Allocated memory is still 310.4 MB. Free memory was 267.7 MB in the beginning and 256.6 MB in the end (delta: 11.1 MB). Peak memory consumption was 11.1 MB. Max. memory is 5.3 GB. [2018-01-20 21:58:37,173 INFO L168 Benchmark]: Boogie Preprocessor took 35.02 ms. Allocated memory is still 310.4 MB. Free memory was 256.6 MB in the beginning and 254.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-01-20 21:58:37,173 INFO L168 Benchmark]: RCFGBuilder took 332.73 ms. Allocated memory is still 310.4 MB. Free memory was 254.6 MB in the beginning and 231.0 MB in the end (delta: 23.6 MB). Peak memory consumption was 23.6 MB. Max. memory is 5.3 GB. [2018-01-20 21:58:37,173 INFO L168 Benchmark]: TraceAbstraction took 43636.20 ms. Allocated memory was 310.4 MB in the beginning and 1.8 GB in the end (delta: 1.5 GB). Free memory was 231.0 MB in the beginning and 905.5 MB in the end (delta: -674.5 MB). Peak memory consumption was 843.8 MB. Max. memory is 5.3 GB. [2018-01-20 21:58:37,175 INFO L344 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.21 ms. Allocated memory is still 310.4 MB. Free memory is still 274.7 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 200.23 ms. Allocated memory is still 310.4 MB. Free memory was 267.7 MB in the beginning and 256.6 MB in the end (delta: 11.1 MB). Peak memory consumption was 11.1 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 35.02 ms. Allocated memory is still 310.4 MB. Free memory was 256.6 MB in the beginning and 254.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 332.73 ms. Allocated memory is still 310.4 MB. Free memory was 254.6 MB in the beginning and 231.0 MB in the end (delta: 23.6 MB). Peak memory consumption was 23.6 MB. Max. memory is 5.3 GB. * TraceAbstraction took 43636.20 ms. Allocated memory was 310.4 MB in the beginning and 1.8 GB in the end (delta: 1.5 GB). Free memory was 231.0 MB in the beginning and 905.5 MB in the end (delta: -674.5 MB). Peak memory consumption was 843.8 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)=3, \old(S)=9, \old(t1)=12, \old(t1)=8, \old(t4)=16, \old(t4)=4, \old(x1)=1, \old(x1)=14, \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] 1 != pc1 || 1 != pc4 || __VERIFIER_nondet_int() [L690] 1 != pc1 || 1 != pc4 || __VERIFIER_nondet_int() VAL [1 != pc1 || 1 != pc4 || __VERIFIER_nondet_int()=0, \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}, t1={0:0}, t4={0:0}, x1={0:0}, x4={0:0}] [L690] COND FALSE !(1 != pc1 || 1 != pc4 || __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 (71706states) and interpolant automaton (currently 131 states, 19 states before enhancement), while ReachableStatesComputation was computing reachable states (27774 states constructedinput type IntersectNwa). - StatisticsResult: Ultimate Automizer benchmark data for error location: mainErr0EnsuresViolation CFG has 5 procedures, 62 locations, 5 error locations. TIMEOUT Result, 42.8s OverallTime, 16 OverallIterations, 7 TraceHistogramMax, 29.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 1334 SDtfs, 10446 SDslu, 4552 SDs, 0 SdLazy, 9312 SolverSat, 3846 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 7.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1651 GetRequests, 1056 SyntacticMatches, 3 SemanticMatches, 592 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 23166 ImplicationChecksByTransitivity, 14.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=71706occurred 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.1s AutomataMinimizationTime, 15 MinimizatonAttempts, 18993 StatesRemovedByMinimization, 13 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 3.3s InterpolantComputationTime, 1881 NumberOfCodeBlocks, 1881 NumberOfCodeBlocksAsserted, 27 NumberOfCheckSat, 1855 ConstructedInterpolants, 4 QuantifiedInterpolants, 411402 SizeOfPredicates, 34 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.1_false-valid-memtrack.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-20_21-58-37-186.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/lockfree-3.1_false-valid-memtrack.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-20_21-58-37-186.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/lockfree-3.1_false-valid-memtrack.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-1-2018-01-20_21-58-37-186.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/lockfree-3.1_false-valid-memtrack.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-2-2018-01-20_21-58-37-186.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/lockfree-3.1_false-valid-memtrack.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-3-2018-01-20_21-58-37-186.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/lockfree-3.1_false-valid-memtrack.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-4-2018-01-20_21-58-37-186.csv Completed graceful shutdown