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/svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ_smtcomp.epf -i ../../../trunk/examples/svcomp/array-memsafety/openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-6b94a2f [2018-01-25 05:28:43,435 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-25 05:28:43,447 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-25 05:28:43,462 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-25 05:28:43,462 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-25 05:28:43,463 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-25 05:28:43,464 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-25 05:28:43,466 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-25 05:28:43,468 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-25 05:28:43,469 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-25 05:28:43,470 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-25 05:28:43,470 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-25 05:28:43,471 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-25 05:28:43,472 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-25 05:28:43,473 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-25 05:28:43,475 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-25 05:28:43,478 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-25 05:28:43,480 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-25 05:28:43,481 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-25 05:28:43,482 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-25 05:28:43,485 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-25 05:28:43,485 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-25 05:28:43,485 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-25 05:28:43,486 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-25 05:28:43,487 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-25 05:28:43,488 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-25 05:28:43,489 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-25 05:28:43,489 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-25 05:28:43,489 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-25 05:28:43,490 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-25 05:28:43,490 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-25 05:28:43,491 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/ai/eq-bench/svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ_smtcomp.epf [2018-01-25 05:28:43,500 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-25 05:28:43,500 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-25 05:28:43,500 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-25 05:28:43,501 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-25 05:28:43,501 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-25 05:28:43,501 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-25 05:28:43,501 INFO L133 SettingsManager]: * Precise comparison operator=true [2018-01-25 05:28:43,501 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-25 05:28:43,501 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-25 05:28:43,502 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-25 05:28:43,502 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-25 05:28:43,502 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-25 05:28:43,502 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-25 05:28:43,502 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-25 05:28:43,502 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-01-25 05:28:43,502 INFO L133 SettingsManager]: * Bitprecise bitfields=true [2018-01-25 05:28:43,502 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-01-25 05:28:43,503 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-25 05:28:43,503 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-25 05:28:43,503 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-25 05:28:43,503 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-01-25 05:28:43,503 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-25 05:28:43,503 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-25 05:28:43,504 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-25 05:28:43,504 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-25 05:28:43,504 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-25 05:28:43,504 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-25 05:28:43,504 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-25 05:28:43,504 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-25 05:28:43,505 INFO L133 SettingsManager]: * Trace refinement strategy=TAIPAN [2018-01-25 05:28:43,505 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-25 05:28:43,505 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-25 05:28:43,505 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-25 05:28:43,505 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-01-25 05:28:43,506 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-25 05:28:43,506 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-25 05:28:43,538 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-25 05:28:43,548 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-25 05:28:43,552 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-25 05:28:43,553 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-25 05:28:43,553 INFO L276 PluginConnector]: CDTParser initialized [2018-01-25 05:28:43,554 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/array-memsafety/openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i [2018-01-25 05:28:43,704 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-25 05:28:43,710 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-25 05:28:43,710 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-25 05:28:43,710 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-25 05:28:43,716 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-25 05:28:43,717 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 25.01 05:28:43" (1/1) ... [2018-01-25 05:28:43,720 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4545185a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:28:43, skipping insertion in model container [2018-01-25 05:28:43,720 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 25.01 05:28:43" (1/1) ... [2018-01-25 05:28:43,733 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-25 05:28:43,770 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-25 05:28:43,892 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-25 05:28:43,909 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-25 05:28:43,916 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:28:43 WrapperNode [2018-01-25 05:28:43,916 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-25 05:28:43,917 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-25 05:28:43,917 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-25 05:28:43,917 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-25 05:28:43,932 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:28:43" (1/1) ... [2018-01-25 05:28:43,932 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:28:43" (1/1) ... [2018-01-25 05:28:43,940 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:28:43" (1/1) ... [2018-01-25 05:28:43,940 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:28:43" (1/1) ... [2018-01-25 05:28:43,944 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:28:43" (1/1) ... [2018-01-25 05:28:43,947 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:28:43" (1/1) ... [2018-01-25 05:28:43,948 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:28:43" (1/1) ... [2018-01-25 05:28:43,949 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-25 05:28:43,950 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-25 05:28:43,950 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-25 05:28:43,950 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-25 05:28:43,951 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:28:43" (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-25 05:28:43,999 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-25 05:28:44,000 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-25 05:28:44,000 INFO L136 BoogieDeclarations]: Found implementation of procedure cstrncat [2018-01-25 05:28:44,000 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-25 05:28:44,000 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-01-25 05:28:44,000 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-01-25 05:28:44,000 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-25 05:28:44,000 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-25 05:28:44,000 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-25 05:28:44,000 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-25 05:28:44,001 INFO L128 BoogieDeclarations]: Found specification of procedure cstrncat [2018-01-25 05:28:44,001 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-25 05:28:44,001 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-25 05:28:44,001 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-25 05:28:44,226 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-25 05:28:44,227 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.01 05:28:44 BoogieIcfgContainer [2018-01-25 05:28:44,227 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-25 05:28:44,228 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-25 05:28:44,228 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-25 05:28:44,230 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-25 05:28:44,231 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 25.01 05:28:43" (1/3) ... [2018-01-25 05:28:44,232 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6c81112f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.01 05:28:44, skipping insertion in model container [2018-01-25 05:28:44,232 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:28:43" (2/3) ... [2018-01-25 05:28:44,232 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6c81112f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.01 05:28:44, skipping insertion in model container [2018-01-25 05:28:44,232 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.01 05:28:44" (3/3) ... [2018-01-25 05:28:44,233 INFO L105 eAbstractionObserver]: Analyzing ICFG openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i [2018-01-25 05:28:44,241 INFO L130 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-25 05:28:44,247 INFO L142 ceAbstractionStarter]: Appying trace abstraction to program that has 13 error locations. [2018-01-25 05:28:44,293 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-25 05:28:44,294 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-25 05:28:44,294 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-25 05:28:44,294 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-25 05:28:44,294 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-25 05:28:44,294 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-25 05:28:44,294 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-25 05:28:44,295 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-01-25 05:28:44,295 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-25 05:28:44,316 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states. [2018-01-25 05:28:44,323 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-01-25 05:28:44,323 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:28:44,324 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:28:44,324 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:28:44,329 INFO L82 PathProgramCache]: Analyzing trace with hash 2055638365, now seen corresponding path program 1 times [2018-01-25 05:28:44,332 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:28:44,378 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:44,378 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:28:44,378 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:44,378 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:28:44,426 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:28:44,433 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:28:44,497 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-25 05:28:44,499 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-25 05:28:44,500 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-25 05:28:44,500 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-25 05:28:44,503 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-25 05:28:44,517 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-25 05:28:44,518 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-25 05:28:44,520 INFO L87 Difference]: Start difference. First operand 54 states. Second operand 3 states. [2018-01-25 05:28:44,714 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:28:44,714 INFO L93 Difference]: Finished difference Result 81 states and 93 transitions. [2018-01-25 05:28:44,715 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-25 05:28:44,717 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 11 [2018-01-25 05:28:44,717 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:28:44,728 INFO L225 Difference]: With dead ends: 81 [2018-01-25 05:28:44,728 INFO L226 Difference]: Without dead ends: 51 [2018-01-25 05:28:44,732 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-25 05:28:44,747 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2018-01-25 05:28:44,760 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2018-01-25 05:28:44,761 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-01-25 05:28:44,763 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 57 transitions. [2018-01-25 05:28:44,764 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 57 transitions. Word has length 11 [2018-01-25 05:28:44,764 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:28:44,764 INFO L432 AbstractCegarLoop]: Abstraction has 51 states and 57 transitions. [2018-01-25 05:28:44,764 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-25 05:28:44,764 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 57 transitions. [2018-01-25 05:28:44,765 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-25 05:28:44,765 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:28:44,765 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:28:44,765 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:28:44,765 INFO L82 PathProgramCache]: Analyzing trace with hash -1872133330, now seen corresponding path program 1 times [2018-01-25 05:28:44,765 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:28:44,766 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:44,766 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:28:44,766 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:44,766 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:28:44,780 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:28:44,781 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:28:44,844 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-25 05:28:44,845 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-25 05:28:44,845 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-25 05:28:44,845 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-25 05:28:44,847 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-25 05:28:44,847 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-25 05:28:44,847 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-25 05:28:44,847 INFO L87 Difference]: Start difference. First operand 51 states and 57 transitions. Second operand 5 states. [2018-01-25 05:28:44,944 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:28:44,945 INFO L93 Difference]: Finished difference Result 95 states and 106 transitions. [2018-01-25 05:28:44,945 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-25 05:28:44,945 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 15 [2018-01-25 05:28:44,946 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:28:44,947 INFO L225 Difference]: With dead ends: 95 [2018-01-25 05:28:44,947 INFO L226 Difference]: Without dead ends: 51 [2018-01-25 05:28:44,948 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2018-01-25 05:28:44,948 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2018-01-25 05:28:44,953 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2018-01-25 05:28:44,954 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-01-25 05:28:44,955 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 56 transitions. [2018-01-25 05:28:44,956 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 56 transitions. Word has length 15 [2018-01-25 05:28:44,956 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:28:44,956 INFO L432 AbstractCegarLoop]: Abstraction has 51 states and 56 transitions. [2018-01-25 05:28:44,956 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-25 05:28:44,956 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 56 transitions. [2018-01-25 05:28:44,957 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-25 05:28:44,957 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:28:44,957 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:28:44,957 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:28:44,958 INFO L82 PathProgramCache]: Analyzing trace with hash -1192074960, now seen corresponding path program 1 times [2018-01-25 05:28:44,958 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:28:44,959 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:44,959 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:28:44,959 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:44,959 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:28:44,978 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:28:44,979 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:28:45,043 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-25 05:28:45,043 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-25 05:28:45,044 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-25 05:28:45,044 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-25 05:28:45,044 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-25 05:28:45,044 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-25 05:28:45,045 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-25 05:28:45,045 INFO L87 Difference]: Start difference. First operand 51 states and 56 transitions. Second operand 4 states. [2018-01-25 05:28:45,112 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:28:45,112 INFO L93 Difference]: Finished difference Result 51 states and 56 transitions. [2018-01-25 05:28:45,112 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-25 05:28:45,112 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 15 [2018-01-25 05:28:45,113 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:28:45,113 INFO L225 Difference]: With dead ends: 51 [2018-01-25 05:28:45,114 INFO L226 Difference]: Without dead ends: 50 [2018-01-25 05:28:45,114 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 1 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-25 05:28:45,114 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2018-01-25 05:28:45,119 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2018-01-25 05:28:45,119 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 50 states. [2018-01-25 05:28:45,120 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 55 transitions. [2018-01-25 05:28:45,121 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 55 transitions. Word has length 15 [2018-01-25 05:28:45,121 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:28:45,121 INFO L432 AbstractCegarLoop]: Abstraction has 50 states and 55 transitions. [2018-01-25 05:28:45,121 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-25 05:28:45,121 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 55 transitions. [2018-01-25 05:28:45,122 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-25 05:28:45,122 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:28:45,122 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:28:45,122 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:28:45,122 INFO L82 PathProgramCache]: Analyzing trace with hash -1192074959, now seen corresponding path program 1 times [2018-01-25 05:28:45,123 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:28:45,124 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:45,124 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:28:45,124 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:45,124 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:28:45,139 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:28:45,140 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:28:45,347 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-25 05:28:45,347 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-25 05:28:45,347 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-25 05:28:45,347 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-25 05:28:45,347 INFO L409 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-01-25 05:28:45,348 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-01-25 05:28:45,348 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-01-25 05:28:45,348 INFO L87 Difference]: Start difference. First operand 50 states and 55 transitions. Second operand 8 states. [2018-01-25 05:28:45,449 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:28:45,450 INFO L93 Difference]: Finished difference Result 50 states and 55 transitions. [2018-01-25 05:28:45,450 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-01-25 05:28:45,450 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 15 [2018-01-25 05:28:45,450 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:28:45,451 INFO L225 Difference]: With dead ends: 50 [2018-01-25 05:28:45,451 INFO L226 Difference]: Without dead ends: 49 [2018-01-25 05:28:45,452 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=48, Invalid=84, Unknown=0, NotChecked=0, Total=132 [2018-01-25 05:28:45,452 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2018-01-25 05:28:45,457 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 49. [2018-01-25 05:28:45,458 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 49 states. [2018-01-25 05:28:45,459 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 54 transitions. [2018-01-25 05:28:45,460 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 54 transitions. Word has length 15 [2018-01-25 05:28:45,460 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:28:45,460 INFO L432 AbstractCegarLoop]: Abstraction has 49 states and 54 transitions. [2018-01-25 05:28:45,460 INFO L433 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-01-25 05:28:45,460 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 54 transitions. [2018-01-25 05:28:45,461 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-01-25 05:28:45,461 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:28:45,461 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:28:45,461 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:28:45,461 INFO L82 PathProgramCache]: Analyzing trace with hash 1700381909, now seen corresponding path program 1 times [2018-01-25 05:28:45,461 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:28:45,462 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:45,462 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:28:45,462 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:45,462 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:28:45,475 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:28:45,475 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:28:45,510 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-25 05:28:45,510 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-25 05:28:45,510 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-25 05:28:45,510 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-25 05:28:45,511 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-25 05:28:45,511 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-25 05:28:45,511 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-25 05:28:45,511 INFO L87 Difference]: Start difference. First operand 49 states and 54 transitions. Second operand 4 states. [2018-01-25 05:28:45,554 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:28:45,554 INFO L93 Difference]: Finished difference Result 49 states and 54 transitions. [2018-01-25 05:28:45,555 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-25 05:28:45,555 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 16 [2018-01-25 05:28:45,555 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:28:45,555 INFO L225 Difference]: With dead ends: 49 [2018-01-25 05:28:45,556 INFO L226 Difference]: Without dead ends: 48 [2018-01-25 05:28:45,556 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 1 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-25 05:28:45,556 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2018-01-25 05:28:45,560 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2018-01-25 05:28:45,560 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 48 states. [2018-01-25 05:28:45,561 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 53 transitions. [2018-01-25 05:28:45,561 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 53 transitions. Word has length 16 [2018-01-25 05:28:45,561 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:28:45,562 INFO L432 AbstractCegarLoop]: Abstraction has 48 states and 53 transitions. [2018-01-25 05:28:45,562 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-25 05:28:45,562 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 53 transitions. [2018-01-25 05:28:45,562 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-01-25 05:28:45,563 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:28:45,563 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:28:45,563 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:28:45,563 INFO L82 PathProgramCache]: Analyzing trace with hash 1700381910, now seen corresponding path program 1 times [2018-01-25 05:28:45,563 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:28:45,564 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:45,564 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:28:45,565 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:45,565 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:28:45,576 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:28:45,577 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:28:45,645 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-25 05:28:45,646 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-25 05:28:45,646 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-25 05:28:45,646 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-25 05:28:45,646 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-25 05:28:45,646 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-25 05:28:45,646 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-25 05:28:45,647 INFO L87 Difference]: Start difference. First operand 48 states and 53 transitions. Second operand 5 states. [2018-01-25 05:28:45,675 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:28:45,675 INFO L93 Difference]: Finished difference Result 48 states and 53 transitions. [2018-01-25 05:28:45,676 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-25 05:28:45,676 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 16 [2018-01-25 05:28:45,676 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:28:45,677 INFO L225 Difference]: With dead ends: 48 [2018-01-25 05:28:45,677 INFO L226 Difference]: Without dead ends: 47 [2018-01-25 05:28:45,677 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-01-25 05:28:45,677 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-01-25 05:28:45,680 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2018-01-25 05:28:45,681 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 47 states. [2018-01-25 05:28:45,681 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 52 transitions. [2018-01-25 05:28:45,681 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 52 transitions. Word has length 16 [2018-01-25 05:28:45,681 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:28:45,681 INFO L432 AbstractCegarLoop]: Abstraction has 47 states and 52 transitions. [2018-01-25 05:28:45,682 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-25 05:28:45,682 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 52 transitions. [2018-01-25 05:28:45,682 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2018-01-25 05:28:45,682 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:28:45,682 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:28:45,682 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:28:45,682 INFO L82 PathProgramCache]: Analyzing trace with hash -275307336, now seen corresponding path program 1 times [2018-01-25 05:28:45,683 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:28:45,683 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:45,683 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:28:45,683 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:45,683 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:28:45,697 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:28:45,698 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:28:45,738 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-25 05:28:45,739 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-25 05:28:45,739 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-25 05:28:45,739 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-25 05:28:45,739 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-25 05:28:45,739 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-25 05:28:45,739 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-25 05:28:45,739 INFO L87 Difference]: Start difference. First operand 47 states and 52 transitions. Second operand 6 states. [2018-01-25 05:28:45,811 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:28:45,811 INFO L93 Difference]: Finished difference Result 50 states and 55 transitions. [2018-01-25 05:28:45,816 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-25 05:28:45,816 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 21 [2018-01-25 05:28:45,817 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:28:45,819 INFO L225 Difference]: With dead ends: 50 [2018-01-25 05:28:45,819 INFO L226 Difference]: Without dead ends: 47 [2018-01-25 05:28:45,819 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-01-25 05:28:45,820 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-01-25 05:28:45,824 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 44. [2018-01-25 05:28:45,825 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 44 states. [2018-01-25 05:28:45,825 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 49 transitions. [2018-01-25 05:28:45,826 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 49 transitions. Word has length 21 [2018-01-25 05:28:45,826 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:28:45,826 INFO L432 AbstractCegarLoop]: Abstraction has 44 states and 49 transitions. [2018-01-25 05:28:45,826 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-25 05:28:45,826 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 49 transitions. [2018-01-25 05:28:45,827 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2018-01-25 05:28:45,827 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:28:45,827 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:28:45,827 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:28:45,828 INFO L82 PathProgramCache]: Analyzing trace with hash -275307335, now seen corresponding path program 1 times [2018-01-25 05:28:45,828 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:28:45,829 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:45,829 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:28:45,829 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:45,829 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:28:45,841 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:28:45,849 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:28:45,993 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-25 05:28:45,994 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-25 05:28:45,994 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2018-01-25 05:28:45,994 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-25 05:28:45,994 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-01-25 05:28:45,994 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-01-25 05:28:45,995 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2018-01-25 05:28:45,995 INFO L87 Difference]: Start difference. First operand 44 states and 49 transitions. Second operand 10 states. [2018-01-25 05:28:46,154 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:28:46,155 INFO L93 Difference]: Finished difference Result 60 states and 67 transitions. [2018-01-25 05:28:46,155 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-01-25 05:28:46,155 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 21 [2018-01-25 05:28:46,155 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:28:46,156 INFO L225 Difference]: With dead ends: 60 [2018-01-25 05:28:46,156 INFO L226 Difference]: Without dead ends: 57 [2018-01-25 05:28:46,157 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2018-01-25 05:28:46,157 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2018-01-25 05:28:46,162 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 52. [2018-01-25 05:28:46,162 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 52 states. [2018-01-25 05:28:46,163 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 61 transitions. [2018-01-25 05:28:46,163 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 61 transitions. Word has length 21 [2018-01-25 05:28:46,163 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:28:46,164 INFO L432 AbstractCegarLoop]: Abstraction has 52 states and 61 transitions. [2018-01-25 05:28:46,164 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-01-25 05:28:46,164 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 61 transitions. [2018-01-25 05:28:46,165 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-01-25 05:28:46,165 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:28:46,165 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:28:46,165 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:28:46,166 INFO L82 PathProgramCache]: Analyzing trace with hash 1706718631, now seen corresponding path program 1 times [2018-01-25 05:28:46,166 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:28:46,167 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:46,167 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:28:46,167 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:46,167 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:28:46,178 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:28:46,179 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:28:46,281 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-25 05:28:46,281 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-25 05:28:46,281 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-01-25 05:28:46,281 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-25 05:28:46,282 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-25 05:28:46,282 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-25 05:28:46,282 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-01-25 05:28:46,283 INFO L87 Difference]: Start difference. First operand 52 states and 61 transitions. Second operand 7 states. [2018-01-25 05:28:46,377 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:28:46,377 INFO L93 Difference]: Finished difference Result 55 states and 64 transitions. [2018-01-25 05:28:46,378 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-01-25 05:28:46,378 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 24 [2018-01-25 05:28:46,378 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:28:46,379 INFO L225 Difference]: With dead ends: 55 [2018-01-25 05:28:46,379 INFO L226 Difference]: Without dead ends: 54 [2018-01-25 05:28:46,380 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=29, Invalid=61, Unknown=0, NotChecked=0, Total=90 [2018-01-25 05:28:46,380 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2018-01-25 05:28:46,384 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 51. [2018-01-25 05:28:46,385 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-01-25 05:28:46,385 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 59 transitions. [2018-01-25 05:28:46,386 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 59 transitions. Word has length 24 [2018-01-25 05:28:46,386 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:28:46,386 INFO L432 AbstractCegarLoop]: Abstraction has 51 states and 59 transitions. [2018-01-25 05:28:46,386 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-25 05:28:46,386 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 59 transitions. [2018-01-25 05:28:46,387 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-01-25 05:28:46,387 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:28:46,387 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:28:46,388 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:28:46,388 INFO L82 PathProgramCache]: Analyzing trace with hash 1706718632, now seen corresponding path program 1 times [2018-01-25 05:28:46,388 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:28:46,389 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:46,389 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:28:46,389 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:46,389 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:28:46,400 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:28:46,401 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:28:46,581 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-25 05:28:46,581 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-25 05:28:46,581 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2018-01-25 05:28:46,582 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-25 05:28:46,582 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-01-25 05:28:46,582 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-01-25 05:28:46,582 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2018-01-25 05:28:46,582 INFO L87 Difference]: Start difference. First operand 51 states and 59 transitions. Second operand 10 states. [2018-01-25 05:28:46,808 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:28:46,808 INFO L93 Difference]: Finished difference Result 57 states and 66 transitions. [2018-01-25 05:28:46,809 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-25 05:28:46,809 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 24 [2018-01-25 05:28:46,809 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:28:46,809 INFO L225 Difference]: With dead ends: 57 [2018-01-25 05:28:46,809 INFO L226 Difference]: Without dead ends: 56 [2018-01-25 05:28:46,810 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2018-01-25 05:28:46,810 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2018-01-25 05:28:46,814 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 53. [2018-01-25 05:28:46,814 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 53 states. [2018-01-25 05:28:46,814 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 60 transitions. [2018-01-25 05:28:46,814 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 60 transitions. Word has length 24 [2018-01-25 05:28:46,815 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:28:46,815 INFO L432 AbstractCegarLoop]: Abstraction has 53 states and 60 transitions. [2018-01-25 05:28:46,815 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-01-25 05:28:46,815 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 60 transitions. [2018-01-25 05:28:46,815 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-01-25 05:28:46,815 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:28:46,816 INFO L322 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:28:46,816 INFO L371 AbstractCegarLoop]: === Iteration 11 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:28:46,816 INFO L82 PathProgramCache]: Analyzing trace with hash 1706720075, now seen corresponding path program 1 times [2018-01-25 05:28:46,816 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:28:46,817 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:46,817 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:28:46,817 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:46,817 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:28:46,829 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:28:46,830 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:28:47,087 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:28:47,088 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:28:47,088 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-25 05:28:47,089 INFO L199 CegarAbsIntRunner]: Running AI on error trace of length 25 with the following transitions: [2018-01-25 05:28:47,090 INFO L201 CegarAbsIntRunner]: [0], [1], [5], [10], [16], [20], [27], [28], [29], [30], [31], [32], [35], [46], [49], [53], [55], [57], [62], [98], [99], [100], [102] [2018-01-25 05:28:47,140 INFO L147 AbstractInterpreter]: Using domain VPDomain [2018-01-25 05:28:47,141 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=2) [2018-01-25 05:28:48,438 INFO L259 AbstractInterpreter]: Some error location(s) were reachable [2018-01-25 05:28:48,440 INFO L268 AbstractInterpreter]: Visited 23 different actions 27 times. Merged at 4 different actions 4 times. Never widened. Found 1 fixpoints after 1 different actions. Largest state had 27 variables. [2018-01-25 05:28:48,467 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-01-25 05:28:48,468 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:28:48,468 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG 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-25 05:28:48,483 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:28:48,483 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-25 05:28:48,509 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:28:48,520 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-25 05:28:48,622 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-25 05:28:48,624 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:48,637 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-25 05:28:48,638 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:48,647 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:28:48,648 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-01-25 05:28:48,738 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:28:48,740 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:28:48,741 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 23 [2018-01-25 05:28:48,742 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:48,754 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:28:48,755 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:28:48,756 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-25 05:28:48,756 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:48,766 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:28:48,766 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:30, output treesize:18 [2018-01-25 05:28:49,027 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:28:49,028 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-25 05:28:49,240 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 3 [2018-01-25 05:28:49,240 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:49,245 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 15 [2018-01-25 05:28:49,255 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 3 [2018-01-25 05:28:49,256 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:49,256 WARN L307 Elim1Store]: Array PQE input equivalent to true [2018-01-25 05:28:49,256 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:49,259 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:28:49,262 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:28:49,262 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:21, output treesize:3 [2018-01-25 05:28:49,274 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:28:49,296 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:28:49,296 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 Starting monitored process 3 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-01-25 05:28:49,300 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:28:49,300 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-25 05:28:49,357 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:28:49,364 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-25 05:28:49,372 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-25 05:28:49,373 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:49,387 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-25 05:28:49,387 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:49,397 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:28:49,397 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-01-25 05:28:49,477 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:28:49,478 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:28:49,479 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 23 [2018-01-25 05:28:49,479 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:49,491 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:28:49,492 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:28:49,493 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-25 05:28:49,493 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:49,500 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-25 05:28:49,500 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:30, output treesize:18 [2018-01-25 05:28:49,649 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:28:49,649 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-25 05:28:49,722 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 3 [2018-01-25 05:28:49,722 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:49,725 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 15 [2018-01-25 05:28:49,733 WARN L307 Elim1Store]: Array PQE input equivalent to true [2018-01-25 05:28:49,733 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:49,734 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 3 [2018-01-25 05:28:49,735 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:49,744 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:28:49,752 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:28:49,752 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:21, output treesize:3 [2018-01-25 05:28:49,819 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:28:49,821 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-25 05:28:49,821 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13, 12, 11, 12] total 38 [2018-01-25 05:28:49,821 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-25 05:28:49,822 INFO L409 AbstractCegarLoop]: Interpolant automaton has 24 states [2018-01-25 05:28:49,822 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2018-01-25 05:28:49,822 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=150, Invalid=1332, Unknown=0, NotChecked=0, Total=1482 [2018-01-25 05:28:49,822 INFO L87 Difference]: Start difference. First operand 53 states and 60 transitions. Second operand 24 states. [2018-01-25 05:28:50,532 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:28:50,532 INFO L93 Difference]: Finished difference Result 75 states and 85 transitions. [2018-01-25 05:28:50,532 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-01-25 05:28:50,532 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 24 [2018-01-25 05:28:50,532 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:28:50,533 INFO L225 Difference]: With dead ends: 75 [2018-01-25 05:28:50,533 INFO L226 Difference]: Without dead ends: 72 [2018-01-25 05:28:50,534 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 61 SyntacticMatches, 9 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 622 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=296, Invalid=1960, Unknown=0, NotChecked=0, Total=2256 [2018-01-25 05:28:50,534 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2018-01-25 05:28:50,540 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 64. [2018-01-25 05:28:50,540 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 64 states. [2018-01-25 05:28:50,541 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 75 transitions. [2018-01-25 05:28:50,541 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 75 transitions. Word has length 24 [2018-01-25 05:28:50,541 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:28:50,541 INFO L432 AbstractCegarLoop]: Abstraction has 64 states and 75 transitions. [2018-01-25 05:28:50,541 INFO L433 AbstractCegarLoop]: Interpolant automaton has 24 states. [2018-01-25 05:28:50,541 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 75 transitions. [2018-01-25 05:28:50,542 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2018-01-25 05:28:50,542 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:28:50,542 INFO L322 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:28:50,542 INFO L371 AbstractCegarLoop]: === Iteration 12 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:28:50,542 INFO L82 PathProgramCache]: Analyzing trace with hash 1074905977, now seen corresponding path program 2 times [2018-01-25 05:28:50,542 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:28:50,543 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:50,543 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:28:50,543 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:28:50,543 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:28:50,560 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:28:50,561 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:28:50,887 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:28:50,888 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:28:50,888 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-25 05:28:50,888 INFO L183 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-01-25 05:28:50,888 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-01-25 05:28:50,888 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:28:50,888 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG 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-25 05:28:50,893 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-25 05:28:50,893 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-01-25 05:28:50,905 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-25 05:28:50,910 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-25 05:28:50,911 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-25 05:28:50,914 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-25 05:28:50,940 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-25 05:28:50,940 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:50,944 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:28:50,944 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:18, output treesize:17 [2018-01-25 05:28:50,978 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:28:50,979 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:28:50,979 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-25 05:28:50,979 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:50,983 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:28:50,983 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:22, output treesize:16 [2018-01-25 05:28:51,026 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 14 [2018-01-25 05:28:51,028 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-01-25 05:28:51,028 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:51,031 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:28:51,040 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2018-01-25 05:28:51,040 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:42, output treesize:38 [2018-01-25 05:28:51,073 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 29 [2018-01-25 05:28:51,088 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 10 [2018-01-25 05:28:51,089 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:51,118 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:28:51,148 INFO L267 ElimStorePlain]: Start of recursive call 1: 5 dim-0 vars, 1 dim-2 vars, End of recursive call: 5 dim-0 vars, and 1 xjuncts. [2018-01-25 05:28:51,148 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 6 variables, input treesize:52, output treesize:48 [2018-01-25 05:28:53,481 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 41 treesize of output 37 [2018-01-25 05:28:53,498 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2018-01-25 05:28:53,499 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:53,509 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:28:53,517 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 25 treesize of output 37 [2018-01-25 05:28:53,518 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-01-25 05:28:53,533 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-25 05:28:53,548 INFO L267 ElimStorePlain]: Start of recursive call 1: 5 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-25 05:28:53,549 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 6 variables, input treesize:66, output treesize:43 [2018-01-25 05:28:53,595 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 5 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:28:53,595 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-25 05:28:53,942 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 50 treesize of output 48 [2018-01-25 05:28:53,943 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:53,957 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 52 treesize of output 48 [2018-01-25 05:28:53,958 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:53,971 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 36 [2018-01-25 05:28:53,988 INFO L682 Elim1Store]: detected equality via solver [2018-01-25 05:28:53,989 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-01-25 05:28:53,990 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:53,995 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:28:54,005 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 36 [2018-01-25 05:28:54,023 INFO L682 Elim1Store]: detected equality via solver [2018-01-25 05:28:54,024 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-01-25 05:28:54,024 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:54,029 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:28:54,039 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, 2 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-25 05:28:54,039 INFO L202 ElimStorePlain]: Needed 7 recursive calls to eliminate 4 variables, input treesize:103, output treesize:33 [2018-01-25 05:28:54,262 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:28:54,284 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:28:54,284 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 Starting monitored process 5 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-01-25 05:28:54,287 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-25 05:28:54,287 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-01-25 05:28:54,303 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-25 05:28:54,333 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-25 05:28:54,368 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-25 05:28:54,375 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-25 05:28:54,428 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-25 05:28:54,428 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:54,439 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-25 05:28:54,439 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:54,447 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:28:54,447 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:19, output treesize:17 [2018-01-25 05:28:54,528 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:28:54,529 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 15 [2018-01-25 05:28:54,529 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:54,539 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:28:54,539 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:28:54,540 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-25 05:28:54,540 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:54,545 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:28:54,545 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:28, output treesize:21 [2018-01-25 05:28:54,625 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 13 [2018-01-25 05:28:54,627 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-01-25 05:28:54,628 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:54,629 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:28:54,635 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:28:54,635 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:29, output treesize:25 [2018-01-25 05:28:54,688 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 30 [2018-01-25 05:28:54,690 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-01-25 05:28:54,691 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:54,694 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:28:54,700 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2018-01-25 05:28:54,701 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:36, output treesize:32 [2018-01-25 05:28:54,930 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 29 [2018-01-25 05:28:54,943 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 15 treesize of output 16 [2018-01-25 05:28:54,943 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-25 05:28:54,952 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 1 [2018-01-25 05:28:54,952 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:54,955 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-25 05:28:54,960 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-25 05:28:54,960 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 3 variables, input treesize:38, output treesize:20 [2018-01-25 05:28:55,133 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:28:55,133 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-25 05:28:55,581 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 14 [2018-01-25 05:28:55,590 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2018-01-25 05:28:55,591 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:55,592 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:28:55,598 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:28:55,598 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:36, output treesize:25 [2018-01-25 05:28:55,880 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 3 [2018-01-25 05:28:55,880 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:55,887 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 23 [2018-01-25 05:28:55,900 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 7 [2018-01-25 05:28:55,901 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:55,901 WARN L307 Elim1Store]: Array PQE input equivalent to true [2018-01-25 05:28:55,901 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-25 05:28:55,906 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:28:55,914 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-25 05:28:55,915 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 6 variables, input treesize:37, output treesize:7 [2018-01-25 05:28:55,946 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:28:55,948 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-25 05:28:55,948 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 16, 14, 15, 13] total 63 [2018-01-25 05:28:55,948 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-25 05:28:55,948 INFO L409 AbstractCegarLoop]: Interpolant automaton has 28 states [2018-01-25 05:28:55,949 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2018-01-25 05:28:55,950 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=230, Invalid=3801, Unknown=1, NotChecked=0, Total=4032 [2018-01-25 05:28:55,950 INFO L87 Difference]: Start difference. First operand 64 states and 75 transitions. Second operand 28 states. [2018-01-25 05:29:23,055 WARN L146 SmtUtils]: Spent 8081ms on a formula simplification. DAG size of input: 80 DAG size of output 78 [2018-01-25 05:29:35,303 WARN L146 SmtUtils]: Spent 8095ms on a formula simplification. DAG size of input: 83 DAG size of output 81 [2018-01-25 05:29:44,123 WARN L146 SmtUtils]: Spent 4165ms on a formula simplification. DAG size of input: 69 DAG size of output 61 [2018-01-25 05:29:49,070 WARN L146 SmtUtils]: Spent 195ms on a formula simplification. DAG size of input: 79 DAG size of output 62 Received shutdown request... [2018-01-25 05:29:57,736 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-01-25 05:29:57,736 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-25 05:29:57,741 WARN L187 ceAbstractionStarter]: Timeout [2018-01-25 05:29:57,741 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.01 05:29:57 BoogieIcfgContainer [2018-01-25 05:29:57,741 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-25 05:29:57,742 INFO L168 Benchmark]: Toolchain (without parser) took 74037.24 ms. Allocated memory was 304.6 MB in the beginning and 640.7 MB in the end (delta: 336.1 MB). Free memory was 264.5 MB in the beginning and 471.6 MB in the end (delta: -207.1 MB). Peak memory consumption was 129.0 MB. Max. memory is 5.3 GB. [2018-01-25 05:29:57,743 INFO L168 Benchmark]: CDTParser took 0.12 ms. Allocated memory is still 304.6 MB. Free memory is still 270.5 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-25 05:29:57,743 INFO L168 Benchmark]: CACSL2BoogieTranslator took 205.96 ms. Allocated memory is still 304.6 MB. Free memory was 263.5 MB in the beginning and 253.5 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 5.3 GB. [2018-01-25 05:29:57,743 INFO L168 Benchmark]: Boogie Preprocessor took 32.67 ms. Allocated memory is still 304.6 MB. Free memory was 253.5 MB in the beginning and 251.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-01-25 05:29:57,744 INFO L168 Benchmark]: RCFGBuilder took 277.86 ms. Allocated memory is still 304.6 MB. Free memory was 251.5 MB in the beginning and 231.5 MB in the end (delta: 20.0 MB). Peak memory consumption was 20.0 MB. Max. memory is 5.3 GB. [2018-01-25 05:29:57,744 INFO L168 Benchmark]: TraceAbstraction took 73512.86 ms. Allocated memory was 304.6 MB in the beginning and 640.7 MB in the end (delta: 336.1 MB). Free memory was 231.5 MB in the beginning and 471.6 MB in the end (delta: -240.1 MB). Peak memory consumption was 96.0 MB. Max. memory is 5.3 GB. [2018-01-25 05:29:57,746 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.12 ms. Allocated memory is still 304.6 MB. Free memory is still 270.5 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 205.96 ms. Allocated memory is still 304.6 MB. Free memory was 263.5 MB in the beginning and 253.5 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 32.67 ms. Allocated memory is still 304.6 MB. Free memory was 253.5 MB in the beginning and 251.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 277.86 ms. Allocated memory is still 304.6 MB. Free memory was 251.5 MB in the beginning and 231.5 MB in the end (delta: 20.0 MB). Peak memory consumption was 20.0 MB. Max. memory is 5.3 GB. * TraceAbstraction took 73512.86 ms. Allocated memory was 304.6 MB in the beginning and 640.7 MB in the end (delta: 336.1 MB). Free memory was 231.5 MB in the beginning and 471.6 MB in the end (delta: -240.1 MB). Peak memory consumption was 96.0 MB. Max. memory is 5.3 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.analysis.abstractinterpretationv2: - StatisticsResult: ArrayEqualityDomainStatistics #Locations : 22 LocStat_MAX_WEQGRAPH_SIZE : 5 LocStat_MAX_SIZEOF_WEQEDGELABEL : 2 LocStat_NO_SUPPORTING_EQUALITIES : 275 LocStat_NO_SUPPORTING_DISEQUALITIES : 42 LocStat_NO_DISJUNCTIONS : -44 LocStat_MAX_NO_DISJUNCTIONS : -1 #Transitions : 29 TransStat_MAX_WEQGRAPH_SIZE : 2 TransStat_MAX_SIZEOF_WEQEDGELABEL : 1 TransStat_NO_SUPPORTING_EQUALITIES : 61 TransStat_NO_SUPPORTING_DISEQUALITIES : 6 TransStat_NO_DISJUNCTIONS : 30 TransStat_MAX_NO_DISJUNCTIONS : 2 - StatisticsResult: EqConstraintFactoryStatistics CONJOIN_DISJUNCTIVE(MILLISECONDS) : 1.437095 RENAME_VARIABLES(MILLISECONDS) : 0.314253 UNFREEZE(MILLISECONDS) : 0.000000 CONJOIN(MILLISECONDS) : 1.380346 PROJECTAWAY(MILLISECONDS) : 0.876441 ADD_WEAK_EQUALITY(MILLISECONDS) : 0.110182 DISJOIN(MILLISECONDS) : 0.410607 RENAME_VARIABLES_DISJUNCTIVE(MILLISECONDS) : 0.358555 ADD_EQUALITY(MILLISECONDS) : 0.025454 DISJOIN_DISJUNCTIVE(MILLISECONDS) : 0.000000 ADD_DISEQUALITY(MILLISECONDS) : 0.017112 #CONJOIN_DISJUNCTIVE : 50 #RENAME_VARIABLES : 74 #UNFREEZE : 0 #CONJOIN : 99 #PROJECTAWAY : 68 #ADD_WEAK_EQUALITY : 9 #DISJOIN : 6 #RENAME_VARIABLES_DISJUNCTIVE : 71 #ADD_EQUALITY : 63 #DISJOIN_DISJUNCTIVE : 0 #ADD_DISEQUALITY : 4 * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 574). Cancelled while BasicCegarLoop was constructing difference of abstraction (64states) and interpolant automaton (currently 25 states, 28 states before enhancement), while ReachableStatesComputation was computing reachable states (52 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 573). Cancelled while BasicCegarLoop was constructing difference of abstraction (64states) and interpolant automaton (currently 25 states, 28 states before enhancement), while ReachableStatesComputation was computing reachable states (52 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 574). Cancelled while BasicCegarLoop was constructing difference of abstraction (64states) and interpolant automaton (currently 25 states, 28 states before enhancement), while ReachableStatesComputation was computing reachable states (52 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 573). Cancelled while BasicCegarLoop was constructing difference of abstraction (64states) and interpolant automaton (currently 25 states, 28 states before enhancement), while ReachableStatesComputation was computing reachable states (52 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 557]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 557). Cancelled while BasicCegarLoop was constructing difference of abstraction (64states) and interpolant automaton (currently 25 states, 28 states before enhancement), while ReachableStatesComputation was computing reachable states (52 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 553). Cancelled while BasicCegarLoop was constructing difference of abstraction (64states) and interpolant automaton (currently 25 states, 28 states before enhancement), while ReachableStatesComputation was computing reachable states (52 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was constructing difference of abstraction (64states) and interpolant automaton (currently 25 states, 28 states before enhancement), while ReachableStatesComputation was computing reachable states (52 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 546). Cancelled while BasicCegarLoop was constructing difference of abstraction (64states) and interpolant automaton (currently 25 states, 28 states before enhancement), while ReachableStatesComputation was computing reachable states (52 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was constructing difference of abstraction (64states) and interpolant automaton (currently 25 states, 28 states before enhancement), while ReachableStatesComputation was computing reachable states (52 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 546). Cancelled while BasicCegarLoop was constructing difference of abstraction (64states) and interpolant automaton (currently 25 states, 28 states before enhancement), while ReachableStatesComputation was computing reachable states (52 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was constructing difference of abstraction (64states) and interpolant automaton (currently 25 states, 28 states before enhancement), while ReachableStatesComputation was computing reachable states (52 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 553). Cancelled while BasicCegarLoop was constructing difference of abstraction (64states) and interpolant automaton (currently 25 states, 28 states before enhancement), while ReachableStatesComputation was computing reachable states (52 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was constructing difference of abstraction (64states) and interpolant automaton (currently 25 states, 28 states before enhancement), while ReachableStatesComputation was computing reachable states (52 states constructedinput type IntersectNwa). - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 54 locations, 13 error locations. TIMEOUT Result, 73.4s OverallTime, 12 OverallIterations, 3 TraceHistogramMax, 63.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 487 SDtfs, 901 SDslu, 1476 SDs, 0 SdLazy, 1297 SolverSat, 182 SolverUnsat, 10 SolverUnknown, 0 SolverNotchecked, 23.9s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 338 GetRequests, 125 SyntacticMatches, 16 SemanticMatches, 197 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2281 ImplicationChecksByTransitivity, 45.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=64occurred in iteration=11, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 1.3s AbstIntTime, 1 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 11 MinimizatonAttempts, 22 StatesRemovedByMinimization, 5 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 7.7s InterpolantComputationTime, 331 NumberOfCodeBlocks, 331 NumberOfCodeBlocksAsserted, 18 NumberOfCheckSat, 413 ConstructedInterpolants, 43 QuantifiedInterpolants, 93593 SizeOfPredicates, 69 NumberOfNonLiveVariables, 516 ConjunctsInSsa, 151 ConjunctsInUnsatCore, 20 InterpolantComputations, 10 PerfectInterpolantSequences, 0/45 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ_smtcomp.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-25_05-29-57-756.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ_smtcomp.epf_AutomizerC.xml/Csv-VPDomainBenchmark-0-2018-01-25_05-29-57-756.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ_smtcomp.epf_AutomizerC.xml/Csv-BenchmarkWithCounters-0-2018-01-25_05-29-57-756.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ_smtcomp.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-25_05-29-57-756.csv Completed graceful shutdown