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_mostprecise.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-24 19:56:00,890 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-24 19:56:00,891 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-24 19:56:00,907 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-24 19:56:00,907 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-24 19:56:00,908 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-24 19:56:00,909 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-24 19:56:00,911 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-24 19:56:00,913 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-24 19:56:00,914 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-24 19:56:00,915 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-24 19:56:00,915 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-24 19:56:00,916 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-24 19:56:00,917 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-24 19:56:00,918 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-24 19:56:00,921 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-24 19:56:00,923 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-24 19:56:00,925 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-24 19:56:00,926 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-24 19:56:00,927 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-24 19:56:00,930 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-24 19:56:00,930 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-24 19:56:00,930 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-24 19:56:00,931 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-24 19:56:00,932 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-24 19:56:00,933 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-24 19:56:00,934 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-24 19:56:00,934 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-24 19:56:00,934 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-24 19:56:00,935 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-24 19:56:00,935 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-24 19:56:00,936 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_mostprecise.epf [2018-01-24 19:56:00,944 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-24 19:56:00,944 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-24 19:56:00,945 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-24 19:56:00,945 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-24 19:56:00,945 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-24 19:56:00,945 INFO L133 SettingsManager]: * Weq Fattening=true [2018-01-24 19:56:00,946 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-24 19:56:00,946 INFO L133 SettingsManager]: * Precise comparison operator=true [2018-01-24 19:56:00,946 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-24 19:56:00,946 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-24 19:56:00,946 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-24 19:56:00,947 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-24 19:56:00,947 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-24 19:56:00,947 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-24 19:56:00,947 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-24 19:56:00,947 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-01-24 19:56:00,947 INFO L133 SettingsManager]: * Bitprecise bitfields=true [2018-01-24 19:56:00,947 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-01-24 19:56:00,948 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-24 19:56:00,948 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-24 19:56:00,948 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-24 19:56:00,948 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-01-24 19:56:00,948 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-24 19:56:00,948 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-24 19:56:00,949 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-24 19:56:00,949 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-24 19:56:00,949 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-24 19:56:00,949 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-24 19:56:00,949 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-24 19:56:00,949 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-24 19:56:00,950 INFO L133 SettingsManager]: * Trace refinement strategy=TAIPAN [2018-01-24 19:56:00,950 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-24 19:56:00,950 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-24 19:56:00,950 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-24 19:56:00,950 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-01-24 19:56:00,951 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-24 19:56:00,951 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-24 19:56:00,984 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-24 19:56:00,994 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-24 19:56:00,997 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-24 19:56:00,998 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-24 19:56:00,998 INFO L276 PluginConnector]: CDTParser initialized [2018-01-24 19:56:00,999 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-24 19:56:01,152 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-24 19:56:01,156 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-24 19:56:01,156 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-24 19:56:01,157 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-24 19:56:01,161 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-24 19:56:01,162 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.01 07:56:01" (1/1) ... [2018-01-24 19:56:01,164 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6ca156b0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 07:56:01, skipping insertion in model container [2018-01-24 19:56:01,165 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.01 07:56:01" (1/1) ... [2018-01-24 19:56:01,177 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-24 19:56:01,215 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-24 19:56:01,335 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-24 19:56:01,355 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-24 19:56:01,360 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 07:56:01 WrapperNode [2018-01-24 19:56:01,361 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-24 19:56:01,361 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-24 19:56:01,361 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-24 19:56:01,361 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-24 19:56:01,378 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 07:56:01" (1/1) ... [2018-01-24 19:56:01,378 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 07:56:01" (1/1) ... [2018-01-24 19:56:01,390 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 07:56:01" (1/1) ... [2018-01-24 19:56:01,390 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 07:56:01" (1/1) ... [2018-01-24 19:56:01,395 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 07:56:01" (1/1) ... [2018-01-24 19:56:01,400 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 07:56:01" (1/1) ... [2018-01-24 19:56:01,402 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 07:56:01" (1/1) ... [2018-01-24 19:56:01,404 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-24 19:56:01,405 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-24 19:56:01,405 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-24 19:56:01,405 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-24 19:56:01,406 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 07:56:01" (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-24 19:56:01,472 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-24 19:56:01,472 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-24 19:56:01,473 INFO L136 BoogieDeclarations]: Found implementation of procedure cstrncat [2018-01-24 19:56:01,473 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-24 19:56:01,473 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-01-24 19:56:01,473 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-01-24 19:56:01,473 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-24 19:56:01,473 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-24 19:56:01,473 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-24 19:56:01,474 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-24 19:56:01,474 INFO L128 BoogieDeclarations]: Found specification of procedure cstrncat [2018-01-24 19:56:01,474 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-24 19:56:01,474 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-24 19:56:01,474 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-24 19:56:01,722 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-24 19:56:01,723 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.01 07:56:01 BoogieIcfgContainer [2018-01-24 19:56:01,723 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-24 19:56:01,724 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-24 19:56:01,724 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-24 19:56:01,725 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-24 19:56:01,725 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 24.01 07:56:01" (1/3) ... [2018-01-24 19:56:01,726 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@21316476 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.01 07:56:01, skipping insertion in model container [2018-01-24 19:56:01,726 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 07:56:01" (2/3) ... [2018-01-24 19:56:01,727 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@21316476 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.01 07:56:01, skipping insertion in model container [2018-01-24 19:56:01,727 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.01 07:56:01" (3/3) ... [2018-01-24 19:56:01,728 INFO L105 eAbstractionObserver]: Analyzing ICFG openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i [2018-01-24 19:56:01,734 INFO L130 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-24 19:56:01,740 INFO L142 ceAbstractionStarter]: Appying trace abstraction to program that has 13 error locations. [2018-01-24 19:56:01,783 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-24 19:56:01,783 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-24 19:56:01,783 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-24 19:56:01,783 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-24 19:56:01,783 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-24 19:56:01,783 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-24 19:56:01,783 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-24 19:56:01,784 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-01-24 19:56:01,784 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-24 19:56:01,805 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states. [2018-01-24 19:56:01,810 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-01-24 19:56:01,810 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 19:56:01,811 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 19:56:01,811 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 19:56:01,815 INFO L82 PathProgramCache]: Analyzing trace with hash 2055638365, now seen corresponding path program 1 times [2018-01-24 19:56:01,817 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 19:56:01,857 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:01,857 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 19:56:01,857 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:01,857 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 19:56:01,902 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 19:56:01,911 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 19:56:01,977 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-24 19:56:01,979 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 19:56:01,979 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-24 19:56:01,980 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 19:56:01,983 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-24 19:56:01,995 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-24 19:56:01,996 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-24 19:56:01,997 INFO L87 Difference]: Start difference. First operand 54 states. Second operand 3 states. [2018-01-24 19:56:02,214 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 19:56:02,215 INFO L93 Difference]: Finished difference Result 81 states and 93 transitions. [2018-01-24 19:56:02,215 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-24 19:56:02,217 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 11 [2018-01-24 19:56:02,217 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 19:56:02,229 INFO L225 Difference]: With dead ends: 81 [2018-01-24 19:56:02,230 INFO L226 Difference]: Without dead ends: 51 [2018-01-24 19:56:02,233 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-24 19:56:02,247 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2018-01-24 19:56:02,266 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2018-01-24 19:56:02,267 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-01-24 19:56:02,268 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 57 transitions. [2018-01-24 19:56:02,269 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 57 transitions. Word has length 11 [2018-01-24 19:56:02,269 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 19:56:02,269 INFO L432 AbstractCegarLoop]: Abstraction has 51 states and 57 transitions. [2018-01-24 19:56:02,270 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-24 19:56:02,270 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 57 transitions. [2018-01-24 19:56:02,270 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-24 19:56:02,270 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 19:56:02,270 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 19:56:02,270 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 19:56:02,271 INFO L82 PathProgramCache]: Analyzing trace with hash -1872133330, now seen corresponding path program 1 times [2018-01-24 19:56:02,271 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 19:56:02,272 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:02,272 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 19:56:02,272 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:02,272 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 19:56:02,286 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 19:56:02,287 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 19:56:02,336 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-24 19:56:02,336 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 19:56:02,336 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-24 19:56:02,337 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 19:56:02,338 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-24 19:56:02,339 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-24 19:56:02,339 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-24 19:56:02,339 INFO L87 Difference]: Start difference. First operand 51 states and 57 transitions. Second operand 5 states. [2018-01-24 19:56:02,436 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 19:56:02,436 INFO L93 Difference]: Finished difference Result 95 states and 106 transitions. [2018-01-24 19:56:02,436 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-24 19:56:02,437 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 15 [2018-01-24 19:56:02,437 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 19:56:02,438 INFO L225 Difference]: With dead ends: 95 [2018-01-24 19:56:02,438 INFO L226 Difference]: Without dead ends: 51 [2018-01-24 19:56:02,439 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-24 19:56:02,440 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2018-01-24 19:56:02,445 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2018-01-24 19:56:02,445 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-01-24 19:56:02,446 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 56 transitions. [2018-01-24 19:56:02,447 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 56 transitions. Word has length 15 [2018-01-24 19:56:02,447 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 19:56:02,447 INFO L432 AbstractCegarLoop]: Abstraction has 51 states and 56 transitions. [2018-01-24 19:56:02,447 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-24 19:56:02,447 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 56 transitions. [2018-01-24 19:56:02,448 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-24 19:56:02,448 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 19:56:02,448 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 19:56:02,448 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 19:56:02,449 INFO L82 PathProgramCache]: Analyzing trace with hash -1192074960, now seen corresponding path program 1 times [2018-01-24 19:56:02,449 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 19:56:02,450 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:02,450 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 19:56:02,450 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:02,451 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 19:56:02,474 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 19:56:02,475 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 19:56:02,559 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-24 19:56:02,559 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 19:56:02,559 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-24 19:56:02,559 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 19:56:02,560 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-24 19:56:02,560 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-24 19:56:02,560 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-24 19:56:02,560 INFO L87 Difference]: Start difference. First operand 51 states and 56 transitions. Second operand 4 states. [2018-01-24 19:56:02,631 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 19:56:02,631 INFO L93 Difference]: Finished difference Result 51 states and 56 transitions. [2018-01-24 19:56:02,631 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-24 19:56:02,631 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 15 [2018-01-24 19:56:02,632 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 19:56:02,632 INFO L225 Difference]: With dead ends: 51 [2018-01-24 19:56:02,632 INFO L226 Difference]: Without dead ends: 50 [2018-01-24 19:56:02,633 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-24 19:56:02,633 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2018-01-24 19:56:02,637 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2018-01-24 19:56:02,638 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 50 states. [2018-01-24 19:56:02,638 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 55 transitions. [2018-01-24 19:56:02,639 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 55 transitions. Word has length 15 [2018-01-24 19:56:02,639 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 19:56:02,639 INFO L432 AbstractCegarLoop]: Abstraction has 50 states and 55 transitions. [2018-01-24 19:56:02,639 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-24 19:56:02,639 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 55 transitions. [2018-01-24 19:56:02,639 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-24 19:56:02,640 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 19:56:02,640 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 19:56:02,640 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 19:56:02,640 INFO L82 PathProgramCache]: Analyzing trace with hash -1192074959, now seen corresponding path program 1 times [2018-01-24 19:56:02,640 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 19:56:02,641 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:02,641 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 19:56:02,641 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:02,641 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 19:56:02,654 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 19:56:02,655 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 19:56:02,806 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-24 19:56:02,807 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 19:56:02,807 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-24 19:56:02,807 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 19:56:02,807 INFO L409 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-01-24 19:56:02,808 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-01-24 19:56:02,808 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-01-24 19:56:02,808 INFO L87 Difference]: Start difference. First operand 50 states and 55 transitions. Second operand 8 states. [2018-01-24 19:56:02,965 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 19:56:02,965 INFO L93 Difference]: Finished difference Result 50 states and 55 transitions. [2018-01-24 19:56:02,965 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-01-24 19:56:02,966 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 15 [2018-01-24 19:56:02,966 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 19:56:02,966 INFO L225 Difference]: With dead ends: 50 [2018-01-24 19:56:02,967 INFO L226 Difference]: Without dead ends: 49 [2018-01-24 19:56:02,967 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=84, Unknown=0, NotChecked=0, Total=132 [2018-01-24 19:56:02,967 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2018-01-24 19:56:02,971 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 49. [2018-01-24 19:56:02,971 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 49 states. [2018-01-24 19:56:02,972 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 54 transitions. [2018-01-24 19:56:02,972 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 54 transitions. Word has length 15 [2018-01-24 19:56:02,972 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 19:56:02,972 INFO L432 AbstractCegarLoop]: Abstraction has 49 states and 54 transitions. [2018-01-24 19:56:02,972 INFO L433 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-01-24 19:56:02,972 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 54 transitions. [2018-01-24 19:56:02,973 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-01-24 19:56:02,973 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 19:56:02,973 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 19:56:02,973 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 19:56:02,973 INFO L82 PathProgramCache]: Analyzing trace with hash 1700381909, now seen corresponding path program 1 times [2018-01-24 19:56:02,973 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 19:56:02,974 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:02,974 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 19:56:02,974 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:02,975 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 19:56:02,985 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 19:56:02,986 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 19:56:03,011 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-24 19:56:03,012 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 19:56:03,012 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-24 19:56:03,012 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 19:56:03,012 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-24 19:56:03,013 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-24 19:56:03,013 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-24 19:56:03,013 INFO L87 Difference]: Start difference. First operand 49 states and 54 transitions. Second operand 4 states. [2018-01-24 19:56:03,058 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 19:56:03,058 INFO L93 Difference]: Finished difference Result 49 states and 54 transitions. [2018-01-24 19:56:03,059 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-24 19:56:03,059 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 16 [2018-01-24 19:56:03,059 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 19:56:03,060 INFO L225 Difference]: With dead ends: 49 [2018-01-24 19:56:03,060 INFO L226 Difference]: Without dead ends: 48 [2018-01-24 19:56:03,061 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-24 19:56:03,061 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2018-01-24 19:56:03,066 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2018-01-24 19:56:03,066 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 48 states. [2018-01-24 19:56:03,067 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 53 transitions. [2018-01-24 19:56:03,067 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 53 transitions. Word has length 16 [2018-01-24 19:56:03,068 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 19:56:03,068 INFO L432 AbstractCegarLoop]: Abstraction has 48 states and 53 transitions. [2018-01-24 19:56:03,068 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-24 19:56:03,068 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 53 transitions. [2018-01-24 19:56:03,068 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-01-24 19:56:03,069 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 19:56:03,069 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 19:56:03,069 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 19:56:03,069 INFO L82 PathProgramCache]: Analyzing trace with hash 1700381910, now seen corresponding path program 1 times [2018-01-24 19:56:03,069 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 19:56:03,070 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:03,071 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 19:56:03,071 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:03,071 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 19:56:03,083 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 19:56:03,084 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 19:56:03,153 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-24 19:56:03,153 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 19:56:03,153 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-24 19:56:03,154 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 19:56:03,154 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-24 19:56:03,154 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-24 19:56:03,154 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-24 19:56:03,155 INFO L87 Difference]: Start difference. First operand 48 states and 53 transitions. Second operand 5 states. [2018-01-24 19:56:03,188 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 19:56:03,189 INFO L93 Difference]: Finished difference Result 48 states and 53 transitions. [2018-01-24 19:56:03,189 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-24 19:56:03,189 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 16 [2018-01-24 19:56:03,190 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 19:56:03,190 INFO L225 Difference]: With dead ends: 48 [2018-01-24 19:56:03,191 INFO L226 Difference]: Without dead ends: 47 [2018-01-24 19:56:03,191 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-24 19:56:03,191 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-01-24 19:56:03,196 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2018-01-24 19:56:03,196 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 47 states. [2018-01-24 19:56:03,197 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 52 transitions. [2018-01-24 19:56:03,197 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 52 transitions. Word has length 16 [2018-01-24 19:56:03,197 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 19:56:03,197 INFO L432 AbstractCegarLoop]: Abstraction has 47 states and 52 transitions. [2018-01-24 19:56:03,197 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-24 19:56:03,198 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 52 transitions. [2018-01-24 19:56:03,198 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2018-01-24 19:56:03,198 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 19:56:03,198 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-24 19:56:03,199 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 19:56:03,199 INFO L82 PathProgramCache]: Analyzing trace with hash -275307336, now seen corresponding path program 1 times [2018-01-24 19:56:03,199 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 19:56:03,200 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:03,200 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 19:56:03,200 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:03,200 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 19:56:03,214 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 19:56:03,215 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 19:56:03,258 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-24 19:56:03,258 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 19:56:03,258 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-24 19:56:03,258 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 19:56:03,259 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-24 19:56:03,259 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-24 19:56:03,259 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-24 19:56:03,259 INFO L87 Difference]: Start difference. First operand 47 states and 52 transitions. Second operand 6 states. [2018-01-24 19:56:03,331 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 19:56:03,331 INFO L93 Difference]: Finished difference Result 50 states and 55 transitions. [2018-01-24 19:56:03,331 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-24 19:56:03,332 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 21 [2018-01-24 19:56:03,332 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 19:56:03,335 INFO L225 Difference]: With dead ends: 50 [2018-01-24 19:56:03,335 INFO L226 Difference]: Without dead ends: 47 [2018-01-24 19:56:03,336 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-24 19:56:03,336 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-01-24 19:56:03,341 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 44. [2018-01-24 19:56:03,341 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 44 states. [2018-01-24 19:56:03,342 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 49 transitions. [2018-01-24 19:56:03,342 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 49 transitions. Word has length 21 [2018-01-24 19:56:03,342 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 19:56:03,342 INFO L432 AbstractCegarLoop]: Abstraction has 44 states and 49 transitions. [2018-01-24 19:56:03,343 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-24 19:56:03,343 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 49 transitions. [2018-01-24 19:56:03,343 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2018-01-24 19:56:03,344 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 19:56:03,344 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-24 19:56:03,344 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 19:56:03,344 INFO L82 PathProgramCache]: Analyzing trace with hash -275307335, now seen corresponding path program 1 times [2018-01-24 19:56:03,344 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 19:56:03,345 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:03,346 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 19:56:03,346 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:03,346 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 19:56:03,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 19:56:03,365 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 19:56:03,531 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-24 19:56:03,531 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 19:56:03,532 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2018-01-24 19:56:03,532 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 19:56:03,532 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-01-24 19:56:03,533 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-01-24 19:56:03,533 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2018-01-24 19:56:03,533 INFO L87 Difference]: Start difference. First operand 44 states and 49 transitions. Second operand 10 states. [2018-01-24 19:56:03,697 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 19:56:03,698 INFO L93 Difference]: Finished difference Result 60 states and 67 transitions. [2018-01-24 19:56:03,698 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-01-24 19:56:03,698 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 21 [2018-01-24 19:56:03,698 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 19:56:03,699 INFO L225 Difference]: With dead ends: 60 [2018-01-24 19:56:03,699 INFO L226 Difference]: Without dead ends: 57 [2018-01-24 19:56:03,699 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-24 19:56:03,699 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2018-01-24 19:56:03,703 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 52. [2018-01-24 19:56:03,703 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 52 states. [2018-01-24 19:56:03,704 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 61 transitions. [2018-01-24 19:56:03,704 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 61 transitions. Word has length 21 [2018-01-24 19:56:03,704 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 19:56:03,704 INFO L432 AbstractCegarLoop]: Abstraction has 52 states and 61 transitions. [2018-01-24 19:56:03,704 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-01-24 19:56:03,705 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 61 transitions. [2018-01-24 19:56:03,705 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-01-24 19:56:03,705 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 19:56:03,705 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-24 19:56:03,705 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 19:56:03,706 INFO L82 PathProgramCache]: Analyzing trace with hash 1706718631, now seen corresponding path program 1 times [2018-01-24 19:56:03,706 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 19:56:03,706 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:03,706 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 19:56:03,706 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:03,707 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 19:56:03,717 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 19:56:03,717 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 19:56:03,762 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-24 19:56:03,762 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 19:56:03,762 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-01-24 19:56:03,763 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 19:56:03,763 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-24 19:56:03,763 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-24 19:56:03,763 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-01-24 19:56:03,763 INFO L87 Difference]: Start difference. First operand 52 states and 61 transitions. Second operand 7 states. [2018-01-24 19:56:03,869 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 19:56:03,869 INFO L93 Difference]: Finished difference Result 55 states and 64 transitions. [2018-01-24 19:56:03,870 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-01-24 19:56:03,870 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 24 [2018-01-24 19:56:03,870 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 19:56:03,871 INFO L225 Difference]: With dead ends: 55 [2018-01-24 19:56:03,871 INFO L226 Difference]: Without dead ends: 54 [2018-01-24 19:56:03,871 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-24 19:56:03,872 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2018-01-24 19:56:03,876 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 51. [2018-01-24 19:56:03,877 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-01-24 19:56:03,877 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 59 transitions. [2018-01-24 19:56:03,878 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 59 transitions. Word has length 24 [2018-01-24 19:56:03,878 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 19:56:03,878 INFO L432 AbstractCegarLoop]: Abstraction has 51 states and 59 transitions. [2018-01-24 19:56:03,878 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-24 19:56:03,878 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 59 transitions. [2018-01-24 19:56:03,879 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-01-24 19:56:03,879 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 19:56:03,879 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-24 19:56:03,879 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 19:56:03,879 INFO L82 PathProgramCache]: Analyzing trace with hash 1706718632, now seen corresponding path program 1 times [2018-01-24 19:56:03,880 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 19:56:03,880 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:03,881 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 19:56:03,881 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:03,881 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 19:56:03,893 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 19:56:03,894 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 19:56:04,028 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-24 19:56:04,028 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 19:56:04,028 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2018-01-24 19:56:04,028 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 19:56:04,029 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-01-24 19:56:04,029 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-01-24 19:56:04,029 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2018-01-24 19:56:04,030 INFO L87 Difference]: Start difference. First operand 51 states and 59 transitions. Second operand 10 states. [2018-01-24 19:56:04,192 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 19:56:04,192 INFO L93 Difference]: Finished difference Result 57 states and 66 transitions. [2018-01-24 19:56:04,193 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-24 19:56:04,193 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 24 [2018-01-24 19:56:04,193 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 19:56:04,194 INFO L225 Difference]: With dead ends: 57 [2018-01-24 19:56:04,194 INFO L226 Difference]: Without dead ends: 56 [2018-01-24 19:56:04,194 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2018-01-24 19:56:04,194 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2018-01-24 19:56:04,200 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 53. [2018-01-24 19:56:04,200 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 53 states. [2018-01-24 19:56:04,200 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 60 transitions. [2018-01-24 19:56:04,201 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 60 transitions. Word has length 24 [2018-01-24 19:56:04,201 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 19:56:04,201 INFO L432 AbstractCegarLoop]: Abstraction has 53 states and 60 transitions. [2018-01-24 19:56:04,201 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-01-24 19:56:04,201 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 60 transitions. [2018-01-24 19:56:04,202 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-01-24 19:56:04,202 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 19:56:04,202 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-24 19:56:04,202 INFO L371 AbstractCegarLoop]: === Iteration 11 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 19:56:04,203 INFO L82 PathProgramCache]: Analyzing trace with hash 1706720075, now seen corresponding path program 1 times [2018-01-24 19:56:04,203 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 19:56:04,204 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:04,204 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 19:56:04,204 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:04,204 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 19:56:04,218 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 19:56:04,219 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 19:56:04,403 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-24 19:56:04,404 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 19:56:04,404 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-24 19:56:04,405 INFO L199 CegarAbsIntRunner]: Running AI on error trace of length 25 with the following transitions: [2018-01-24 19:56:04,407 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-24 19:56:04,454 INFO L147 AbstractInterpreter]: Using domain VPDomain [2018-01-24 19:56:04,454 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=2) [2018-01-24 19:56:32,656 INFO L259 AbstractInterpreter]: Some error location(s) were reachable [2018-01-24 19:56:32,657 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-24 19:56:32,675 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-01-24 19:56:32,676 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 19:56:32,676 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-24 19:56:32,688 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 19:56:32,688 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-24 19:56:32,717 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 19:56:32,728 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 19:56:32,827 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-24 19:56:32,828 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:32,839 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-24 19:56:32,839 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:32,846 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-24 19:56:32,846 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-01-24 19:56:32,891 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 19:56:32,892 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 19:56:32,893 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-24 19:56:32,894 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:32,907 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 19:56:32,907 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 19:56:32,908 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-24 19:56:32,908 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:32,914 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-24 19:56:32,914 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:30, output treesize:18 [2018-01-24 19:56:33,124 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-24 19:56:33,124 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 19:56:33,325 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-24 19:56:33,325 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:33,330 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-24 19:56:33,339 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-24 19:56:33,339 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:33,340 WARN L307 Elim1Store]: Array PQE input equivalent to true [2018-01-24 19:56:33,340 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:33,344 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 19:56:33,346 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-24 19:56:33,347 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:21, output treesize:3 [2018-01-24 19:56:33,358 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-24 19:56:33,379 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 19:56:33,379 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-24 19:56:33,383 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 19:56:33,383 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-24 19:56:33,415 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 19:56:33,420 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 19:56:33,425 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-24 19:56:33,425 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:33,433 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-24 19:56:33,433 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:33,439 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-24 19:56:33,439 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-01-24 19:56:33,502 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 19:56:33,503 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 19:56:33,504 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-24 19:56:33,505 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:33,516 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 19:56:33,517 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 19:56:33,517 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-24 19:56:33,517 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:33,523 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-24 19:56:33,524 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:30, output treesize:18 [2018-01-24 19:56:33,646 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-24 19:56:33,647 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 19:56:33,703 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-24 19:56:33,704 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:33,707 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-24 19:56:33,715 WARN L307 Elim1Store]: Array PQE input equivalent to true [2018-01-24 19:56:33,715 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:33,717 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-24 19:56:33,717 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:33,725 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 19:56:33,728 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-24 19:56:33,728 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:21, output treesize:3 [2018-01-24 19:56:33,783 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-24 19:56:33,785 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-24 19:56:33,785 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13, 12, 11, 12] total 38 [2018-01-24 19:56:33,785 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-24 19:56:33,786 INFO L409 AbstractCegarLoop]: Interpolant automaton has 24 states [2018-01-24 19:56:33,786 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2018-01-24 19:56:33,787 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=150, Invalid=1332, Unknown=0, NotChecked=0, Total=1482 [2018-01-24 19:56:33,787 INFO L87 Difference]: Start difference. First operand 53 states and 60 transitions. Second operand 24 states. [2018-01-24 19:56:34,477 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 19:56:34,478 INFO L93 Difference]: Finished difference Result 75 states and 85 transitions. [2018-01-24 19:56:34,478 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-01-24 19:56:34,478 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 24 [2018-01-24 19:56:34,478 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 19:56:34,479 INFO L225 Difference]: With dead ends: 75 [2018-01-24 19:56:34,479 INFO L226 Difference]: Without dead ends: 72 [2018-01-24 19:56:34,479 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 61 SyntacticMatches, 9 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 622 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=296, Invalid=1960, Unknown=0, NotChecked=0, Total=2256 [2018-01-24 19:56:34,480 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2018-01-24 19:56:34,485 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 64. [2018-01-24 19:56:34,485 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 64 states. [2018-01-24 19:56:34,485 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 75 transitions. [2018-01-24 19:56:34,486 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 75 transitions. Word has length 24 [2018-01-24 19:56:34,486 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 19:56:34,486 INFO L432 AbstractCegarLoop]: Abstraction has 64 states and 75 transitions. [2018-01-24 19:56:34,486 INFO L433 AbstractCegarLoop]: Interpolant automaton has 24 states. [2018-01-24 19:56:34,486 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 75 transitions. [2018-01-24 19:56:34,486 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2018-01-24 19:56:34,487 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 19:56:34,487 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-24 19:56:34,487 INFO L371 AbstractCegarLoop]: === Iteration 12 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 19:56:34,487 INFO L82 PathProgramCache]: Analyzing trace with hash 1074905977, now seen corresponding path program 2 times [2018-01-24 19:56:34,487 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 19:56:34,488 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:34,488 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 19:56:34,488 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 19:56:34,488 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 19:56:34,506 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 19:56:34,507 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 19:56:34,947 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-24 19:56:34,947 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 19:56:34,947 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-24 19:56:34,947 INFO L183 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-01-24 19:56:34,947 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-01-24 19:56:34,947 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 19:56:34,947 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-24 19:56:34,953 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-24 19:56:34,953 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-01-24 19:56:34,968 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 19:56:34,972 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 19:56:34,974 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-24 19:56:34,977 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 19:56:35,017 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-24 19:56:35,018 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:35,023 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 19:56:35,023 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:18, output treesize:17 [2018-01-24 19:56:35,078 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 19:56:35,079 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 19:56:35,080 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-24 19:56:35,080 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:35,085 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 19:56:35,085 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:22, output treesize:16 [2018-01-24 19:56:35,132 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-24 19:56:35,135 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-24 19:56:35,136 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:35,139 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 19:56:35,149 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-24 19:56:35,149 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:42, output treesize:38 [2018-01-24 19:56:35,191 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-24 19:56:35,194 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-24 19:56:35,194 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:35,199 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 19:56:35,210 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-24 19:56:35,210 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 6 variables, input treesize:52, output treesize:48 [2018-01-24 19:56:37,509 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-24 19:56:37,516 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-24 19:56:37,516 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:37,528 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 19:56:37,537 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-24 19:56:37,538 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-01-24 19:56:37,553 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 19:56:37,570 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-24 19:56:37,570 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 6 variables, input treesize:66, output treesize:43 [2018-01-24 19:56:37,619 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-24 19:56:37,619 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 19:56:38,003 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-24 19:56:38,004 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:38,021 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-24 19:56:38,021 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:38,035 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-24 19:56:38,057 INFO L682 Elim1Store]: detected equality via solver [2018-01-24 19:56:38,058 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-24 19:56:38,059 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:38,068 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 19:56:38,078 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-24 19:56:38,095 INFO L682 Elim1Store]: detected equality via solver [2018-01-24 19:56:38,096 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-24 19:56:38,097 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:38,101 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 19:56:38,110 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-24 19:56:38,110 INFO L202 ElimStorePlain]: Needed 7 recursive calls to eliminate 4 variables, input treesize:103, output treesize:33 [2018-01-24 19:56:38,337 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-24 19:56:38,359 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 19:56:38,359 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-24 19:56:38,364 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-24 19:56:38,364 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-01-24 19:56:38,381 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 19:56:38,411 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 19:56:38,448 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-24 19:56:38,455 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 19:56:38,500 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-24 19:56:38,500 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:38,508 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-24 19:56:38,508 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:38,514 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 19:56:38,514 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:19, output treesize:17 [2018-01-24 19:56:38,603 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 19:56:38,605 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-24 19:56:38,606 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:38,616 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 19:56:38,616 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 19:56:38,617 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-24 19:56:38,617 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:38,623 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 19:56:38,623 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:28, output treesize:21 [2018-01-24 19:56:38,712 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-24 19:56:38,714 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-24 19:56:38,714 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:38,716 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 19:56:38,721 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-24 19:56:38,721 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:29, output treesize:25 [2018-01-24 19:56:38,779 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-24 19:56:38,781 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-24 19:56:38,782 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:38,785 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 19:56:38,792 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-24 19:56:38,792 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:36, output treesize:32 [2018-01-24 19:56:39,025 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-24 19:56:39,031 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-24 19:56:39,031 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-24 19:56:39,040 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-24 19:56:39,041 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:39,043 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 19:56:39,049 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-24 19:56:39,049 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 3 variables, input treesize:38, output treesize:20 [2018-01-24 19:56:39,231 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-24 19:56:39,231 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 19:56:39,635 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-24 19:56:39,643 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-24 19:56:39,643 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:39,644 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 19:56:39,649 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-24 19:56:39,649 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:36, output treesize:25 [2018-01-24 19:56:39,873 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-24 19:56:39,873 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:39,883 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-24 19:56:39,901 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-24 19:56:39,902 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:39,903 WARN L307 Elim1Store]: Array PQE input equivalent to true [2018-01-24 19:56:39,903 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-24 19:56:39,913 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 19:56:39,926 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-24 19:56:39,926 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 6 variables, input treesize:37, output treesize:7 [2018-01-24 19:56:39,962 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-24 19:56:39,964 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-24 19:56:39,964 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 16, 14, 15, 13] total 63 [2018-01-24 19:56:39,964 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-24 19:56:39,965 INFO L409 AbstractCegarLoop]: Interpolant automaton has 28 states [2018-01-24 19:56:39,965 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2018-01-24 19:56:39,966 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=230, Invalid=3801, Unknown=1, NotChecked=0, Total=4032 [2018-01-24 19:56:39,966 INFO L87 Difference]: Start difference. First operand 64 states and 75 transitions. Second operand 28 states. [2018-01-24 19:56:53,815 WARN L146 SmtUtils]: Spent 489ms on a formula simplification. DAG size of input: 69 DAG size of output 61 [2018-01-24 19:56:59,150 WARN L146 SmtUtils]: Spent 5191ms on a formula simplification. DAG size of input: 72 DAG size of output 64 Received shutdown request... [2018-01-24 19:57:05,607 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-01-24 19:57:05,607 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-24 19:57:05,611 WARN L187 ceAbstractionStarter]: Timeout [2018-01-24 19:57:05,611 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 24.01 07:57:05 BoogieIcfgContainer [2018-01-24 19:57:05,611 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-24 19:57:05,612 INFO L168 Benchmark]: Toolchain (without parser) took 64459.40 ms. Allocated memory was 304.1 MB in the beginning and 1.6 GB in the end (delta: 1.2 GB). Free memory was 262.4 MB in the beginning and 869.7 MB in the end (delta: -607.3 MB). Peak memory consumption was 640.5 MB. Max. memory is 5.3 GB. [2018-01-24 19:57:05,612 INFO L168 Benchmark]: CDTParser took 0.15 ms. Allocated memory is still 304.1 MB. Free memory is still 268.4 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-24 19:57:05,612 INFO L168 Benchmark]: CACSL2BoogieTranslator took 204.49 ms. Allocated memory is still 304.1 MB. Free memory was 261.4 MB in the beginning and 251.4 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 5.3 GB. [2018-01-24 19:57:05,612 INFO L168 Benchmark]: Boogie Preprocessor took 42.92 ms. Allocated memory is still 304.1 MB. Free memory was 251.4 MB in the beginning and 249.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-01-24 19:57:05,613 INFO L168 Benchmark]: RCFGBuilder took 318.50 ms. Allocated memory is still 304.1 MB. Free memory was 249.4 MB in the beginning and 229.8 MB in the end (delta: 19.6 MB). Peak memory consumption was 19.6 MB. Max. memory is 5.3 GB. [2018-01-24 19:57:05,613 INFO L168 Benchmark]: TraceAbstraction took 63887.51 ms. Allocated memory was 304.1 MB in the beginning and 1.6 GB in the end (delta: 1.2 GB). Free memory was 229.8 MB in the beginning and 869.7 MB in the end (delta: -639.9 MB). Peak memory consumption was 607.9 MB. Max. memory is 5.3 GB. [2018-01-24 19:57:05,614 INFO L344 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.15 ms. Allocated memory is still 304.1 MB. Free memory is still 268.4 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 204.49 ms. Allocated memory is still 304.1 MB. Free memory was 261.4 MB in the beginning and 251.4 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 42.92 ms. Allocated memory is still 304.1 MB. Free memory was 251.4 MB in the beginning and 249.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 318.50 ms. Allocated memory is still 304.1 MB. Free memory was 249.4 MB in the beginning and 229.8 MB in the end (delta: 19.6 MB). Peak memory consumption was 19.6 MB. Max. memory is 5.3 GB. * TraceAbstraction took 63887.51 ms. Allocated memory was 304.1 MB in the beginning and 1.6 GB in the end (delta: 1.2 GB). Free memory was 229.8 MB in the beginning and 869.7 MB in the end (delta: -639.9 MB). Peak memory consumption was 607.9 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 : 291 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.515130 RENAME_VARIABLES(MILLISECONDS) : 0.328225 UNFREEZE(MILLISECONDS) : 0.000000 CONJOIN(MILLISECONDS) : 1.452193 PROJECTAWAY(MILLISECONDS) : 0.696132 ADD_WEAK_EQUALITY(MILLISECONDS) : 0.066927 DISJOIN(MILLISECONDS) : 0.479836 RENAME_VARIABLES_DISJUNCTIVE(MILLISECONDS) : 0.364150 ADD_EQUALITY(MILLISECONDS) : 0.013940 DISJOIN_DISJUNCTIVE(MILLISECONDS) : 0.000000 ADD_DISEQUALITY(MILLISECONDS) : 0.012673 #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 21 states, 28 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 79. - 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 21 states, 28 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 79. - 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 21 states, 28 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 79. - 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 21 states, 28 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 79. - 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 21 states, 28 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 79. - 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 21 states, 28 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 79. - 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 21 states, 28 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 79. - 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 21 states, 28 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 79. - 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 21 states, 28 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 79. - 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 21 states, 28 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 79. - 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 21 states, 28 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 79. - 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 21 states, 28 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 79. - 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 21 states, 28 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 79. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 54 locations, 13 error locations. TIMEOUT Result, 63.8s OverallTime, 12 OverallIterations, 3 TraceHistogramMax, 27.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 484 SDtfs, 892 SDslu, 1429 SDs, 0 SdLazy, 1259 SolverSat, 171 SolverUnsat, 6 SolverUnknown, 0 SolverNotchecked, 12.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 334 GetRequests, 125 SyntacticMatches, 15 SemanticMatches, 193 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2149 ImplicationChecksByTransitivity, 18.6s 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, 28.2s 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.3s 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_mostprecise.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-24_19-57-05-622.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_mostprecise.epf_AutomizerC.xml/Csv-VPDomainBenchmark-0-2018-01-24_19-57-05-622.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_mostprecise.epf_AutomizerC.xml/Csv-BenchmarkWithCounters-0-2018-01-24_19-57-05-622.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_mostprecise.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-24_19-57-05-622.csv Completed graceful shutdown