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-47db877 [2018-01-23 14:23:56,546 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-23 14:23:56,548 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-23 14:23:56,560 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-23 14:23:56,561 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-23 14:23:56,561 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-23 14:23:56,563 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-23 14:23:56,564 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-23 14:23:56,566 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-23 14:23:56,567 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-23 14:23:56,568 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-23 14:23:56,568 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-23 14:23:56,569 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-23 14:23:56,569 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-23 14:23:56,570 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-23 14:23:56,572 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-23 14:23:56,574 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-23 14:23:56,576 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-23 14:23:56,578 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-23 14:23:56,579 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-23 14:23:56,581 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-23 14:23:56,581 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-23 14:23:56,582 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-23 14:23:56,583 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-23 14:23:56,583 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-23 14:23:56,584 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-23 14:23:56,585 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-23 14:23:56,585 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-23 14:23:56,585 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-23 14:23:56,586 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-23 14:23:56,586 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-23 14:23:56,587 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/ai/eq-bench/mempurity-32bit-Automizer_Camel+AI_EQ.epf [2018-01-23 14:23:56,596 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-23 14:23:56,597 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-23 14:23:56,597 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-23 14:23:56,598 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-23 14:23:56,598 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-23 14:23:56,598 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-23 14:23:56,598 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-23 14:23:56,599 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-23 14:23:56,599 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-23 14:23:56,599 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-23 14:23:56,599 INFO L133 SettingsManager]: * Check allocation purity=true [2018-01-23 14:23:56,600 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-23 14:23:56,600 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-23 14:23:56,600 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-23 14:23:56,600 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-01-23 14:23:56,600 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-23 14:23:56,600 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-01-23 14:23:56,601 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-23 14:23:56,601 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-01-23 14:23:56,601 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-01-23 14:23:56,601 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-23 14:23:56,602 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-01-23 14:23:56,602 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-23 14:23:56,602 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-23 14:23:56,602 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-23 14:23:56,602 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-23 14:23:56,603 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-23 14:23:56,603 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-23 14:23:56,603 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-23 14:23:56,603 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-23 14:23:56,603 INFO L133 SettingsManager]: * Stop after first violation was found=false [2018-01-23 14:23:56,604 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-01-23 14:23:56,604 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-23 14:23:56,604 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-23 14:23:56,604 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-23 14:23:56,605 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-23 14:23:56,605 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-23 14:23:56,638 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-23 14:23:56,648 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-23 14:23:56,652 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-23 14:23:56,653 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-23 14:23:56,653 INFO L276 PluginConnector]: CDTParser initialized [2018-01-23 14:23:56,653 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-23 14:23:56,826 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-23 14:23:56,831 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-23 14:23:56,831 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-23 14:23:56,832 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-23 14:23:56,837 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-23 14:23:56,838 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.01 02:23:56" (1/1) ... [2018-01-23 14:23:56,840 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4b942210 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:23:56, skipping insertion in model container [2018-01-23 14:23:56,841 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.01 02:23:56" (1/1) ... [2018-01-23 14:23:56,854 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-23 14:23:56,891 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-23 14:23:57,012 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-23 14:23:57,038 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-23 14:23:57,046 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:23:57 WrapperNode [2018-01-23 14:23:57,047 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-23 14:23:57,047 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-23 14:23:57,047 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-23 14:23:57,047 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-23 14:23:57,059 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:23:57" (1/1) ... [2018-01-23 14:23:57,059 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:23:57" (1/1) ... [2018-01-23 14:23:57,070 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:23:57" (1/1) ... [2018-01-23 14:23:57,070 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:23:57" (1/1) ... [2018-01-23 14:23:57,074 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:23:57" (1/1) ... [2018-01-23 14:23:57,078 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:23:57" (1/1) ... [2018-01-23 14:23:57,079 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:23:57" (1/1) ... [2018-01-23 14:23:57,081 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-23 14:23:57,082 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-23 14:23:57,082 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-23 14:23:57,082 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-23 14:23:57,083 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:23:57" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-23 14:23:57,138 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-23 14:23:57,138 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-23 14:23:57,138 INFO L136 BoogieDeclarations]: Found implementation of procedure push [2018-01-23 14:23:57,139 INFO L136 BoogieDeclarations]: Found implementation of procedure pop [2018-01-23 14:23:57,139 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-23 14:23:57,139 INFO L128 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2018-01-23 14:23:57,139 INFO L128 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2018-01-23 14:23:57,139 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-01-23 14:23:57,139 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-01-23 14:23:57,139 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-23 14:23:57,139 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-23 14:23:57,139 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-23 14:23:57,139 INFO L128 BoogieDeclarations]: Found specification of procedure malloc [2018-01-23 14:23:57,140 INFO L128 BoogieDeclarations]: Found specification of procedure free [2018-01-23 14:23:57,140 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-23 14:23:57,140 INFO L128 BoogieDeclarations]: Found specification of procedure push [2018-01-23 14:23:57,140 INFO L128 BoogieDeclarations]: Found specification of procedure pop [2018-01-23 14:23:57,140 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-23 14:23:57,140 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-23 14:23:57,140 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-23 14:23:57,447 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-23 14:23:57,448 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.01 02:23:57 BoogieIcfgContainer [2018-01-23 14:23:57,448 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-23 14:23:57,448 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-23 14:23:57,449 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-23 14:23:57,450 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-23 14:23:57,451 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 23.01 02:23:56" (1/3) ... [2018-01-23 14:23:57,451 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@ce304a6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.01 02:23:57, skipping insertion in model container [2018-01-23 14:23:57,452 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:23:57" (2/3) ... [2018-01-23 14:23:57,452 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@ce304a6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.01 02:23:57, skipping insertion in model container [2018-01-23 14:23:57,452 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.01 02:23:57" (3/3) ... [2018-01-23 14:23:57,454 INFO L105 eAbstractionObserver]: Analyzing ICFG lockfree-3.1_false-valid-memtrack.i [2018-01-23 14:23:57,464 INFO L130 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-23 14:23:57,472 INFO L142 ceAbstractionStarter]: Appying trace abstraction to program that has 5 error locations. [2018-01-23 14:23:57,514 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-23 14:23:57,515 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-23 14:23:57,515 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-23 14:23:57,515 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-23 14:23:57,515 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-23 14:23:57,515 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-23 14:23:57,515 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-23 14:23:57,515 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == popErr0EnsuresViolation======== [2018-01-23 14:23:57,516 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-23 14:23:57,532 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states. [2018-01-23 14:23:57,539 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2018-01-23 14:23:57,539 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:23:57,540 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:23:57,540 INFO L371 AbstractCegarLoop]: === Iteration 1 === [popErr0EnsuresViolation]=== [2018-01-23 14:23:57,544 INFO L82 PathProgramCache]: Analyzing trace with hash 816843792, now seen corresponding path program 1 times [2018-01-23 14:23:57,546 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:23:57,546 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:23:57,587 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:57,588 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:23:57,588 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:57,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:23:57,669 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:23:57,730 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-23 14:23:57,733 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:23:57,734 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2018-01-23 14:23:57,736 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-23 14:23:57,747 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-23 14:23:57,748 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-23 14:23:57,750 INFO L87 Difference]: Start difference. First operand 62 states. Second operand 2 states. [2018-01-23 14:23:57,857 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:23:57,858 INFO L93 Difference]: Finished difference Result 75 states and 95 transitions. [2018-01-23 14:23:57,858 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-23 14:23:57,859 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 14 [2018-01-23 14:23:57,859 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:23:57,865 INFO L225 Difference]: With dead ends: 75 [2018-01-23 14:23:57,865 INFO L226 Difference]: Without dead ends: 0 [2018-01-23 14:23:57,869 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 1 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-23 14:23:57,884 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2018-01-23 14:23:57,889 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2018-01-23 14:23:57,890 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 0 states. [2018-01-23 14:23:57,890 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2018-01-23 14:23:57,891 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 14 [2018-01-23 14:23:57,891 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:23:57,891 INFO L432 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2018-01-23 14:23:57,891 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-23 14:23:57,892 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2018-01-23 14:23:57,892 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2018-01-23 14:23:57,895 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2018-01-23 14:23:57,922 INFO L401 ceAbstractionStarter]: For program point L681(line 681) no Hoare annotation was computed. [2018-01-23 14:23:57,922 INFO L401 ceAbstractionStarter]: For program point L680(line 680) no Hoare annotation was computed. [2018-01-23 14:23:57,922 INFO L401 ceAbstractionStarter]: For program point popEXIT(lines 660 687) no Hoare annotation was computed. [2018-01-23 14:23:57,922 INFO L401 ceAbstractionStarter]: For program point L663(lines 663 686) no Hoare annotation was computed. [2018-01-23 14:23:57,923 INFO L404 ceAbstractionStarter]: At program point popENTRY(lines 660 687) the Hoare annotation is: true [2018-01-23 14:23:57,923 INFO L401 ceAbstractionStarter]: For program point L682(line 682) no Hoare annotation was computed. [2018-01-23 14:23:57,923 INFO L401 ceAbstractionStarter]: For program point L667(line 667) no Hoare annotation was computed. [2018-01-23 14:23:57,923 INFO L401 ceAbstractionStarter]: For program point L672'(line 672) no Hoare annotation was computed. [2018-01-23 14:23:57,923 INFO L401 ceAbstractionStarter]: For program point L664(line 664) no Hoare annotation was computed. [2018-01-23 14:23:57,923 INFO L401 ceAbstractionStarter]: For program point L682'(line 682) no Hoare annotation was computed. [2018-01-23 14:23:57,924 INFO L401 ceAbstractionStarter]: For program point L668(lines 668 669) no Hoare annotation was computed. [2018-01-23 14:23:57,924 INFO L401 ceAbstractionStarter]: For program point L674(line 674) no Hoare annotation was computed. [2018-01-23 14:23:57,924 INFO L401 ceAbstractionStarter]: For program point L672(line 672) no Hoare annotation was computed. [2018-01-23 14:23:57,924 INFO L401 ceAbstractionStarter]: For program point L671(line 671) no Hoare annotation was computed. [2018-01-23 14:23:57,924 INFO L401 ceAbstractionStarter]: For program point L675(lines 675 678) no Hoare annotation was computed. [2018-01-23 14:23:57,924 INFO L401 ceAbstractionStarter]: For program point L675''(lines 675 678) no Hoare annotation was computed. [2018-01-23 14:23:57,924 INFO L401 ceAbstractionStarter]: For program point L681'(line 681) no Hoare annotation was computed. [2018-01-23 14:23:57,925 INFO L401 ceAbstractionStarter]: For program point popErr0EnsuresViolation(lines 660 687) no Hoare annotation was computed. [2018-01-23 14:23:57,925 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.initErr0EnsuresViolation(lines 1 707) no Hoare annotation was computed. [2018-01-23 14:23:57,925 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.initEXIT(lines 1 707) no Hoare annotation was computed. [2018-01-23 14:23:57,925 INFO L404 ceAbstractionStarter]: At program point ULTIMATE.initENTRY(lines 1 707) the Hoare annotation is: true [2018-01-23 14:23:57,925 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.initFINAL(lines 1 707) no Hoare annotation was computed. [2018-01-23 14:23:57,925 INFO L404 ceAbstractionStarter]: At program point ULTIMATE.startENTRY(lines 1 707) the Hoare annotation is: true [2018-01-23 14:23:57,925 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.startFINAL(lines 1 707) no Hoare annotation was computed. [2018-01-23 14:23:57,926 INFO L404 ceAbstractionStarter]: At program point L1(lines 1 707) the Hoare annotation is: true [2018-01-23 14:23:57,926 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.startErr0EnsuresViolation(lines 1 707) no Hoare annotation was computed. [2018-01-23 14:23:57,926 INFO L401 ceAbstractionStarter]: For program point ULTIMATE.startEXIT(lines 1 707) no Hoare annotation was computed. [2018-01-23 14:23:57,926 INFO L404 ceAbstractionStarter]: At program point L694'(line 694) the Hoare annotation is: true [2018-01-23 14:23:57,926 INFO L401 ceAbstractionStarter]: For program point L690'(line 690) no Hoare annotation was computed. [2018-01-23 14:23:57,926 INFO L401 ceAbstractionStarter]: For program point L697'(line 697) no Hoare annotation was computed. [2018-01-23 14:23:57,926 INFO L401 ceAbstractionStarter]: For program point L696'''(lines 696 700) no Hoare annotation was computed. [2018-01-23 14:23:57,927 INFO L401 ceAbstractionStarter]: For program point L690'''(line 690) no Hoare annotation was computed. [2018-01-23 14:23:57,927 INFO L401 ceAbstractionStarter]: For program point mainErr0EnsuresViolation(lines 688 707) no Hoare annotation was computed. [2018-01-23 14:23:57,927 INFO L404 ceAbstractionStarter]: At program point L692(line 692) the Hoare annotation is: true [2018-01-23 14:23:57,927 INFO L401 ceAbstractionStarter]: For program point L691(lines 691 694) no Hoare annotation was computed. [2018-01-23 14:23:57,927 INFO L401 ceAbstractionStarter]: For program point L690(lines 690 695) no Hoare annotation was computed. [2018-01-23 14:23:57,927 INFO L401 ceAbstractionStarter]: For program point L696(lines 696 700) no Hoare annotation was computed. [2018-01-23 14:23:57,927 INFO L401 ceAbstractionStarter]: For program point L696''(lines 696 700) no Hoare annotation was computed. [2018-01-23 14:23:57,928 INFO L404 ceAbstractionStarter]: At program point L694(line 694) the Hoare annotation is: true [2018-01-23 14:23:57,928 INFO L401 ceAbstractionStarter]: For program point mainFINAL(lines 688 707) no Hoare annotation was computed. [2018-01-23 14:23:57,928 INFO L401 ceAbstractionStarter]: For program point L698(line 698) no Hoare annotation was computed. [2018-01-23 14:23:57,928 INFO L401 ceAbstractionStarter]: For program point L697(line 697) no Hoare annotation was computed. [2018-01-23 14:23:57,928 INFO L401 ceAbstractionStarter]: For program point mainEXIT(lines 688 707) no Hoare annotation was computed. [2018-01-23 14:23:57,928 INFO L401 ceAbstractionStarter]: For program point L698'(line 698) no Hoare annotation was computed. [2018-01-23 14:23:57,928 INFO L401 ceAbstractionStarter]: For program point L640(line 640) no Hoare annotation was computed. [2018-01-23 14:23:57,929 INFO L401 ceAbstractionStarter]: For program point L644(line 644) no Hoare annotation was computed. [2018-01-23 14:23:57,929 INFO L401 ceAbstractionStarter]: For program point L643(line 643) no Hoare annotation was computed. [2018-01-23 14:23:57,929 INFO L401 ceAbstractionStarter]: For program point L647''(lines 647 650) no Hoare annotation was computed. [2018-01-23 14:23:57,929 INFO L401 ceAbstractionStarter]: For program point L647(lines 647 650) no Hoare annotation was computed. [2018-01-23 14:23:57,929 INFO L401 ceAbstractionStarter]: For program point L646(line 646) no Hoare annotation was computed. [2018-01-23 14:23:57,929 INFO L401 ceAbstractionStarter]: For program point L633'(line 633) no Hoare annotation was computed. [2018-01-23 14:23:57,929 INFO L404 ceAbstractionStarter]: At program point pushENTRY(lines 629 656) the Hoare annotation is: true [2018-01-23 14:23:57,929 INFO L401 ceAbstractionStarter]: For program point L652(line 652) no Hoare annotation was computed. [2018-01-23 14:23:57,930 INFO L401 ceAbstractionStarter]: For program point pushErr0EnsuresViolation(lines 629 656) no Hoare annotation was computed. [2018-01-23 14:23:57,930 INFO L401 ceAbstractionStarter]: For program point L634(line 634) no Hoare annotation was computed. [2018-01-23 14:23:57,930 INFO L401 ceAbstractionStarter]: For program point L633(line 633) no Hoare annotation was computed. [2018-01-23 14:23:57,930 INFO L401 ceAbstractionStarter]: For program point L632(line 632) no Hoare annotation was computed. [2018-01-23 14:23:57,930 INFO L401 ceAbstractionStarter]: For program point L631(lines 631 655) no Hoare annotation was computed. [2018-01-23 14:23:57,930 INFO L401 ceAbstractionStarter]: For program point L638(line 638) no Hoare annotation was computed. [2018-01-23 14:23:57,930 INFO L401 ceAbstractionStarter]: For program point pushEXIT(lines 629 656) no Hoare annotation was computed. [2018-01-23 14:23:57,931 INFO L401 ceAbstractionStarter]: For program point L637(line 637) no Hoare annotation was computed. [2018-01-23 14:23:57,931 INFO L401 ceAbstractionStarter]: For program point L634'(line 634) no Hoare annotation was computed. [2018-01-23 14:23:57,935 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-23 14:23:57,935 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-23 14:23:57,935 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-23 14:23:57,935 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-23 14:23:57,935 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-23 14:23:57,935 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-23 14:23:57,935 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-23 14:23:57,936 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.initErr0EnsuresViolation======== [2018-01-23 14:23:57,936 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-23 14:23:57,938 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states. [2018-01-23 14:23:57,939 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2018-01-23 14:23:57,939 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:23:57,939 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1] [2018-01-23 14:23:57,939 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.initErr0EnsuresViolation]=== [2018-01-23 14:23:57,939 INFO L82 PathProgramCache]: Analyzing trace with hash 169454, now seen corresponding path program 1 times [2018-01-23 14:23:57,940 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:23:57,940 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:23:57,941 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:57,941 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:23:57,941 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:57,955 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-23 14:23:57,968 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-23 14:23:57,994 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-23 14:23:58,003 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-23 14:23:58,012 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-23 14:23:58,012 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-23 14:23:58,012 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-23 14:23:58,012 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-23 14:23:58,013 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-23 14:23:58,013 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-23 14:23:58,013 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-23 14:23:58,013 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.startErr0EnsuresViolation======== [2018-01-23 14:23:58,013 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-23 14:23:58,015 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states. [2018-01-23 14:23:58,016 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-01-23 14:23:58,016 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:23:58,016 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:23:58,016 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:23:58,016 INFO L82 PathProgramCache]: Analyzing trace with hash 1316586551, now seen corresponding path program 1 times [2018-01-23 14:23:58,017 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:23:58,017 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:23:58,018 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:58,018 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:23:58,018 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:58,032 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:23:58,033 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:23:58,047 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-23 14:23:58,047 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:23:58,047 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-23 14:23:58,048 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-23 14:23:58,048 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-23 14:23:58,048 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-23 14:23:58,048 INFO L87 Difference]: Start difference. First operand 62 states. Second operand 2 states. [2018-01-23 14:23:58,055 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:23:58,055 INFO L93 Difference]: Finished difference Result 75 states and 95 transitions. [2018-01-23 14:23:58,055 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-23 14:23:58,055 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 11 [2018-01-23 14:23:58,056 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:23:58,063 INFO L225 Difference]: With dead ends: 75 [2018-01-23 14:23:58,064 INFO L226 Difference]: Without dead ends: 57 [2018-01-23 14:23:58,064 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-23 14:23:58,065 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2018-01-23 14:23:58,081 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 57. [2018-01-23 14:23:58,081 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 57 states. [2018-01-23 14:23:58,083 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 74 transitions. [2018-01-23 14:23:58,083 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 74 transitions. Word has length 11 [2018-01-23 14:23:58,083 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:23:58,083 INFO L432 AbstractCegarLoop]: Abstraction has 57 states and 74 transitions. [2018-01-23 14:23:58,083 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-23 14:23:58,083 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 74 transitions. [2018-01-23 14:23:58,084 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-23 14:23:58,084 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:23:58,085 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:23:58,085 INFO L371 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:23:58,085 INFO L82 PathProgramCache]: Analyzing trace with hash -2092868013, now seen corresponding path program 1 times [2018-01-23 14:23:58,085 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:23:58,085 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:23:58,086 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:58,087 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:23:58,087 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:58,103 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:23:58,104 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:23:58,131 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-23 14:23:58,132 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:23:58,132 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-23 14:23:58,133 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-23 14:23:58,134 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-23 14:23:58,134 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-23 14:23:58,134 INFO L87 Difference]: Start difference. First operand 57 states and 74 transitions. Second operand 3 states. [2018-01-23 14:23:58,160 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:23:58,160 INFO L93 Difference]: Finished difference Result 69 states and 87 transitions. [2018-01-23 14:23:58,161 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-23 14:23:58,161 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 15 [2018-01-23 14:23:58,161 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:23:58,162 INFO L225 Difference]: With dead ends: 69 [2018-01-23 14:23:58,163 INFO L226 Difference]: Without dead ends: 58 [2018-01-23 14:23:58,164 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-23 14:23:58,164 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2018-01-23 14:23:58,170 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 58. [2018-01-23 14:23:58,170 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 58 states. [2018-01-23 14:23:58,172 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 75 transitions. [2018-01-23 14:23:58,172 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 75 transitions. Word has length 15 [2018-01-23 14:23:58,172 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:23:58,172 INFO L432 AbstractCegarLoop]: Abstraction has 58 states and 75 transitions. [2018-01-23 14:23:58,172 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-23 14:23:58,172 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 75 transitions. [2018-01-23 14:23:58,173 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-23 14:23:58,173 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:23:58,174 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:23:58,174 INFO L371 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:23:58,174 INFO L82 PathProgramCache]: Analyzing trace with hash 1392752657, now seen corresponding path program 1 times [2018-01-23 14:23:58,174 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:23:58,174 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:23:58,175 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:58,175 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:23:58,176 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:58,200 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-23 14:23:58,215 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-23 14:23:58,227 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-23 14:23:58,236 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-23 14:23:58,243 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-23 14:23:58,244 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-23 14:23:58,256 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-23 14:23:58,256 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-23 14:23:58,256 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-23 14:23:58,256 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-23 14:23:58,256 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-23 14:23:58,257 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-23 14:23:58,257 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-23 14:23:58,257 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == mainErr0EnsuresViolation======== [2018-01-23 14:23:58,257 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-23 14:23:58,258 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states. [2018-01-23 14:23:58,259 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2018-01-23 14:23:58,259 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:23:58,259 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:23:58,259 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr0EnsuresViolation]=== [2018-01-23 14:23:58,259 INFO L82 PathProgramCache]: Analyzing trace with hash 1784608256, now seen corresponding path program 1 times [2018-01-23 14:23:58,260 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:23:58,260 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:23:58,261 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:58,261 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:23:58,261 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:58,270 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:23:58,271 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:23:58,282 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-23 14:23:58,282 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:23:58,282 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-23 14:23:58,283 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-23 14:23:58,283 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-23 14:23:58,283 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-23 14:23:58,283 INFO L87 Difference]: Start difference. First operand 62 states. Second operand 2 states. [2018-01-23 14:23:58,288 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:23:58,289 INFO L93 Difference]: Finished difference Result 75 states and 95 transitions. [2018-01-23 14:23:58,289 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-23 14:23:58,289 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 9 [2018-01-23 14:23:58,289 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:23:58,290 INFO L225 Difference]: With dead ends: 75 [2018-01-23 14:23:58,290 INFO L226 Difference]: Without dead ends: 55 [2018-01-23 14:23:58,291 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-23 14:23:58,291 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2018-01-23 14:23:58,296 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2018-01-23 14:23:58,296 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-01-23 14:23:58,298 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 72 transitions. [2018-01-23 14:23:58,298 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 72 transitions. Word has length 9 [2018-01-23 14:23:58,298 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:23:58,298 INFO L432 AbstractCegarLoop]: Abstraction has 55 states and 72 transitions. [2018-01-23 14:23:58,298 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-23 14:23:58,298 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 72 transitions. [2018-01-23 14:23:58,299 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-01-23 14:23:58,299 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:23:58,299 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:23:58,299 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr0EnsuresViolation]=== [2018-01-23 14:23:58,300 INFO L82 PathProgramCache]: Analyzing trace with hash 1548658460, now seen corresponding path program 1 times [2018-01-23 14:23:58,300 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:23:58,300 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:23:58,301 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:58,301 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:23:58,301 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:58,309 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:23:58,310 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:23:58,337 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-23 14:23:58,338 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:23:58,338 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-23 14:23:58,338 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-23 14:23:58,338 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-23 14:23:58,339 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-23 14:23:58,339 INFO L87 Difference]: Start difference. First operand 55 states and 72 transitions. Second operand 3 states. [2018-01-23 14:23:58,356 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:23:58,356 INFO L93 Difference]: Finished difference Result 65 states and 83 transitions. [2018-01-23 14:23:58,356 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-23 14:23:58,357 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 13 [2018-01-23 14:23:58,357 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:23:58,358 INFO L225 Difference]: With dead ends: 65 [2018-01-23 14:23:58,358 INFO L226 Difference]: Without dead ends: 56 [2018-01-23 14:23:58,359 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-23 14:23:58,359 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2018-01-23 14:23:58,363 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 56. [2018-01-23 14:23:58,364 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 56 states. [2018-01-23 14:23:58,365 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 73 transitions. [2018-01-23 14:23:58,365 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 73 transitions. Word has length 13 [2018-01-23 14:23:58,366 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:23:58,366 INFO L432 AbstractCegarLoop]: Abstraction has 56 states and 73 transitions. [2018-01-23 14:23:58,366 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-23 14:23:58,366 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 73 transitions. [2018-01-23 14:23:58,367 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-01-23 14:23:58,367 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:23:58,367 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:23:58,367 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr0EnsuresViolation]=== [2018-01-23 14:23:58,367 INFO L82 PathProgramCache]: Analyzing trace with hash 1605916762, now seen corresponding path program 1 times [2018-01-23 14:23:58,367 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:23:58,368 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:23:58,368 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:58,368 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:23:58,368 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:58,378 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:23:58,379 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:23:58,416 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-23 14:23:58,416 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:23:58,416 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-23 14:23:58,416 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-23 14:23:58,416 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-23 14:23:58,417 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-23 14:23:58,417 INFO L87 Difference]: Start difference. First operand 56 states and 73 transitions. Second operand 3 states. [2018-01-23 14:23:58,491 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:23:58,492 INFO L93 Difference]: Finished difference Result 65 states and 82 transitions. [2018-01-23 14:23:58,492 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-23 14:23:58,492 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 13 [2018-01-23 14:23:58,493 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:23:58,493 INFO L225 Difference]: With dead ends: 65 [2018-01-23 14:23:58,494 INFO L226 Difference]: Without dead ends: 62 [2018-01-23 14:23:58,494 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-23 14:23:58,494 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2018-01-23 14:23:58,498 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 58. [2018-01-23 14:23:58,498 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 58 states. [2018-01-23 14:23:58,499 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 75 transitions. [2018-01-23 14:23:58,499 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 75 transitions. Word has length 13 [2018-01-23 14:23:58,500 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:23:58,500 INFO L432 AbstractCegarLoop]: Abstraction has 58 states and 75 transitions. [2018-01-23 14:23:58,500 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-23 14:23:58,500 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 75 transitions. [2018-01-23 14:23:58,500 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2018-01-23 14:23:58,501 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:23:58,501 INFO L322 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:23:58,501 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr0EnsuresViolation]=== [2018-01-23 14:23:58,501 INFO L82 PathProgramCache]: Analyzing trace with hash 1614897922, now seen corresponding path program 1 times [2018-01-23 14:23:58,501 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:23:58,501 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:23:58,502 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:58,502 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:23:58,502 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:58,514 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:23:58,515 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:23:58,558 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-23 14:23:58,558 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:23:58,559 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-23 14:23:58,559 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-23 14:23:58,559 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-23 14:23:58,559 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-23 14:23:58,559 INFO L87 Difference]: Start difference. First operand 58 states and 75 transitions. Second operand 4 states. [2018-01-23 14:23:58,615 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:23:58,615 INFO L93 Difference]: Finished difference Result 114 states and 149 transitions. [2018-01-23 14:23:58,617 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-23 14:23:58,618 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 19 [2018-01-23 14:23:58,618 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:23:58,619 INFO L225 Difference]: With dead ends: 114 [2018-01-23 14:23:58,620 INFO L226 Difference]: Without dead ends: 100 [2018-01-23 14:23:58,620 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-23 14:23:58,621 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2018-01-23 14:23:58,634 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 95. [2018-01-23 14:23:58,634 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 95 states. [2018-01-23 14:23:58,636 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 129 transitions. [2018-01-23 14:23:58,636 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 129 transitions. Word has length 19 [2018-01-23 14:23:58,636 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:23:58,637 INFO L432 AbstractCegarLoop]: Abstraction has 95 states and 129 transitions. [2018-01-23 14:23:58,637 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-23 14:23:58,637 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 129 transitions. [2018-01-23 14:23:58,639 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2018-01-23 14:23:58,639 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:23:58,640 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:23:58,640 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr0EnsuresViolation]=== [2018-01-23 14:23:58,640 INFO L82 PathProgramCache]: Analyzing trace with hash -302614467, now seen corresponding path program 1 times [2018-01-23 14:23:58,640 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:23:58,640 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:23:58,641 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:58,641 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:23:58,641 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:58,657 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:23:58,658 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:23:58,778 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-23 14:23:58,779 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:23:58,779 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-23 14:23:58,779 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-23 14:23:58,779 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-23 14:23:58,780 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2018-01-23 14:23:58,780 INFO L87 Difference]: Start difference. First operand 95 states and 129 transitions. Second operand 7 states. [2018-01-23 14:23:59,206 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:23:59,206 INFO L93 Difference]: Finished difference Result 227 states and 312 transitions. [2018-01-23 14:23:59,207 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-23 14:23:59,207 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 37 [2018-01-23 14:23:59,207 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:23:59,210 INFO L225 Difference]: With dead ends: 227 [2018-01-23 14:23:59,210 INFO L226 Difference]: Without dead ends: 174 [2018-01-23 14:23:59,212 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=93, Unknown=0, NotChecked=0, Total=132 [2018-01-23 14:23:59,212 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 174 states. [2018-01-23 14:23:59,233 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 174 to 150. [2018-01-23 14:23:59,233 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 150 states. [2018-01-23 14:23:59,236 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 150 states to 150 states and 207 transitions. [2018-01-23 14:23:59,236 INFO L78 Accepts]: Start accepts. Automaton has 150 states and 207 transitions. Word has length 37 [2018-01-23 14:23:59,236 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:23:59,237 INFO L432 AbstractCegarLoop]: Abstraction has 150 states and 207 transitions. [2018-01-23 14:23:59,237 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-23 14:23:59,237 INFO L276 IsEmpty]: Start isEmpty. Operand 150 states and 207 transitions. [2018-01-23 14:23:59,239 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2018-01-23 14:23:59,239 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:23:59,240 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:23:59,240 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr0EnsuresViolation]=== [2018-01-23 14:23:59,241 INFO L82 PathProgramCache]: Analyzing trace with hash 1718063660, now seen corresponding path program 1 times [2018-01-23 14:23:59,241 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:23:59,241 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:23:59,242 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:59,242 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:23:59,242 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:23:59,274 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:23:59,275 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:23:59,441 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 2 proven. 18 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-23 14:23:59,441 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:23:59,441 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:23:59,452 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:23:59,529 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:23:59,536 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:23:59,720 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 15 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-23 14:23:59,741 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:23:59,742 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 15 [2018-01-23 14:23:59,742 INFO L409 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-01-23 14:23:59,742 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-01-23 14:23:59,743 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=181, Unknown=0, NotChecked=0, Total=210 [2018-01-23 14:23:59,743 INFO L87 Difference]: Start difference. First operand 150 states and 207 transitions. Second operand 15 states. [2018-01-23 14:24:02,765 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:02,765 INFO L93 Difference]: Finished difference Result 1106 states and 1684 transitions. [2018-01-23 14:24:02,766 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 83 states. [2018-01-23 14:24:02,766 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 47 [2018-01-23 14:24:02,766 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:02,777 INFO L225 Difference]: With dead ends: 1106 [2018-01-23 14:24:02,777 INFO L226 Difference]: Without dead ends: 937 [2018-01-23 14:24:02,784 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-23 14:24:02,785 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 937 states. [2018-01-23 14:24:02,865 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 937 to 363. [2018-01-23 14:24:02,866 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 363 states. [2018-01-23 14:24:02,869 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 363 states to 363 states and 511 transitions. [2018-01-23 14:24:02,869 INFO L78 Accepts]: Start accepts. Automaton has 363 states and 511 transitions. Word has length 47 [2018-01-23 14:24:02,870 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:02,870 INFO L432 AbstractCegarLoop]: Abstraction has 363 states and 511 transitions. [2018-01-23 14:24:02,870 INFO L433 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-01-23 14:24:02,870 INFO L276 IsEmpty]: Start isEmpty. Operand 363 states and 511 transitions. [2018-01-23 14:24:02,874 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2018-01-23 14:24:02,874 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:02,874 INFO L322 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:24:02,874 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr0EnsuresViolation]=== [2018-01-23 14:24:02,874 INFO L82 PathProgramCache]: Analyzing trace with hash -1650249222, now seen corresponding path program 1 times [2018-01-23 14:24:02,875 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:02,875 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:02,876 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:02,876 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:02,876 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:02,892 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:02,893 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:03,006 INFO L134 CoverageAnalysis]: Checked inductivity of 83 backedges. 22 proven. 16 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-01-23 14:24:03,006 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:24:03,006 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:24:03,020 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:03,102 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:03,108 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:24:03,150 INFO L134 CoverageAnalysis]: Checked inductivity of 83 backedges. 38 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-01-23 14:24:03,187 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-23 14:24:03,187 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 9 [2018-01-23 14:24:03,187 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-23 14:24:03,188 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-23 14:24:03,188 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-01-23 14:24:03,188 INFO L87 Difference]: Start difference. First operand 363 states and 511 transitions. Second operand 9 states. [2018-01-23 14:24:03,530 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:03,531 INFO L93 Difference]: Finished difference Result 801 states and 1160 transitions. [2018-01-23 14:24:03,531 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-23 14:24:03,531 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 73 [2018-01-23 14:24:03,531 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:03,534 INFO L225 Difference]: With dead ends: 801 [2018-01-23 14:24:03,534 INFO L226 Difference]: Without dead ends: 516 [2018-01-23 14:24:03,535 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 76 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=51, Invalid=131, Unknown=0, NotChecked=0, Total=182 [2018-01-23 14:24:03,536 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 516 states. [2018-01-23 14:24:03,565 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 516 to 476. [2018-01-23 14:24:03,565 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 476 states. [2018-01-23 14:24:03,569 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 476 states to 476 states and 678 transitions. [2018-01-23 14:24:03,569 INFO L78 Accepts]: Start accepts. Automaton has 476 states and 678 transitions. Word has length 73 [2018-01-23 14:24:03,569 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:03,570 INFO L432 AbstractCegarLoop]: Abstraction has 476 states and 678 transitions. [2018-01-23 14:24:03,570 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-23 14:24:03,570 INFO L276 IsEmpty]: Start isEmpty. Operand 476 states and 678 transitions. [2018-01-23 14:24:03,573 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2018-01-23 14:24:03,573 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:03,573 INFO L322 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:24:03,573 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr0EnsuresViolation]=== [2018-01-23 14:24:03,574 INFO L82 PathProgramCache]: Analyzing trace with hash -1980963244, now seen corresponding path program 1 times [2018-01-23 14:24:03,574 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:03,574 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:03,575 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:03,575 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:03,575 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:03,585 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:03,586 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:03,675 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 19 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-01-23 14:24:03,676 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:24:03,676 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-23 14:24:03,676 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-23 14:24:03,676 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-23 14:24:03,676 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2018-01-23 14:24:03,677 INFO L87 Difference]: Start difference. First operand 476 states and 678 transitions. Second operand 7 states. [2018-01-23 14:24:04,054 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:04,054 INFO L93 Difference]: Finished difference Result 1379 states and 2090 transitions. [2018-01-23 14:24:04,054 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-23 14:24:04,054 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 74 [2018-01-23 14:24:04,055 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:04,062 INFO L225 Difference]: With dead ends: 1379 [2018-01-23 14:24:04,063 INFO L226 Difference]: Without dead ends: 908 [2018-01-23 14:24:04,065 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=34, Invalid=76, Unknown=0, NotChecked=0, Total=110 [2018-01-23 14:24:04,066 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 908 states. [2018-01-23 14:24:04,168 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 908 to 748. [2018-01-23 14:24:04,168 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 748 states. [2018-01-23 14:24:04,176 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 748 states to 748 states and 1068 transitions. [2018-01-23 14:24:04,176 INFO L78 Accepts]: Start accepts. Automaton has 748 states and 1068 transitions. Word has length 74 [2018-01-23 14:24:04,177 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:04,177 INFO L432 AbstractCegarLoop]: Abstraction has 748 states and 1068 transitions. [2018-01-23 14:24:04,177 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-23 14:24:04,177 INFO L276 IsEmpty]: Start isEmpty. Operand 748 states and 1068 transitions. [2018-01-23 14:24:04,181 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2018-01-23 14:24:04,181 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:04,181 INFO L322 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 5, 5, 5, 5, 5, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:24:04,182 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr0EnsuresViolation]=== [2018-01-23 14:24:04,182 INFO L82 PathProgramCache]: Analyzing trace with hash 787103849, now seen corresponding path program 2 times [2018-01-23 14:24:04,182 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:04,182 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:04,183 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:04,183 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:04,183 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:04,201 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:04,202 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:04,364 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 40 proven. 73 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2018-01-23 14:24:04,364 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:24:04,364 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:24:04,372 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-23 14:24:04,413 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-23 14:24:04,444 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-23 14:24:04,449 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-23 14:24:04,454 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:24:04,557 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 79 proven. 3 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-01-23 14:24:04,592 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:24:04,592 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 17 [2018-01-23 14:24:04,592 INFO L409 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-01-23 14:24:04,593 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-01-23 14:24:04,593 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=239, Unknown=0, NotChecked=0, Total=272 [2018-01-23 14:24:04,593 INFO L87 Difference]: Start difference. First operand 748 states and 1068 transitions. Second operand 17 states. [2018-01-23 14:24:05,380 WARN L146 SmtUtils]: Spent 241ms on a formula simplification. DAG size of input: 35 DAG size of output 31 [2018-01-23 14:24:10,424 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:10,425 INFO L93 Difference]: Finished difference Result 5106 states and 8026 transitions. [2018-01-23 14:24:10,425 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 135 states. [2018-01-23 14:24:10,425 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 83 [2018-01-23 14:24:10,425 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:10,459 INFO L225 Difference]: With dead ends: 5106 [2018-01-23 14:24:10,459 INFO L226 Difference]: Without dead ends: 4555 [2018-01-23 14:24:10,472 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 316 GetRequests, 170 SyntacticMatches, 0 SemanticMatches, 146 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8914 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=2873, Invalid=18883, Unknown=0, NotChecked=0, Total=21756 [2018-01-23 14:24:10,475 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4555 states. [2018-01-23 14:24:10,790 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4555 to 3144. [2018-01-23 14:24:10,790 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3144 states. [2018-01-23 14:24:10,806 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3144 states to 3144 states and 4486 transitions. [2018-01-23 14:24:10,806 INFO L78 Accepts]: Start accepts. Automaton has 3144 states and 4486 transitions. Word has length 83 [2018-01-23 14:24:10,806 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:10,806 INFO L432 AbstractCegarLoop]: Abstraction has 3144 states and 4486 transitions. [2018-01-23 14:24:10,806 INFO L433 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-01-23 14:24:10,807 INFO L276 IsEmpty]: Start isEmpty. Operand 3144 states and 4486 transitions. [2018-01-23 14:24:10,814 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2018-01-23 14:24:10,814 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:10,815 INFO L322 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:24:10,815 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr0EnsuresViolation]=== [2018-01-23 14:24:10,815 INFO L82 PathProgramCache]: Analyzing trace with hash 1494721301, now seen corresponding path program 1 times [2018-01-23 14:24:10,815 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:10,815 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:10,816 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:10,816 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-23 14:24:10,816 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:10,828 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:10,829 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:10,901 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 25 proven. 5 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2018-01-23 14:24:10,901 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:24:10,901 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:24:10,910 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:10,986 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:10,993 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:24:11,075 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2018-01-23 14:24:11,103 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-23 14:24:11,103 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 9 [2018-01-23 14:24:11,103 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-23 14:24:11,103 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-23 14:24:11,104 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-01-23 14:24:11,104 INFO L87 Difference]: Start difference. First operand 3144 states and 4486 transitions. Second operand 9 states. [2018-01-23 14:24:11,683 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:11,683 INFO L93 Difference]: Finished difference Result 6836 states and 9969 transitions. [2018-01-23 14:24:11,683 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-23 14:24:11,683 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 86 [2018-01-23 14:24:11,683 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:11,708 INFO L225 Difference]: With dead ends: 6836 [2018-01-23 14:24:11,708 INFO L226 Difference]: Without dead ends: 3697 [2018-01-23 14:24:11,722 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 89 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=45, Invalid=111, Unknown=0, NotChecked=0, Total=156 [2018-01-23 14:24:11,724 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3697 states. [2018-01-23 14:24:12,003 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3697 to 3144. [2018-01-23 14:24:12,003 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3144 states. [2018-01-23 14:24:12,015 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3144 states to 3144 states and 4486 transitions. [2018-01-23 14:24:12,015 INFO L78 Accepts]: Start accepts. Automaton has 3144 states and 4486 transitions. Word has length 86 [2018-01-23 14:24:12,016 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:12,016 INFO L432 AbstractCegarLoop]: Abstraction has 3144 states and 4486 transitions. [2018-01-23 14:24:12,016 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-23 14:24:12,016 INFO L276 IsEmpty]: Start isEmpty. Operand 3144 states and 4486 transitions. [2018-01-23 14:24:12,024 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2018-01-23 14:24:12,024 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:12,024 INFO L322 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 5, 5, 5, 5, 5, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:24:12,025 INFO L371 AbstractCegarLoop]: === Iteration 11 === [mainErr0EnsuresViolation]=== [2018-01-23 14:24:12,025 INFO L82 PathProgramCache]: Analyzing trace with hash 1024435374, now seen corresponding path program 1 times [2018-01-23 14:24:12,025 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:12,025 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:12,026 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:12,026 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:12,026 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:12,037 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:12,039 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:12,189 INFO L134 CoverageAnalysis]: Checked inductivity of 132 backedges. 28 proven. 21 refuted. 0 times theorem prover too weak. 83 trivial. 0 not checked. [2018-01-23 14:24:12,189 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:24:12,189 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:24:12,202 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:12,278 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:12,289 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:24:12,336 INFO L134 CoverageAnalysis]: Checked inductivity of 132 backedges. 49 proven. 0 refuted. 0 times theorem prover too weak. 83 trivial. 0 not checked. [2018-01-23 14:24:12,369 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-23 14:24:12,369 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 9 [2018-01-23 14:24:12,370 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-23 14:24:12,370 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-23 14:24:12,370 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-01-23 14:24:12,370 INFO L87 Difference]: Start difference. First operand 3144 states and 4486 transitions. Second operand 9 states. [2018-01-23 14:24:12,698 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:12,698 INFO L93 Difference]: Finished difference Result 5258 states and 7573 transitions. [2018-01-23 14:24:12,699 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-23 14:24:12,699 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 87 [2018-01-23 14:24:12,699 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:12,714 INFO L225 Difference]: With dead ends: 5258 [2018-01-23 14:24:12,714 INFO L226 Difference]: Without dead ends: 3673 [2018-01-23 14:24:12,720 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 90 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=51, Invalid=131, Unknown=0, NotChecked=0, Total=182 [2018-01-23 14:24:12,722 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3673 states. [2018-01-23 14:24:12,932 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3673 to 3550. [2018-01-23 14:24:12,932 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3550 states. [2018-01-23 14:24:12,940 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3550 states to 3550 states and 5100 transitions. [2018-01-23 14:24:12,940 INFO L78 Accepts]: Start accepts. Automaton has 3550 states and 5100 transitions. Word has length 87 [2018-01-23 14:24:12,941 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:12,941 INFO L432 AbstractCegarLoop]: Abstraction has 3550 states and 5100 transitions. [2018-01-23 14:24:12,941 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-23 14:24:12,941 INFO L276 IsEmpty]: Start isEmpty. Operand 3550 states and 5100 transitions. [2018-01-23 14:24:12,947 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2018-01-23 14:24:12,947 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:12,947 INFO L322 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:24:12,948 INFO L371 AbstractCegarLoop]: === Iteration 12 === [mainErr0EnsuresViolation]=== [2018-01-23 14:24:12,948 INFO L82 PathProgramCache]: Analyzing trace with hash 160797049, now seen corresponding path program 1 times [2018-01-23 14:24:12,948 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:12,948 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:12,949 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:12,949 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:12,949 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:12,960 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:12,961 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:13,190 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 25 proven. 4 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2018-01-23 14:24:13,191 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:24:13,191 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:24:13,196 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:13,263 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:13,268 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:24:13,402 WARN L1029 $PredicateComparison]: unable to prove that (exists ((|push_#t~malloc2.base| Int)) (and (<= (select |c_old(#valid)| |push_#t~malloc2.base|) 0) (= |c_#valid| (store |c_old(#valid)| |push_#t~malloc2.base| 1)))) is different from true [2018-01-23 14:24:13,418 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 28 proven. 0 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2018-01-23 14:24:13,441 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-23 14:24:13,441 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [8] total 10 [2018-01-23 14:24:13,441 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-01-23 14:24:13,442 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-01-23 14:24:13,442 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=54, Unknown=1, NotChecked=14, Total=90 [2018-01-23 14:24:13,442 INFO L87 Difference]: Start difference. First operand 3550 states and 5100 transitions. Second operand 10 states. [2018-01-23 14:24:14,148 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:14,149 INFO L93 Difference]: Finished difference Result 8706 states and 13158 transitions. [2018-01-23 14:24:14,149 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-01-23 14:24:14,149 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 88 [2018-01-23 14:24:14,149 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:14,205 INFO L225 Difference]: With dead ends: 8706 [2018-01-23 14:24:14,205 INFO L226 Difference]: Without dead ends: 4831 [2018-01-23 14:24:14,222 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-23 14:24:14,225 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4831 states. [2018-01-23 14:24:14,691 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4831 to 4394. [2018-01-23 14:24:14,691 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4394 states. [2018-01-23 14:24:14,705 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4394 states to 4394 states and 6385 transitions. [2018-01-23 14:24:14,706 INFO L78 Accepts]: Start accepts. Automaton has 4394 states and 6385 transitions. Word has length 88 [2018-01-23 14:24:14,706 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:14,706 INFO L432 AbstractCegarLoop]: Abstraction has 4394 states and 6385 transitions. [2018-01-23 14:24:14,707 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-01-23 14:24:14,707 INFO L276 IsEmpty]: Start isEmpty. Operand 4394 states and 6385 transitions. [2018-01-23 14:24:14,717 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2018-01-23 14:24:14,718 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:14,718 INFO L322 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:24:14,718 INFO L371 AbstractCegarLoop]: === Iteration 13 === [mainErr0EnsuresViolation]=== [2018-01-23 14:24:14,718 INFO L82 PathProgramCache]: Analyzing trace with hash -2024113882, now seen corresponding path program 1 times [2018-01-23 14:24:14,718 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:14,718 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:14,719 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:14,719 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:14,719 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:14,742 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:14,744 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:14,935 INFO L134 CoverageAnalysis]: Checked inductivity of 97 backedges. 38 proven. 41 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2018-01-23 14:24:14,935 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:24:14,935 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:24:14,940 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:15,014 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:15,019 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:24:15,112 INFO L134 CoverageAnalysis]: Checked inductivity of 97 backedges. 48 proven. 3 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2018-01-23 14:24:15,146 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:24:15,146 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 6] total 15 [2018-01-23 14:24:15,146 INFO L409 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-01-23 14:24:15,147 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-01-23 14:24:15,147 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=182, Unknown=0, NotChecked=0, Total=210 [2018-01-23 14:24:15,147 INFO L87 Difference]: Start difference. First operand 4394 states and 6385 transitions. Second operand 15 states. [2018-01-23 14:24:18,010 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:18,011 INFO L93 Difference]: Finished difference Result 16377 states and 25815 transitions. [2018-01-23 14:24:18,011 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 58 states. [2018-01-23 14:24:18,011 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 90 [2018-01-23 14:24:18,011 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:18,081 INFO L225 Difference]: With dead ends: 16377 [2018-01-23 14:24:18,081 INFO L226 Difference]: Without dead ends: 12378 [2018-01-23 14:24:18,109 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-23 14:24:18,118 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 12378 states. [2018-01-23 14:24:18,974 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 12378 to 10054. [2018-01-23 14:24:18,975 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 10054 states. [2018-01-23 14:24:19,002 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10054 states to 10054 states and 14764 transitions. [2018-01-23 14:24:19,002 INFO L78 Accepts]: Start accepts. Automaton has 10054 states and 14764 transitions. Word has length 90 [2018-01-23 14:24:19,003 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:19,003 INFO L432 AbstractCegarLoop]: Abstraction has 10054 states and 14764 transitions. [2018-01-23 14:24:19,003 INFO L433 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-01-23 14:24:19,003 INFO L276 IsEmpty]: Start isEmpty. Operand 10054 states and 14764 transitions. [2018-01-23 14:24:19,014 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2018-01-23 14:24:19,014 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:19,014 INFO L322 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 5, 5, 5, 5, 5, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:24:19,014 INFO L371 AbstractCegarLoop]: === Iteration 14 === [mainErr0EnsuresViolation]=== [2018-01-23 14:24:19,015 INFO L82 PathProgramCache]: Analyzing trace with hash 507171894, now seen corresponding path program 1 times [2018-01-23 14:24:19,015 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:19,015 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:19,016 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:19,016 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:19,016 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:19,033 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:19,034 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:19,147 INFO L134 CoverageAnalysis]: Checked inductivity of 138 backedges. 71 proven. 22 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-01-23 14:24:19,147 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:24:19,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-23 14:24:19,154 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:19,249 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:19,254 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:24:19,338 INFO L134 CoverageAnalysis]: Checked inductivity of 138 backedges. 79 proven. 12 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2018-01-23 14:24:19,358 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:24:19,358 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 16 [2018-01-23 14:24:19,359 INFO L409 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-01-23 14:24:19,359 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-01-23 14:24:19,359 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=203, Unknown=0, NotChecked=0, Total=240 [2018-01-23 14:24:19,359 INFO L87 Difference]: Start difference. First operand 10054 states and 14764 transitions. Second operand 16 states. [2018-01-23 14:24:21,661 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:21,661 INFO L93 Difference]: Finished difference Result 34479 states and 56881 transitions. [2018-01-23 14:24:21,661 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-01-23 14:24:21,661 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 90 [2018-01-23 14:24:21,662 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:21,833 INFO L225 Difference]: With dead ends: 34479 [2018-01-23 14:24:21,833 INFO L226 Difference]: Without dead ends: 24430 [2018-01-23 14:24:21,867 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-23 14:24:21,882 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24430 states. [2018-01-23 14:24:22,952 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24430 to 14850. [2018-01-23 14:24:22,952 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 14850 states. [2018-01-23 14:24:22,977 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14850 states to 14850 states and 21251 transitions. [2018-01-23 14:24:22,977 INFO L78 Accepts]: Start accepts. Automaton has 14850 states and 21251 transitions. Word has length 90 [2018-01-23 14:24:22,978 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:22,978 INFO L432 AbstractCegarLoop]: Abstraction has 14850 states and 21251 transitions. [2018-01-23 14:24:22,978 INFO L433 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-01-23 14:24:22,978 INFO L276 IsEmpty]: Start isEmpty. Operand 14850 states and 21251 transitions. [2018-01-23 14:24:22,985 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2018-01-23 14:24:22,985 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:22,985 INFO L322 BasicCegarLoop]: trace histogram [7, 7, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:24:22,985 INFO L371 AbstractCegarLoop]: === Iteration 15 === [mainErr0EnsuresViolation]=== [2018-01-23 14:24:22,985 INFO L82 PathProgramCache]: Analyzing trace with hash 671709488, now seen corresponding path program 1 times [2018-01-23 14:24:22,985 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:22,985 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:22,986 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:22,986 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:22,986 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:22,997 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:22,998 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:23,174 INFO L134 CoverageAnalysis]: Checked inductivity of 146 backedges. 57 proven. 31 refuted. 0 times theorem prover too weak. 58 trivial. 0 not checked. [2018-01-23 14:24:23,174 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:24:23,174 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:24:23,179 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:23,237 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:23,240 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:24:23,262 INFO L134 CoverageAnalysis]: Checked inductivity of 146 backedges. 64 proven. 3 refuted. 0 times theorem prover too weak. 79 trivial. 0 not checked. [2018-01-23 14:24:23,282 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:24:23,282 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 4] total 10 [2018-01-23 14:24:23,282 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-01-23 14:24:23,282 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-01-23 14:24:23,283 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=73, Unknown=0, NotChecked=0, Total=90 [2018-01-23 14:24:23,283 INFO L87 Difference]: Start difference. First operand 14850 states and 21251 transitions. Second operand 10 states. [2018-01-23 14:24:27,930 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:24:27,930 INFO L93 Difference]: Finished difference Result 90309 states and 131452 transitions. [2018-01-23 14:24:27,930 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-01-23 14:24:27,931 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 107 [2018-01-23 14:24:27,931 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:24:28,134 INFO L225 Difference]: With dead ends: 90309 [2018-01-23 14:24:28,134 INFO L226 Difference]: Without dead ends: 75464 [2018-01-23 14:24:28,204 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 161 GetRequests, 126 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 280 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=272, Invalid=1060, Unknown=0, NotChecked=0, Total=1332 [2018-01-23 14:24:28,241 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 75464 states. [2018-01-23 14:24:32,779 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 75464 to 71706. [2018-01-23 14:24:32,779 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 71706 states. [2018-01-23 14:24:32,940 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71706 states to 71706 states and 103461 transitions. [2018-01-23 14:24:32,940 INFO L78 Accepts]: Start accepts. Automaton has 71706 states and 103461 transitions. Word has length 107 [2018-01-23 14:24:32,941 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:24:32,941 INFO L432 AbstractCegarLoop]: Abstraction has 71706 states and 103461 transitions. [2018-01-23 14:24:32,941 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-01-23 14:24:32,941 INFO L276 IsEmpty]: Start isEmpty. Operand 71706 states and 103461 transitions. [2018-01-23 14:24:32,951 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2018-01-23 14:24:32,951 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:24:32,952 INFO L322 BasicCegarLoop]: trace histogram [7, 7, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:24:32,952 INFO L371 AbstractCegarLoop]: === Iteration 16 === [mainErr0EnsuresViolation]=== [2018-01-23 14:24:32,952 INFO L82 PathProgramCache]: Analyzing trace with hash -1515124594, now seen corresponding path program 1 times [2018-01-23 14:24:32,952 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:24:32,952 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:24:32,953 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:32,953 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:32,953 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:24:32,971 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:32,972 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:24:33,439 INFO L134 CoverageAnalysis]: Checked inductivity of 146 backedges. 2 proven. 117 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2018-01-23 14:24:33,439 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:24:33,439 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:24:33,446 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:24:33,513 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:24:33,517 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:24:33,658 INFO L134 CoverageAnalysis]: Checked inductivity of 146 backedges. 67 proven. 13 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2018-01-23 14:24:33,680 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:24:33,680 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9] total 19 [2018-01-23 14:24:33,681 INFO L409 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-01-23 14:24:33,681 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-01-23 14:24:33,681 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=304, Unknown=0, NotChecked=0, Total=342 [2018-01-23 14:24:33,681 INFO L87 Difference]: Start difference. First operand 71706 states and 103461 transitions. Second operand 19 states. [2018-01-23 14:24:36,768 WARN L143 SmtUtils]: Spent 154ms on a formula simplification that was a NOOP. DAG size: 31 Received shutdown request... [2018-01-23 14:24:41,607 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 140 states. [2018-01-23 14:24:41,608 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-23 14:24:41,610 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-23 14:24:41,610 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-23 14:24:41,610 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-23 14:24:41,610 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-23 14:24:41,610 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-23 14:24:41,610 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-23 14:24:41,610 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-23 14:24:41,610 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == pushErr0EnsuresViolation======== [2018-01-23 14:24:41,610 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-23 14:24:41,611 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states. [2018-01-23 14:24:41,612 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-23 14:24:41,613 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 23.01 02:24:41 BoogieIcfgContainer [2018-01-23 14:24:41,613 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-23 14:24:41,614 INFO L168 Benchmark]: Toolchain (without parser) took 44787.46 ms. Allocated memory was 305.1 MB in the beginning and 2.1 GB in the end (delta: 1.8 GB). Free memory was 261.9 MB in the beginning and 1.6 GB in the end (delta: -1.3 GB). Peak memory consumption was 492.5 MB. Max. memory is 5.3 GB. [2018-01-23 14:24:41,616 INFO L168 Benchmark]: CDTParser took 0.15 ms. Allocated memory is still 305.1 MB. Free memory is still 267.9 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-23 14:24:41,616 INFO L168 Benchmark]: CACSL2BoogieTranslator took 215.58 ms. Allocated memory is still 305.1 MB. Free memory was 261.9 MB in the beginning and 250.0 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 5.3 GB. [2018-01-23 14:24:41,616 INFO L168 Benchmark]: Boogie Preprocessor took 34.13 ms. Allocated memory is still 305.1 MB. Free memory was 250.0 MB in the beginning and 248.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-01-23 14:24:41,617 INFO L168 Benchmark]: RCFGBuilder took 366.19 ms. Allocated memory is still 305.1 MB. Free memory was 248.0 MB in the beginning and 225.0 MB in the end (delta: 23.0 MB). Peak memory consumption was 23.0 MB. Max. memory is 5.3 GB. [2018-01-23 14:24:41,617 INFO L168 Benchmark]: TraceAbstraction took 44164.48 ms. Allocated memory was 305.1 MB in the beginning and 2.1 GB in the end (delta: 1.8 GB). Free memory was 225.0 MB in the beginning and 1.6 GB in the end (delta: -1.3 GB). Peak memory consumption was 455.6 MB. Max. memory is 5.3 GB. [2018-01-23 14:24:41,619 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.15 ms. Allocated memory is still 305.1 MB. Free memory is still 267.9 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 215.58 ms. Allocated memory is still 305.1 MB. Free memory was 261.9 MB in the beginning and 250.0 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 34.13 ms. Allocated memory is still 305.1 MB. Free memory was 250.0 MB in the beginning and 248.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 366.19 ms. Allocated memory is still 305.1 MB. Free memory was 248.0 MB in the beginning and 225.0 MB in the end (delta: 23.0 MB). Peak memory consumption was 23.0 MB. Max. memory is 5.3 GB. * TraceAbstraction took 44164.48 ms. Allocated memory was 305.1 MB in the beginning and 2.1 GB in the end (delta: 1.8 GB). Free memory was 225.0 MB in the beginning and 1.6 GB in the end (delta: -1.3 GB). Peak memory consumption was 455.6 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)=17, \old(garbage)=15, \old(pc1)=7, \old(pc4)=11, \old(res4)=5, \old(S)=9, \old(S)=3, \old(t1)=12, \old(t1)=8, \old(t4)=16, \old(t4)=4, \old(x1)=14, \old(x1)=1, \old(x4)=6, \old(x4)=13, 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 140 states, 19 states before enhancement), while PredicateComparison was comparing new predicate (quantifier-free) to 157 known predicates. - StatisticsResult: Ultimate Automizer benchmark data for error location: mainErr0EnsuresViolation CFG has 5 procedures, 62 locations, 5 error locations. TIMEOUT Result, 43.3s OverallTime, 16 OverallIterations, 7 TraceHistogramMax, 30.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 1336 SDtfs, 10508 SDslu, 4576 SDs, 0 SdLazy, 9360 SolverSat, 3869 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 7.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1661 GetRequests, 1056 SyntacticMatches, 3 SemanticMatches, 601 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 24482 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.3s AutomataMinimizationTime, 15 MinimizatonAttempts, 18993 StatesRemovedByMinimization, 13 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 0.7s SatisfiabilityAnalysisTime, 3.1s 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-23_14-24-41-630.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-23_14-24-41-630.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-23_14-24-41-630.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-23_14-24-41-630.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-23_14-24-41-630.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-23_14-24-41-630.csv Completed graceful shutdown