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.epf -i ../../../trunk/examples/svcomp/array-memsafety/openbsd_cstrstr-alloca_true-valid-memsafety_true-termination.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-6b94a2f [2018-01-24 15:22:29,919 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-24 15:22:29,920 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-24 15:22:29,936 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-24 15:22:29,936 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-24 15:22:29,937 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-24 15:22:29,938 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-24 15:22:29,940 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-24 15:22:29,942 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-24 15:22:29,943 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-24 15:22:29,944 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-24 15:22:29,944 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-24 15:22:29,945 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-24 15:22:29,946 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-24 15:22:29,947 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-24 15:22:29,950 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-24 15:22:29,952 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-24 15:22:29,954 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-24 15:22:29,956 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-24 15:22:29,957 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-24 15:22:29,959 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-24 15:22:29,960 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-24 15:22:29,960 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-24 15:22:29,961 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-24 15:22:29,962 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-24 15:22:29,963 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-24 15:22:29,963 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-24 15:22:29,964 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-24 15:22:29,964 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-24 15:22:29,964 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-24 15:22:29,965 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-24 15:22:29,966 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.epf [2018-01-24 15:22:29,974 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-24 15:22:29,975 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-24 15:22:29,975 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-24 15:22:29,976 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-24 15:22:29,976 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-24 15:22:29,976 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-24 15:22:29,976 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-24 15:22:29,976 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-24 15:22:29,977 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-24 15:22:29,977 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-24 15:22:29,977 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-24 15:22:29,977 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-24 15:22:29,977 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-24 15:22:29,977 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-01-24 15:22:29,977 INFO L133 SettingsManager]: * Bitprecise bitfields=true [2018-01-24 15:22:29,978 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-01-24 15:22:29,978 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-24 15:22:29,978 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-24 15:22:29,978 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-24 15:22:29,978 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-01-24 15:22:29,978 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-24 15:22:29,978 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-24 15:22:29,979 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-24 15:22:29,979 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-24 15:22:29,979 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-24 15:22:29,979 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-24 15:22:29,980 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-24 15:22:29,980 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-24 15:22:29,980 INFO L133 SettingsManager]: * Trace refinement strategy=TAIPAN [2018-01-24 15:22:29,980 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-24 15:22:29,980 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-24 15:22:29,980 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-24 15:22:29,980 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-01-24 15:22:29,981 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-24 15:22:29,981 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-24 15:22:30,014 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-24 15:22:30,025 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-24 15:22:30,028 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-24 15:22:30,029 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-24 15:22:30,030 INFO L276 PluginConnector]: CDTParser initialized [2018-01-24 15:22:30,030 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/array-memsafety/openbsd_cstrstr-alloca_true-valid-memsafety_true-termination.i [2018-01-24 15:22:30,211 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-24 15:22:30,217 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-24 15:22:30,217 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-24 15:22:30,217 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-24 15:22:30,222 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-24 15:22:30,223 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.01 03:22:30" (1/1) ... [2018-01-24 15:22:30,226 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4545185a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:22:30, skipping insertion in model container [2018-01-24 15:22:30,226 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.01 03:22:30" (1/1) ... [2018-01-24 15:22:30,240 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-24 15:22:30,279 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-24 15:22:30,404 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-24 15:22:30,425 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-24 15:22:30,435 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:22:30 WrapperNode [2018-01-24 15:22:30,435 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-24 15:22:30,436 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-24 15:22:30,436 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-24 15:22:30,436 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-24 15:22:30,452 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:22:30" (1/1) ... [2018-01-24 15:22:30,453 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:22:30" (1/1) ... [2018-01-24 15:22:30,462 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:22:30" (1/1) ... [2018-01-24 15:22:30,462 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:22:30" (1/1) ... [2018-01-24 15:22:30,469 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:22:30" (1/1) ... [2018-01-24 15:22:30,474 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:22:30" (1/1) ... [2018-01-24 15:22:30,490 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:22:30" (1/1) ... [2018-01-24 15:22:30,493 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-24 15:22:30,494 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-24 15:22:30,494 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-24 15:22:30,495 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-24 15:22:30,496 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:22:30" (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 15:22:30,545 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-24 15:22:30,545 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-24 15:22:30,545 INFO L136 BoogieDeclarations]: Found implementation of procedure cstrlen [2018-01-24 15:22:30,545 INFO L136 BoogieDeclarations]: Found implementation of procedure cstrncmp [2018-01-24 15:22:30,545 INFO L136 BoogieDeclarations]: Found implementation of procedure cstrstr [2018-01-24 15:22:30,545 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-24 15:22:30,545 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-01-24 15:22:30,545 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-01-24 15:22:30,546 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-24 15:22:30,546 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-24 15:22:30,546 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-24 15:22:30,546 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-24 15:22:30,546 INFO L128 BoogieDeclarations]: Found specification of procedure cstrlen [2018-01-24 15:22:30,546 INFO L128 BoogieDeclarations]: Found specification of procedure cstrncmp [2018-01-24 15:22:30,546 INFO L128 BoogieDeclarations]: Found specification of procedure cstrstr [2018-01-24 15:22:30,546 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-24 15:22:30,546 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-24 15:22:30,547 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-24 15:22:30,898 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-24 15:22:30,899 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.01 03:22:30 BoogieIcfgContainer [2018-01-24 15:22:30,899 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-24 15:22:30,900 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-24 15:22:30,901 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-24 15:22:30,903 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-24 15:22:30,904 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 24.01 03:22:30" (1/3) ... [2018-01-24 15:22:30,905 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@394b0019 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.01 03:22:30, skipping insertion in model container [2018-01-24 15:22:30,905 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:22:30" (2/3) ... [2018-01-24 15:22:30,906 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@394b0019 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.01 03:22:30, skipping insertion in model container [2018-01-24 15:22:30,906 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.01 03:22:30" (3/3) ... [2018-01-24 15:22:30,908 INFO L105 eAbstractionObserver]: Analyzing ICFG openbsd_cstrstr-alloca_true-valid-memsafety_true-termination.i [2018-01-24 15:22:30,918 INFO L130 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-24 15:22:30,926 INFO L142 ceAbstractionStarter]: Appying trace abstraction to program that has 21 error locations. [2018-01-24 15:22:30,971 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-24 15:22:30,971 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-24 15:22:30,971 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-24 15:22:30,971 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-24 15:22:30,971 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-24 15:22:30,971 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-24 15:22:30,972 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-24 15:22:30,972 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-01-24 15:22:30,972 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-24 15:22:30,989 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states. [2018-01-24 15:22:30,994 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-01-24 15:22:30,994 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:22:30,995 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 15:22:30,995 INFO L371 AbstractCegarLoop]: === Iteration 1 === [cstrlenErr1RequiresViolation, cstrlenErr0RequiresViolation, mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncmpErr1RequiresViolation, cstrncmpErr5RequiresViolation, cstrncmpErr6RequiresViolation, cstrncmpErr0RequiresViolation, cstrncmpErr4RequiresViolation, cstrncmpErr7RequiresViolation, cstrncmpErr2RequiresViolation, cstrncmpErr3RequiresViolation, cstrncmpErr8RequiresViolation, cstrncmpErr9RequiresViolation, cstrstrErr2RequiresViolation, cstrstrErr3RequiresViolation, cstrstrErr1RequiresViolation, cstrstrErr0RequiresViolation]=== [2018-01-24 15:22:30,998 INFO L82 PathProgramCache]: Analyzing trace with hash -718609434, now seen corresponding path program 1 times [2018-01-24 15:22:31,000 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:22:31,041 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:31,042 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:22:31,042 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:31,042 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:22:31,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:22:31,097 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:22:31,217 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 15:22:31,220 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:22:31,221 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-24 15:22:31,221 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:22:31,225 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-24 15:22:31,314 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-24 15:22:31,315 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-24 15:22:31,317 INFO L87 Difference]: Start difference. First operand 90 states. Second operand 4 states. [2018-01-24 15:22:31,471 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:22:31,472 INFO L93 Difference]: Finished difference Result 147 states and 171 transitions. [2018-01-24 15:22:31,472 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-24 15:22:31,474 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 13 [2018-01-24 15:22:31,474 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:22:31,484 INFO L225 Difference]: With dead ends: 147 [2018-01-24 15:22:31,484 INFO L226 Difference]: Without dead ends: 86 [2018-01-24 15:22:31,489 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 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 15:22:31,504 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2018-01-24 15:22:31,524 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 86. [2018-01-24 15:22:31,525 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 86 states. [2018-01-24 15:22:31,527 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 96 transitions. [2018-01-24 15:22:31,529 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 96 transitions. Word has length 13 [2018-01-24 15:22:31,529 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:22:31,529 INFO L432 AbstractCegarLoop]: Abstraction has 86 states and 96 transitions. [2018-01-24 15:22:31,529 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-24 15:22:31,529 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 96 transitions. [2018-01-24 15:22:31,530 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-01-24 15:22:31,530 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:22:31,530 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 15:22:31,530 INFO L371 AbstractCegarLoop]: === Iteration 2 === [cstrlenErr1RequiresViolation, cstrlenErr0RequiresViolation, mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncmpErr1RequiresViolation, cstrncmpErr5RequiresViolation, cstrncmpErr6RequiresViolation, cstrncmpErr0RequiresViolation, cstrncmpErr4RequiresViolation, cstrncmpErr7RequiresViolation, cstrncmpErr2RequiresViolation, cstrncmpErr3RequiresViolation, cstrncmpErr8RequiresViolation, cstrncmpErr9RequiresViolation, cstrstrErr2RequiresViolation, cstrstrErr3RequiresViolation, cstrstrErr1RequiresViolation, cstrstrErr0RequiresViolation]=== [2018-01-24 15:22:31,530 INFO L82 PathProgramCache]: Analyzing trace with hash -718609433, now seen corresponding path program 1 times [2018-01-24 15:22:31,530 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:22:31,531 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:31,531 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:22:31,532 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:31,532 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:22:31,550 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:22:31,551 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:22:31,700 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 15:22:31,700 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:22:31,701 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-24 15:22:31,701 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:22:31,703 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-24 15:22:31,703 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-24 15:22:31,703 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-01-24 15:22:31,703 INFO L87 Difference]: Start difference. First operand 86 states and 96 transitions. Second operand 6 states. [2018-01-24 15:22:31,857 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:22:31,857 INFO L93 Difference]: Finished difference Result 86 states and 96 transitions. [2018-01-24 15:22:31,857 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-24 15:22:31,857 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 13 [2018-01-24 15:22:31,858 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:22:31,859 INFO L225 Difference]: With dead ends: 86 [2018-01-24 15:22:31,859 INFO L226 Difference]: Without dead ends: 85 [2018-01-24 15:22:31,860 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=19, Invalid=23, Unknown=0, NotChecked=0, Total=42 [2018-01-24 15:22:31,861 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2018-01-24 15:22:31,869 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 85. [2018-01-24 15:22:31,869 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 85 states. [2018-01-24 15:22:31,871 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 85 states to 85 states and 95 transitions. [2018-01-24 15:22:31,871 INFO L78 Accepts]: Start accepts. Automaton has 85 states and 95 transitions. Word has length 13 [2018-01-24 15:22:31,871 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:22:31,871 INFO L432 AbstractCegarLoop]: Abstraction has 85 states and 95 transitions. [2018-01-24 15:22:31,872 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-24 15:22:31,872 INFO L276 IsEmpty]: Start isEmpty. Operand 85 states and 95 transitions. [2018-01-24 15:22:31,872 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2018-01-24 15:22:31,872 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:22:31,872 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 15:22:31,873 INFO L371 AbstractCegarLoop]: === Iteration 3 === [cstrlenErr1RequiresViolation, cstrlenErr0RequiresViolation, mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncmpErr1RequiresViolation, cstrncmpErr5RequiresViolation, cstrncmpErr6RequiresViolation, cstrncmpErr0RequiresViolation, cstrncmpErr4RequiresViolation, cstrncmpErr7RequiresViolation, cstrncmpErr2RequiresViolation, cstrncmpErr3RequiresViolation, cstrncmpErr8RequiresViolation, cstrncmpErr9RequiresViolation, cstrstrErr2RequiresViolation, cstrstrErr3RequiresViolation, cstrstrErr1RequiresViolation, cstrstrErr0RequiresViolation]=== [2018-01-24 15:22:31,873 INFO L82 PathProgramCache]: Analyzing trace with hash -802055959, now seen corresponding path program 1 times [2018-01-24 15:22:31,873 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:22:31,874 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:31,874 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:22:31,874 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:31,875 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:22:31,888 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:22:31,889 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:22:31,922 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 15:22:31,922 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:22:31,922 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-24 15:22:31,922 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:22:31,923 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-24 15:22:31,923 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-24 15:22:31,923 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-24 15:22:31,923 INFO L87 Difference]: Start difference. First operand 85 states and 95 transitions. Second operand 4 states. [2018-01-24 15:22:31,999 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:22:31,999 INFO L93 Difference]: Finished difference Result 85 states and 95 transitions. [2018-01-24 15:22:31,999 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-24 15:22:32,000 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 14 [2018-01-24 15:22:32,000 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:22:32,001 INFO L225 Difference]: With dead ends: 85 [2018-01-24 15:22:32,001 INFO L226 Difference]: Without dead ends: 84 [2018-01-24 15:22:32,001 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 15:22:32,002 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2018-01-24 15:22:32,008 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 84. [2018-01-24 15:22:32,008 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 84 states. [2018-01-24 15:22:32,010 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 94 transitions. [2018-01-24 15:22:32,010 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 94 transitions. Word has length 14 [2018-01-24 15:22:32,010 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:22:32,010 INFO L432 AbstractCegarLoop]: Abstraction has 84 states and 94 transitions. [2018-01-24 15:22:32,010 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-24 15:22:32,011 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 94 transitions. [2018-01-24 15:22:32,011 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2018-01-24 15:22:32,011 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:22:32,011 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 15:22:32,011 INFO L371 AbstractCegarLoop]: === Iteration 4 === [cstrlenErr1RequiresViolation, cstrlenErr0RequiresViolation, mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncmpErr1RequiresViolation, cstrncmpErr5RequiresViolation, cstrncmpErr6RequiresViolation, cstrncmpErr0RequiresViolation, cstrncmpErr4RequiresViolation, cstrncmpErr7RequiresViolation, cstrncmpErr2RequiresViolation, cstrncmpErr3RequiresViolation, cstrncmpErr8RequiresViolation, cstrncmpErr9RequiresViolation, cstrstrErr2RequiresViolation, cstrstrErr3RequiresViolation, cstrstrErr1RequiresViolation, cstrstrErr0RequiresViolation]=== [2018-01-24 15:22:32,012 INFO L82 PathProgramCache]: Analyzing trace with hash -802055958, now seen corresponding path program 1 times [2018-01-24 15:22:32,012 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:22:32,013 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:32,013 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:22:32,013 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:32,013 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:22:32,026 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:22:32,027 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:22:32,116 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 15:22:32,116 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:22:32,116 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-24 15:22:32,116 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:22:32,116 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-24 15:22:32,117 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-24 15:22:32,117 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-24 15:22:32,117 INFO L87 Difference]: Start difference. First operand 84 states and 94 transitions. Second operand 5 states. [2018-01-24 15:22:32,153 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:22:32,153 INFO L93 Difference]: Finished difference Result 84 states and 94 transitions. [2018-01-24 15:22:32,154 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-24 15:22:32,154 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 14 [2018-01-24 15:22:32,154 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:22:32,155 INFO L225 Difference]: With dead ends: 84 [2018-01-24 15:22:32,155 INFO L226 Difference]: Without dead ends: 83 [2018-01-24 15:22:32,156 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 15:22:32,156 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 83 states. [2018-01-24 15:22:32,160 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 83 to 83. [2018-01-24 15:22:32,160 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 83 states. [2018-01-24 15:22:32,161 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 93 transitions. [2018-01-24 15:22:32,161 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 93 transitions. Word has length 14 [2018-01-24 15:22:32,161 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:22:32,161 INFO L432 AbstractCegarLoop]: Abstraction has 83 states and 93 transitions. [2018-01-24 15:22:32,161 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-24 15:22:32,161 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 93 transitions. [2018-01-24 15:22:32,162 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2018-01-24 15:22:32,162 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:22:32,162 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 15:22:32,162 INFO L371 AbstractCegarLoop]: === Iteration 5 === [cstrlenErr1RequiresViolation, cstrlenErr0RequiresViolation, mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncmpErr1RequiresViolation, cstrncmpErr5RequiresViolation, cstrncmpErr6RequiresViolation, cstrncmpErr0RequiresViolation, cstrncmpErr4RequiresViolation, cstrncmpErr7RequiresViolation, cstrncmpErr2RequiresViolation, cstrncmpErr3RequiresViolation, cstrncmpErr8RequiresViolation, cstrncmpErr9RequiresViolation, cstrstrErr2RequiresViolation, cstrstrErr3RequiresViolation, cstrstrErr1RequiresViolation, cstrstrErr0RequiresViolation]=== [2018-01-24 15:22:32,162 INFO L82 PathProgramCache]: Analyzing trace with hash -1145880583, now seen corresponding path program 1 times [2018-01-24 15:22:32,162 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:22:32,163 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:32,163 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:22:32,163 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:32,163 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:22:32,174 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:22:32,174 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:22:32,205 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 15:22:32,205 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:22:32,205 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-24 15:22:32,205 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:22:32,206 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-24 15:22:32,206 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-24 15:22:32,206 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-24 15:22:32,206 INFO L87 Difference]: Start difference. First operand 83 states and 93 transitions. Second operand 5 states. [2018-01-24 15:22:32,288 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:22:32,288 INFO L93 Difference]: Finished difference Result 83 states and 93 transitions. [2018-01-24 15:22:32,288 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-24 15:22:32,288 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 17 [2018-01-24 15:22:32,289 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:22:32,290 INFO L225 Difference]: With dead ends: 83 [2018-01-24 15:22:32,290 INFO L226 Difference]: Without dead ends: 82 [2018-01-24 15:22:32,290 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-01-24 15:22:32,291 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2018-01-24 15:22:32,297 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 82. [2018-01-24 15:22:32,297 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 82 states. [2018-01-24 15:22:32,298 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 92 transitions. [2018-01-24 15:22:32,299 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 92 transitions. Word has length 17 [2018-01-24 15:22:32,299 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:22:32,299 INFO L432 AbstractCegarLoop]: Abstraction has 82 states and 92 transitions. [2018-01-24 15:22:32,299 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-24 15:22:32,299 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 92 transitions. [2018-01-24 15:22:32,300 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2018-01-24 15:22:32,300 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:22:32,300 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 15:22:32,300 INFO L371 AbstractCegarLoop]: === Iteration 6 === [cstrlenErr1RequiresViolation, cstrlenErr0RequiresViolation, mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncmpErr1RequiresViolation, cstrncmpErr5RequiresViolation, cstrncmpErr6RequiresViolation, cstrncmpErr0RequiresViolation, cstrncmpErr4RequiresViolation, cstrncmpErr7RequiresViolation, cstrncmpErr2RequiresViolation, cstrncmpErr3RequiresViolation, cstrncmpErr8RequiresViolation, cstrncmpErr9RequiresViolation, cstrstrErr2RequiresViolation, cstrstrErr3RequiresViolation, cstrstrErr1RequiresViolation, cstrstrErr0RequiresViolation]=== [2018-01-24 15:22:32,301 INFO L82 PathProgramCache]: Analyzing trace with hash -1145880582, now seen corresponding path program 1 times [2018-01-24 15:22:32,301 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:22:32,302 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:32,302 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:22:32,302 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:32,302 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:22:32,314 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:22:32,315 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:22:32,381 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 15:22:32,382 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:22:32,382 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-24 15:22:32,382 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:22:32,382 INFO L409 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-01-24 15:22:32,382 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-01-24 15:22:32,382 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2018-01-24 15:22:32,383 INFO L87 Difference]: Start difference. First operand 82 states and 92 transitions. Second operand 8 states. [2018-01-24 15:22:32,505 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:22:32,505 INFO L93 Difference]: Finished difference Result 82 states and 92 transitions. [2018-01-24 15:22:32,506 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-01-24 15:22:32,506 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 17 [2018-01-24 15:22:32,506 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:22:32,507 INFO L225 Difference]: With dead ends: 82 [2018-01-24 15:22:32,507 INFO L226 Difference]: Without dead ends: 81 [2018-01-24 15:22:32,507 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2018-01-24 15:22:32,507 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2018-01-24 15:22:32,514 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 81. [2018-01-24 15:22:32,514 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 81 states. [2018-01-24 15:22:32,515 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 91 transitions. [2018-01-24 15:22:32,515 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 91 transitions. Word has length 17 [2018-01-24 15:22:32,515 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:22:32,515 INFO L432 AbstractCegarLoop]: Abstraction has 81 states and 91 transitions. [2018-01-24 15:22:32,516 INFO L433 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-01-24 15:22:32,516 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 91 transitions. [2018-01-24 15:22:32,516 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-01-24 15:22:32,517 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:22:32,517 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] [2018-01-24 15:22:32,517 INFO L371 AbstractCegarLoop]: === Iteration 7 === [cstrlenErr1RequiresViolation, cstrlenErr0RequiresViolation, mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncmpErr1RequiresViolation, cstrncmpErr5RequiresViolation, cstrncmpErr6RequiresViolation, cstrncmpErr0RequiresViolation, cstrncmpErr4RequiresViolation, cstrncmpErr7RequiresViolation, cstrncmpErr2RequiresViolation, cstrncmpErr3RequiresViolation, cstrncmpErr8RequiresViolation, cstrncmpErr9RequiresViolation, cstrstrErr2RequiresViolation, cstrstrErr3RequiresViolation, cstrstrErr1RequiresViolation, cstrstrErr0RequiresViolation]=== [2018-01-24 15:22:32,517 INFO L82 PathProgramCache]: Analyzing trace with hash -1883098626, now seen corresponding path program 1 times [2018-01-24 15:22:32,517 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:22:32,519 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:32,519 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:22:32,519 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:32,519 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:22:32,532 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:22:32,533 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:22:32,635 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 15:22:32,635 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:22:32,635 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-01-24 15:22:32,635 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:22:32,636 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-24 15:22:32,636 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-24 15:22:32,636 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-01-24 15:22:32,637 INFO L87 Difference]: Start difference. First operand 81 states and 91 transitions. Second operand 7 states. [2018-01-24 15:22:32,818 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:22:32,819 INFO L93 Difference]: Finished difference Result 81 states and 91 transitions. [2018-01-24 15:22:32,819 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-01-24 15:22:32,819 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 23 [2018-01-24 15:22:32,819 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:22:32,820 INFO L225 Difference]: With dead ends: 81 [2018-01-24 15:22:32,820 INFO L226 Difference]: Without dead ends: 80 [2018-01-24 15:22:32,821 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2018-01-24 15:22:32,821 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2018-01-24 15:22:32,826 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 80. [2018-01-24 15:22:32,827 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 80 states. [2018-01-24 15:22:32,827 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 90 transitions. [2018-01-24 15:22:32,827 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 90 transitions. Word has length 23 [2018-01-24 15:22:32,828 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:22:32,828 INFO L432 AbstractCegarLoop]: Abstraction has 80 states and 90 transitions. [2018-01-24 15:22:32,828 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-24 15:22:32,828 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 90 transitions. [2018-01-24 15:22:32,828 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-01-24 15:22:32,828 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:22:32,828 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] [2018-01-24 15:22:32,829 INFO L371 AbstractCegarLoop]: === Iteration 8 === [cstrlenErr1RequiresViolation, cstrlenErr0RequiresViolation, mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncmpErr1RequiresViolation, cstrncmpErr5RequiresViolation, cstrncmpErr6RequiresViolation, cstrncmpErr0RequiresViolation, cstrncmpErr4RequiresViolation, cstrncmpErr7RequiresViolation, cstrncmpErr2RequiresViolation, cstrncmpErr3RequiresViolation, cstrncmpErr8RequiresViolation, cstrncmpErr9RequiresViolation, cstrstrErr2RequiresViolation, cstrstrErr3RequiresViolation, cstrstrErr1RequiresViolation, cstrstrErr0RequiresViolation]=== [2018-01-24 15:22:32,829 INFO L82 PathProgramCache]: Analyzing trace with hash -1883098625, now seen corresponding path program 1 times [2018-01-24 15:22:32,829 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:22:32,829 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:32,830 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:22:32,830 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:32,830 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:22:32,846 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:22:32,847 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:22:32,972 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 15:22:32,973 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:22:32,973 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2018-01-24 15:22:32,973 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:22:32,973 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-01-24 15:22:32,974 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-01-24 15:22:32,974 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2018-01-24 15:22:32,974 INFO L87 Difference]: Start difference. First operand 80 states and 90 transitions. Second operand 10 states. [2018-01-24 15:22:33,144 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:22:33,145 INFO L93 Difference]: Finished difference Result 165 states and 182 transitions. [2018-01-24 15:22:33,145 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-01-24 15:22:33,145 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 23 [2018-01-24 15:22:33,145 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:22:33,148 INFO L225 Difference]: With dead ends: 165 [2018-01-24 15:22:33,148 INFO L226 Difference]: Without dead ends: 104 [2018-01-24 15:22:33,149 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 35 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=60, Invalid=212, Unknown=0, NotChecked=0, Total=272 [2018-01-24 15:22:33,149 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2018-01-24 15:22:33,154 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 94. [2018-01-24 15:22:33,154 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 94 states. [2018-01-24 15:22:33,154 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 104 transitions. [2018-01-24 15:22:33,154 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 104 transitions. Word has length 23 [2018-01-24 15:22:33,155 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:22:33,155 INFO L432 AbstractCegarLoop]: Abstraction has 94 states and 104 transitions. [2018-01-24 15:22:33,155 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-01-24 15:22:33,155 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 104 transitions. [2018-01-24 15:22:33,156 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-01-24 15:22:33,156 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:22:33,156 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] [2018-01-24 15:22:33,156 INFO L371 AbstractCegarLoop]: === Iteration 9 === [cstrlenErr1RequiresViolation, cstrlenErr0RequiresViolation, mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncmpErr1RequiresViolation, cstrncmpErr5RequiresViolation, cstrncmpErr6RequiresViolation, cstrncmpErr0RequiresViolation, cstrncmpErr4RequiresViolation, cstrncmpErr7RequiresViolation, cstrncmpErr2RequiresViolation, cstrncmpErr3RequiresViolation, cstrncmpErr8RequiresViolation, cstrncmpErr9RequiresViolation, cstrstrErr2RequiresViolation, cstrstrErr3RequiresViolation, cstrstrErr1RequiresViolation, cstrstrErr0RequiresViolation]=== [2018-01-24 15:22:33,156 INFO L82 PathProgramCache]: Analyzing trace with hash 1390800317, now seen corresponding path program 1 times [2018-01-24 15:22:33,156 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:22:33,157 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:33,157 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:22:33,157 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:33,157 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:22:33,174 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:22:33,175 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:22:33,633 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 15:22:33,633 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:22:33,633 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [15] imperfect sequences [] total 15 [2018-01-24 15:22:33,633 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:22:33,633 INFO L409 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-01-24 15:22:33,634 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-01-24 15:22:33,634 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=205, Unknown=0, NotChecked=0, Total=240 [2018-01-24 15:22:33,634 INFO L87 Difference]: Start difference. First operand 94 states and 104 transitions. Second operand 16 states. [2018-01-24 15:22:34,458 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:22:34,458 INFO L93 Difference]: Finished difference Result 153 states and 170 transitions. [2018-01-24 15:22:34,459 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-01-24 15:22:34,459 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 23 [2018-01-24 15:22:34,459 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:22:34,461 INFO L225 Difference]: With dead ends: 153 [2018-01-24 15:22:34,462 INFO L226 Difference]: Without dead ends: 152 [2018-01-24 15:22:34,463 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 1 SyntacticMatches, 2 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 128 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=119, Invalid=637, Unknown=0, NotChecked=0, Total=756 [2018-01-24 15:22:34,464 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 152 states. [2018-01-24 15:22:34,480 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 152 to 131. [2018-01-24 15:22:34,480 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 131 states. [2018-01-24 15:22:34,481 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 131 states to 131 states and 151 transitions. [2018-01-24 15:22:34,481 INFO L78 Accepts]: Start accepts. Automaton has 131 states and 151 transitions. Word has length 23 [2018-01-24 15:22:34,482 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:22:34,482 INFO L432 AbstractCegarLoop]: Abstraction has 131 states and 151 transitions. [2018-01-24 15:22:34,482 INFO L433 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-01-24 15:22:34,482 INFO L276 IsEmpty]: Start isEmpty. Operand 131 states and 151 transitions. [2018-01-24 15:22:34,482 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-01-24 15:22:34,482 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:22:34,483 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] [2018-01-24 15:22:34,483 INFO L371 AbstractCegarLoop]: === Iteration 10 === [cstrlenErr1RequiresViolation, cstrlenErr0RequiresViolation, mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncmpErr1RequiresViolation, cstrncmpErr5RequiresViolation, cstrncmpErr6RequiresViolation, cstrncmpErr0RequiresViolation, cstrncmpErr4RequiresViolation, cstrncmpErr7RequiresViolation, cstrncmpErr2RequiresViolation, cstrncmpErr3RequiresViolation, cstrncmpErr8RequiresViolation, cstrncmpErr9RequiresViolation, cstrstrErr2RequiresViolation, cstrstrErr3RequiresViolation, cstrstrErr1RequiresViolation, cstrstrErr0RequiresViolation]=== [2018-01-24 15:22:34,483 INFO L82 PathProgramCache]: Analyzing trace with hash -197547585, now seen corresponding path program 1 times [2018-01-24 15:22:34,483 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:22:34,484 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:34,484 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:22:34,484 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:34,484 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:22:34,496 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:22:34,497 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:22:34,779 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 15:22:34,779 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:22:34,779 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2018-01-24 15:22:34,780 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:22:34,780 INFO L409 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-01-24 15:22:34,780 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-01-24 15:22:34,780 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2018-01-24 15:22:34,780 INFO L87 Difference]: Start difference. First operand 131 states and 151 transitions. Second operand 13 states. [2018-01-24 15:22:35,192 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:22:35,192 INFO L93 Difference]: Finished difference Result 150 states and 172 transitions. [2018-01-24 15:22:35,192 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-01-24 15:22:35,192 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 23 [2018-01-24 15:22:35,193 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:22:35,194 INFO L225 Difference]: With dead ends: 150 [2018-01-24 15:22:35,194 INFO L226 Difference]: Without dead ends: 149 [2018-01-24 15:22:35,195 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 68 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=79, Invalid=383, Unknown=0, NotChecked=0, Total=462 [2018-01-24 15:22:35,195 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 149 states. [2018-01-24 15:22:35,204 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 149 to 96. [2018-01-24 15:22:35,204 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 96 states. [2018-01-24 15:22:35,205 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 106 transitions. [2018-01-24 15:22:35,205 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 106 transitions. Word has length 23 [2018-01-24 15:22:35,205 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:22:35,205 INFO L432 AbstractCegarLoop]: Abstraction has 96 states and 106 transitions. [2018-01-24 15:22:35,206 INFO L433 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-01-24 15:22:35,206 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 106 transitions. [2018-01-24 15:22:35,207 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2018-01-24 15:22:35,207 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:22:35,207 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, 1, 1, 1] [2018-01-24 15:22:35,207 INFO L371 AbstractCegarLoop]: === Iteration 11 === [cstrlenErr1RequiresViolation, cstrlenErr0RequiresViolation, mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncmpErr1RequiresViolation, cstrncmpErr5RequiresViolation, cstrncmpErr6RequiresViolation, cstrncmpErr0RequiresViolation, cstrncmpErr4RequiresViolation, cstrncmpErr7RequiresViolation, cstrncmpErr2RequiresViolation, cstrncmpErr3RequiresViolation, cstrncmpErr8RequiresViolation, cstrncmpErr9RequiresViolation, cstrstrErr2RequiresViolation, cstrstrErr3RequiresViolation, cstrstrErr1RequiresViolation, cstrstrErr0RequiresViolation]=== [2018-01-24 15:22:35,208 INFO L82 PathProgramCache]: Analyzing trace with hash 1853436480, now seen corresponding path program 1 times [2018-01-24 15:22:35,208 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:22:35,209 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:35,209 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:22:35,209 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:35,209 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:22:35,222 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:22:35,223 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:22:35,441 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 15:22:35,441 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:22:35,441 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-24 15:22:35,442 INFO L199 CegarAbsIntRunner]: Running AI on error trace of length 28 with the following transitions: [2018-01-24 15:22:35,444 INFO L201 CegarAbsIntRunner]: [0], [1], [2], [6], [7], [9], [14], [16], [25], [28], [36], [38], [39], [40], [41], [42], [45], [104], [105], [108], [111], [155], [156], [157], [159], [161] [2018-01-24 15:22:35,491 INFO L147 AbstractInterpreter]: Using domain VPDomain [2018-01-24 15:22:35,491 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=2) [2018-01-24 15:22:37,197 INFO L259 AbstractInterpreter]: Some error location(s) were reachable [2018-01-24 15:22:37,199 INFO L268 AbstractInterpreter]: Visited 26 different actions 31 times. Merged at 5 different actions 5 times. Never widened. Found 1 fixpoints after 1 different actions. Largest state had 24 variables. [2018-01-24 15:22:37,215 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-01-24 15:22:37,215 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:22:37,215 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 15:22:37,228 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:22:37,228 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-24 15:22:37,271 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:22:37,282 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 15:22:37,321 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 15:22:37,322 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:22:37,346 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:22:37,346 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:10, output treesize:9 [2018-01-24 15:22:37,355 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 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 15 treesize of output 12 [2018-01-24 15:22:37,358 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 12 treesize of output 11 [2018-01-24 15:22:37,358 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:22:37,360 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:22:37,362 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:22:37,362 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:15, output treesize:11 [2018-01-24 15:22:37,564 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 19 treesize of output 15 [2018-01-24 15:22:37,584 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 12 [2018-01-24 15:22:37,584 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-24 15:22:37,588 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 15:22:37,605 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-24 15:22:37,605 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:29, output treesize:34 [2018-01-24 15:22:37,708 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 15:22:37,709 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 15:22:38,256 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 13 treesize of output 11 [2018-01-24 15:22:38,271 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 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 5 treesize of output 3 [2018-01-24 15:22:38,272 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:22:38,274 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:22:38,283 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-24 15:22:38,283 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:31, output treesize:35 [2018-01-24 15:22:38,428 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 15:22:38,459 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:22:38,459 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 15:22:38,463 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:22:38,464 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-24 15:22:38,529 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:22:38,534 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 15:22:38,538 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 15:22:38,539 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:22:38,542 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:22:38,542 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:10, output treesize:9 [2018-01-24 15:22:38,547 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 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 15 treesize of output 12 [2018-01-24 15:22:38,549 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 12 treesize of output 11 [2018-01-24 15:22:38,549 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:22:38,550 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:22:38,551 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:22:38,551 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:15, output treesize:11 [2018-01-24 15:22:38,558 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 19 treesize of output 15 [2018-01-24 15:22:38,588 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 12 [2018-01-24 15:22:38,589 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-24 15:22:38,597 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 15:22:38,656 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-24 15:22:38,656 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:29, output treesize:34 [2018-01-24 15:22:38,659 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 15:22:38,659 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 15:22:38,776 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 13 treesize of output 11 [2018-01-24 15:22:38,792 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 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 5 treesize of output 3 [2018-01-24 15:22:38,792 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:22:38,794 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:22:38,799 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-24 15:22:38,799 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:31, output treesize:35 [2018-01-24 15:22:38,806 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 15:22:38,808 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-24 15:22:38,808 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12, 12, 12, 12] total 32 [2018-01-24 15:22:38,808 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-24 15:22:38,808 INFO L409 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-01-24 15:22:38,808 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-01-24 15:22:38,809 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=102, Invalid=954, Unknown=0, NotChecked=0, Total=1056 [2018-01-24 15:22:38,809 INFO L87 Difference]: Start difference. First operand 96 states and 106 transitions. Second operand 22 states. [2018-01-24 15:22:39,725 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:22:39,725 INFO L93 Difference]: Finished difference Result 101 states and 112 transitions. [2018-01-24 15:22:39,725 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-01-24 15:22:39,726 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 27 [2018-01-24 15:22:39,726 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:22:39,727 INFO L225 Difference]: With dead ends: 101 [2018-01-24 15:22:39,727 INFO L226 Difference]: Without dead ends: 100 [2018-01-24 15:22:39,728 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 84 SyntacticMatches, 3 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 313 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=273, Invalid=1889, Unknown=0, NotChecked=0, Total=2162 [2018-01-24 15:22:39,728 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2018-01-24 15:22:39,736 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 93. [2018-01-24 15:22:39,736 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 93 states. [2018-01-24 15:22:39,736 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 103 transitions. [2018-01-24 15:22:39,736 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 103 transitions. Word has length 27 [2018-01-24 15:22:39,737 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:22:39,737 INFO L432 AbstractCegarLoop]: Abstraction has 93 states and 103 transitions. [2018-01-24 15:22:39,737 INFO L433 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-01-24 15:22:39,737 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 103 transitions. [2018-01-24 15:22:39,737 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2018-01-24 15:22:39,737 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:22:39,738 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, 1, 1, 1, 1] [2018-01-24 15:22:39,738 INFO L371 AbstractCegarLoop]: === Iteration 12 === [cstrlenErr1RequiresViolation, cstrlenErr0RequiresViolation, mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncmpErr1RequiresViolation, cstrncmpErr5RequiresViolation, cstrncmpErr6RequiresViolation, cstrncmpErr0RequiresViolation, cstrncmpErr4RequiresViolation, cstrncmpErr7RequiresViolation, cstrncmpErr2RequiresViolation, cstrncmpErr3RequiresViolation, cstrncmpErr8RequiresViolation, cstrncmpErr9RequiresViolation, cstrstrErr2RequiresViolation, cstrstrErr3RequiresViolation, cstrstrErr1RequiresViolation, cstrstrErr0RequiresViolation]=== [2018-01-24 15:22:39,738 INFO L82 PathProgramCache]: Analyzing trace with hash -1699013504, now seen corresponding path program 1 times [2018-01-24 15:22:39,738 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:22:39,739 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:39,739 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:22:39,739 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:39,739 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:22:39,753 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:22:39,754 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:22:39,870 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 15:22:39,871 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:22:39,871 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-24 15:22:39,871 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:22:39,871 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-24 15:22:39,871 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-24 15:22:39,872 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-24 15:22:39,872 INFO L87 Difference]: Start difference. First operand 93 states and 103 transitions. Second operand 6 states. [2018-01-24 15:22:40,060 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:22:40,061 INFO L93 Difference]: Finished difference Result 93 states and 103 transitions. [2018-01-24 15:22:40,061 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-01-24 15:22:40,061 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 28 [2018-01-24 15:22:40,061 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:22:40,062 INFO L225 Difference]: With dead ends: 93 [2018-01-24 15:22:40,062 INFO L226 Difference]: Without dead ends: 68 [2018-01-24 15:22:40,062 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2018-01-24 15:22:40,062 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 68 states. [2018-01-24 15:22:40,068 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 68 to 68. [2018-01-24 15:22:40,068 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 68 states. [2018-01-24 15:22:40,068 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 75 transitions. [2018-01-24 15:22:40,068 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 75 transitions. Word has length 28 [2018-01-24 15:22:40,068 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:22:40,069 INFO L432 AbstractCegarLoop]: Abstraction has 68 states and 75 transitions. [2018-01-24 15:22:40,069 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-24 15:22:40,069 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 75 transitions. [2018-01-24 15:22:40,069 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2018-01-24 15:22:40,069 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:22:40,069 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, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 15:22:40,069 INFO L371 AbstractCegarLoop]: === Iteration 13 === [cstrlenErr1RequiresViolation, cstrlenErr0RequiresViolation, mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncmpErr1RequiresViolation, cstrncmpErr5RequiresViolation, cstrncmpErr6RequiresViolation, cstrncmpErr0RequiresViolation, cstrncmpErr4RequiresViolation, cstrncmpErr7RequiresViolation, cstrncmpErr2RequiresViolation, cstrncmpErr3RequiresViolation, cstrncmpErr8RequiresViolation, cstrncmpErr9RequiresViolation, cstrstrErr2RequiresViolation, cstrstrErr3RequiresViolation, cstrstrErr1RequiresViolation, cstrstrErr0RequiresViolation]=== [2018-01-24 15:22:40,070 INFO L82 PathProgramCache]: Analyzing trace with hash 1948682038, now seen corresponding path program 1 times [2018-01-24 15:22:40,070 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:22:40,070 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:40,070 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:22:40,070 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:40,070 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:22:40,079 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:22:40,080 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:22:40,140 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 15:22:40,140 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:22:40,140 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-24 15:22:40,140 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:22:40,141 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-24 15:22:40,141 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-24 15:22:40,141 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-24 15:22:40,141 INFO L87 Difference]: Start difference. First operand 68 states and 75 transitions. Second operand 6 states. [2018-01-24 15:22:40,391 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:22:40,391 INFO L93 Difference]: Finished difference Result 68 states and 75 transitions. [2018-01-24 15:22:40,392 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-24 15:22:40,392 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 31 [2018-01-24 15:22:40,392 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:22:40,393 INFO L225 Difference]: With dead ends: 68 [2018-01-24 15:22:40,393 INFO L226 Difference]: Without dead ends: 67 [2018-01-24 15:22:40,393 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 15:22:40,393 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2018-01-24 15:22:40,399 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 67. [2018-01-24 15:22:40,399 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 67 states. [2018-01-24 15:22:40,400 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 74 transitions. [2018-01-24 15:22:40,400 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 74 transitions. Word has length 31 [2018-01-24 15:22:40,400 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:22:40,401 INFO L432 AbstractCegarLoop]: Abstraction has 67 states and 74 transitions. [2018-01-24 15:22:40,401 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-24 15:22:40,401 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 74 transitions. [2018-01-24 15:22:40,402 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2018-01-24 15:22:40,402 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:22:40,402 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, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 15:22:40,402 INFO L371 AbstractCegarLoop]: === Iteration 14 === [cstrlenErr1RequiresViolation, cstrlenErr0RequiresViolation, mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncmpErr1RequiresViolation, cstrncmpErr5RequiresViolation, cstrncmpErr6RequiresViolation, cstrncmpErr0RequiresViolation, cstrncmpErr4RequiresViolation, cstrncmpErr7RequiresViolation, cstrncmpErr2RequiresViolation, cstrncmpErr3RequiresViolation, cstrncmpErr8RequiresViolation, cstrncmpErr9RequiresViolation, cstrstrErr2RequiresViolation, cstrstrErr3RequiresViolation, cstrstrErr1RequiresViolation, cstrstrErr0RequiresViolation]=== [2018-01-24 15:22:40,402 INFO L82 PathProgramCache]: Analyzing trace with hash 1948682039, now seen corresponding path program 1 times [2018-01-24 15:22:40,402 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:22:40,403 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:40,403 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:22:40,403 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:40,403 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:22:40,413 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:22:40,414 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:22:40,534 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 15:22:40,539 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:22:40,539 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-01-24 15:22:40,539 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:22:40,540 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-24 15:22:40,540 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-24 15:22:40,540 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2018-01-24 15:22:40,540 INFO L87 Difference]: Start difference. First operand 67 states and 74 transitions. Second operand 9 states. [2018-01-24 15:22:40,740 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:22:40,741 INFO L93 Difference]: Finished difference Result 73 states and 80 transitions. [2018-01-24 15:22:40,741 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-24 15:22:40,741 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 31 [2018-01-24 15:22:40,741 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:22:40,742 INFO L225 Difference]: With dead ends: 73 [2018-01-24 15:22:40,742 INFO L226 Difference]: Without dead ends: 72 [2018-01-24 15:22:40,742 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2018-01-24 15:22:40,742 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2018-01-24 15:22:40,746 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 70. [2018-01-24 15:22:40,747 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 70 states. [2018-01-24 15:22:40,747 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 77 transitions. [2018-01-24 15:22:40,747 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 77 transitions. Word has length 31 [2018-01-24 15:22:40,747 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:22:40,748 INFO L432 AbstractCegarLoop]: Abstraction has 70 states and 77 transitions. [2018-01-24 15:22:40,748 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-24 15:22:40,748 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 77 transitions. [2018-01-24 15:22:40,748 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2018-01-24 15:22:40,748 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:22:40,748 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 15:22:40,749 INFO L371 AbstractCegarLoop]: === Iteration 15 === [cstrlenErr1RequiresViolation, cstrlenErr0RequiresViolation, mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncmpErr1RequiresViolation, cstrncmpErr5RequiresViolation, cstrncmpErr6RequiresViolation, cstrncmpErr0RequiresViolation, cstrncmpErr4RequiresViolation, cstrncmpErr7RequiresViolation, cstrncmpErr2RequiresViolation, cstrncmpErr3RequiresViolation, cstrncmpErr8RequiresViolation, cstrncmpErr9RequiresViolation, cstrstrErr2RequiresViolation, cstrstrErr3RequiresViolation, cstrstrErr1RequiresViolation, cstrstrErr0RequiresViolation]=== [2018-01-24 15:22:40,749 INFO L82 PathProgramCache]: Analyzing trace with hash -211494479, now seen corresponding path program 1 times [2018-01-24 15:22:40,749 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:22:40,749 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:40,749 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:22:40,750 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:40,750 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:22:40,760 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:22:40,761 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:22:41,007 WARN L146 SmtUtils]: Spent 137ms on a formula simplification. DAG size of input: 21 DAG size of output 12 [2018-01-24 15:22:41,118 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 15:22:41,118 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:22:41,118 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2018-01-24 15:22:41,119 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:22:41,119 INFO L409 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-01-24 15:22:41,119 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-01-24 15:22:41,119 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2018-01-24 15:22:41,120 INFO L87 Difference]: Start difference. First operand 70 states and 77 transitions. Second operand 13 states. [2018-01-24 15:22:41,329 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:22:41,329 INFO L93 Difference]: Finished difference Result 127 states and 140 transitions. [2018-01-24 15:22:41,329 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-01-24 15:22:41,329 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 36 [2018-01-24 15:22:41,329 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:22:41,330 INFO L225 Difference]: With dead ends: 127 [2018-01-24 15:22:41,330 INFO L226 Difference]: Without dead ends: 70 [2018-01-24 15:22:41,330 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 63 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=81, Invalid=339, Unknown=0, NotChecked=0, Total=420 [2018-01-24 15:22:41,331 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2018-01-24 15:22:41,338 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 70. [2018-01-24 15:22:41,338 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 70 states. [2018-01-24 15:22:41,339 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 76 transitions. [2018-01-24 15:22:41,339 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 76 transitions. Word has length 36 [2018-01-24 15:22:41,339 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:22:41,339 INFO L432 AbstractCegarLoop]: Abstraction has 70 states and 76 transitions. [2018-01-24 15:22:41,339 INFO L433 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-01-24 15:22:41,340 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 76 transitions. [2018-01-24 15:22:41,340 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2018-01-24 15:22:41,340 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:22:41,341 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 15:22:41,341 INFO L371 AbstractCegarLoop]: === Iteration 16 === [cstrlenErr1RequiresViolation, cstrlenErr0RequiresViolation, mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncmpErr1RequiresViolation, cstrncmpErr5RequiresViolation, cstrncmpErr6RequiresViolation, cstrncmpErr0RequiresViolation, cstrncmpErr4RequiresViolation, cstrncmpErr7RequiresViolation, cstrncmpErr2RequiresViolation, cstrncmpErr3RequiresViolation, cstrncmpErr8RequiresViolation, cstrncmpErr9RequiresViolation, cstrstrErr2RequiresViolation, cstrstrErr3RequiresViolation, cstrstrErr1RequiresViolation, cstrstrErr0RequiresViolation]=== [2018-01-24 15:22:41,341 INFO L82 PathProgramCache]: Analyzing trace with hash -188862225, now seen corresponding path program 1 times [2018-01-24 15:22:41,341 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:22:41,342 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:41,342 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:22:41,342 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:22:41,342 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:22:41,355 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:22:41,356 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:22:41,603 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 15:22:41,604 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:22:41,604 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-24 15:22:41,604 INFO L199 CegarAbsIntRunner]: Running AI on error trace of length 37 with the following transitions: [2018-01-24 15:22:41,604 INFO L201 CegarAbsIntRunner]: [0], [1], [2], [6], [7], [12], [20], [21], [25], [30], [36], [38], [39], [40], [41], [42], [45], [104], [105], [108], [111], [113], [117], [121], [122], [124], [125], [129], [135], [155], [156], [157], [159], [161], [162] [2018-01-24 15:22:41,605 INFO L147 AbstractInterpreter]: Using domain VPDomain [2018-01-24 15:22:41,605 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=2) [2018-01-24 15:22:42,359 INFO L259 AbstractInterpreter]: Some error location(s) were reachable [2018-01-24 15:22:42,360 INFO L268 AbstractInterpreter]: Visited 35 different actions 45 times. Merged at 6 different actions 10 times. Never widened. Found 1 fixpoints after 1 different actions. Largest state had 28 variables. [2018-01-24 15:22:42,364 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-01-24 15:22:42,364 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:22:42,364 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 15:22:42,378 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:22:42,378 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-24 15:22:42,408 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:22:42,411 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 15:22:42,427 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 15:22:42,428 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:22:42,485 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:22:42,486 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:10, output treesize:9 [2018-01-24 15:22:42,667 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:22:42,667 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:22:42,668 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 15:22:42,668 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:22:42,671 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:22:42,671 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:14, output treesize:8 [2018-01-24 15:22:42,707 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 14 treesize of output 11 [2018-01-24 15:22:42,709 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 15:22:42,710 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:22:42,713 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:22:42,719 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-24 15:22:42,720 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:29, output treesize:25 [2018-01-24 15:22:42,758 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 25 treesize of output 26 [2018-01-24 15:22:42,761 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 15:22:42,761 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:22:42,767 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:22:42,781 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: 4 dim-0 vars, and 1 xjuncts. [2018-01-24 15:22:42,781 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 5 variables, input treesize:39, output treesize:35 [2018-01-24 15:22:47,095 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 30 treesize of output 28 [2018-01-24 15:22:47,106 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 16 treesize of output 13 [2018-01-24 15:22:47,106 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-24 15:22:47,115 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 15:22:47,115 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 15:22:47,119 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 15:22:47,129 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 15:22:47,129 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 6 variables, input treesize:52, output treesize:29 [2018-01-24 15:22:47,197 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 15:22:47,198 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 15:22:47,482 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 16 treesize of output 12 [2018-01-24 15:22:47,483 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:22:47,491 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 13 treesize of output 11 [2018-01-24 15:22:47,501 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 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 5 treesize of output 3 [2018-01-24 15:22:47,501 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 15:22:47,502 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:22:47,507 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:22:47,508 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:35, output treesize:7 [2018-01-24 15:22:47,537 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 15:22:47,557 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:22:47,557 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 15:22:47,560 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:22:47,560 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-24 15:22:47,617 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:22:47,623 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 15:22:47,626 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 15:22:47,626 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:22:47,654 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 15:22:47,654 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:22:47,659 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:22:47,659 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:16, output treesize:14 [2018-01-24 15:22:47,734 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:22:47,734 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:22:47,735 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 15:22:47,735 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:22:47,742 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 15:22:47,742 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:22:47,747 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:22:47,747 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:25, output treesize:18 [2018-01-24 15:22:47,807 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 15:22:47,810 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 15:22:47,810 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:22:47,811 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:22:47,815 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:22:47,816 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:29, output treesize:25 [2018-01-24 15:22:49,857 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 15:22:49,859 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 15:22:49,859 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:22:49,862 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:22:49,868 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 15:22:49,868 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:36, output treesize:32 [2018-01-24 15:23:03,461 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 15:23:03,465 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 15:23:03,465 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:23:03,473 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 12 [2018-01-24 15:23:03,473 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-01-24 15:23:03,476 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 15:23:03,482 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 15:23:03,482 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 3 variables, input treesize:43, output treesize:30 [2018-01-24 15:23:03,641 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 15:23:03,641 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 15:23:03,923 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 13 treesize of output 11 [2018-01-24 15:23:03,929 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 15:23:03,930 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:23:03,931 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:23:03,935 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:23:03,935 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:31, output treesize:21 [2018-01-24 15:23:04,099 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 15:23:04,100 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-24 15:23:04,101 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 16, 11, 15, 12] total 56 [2018-01-24 15:23:04,101 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-24 15:23:04,101 INFO L409 AbstractCegarLoop]: Interpolant automaton has 27 states [2018-01-24 15:23:04,101 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2018-01-24 15:23:04,102 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=207, Invalid=2976, Unknown=9, NotChecked=0, Total=3192 [2018-01-24 15:23:04,102 INFO L87 Difference]: Start difference. First operand 70 states and 76 transitions. Second operand 27 states. [2018-01-24 15:23:06,599 WARN L146 SmtUtils]: Spent 2051ms on a formula simplification. DAG size of input: 74 DAG size of output 53 [2018-01-24 15:23:10,132 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:23:10,132 INFO L93 Difference]: Finished difference Result 82 states and 90 transitions. [2018-01-24 15:23:10,132 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-01-24 15:23:10,132 INFO L78 Accepts]: Start accepts. Automaton has 27 states. Word has length 36 [2018-01-24 15:23:10,132 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:23:10,133 INFO L225 Difference]: With dead ends: 82 [2018-01-24 15:23:10,133 INFO L226 Difference]: Without dead ends: 81 [2018-01-24 15:23:10,134 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 96 SyntacticMatches, 6 SemanticMatches, 67 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1196 ImplicationChecksByTransitivity, 24.6s TimeCoverageRelationStatistics Valid=387, Invalid=4296, Unknown=9, NotChecked=0, Total=4692 [2018-01-24 15:23:10,134 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2018-01-24 15:23:10,145 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 79. [2018-01-24 15:23:10,145 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 79 states. [2018-01-24 15:23:10,145 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 87 transitions. [2018-01-24 15:23:10,145 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 87 transitions. Word has length 36 [2018-01-24 15:23:10,146 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:23:10,146 INFO L432 AbstractCegarLoop]: Abstraction has 79 states and 87 transitions. [2018-01-24 15:23:10,146 INFO L433 AbstractCegarLoop]: Interpolant automaton has 27 states. [2018-01-24 15:23:10,146 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 87 transitions. [2018-01-24 15:23:10,146 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2018-01-24 15:23:10,146 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:23:10,147 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 15:23:10,147 INFO L371 AbstractCegarLoop]: === Iteration 17 === [cstrlenErr1RequiresViolation, cstrlenErr0RequiresViolation, mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncmpErr1RequiresViolation, cstrncmpErr5RequiresViolation, cstrncmpErr6RequiresViolation, cstrncmpErr0RequiresViolation, cstrncmpErr4RequiresViolation, cstrncmpErr7RequiresViolation, cstrncmpErr2RequiresViolation, cstrncmpErr3RequiresViolation, cstrncmpErr8RequiresViolation, cstrncmpErr9RequiresViolation, cstrstrErr2RequiresViolation, cstrstrErr3RequiresViolation, cstrstrErr1RequiresViolation, cstrstrErr0RequiresViolation]=== [2018-01-24 15:23:10,147 INFO L82 PathProgramCache]: Analyzing trace with hash -7823713, now seen corresponding path program 1 times [2018-01-24 15:23:10,147 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:23:10,148 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:23:10,148 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:23:10,148 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:23:10,148 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:23:10,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:23:10,160 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:23:10,225 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 15:23:10,225 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:23:10,226 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-01-24 15:23:10,226 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:23:10,226 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-24 15:23:10,226 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-24 15:23:10,226 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-01-24 15:23:10,227 INFO L87 Difference]: Start difference. First operand 79 states and 87 transitions. Second operand 7 states. [2018-01-24 15:23:10,326 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:23:10,326 INFO L93 Difference]: Finished difference Result 79 states and 87 transitions. [2018-01-24 15:23:10,326 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-01-24 15:23:10,326 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 39 [2018-01-24 15:23:10,327 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:23:10,327 INFO L225 Difference]: With dead ends: 79 [2018-01-24 15:23:10,327 INFO L226 Difference]: Without dead ends: 77 [2018-01-24 15:23:10,327 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2018-01-24 15:23:10,328 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2018-01-24 15:23:10,337 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 77. [2018-01-24 15:23:10,338 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 77 states. [2018-01-24 15:23:10,338 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 85 transitions. [2018-01-24 15:23:10,339 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 85 transitions. Word has length 39 [2018-01-24 15:23:10,339 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:23:10,339 INFO L432 AbstractCegarLoop]: Abstraction has 77 states and 85 transitions. [2018-01-24 15:23:10,339 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-24 15:23:10,339 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 85 transitions. [2018-01-24 15:23:10,340 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2018-01-24 15:23:10,340 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:23:10,340 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 15:23:10,340 INFO L371 AbstractCegarLoop]: === Iteration 18 === [cstrlenErr1RequiresViolation, cstrlenErr0RequiresViolation, mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncmpErr1RequiresViolation, cstrncmpErr5RequiresViolation, cstrncmpErr6RequiresViolation, cstrncmpErr0RequiresViolation, cstrncmpErr4RequiresViolation, cstrncmpErr7RequiresViolation, cstrncmpErr2RequiresViolation, cstrncmpErr3RequiresViolation, cstrncmpErr8RequiresViolation, cstrncmpErr9RequiresViolation, cstrstrErr2RequiresViolation, cstrstrErr3RequiresViolation, cstrstrErr1RequiresViolation, cstrstrErr0RequiresViolation]=== [2018-01-24 15:23:10,341 INFO L82 PathProgramCache]: Analyzing trace with hash -7823712, now seen corresponding path program 1 times [2018-01-24 15:23:10,341 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:23:10,341 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:23:10,342 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:23:10,342 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:23:10,342 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:23:10,360 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:23:10,361 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:23:10,466 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 15:23:10,466 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:23:10,466 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-01-24 15:23:10,466 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:23:10,466 INFO L409 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-01-24 15:23:10,466 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-01-24 15:23:10,467 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2018-01-24 15:23:10,467 INFO L87 Difference]: Start difference. First operand 77 states and 85 transitions. Second operand 8 states. [2018-01-24 15:23:10,568 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:23:10,568 INFO L93 Difference]: Finished difference Result 152 states and 172 transitions. [2018-01-24 15:23:10,569 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-01-24 15:23:10,569 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 39 [2018-01-24 15:23:10,569 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:23:10,570 INFO L225 Difference]: With dead ends: 152 [2018-01-24 15:23:10,570 INFO L226 Difference]: Without dead ends: 111 [2018-01-24 15:23:10,572 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2018-01-24 15:23:10,572 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2018-01-24 15:23:10,595 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 109. [2018-01-24 15:23:10,596 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 109 states. [2018-01-24 15:23:10,597 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 122 transitions. [2018-01-24 15:23:10,597 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 122 transitions. Word has length 39 [2018-01-24 15:23:10,597 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:23:10,597 INFO L432 AbstractCegarLoop]: Abstraction has 109 states and 122 transitions. [2018-01-24 15:23:10,597 INFO L433 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-01-24 15:23:10,597 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 122 transitions. [2018-01-24 15:23:10,598 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2018-01-24 15:23:10,598 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:23:10,598 INFO L322 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 15:23:10,598 INFO L371 AbstractCegarLoop]: === Iteration 19 === [cstrlenErr1RequiresViolation, cstrlenErr0RequiresViolation, mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncmpErr1RequiresViolation, cstrncmpErr5RequiresViolation, cstrncmpErr6RequiresViolation, cstrncmpErr0RequiresViolation, cstrncmpErr4RequiresViolation, cstrncmpErr7RequiresViolation, cstrncmpErr2RequiresViolation, cstrncmpErr3RequiresViolation, cstrncmpErr8RequiresViolation, cstrncmpErr9RequiresViolation, cstrstrErr2RequiresViolation, cstrstrErr3RequiresViolation, cstrstrErr1RequiresViolation, cstrstrErr0RequiresViolation]=== [2018-01-24 15:23:10,599 INFO L82 PathProgramCache]: Analyzing trace with hash -701857031, now seen corresponding path program 2 times [2018-01-24 15:23:10,599 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:23:10,599 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:23:10,600 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:23:10,600 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:23:10,600 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:23:10,612 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:23:10,613 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:23:11,030 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 15:23:11,030 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:23:11,030 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-24 15:23:11,030 INFO L183 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-01-24 15:23:11,030 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-01-24 15:23:11,030 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:23:11,031 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-24 15:23:11,035 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-24 15:23:11,036 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-01-24 15:23:11,048 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 15:23:11,054 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 15:23:11,055 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-24 15:23:11,059 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 15:23:11,062 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 15:23:11,063 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:23:11,068 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 15:23:11,068 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:23:11,071 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:23:11,072 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:16, output treesize:14 [2018-01-24 15:23:11,109 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:23:11,111 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 15:23:11,111 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:23:11,119 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:23:11,120 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:23:11,120 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 15:23:11,121 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:23:11,125 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:23:11,125 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:25, output treesize:18 [2018-01-24 15:23:11,167 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 15:23:11,169 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 15:23:11,169 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:23:11,170 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:23:11,176 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-24 15:23:11,177 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:32, output treesize:28 [2018-01-24 15:23:11,214 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 15:23:11,216 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 15:23:11,216 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:23:11,220 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:23:11,227 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 3 dim-0 vars, and 1 xjuncts. [2018-01-24 15:23:11,227 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:39, output treesize:35 [2018-01-24 15:23:18,421 WARN L146 SmtUtils]: Spent 2053ms on a formula simplification. DAG size of input: 47 DAG size of output 36 [2018-01-24 15:23:18,938 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 46 treesize of output 58 [2018-01-24 15:23:18,961 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 42 treesize of output 50 [2018-01-24 15:23:18,962 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-24 15:23:19,017 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 38 treesize of output 28 [2018-01-24 15:23:19,018 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 15:23:19,085 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 28 treesize of output 31 [2018-01-24 15:23:19,086 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 2 xjuncts. [2018-01-24 15:23:19,155 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 46 treesize of output 36 [2018-01-24 15:23:19,155 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-24 15:23:19,191 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 42 treesize of output 32 [2018-01-24 15:23:19,192 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-24 15:23:19,241 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 32 treesize of output 35 [2018-01-24 15:23:19,241 INFO L267 ElimStorePlain]: Start of recursive call 8: End of recursive call: and 2 xjuncts. [2018-01-24 15:23:19,265 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 32 treesize of output 22 [2018-01-24 15:23:19,266 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 1 xjuncts. [2018-01-24 15:23:19,295 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 22 treesize of output 20 [2018-01-24 15:23:19,296 INFO L267 ElimStorePlain]: Start of recursive call 10: End of recursive call: and 2 xjuncts. [2018-01-24 15:23:19,323 INFO L267 ElimStorePlain]: Start of recursive call 2: 8 dim-1 vars, End of recursive call: and 3 xjuncts. [2018-01-24 15:23:19,347 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 15:23:19,347 INFO L202 ElimStorePlain]: Needed 10 recursive calls to eliminate 6 variables, input treesize:70, output treesize:37 [2018-01-24 15:23:19,450 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 15:23:19,450 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 15:23:20,664 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 15 treesize of output 13 [2018-01-24 15:23:20,674 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 7 treesize of output 3 [2018-01-24 15:23:20,674 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:23:20,676 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:23:20,683 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:23:20,683 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:39, output treesize:44 [2018-01-24 15:23:21,078 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 15:23:21,100 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:23:21,100 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 Starting monitored process 7 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 7 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-01-24 15:23:21,107 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-24 15:23:21,107 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-01-24 15:23:21,132 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 15:23:21,171 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 15:23:21,213 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-24 15:23:21,220 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 15:23:21,227 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 15:23:21,228 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:23:21,249 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 15:23:21,250 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:23:21,254 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:23:21,254 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:16, output treesize:14 [2018-01-24 15:23:21,301 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:23:21,302 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 15:23:21,302 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:23:21,311 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:23:21,312 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:23:21,312 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 15:23:21,312 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:23:21,317 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:23:21,318 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:25, output treesize:18 [2018-01-24 15:23:21,463 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 15 treesize of output 12 [2018-01-24 15:23:21,465 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 12 treesize of output 11 [2018-01-24 15:23:21,465 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:23:21,466 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:23:21,471 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:23:21,471 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:25, output treesize:21 [2018-01-24 15:23:21,647 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 15:23:21,649 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 15:23:21,649 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:23:21,654 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:23:21,659 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 15:23:21,659 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:32, output treesize:28 Received shutdown request... [2018-01-24 15:23:26,508 INFO L175 TraceCheckSpWp]: Timeout while computing interpolants [2018-01-24 15:23:26,508 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-24 15:23:26,513 WARN L187 ceAbstractionStarter]: Timeout [2018-01-24 15:23:26,513 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 24.01 03:23:26 BoogieIcfgContainer [2018-01-24 15:23:26,513 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-24 15:23:26,514 INFO L168 Benchmark]: Toolchain (without parser) took 56302.35 ms. Allocated memory was 303.0 MB in the beginning and 716.7 MB in the end (delta: 413.7 MB). Free memory was 263.1 MB in the beginning and 524.9 MB in the end (delta: -261.8 MB). Peak memory consumption was 151.8 MB. Max. memory is 5.3 GB. [2018-01-24 15:23:26,515 INFO L168 Benchmark]: CDTParser took 0.15 ms. Allocated memory is still 303.0 MB. Free memory is still 269.1 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-24 15:23:26,515 INFO L168 Benchmark]: CACSL2BoogieTranslator took 218.15 ms. Allocated memory is still 303.0 MB. Free memory was 262.1 MB in the beginning and 252.0 MB in the end (delta: 10.1 MB). Peak memory consumption was 10.1 MB. Max. memory is 5.3 GB. [2018-01-24 15:23:26,516 INFO L168 Benchmark]: Boogie Preprocessor took 57.53 ms. Allocated memory is still 303.0 MB. Free memory was 251.0 MB in the beginning and 250.0 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 5.3 GB. [2018-01-24 15:23:26,516 INFO L168 Benchmark]: RCFGBuilder took 405.10 ms. Allocated memory is still 303.0 MB. Free memory was 250.0 MB in the beginning and 224.4 MB in the end (delta: 25.7 MB). Peak memory consumption was 25.7 MB. Max. memory is 5.3 GB. [2018-01-24 15:23:26,516 INFO L168 Benchmark]: TraceAbstraction took 55613.17 ms. Allocated memory was 303.0 MB in the beginning and 716.7 MB in the end (delta: 413.7 MB). Free memory was 223.4 MB in the beginning and 524.9 MB in the end (delta: -301.6 MB). Peak memory consumption was 112.1 MB. Max. memory is 5.3 GB. [2018-01-24 15:23:26,518 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 303.0 MB. Free memory is still 269.1 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 218.15 ms. Allocated memory is still 303.0 MB. Free memory was 262.1 MB in the beginning and 252.0 MB in the end (delta: 10.1 MB). Peak memory consumption was 10.1 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 57.53 ms. Allocated memory is still 303.0 MB. Free memory was 251.0 MB in the beginning and 250.0 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 5.3 GB. * RCFGBuilder took 405.10 ms. Allocated memory is still 303.0 MB. Free memory was 250.0 MB in the beginning and 224.4 MB in the end (delta: 25.7 MB). Peak memory consumption was 25.7 MB. Max. memory is 5.3 GB. * TraceAbstraction took 55613.17 ms. Allocated memory was 303.0 MB in the beginning and 716.7 MB in the end (delta: 413.7 MB). Free memory was 223.4 MB in the beginning and 524.9 MB in the end (delta: -301.6 MB). Peak memory consumption was 112.1 MB. Max. memory is 5.3 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.analysis.abstractinterpretationv2: - StatisticsResult: ArrayEqualityDomainStatistics #Locations : 25 LocStat_MAX_WEQGRAPH_SIZE : 9 LocStat_MAX_SIZEOF_WEQEDGELABEL : 2 LocStat_NO_SUPPORTING_EQUALITIES : 239 LocStat_NO_SUPPORTING_DISEQUALITIES : 59 LocStat_NO_DISJUNCTIONS : -50 LocStat_MAX_NO_DISJUNCTIONS : -1 #Transitions : 34 TransStat_MAX_WEQGRAPH_SIZE : 2 TransStat_MAX_SIZEOF_WEQEDGELABEL : 1 TransStat_NO_SUPPORTING_EQUALITIES : 60 TransStat_NO_SUPPORTING_DISEQUALITIES : 6 TransStat_NO_DISJUNCTIONS : 35 TransStat_MAX_NO_DISJUNCTIONS : 2 - StatisticsResult: EqConstraintFactoryStatistics CONJOIN_DISJUNCTIVE(MILLISECONDS) : 1.351686 RENAME_VARIABLES(MILLISECONDS) : 0.383142 UNFREEZE(MILLISECONDS) : 0.000000 CONJOIN(MILLISECONDS) : 1.271117 PROJECTAWAY(MILLISECONDS) : 0.600099 ADD_WEAK_EQUALITY(MILLISECONDS) : 0.136683 DISJOIN(MILLISECONDS) : 0.356959 RENAME_VARIABLES_DISJUNCTIVE(MILLISECONDS) : 0.417170 ADD_EQUALITY(MILLISECONDS) : 0.024108 DISJOIN_DISJUNCTIVE(MILLISECONDS) : 0.000000 ADD_DISEQUALITY(MILLISECONDS) : 0.019681 #CONJOIN_DISJUNCTIVE : 55 #RENAME_VARIABLES : 84 #UNFREEZE : 0 #CONJOIN : 103 #PROJECTAWAY : 78 #ADD_WEAK_EQUALITY : 9 #DISJOIN : 6 #RENAME_VARIABLES_DISJUNCTIVE : 81 #ADD_EQUALITY : 62 #DISJOIN_DISJUNCTIVE : 0 #ADD_DISEQUALITY : 4 - StatisticsResult: ArrayEqualityDomainStatistics #Locations : 34 LocStat_MAX_WEQGRAPH_SIZE : 5 LocStat_MAX_SIZEOF_WEQEDGELABEL : 2 LocStat_NO_SUPPORTING_EQUALITIES : 368 LocStat_NO_SUPPORTING_DISEQUALITIES : 112 LocStat_NO_DISJUNCTIONS : -68 LocStat_MAX_NO_DISJUNCTIONS : -1 #Transitions : 43 TransStat_MAX_WEQGRAPH_SIZE : 2 TransStat_MAX_SIZEOF_WEQEDGELABEL : 1 TransStat_NO_SUPPORTING_EQUALITIES : 69 TransStat_NO_SUPPORTING_DISEQUALITIES : 7 TransStat_NO_DISJUNCTIONS : 44 TransStat_MAX_NO_DISJUNCTIONS : 2 - StatisticsResult: EqConstraintFactoryStatistics CONJOIN_DISJUNCTIVE(MILLISECONDS) : 1.489448 RENAME_VARIABLES(MILLISECONDS) : 0.216019 UNFREEZE(MILLISECONDS) : 0.000000 CONJOIN(MILLISECONDS) : 1.450434 PROJECTAWAY(MILLISECONDS) : 0.197176 ADD_WEAK_EQUALITY(MILLISECONDS) : 0.082657 DISJOIN(MILLISECONDS) : 0.402628 RENAME_VARIABLES_DISJUNCTIVE(MILLISECONDS) : 0.236873 ADD_EQUALITY(MILLISECONDS) : 0.019492 DISJOIN_DISJUNCTIVE(MILLISECONDS) : 0.000000 ADD_DISEQUALITY(MILLISECONDS) : 0.011585 #CONJOIN_DISJUNCTIVE : 75 #RENAME_VARIABLES : 129 #UNFREEZE : 0 #CONJOIN : 133 #PROJECTAWAY : 113 #ADD_WEAK_EQUALITY : 9 #DISJOIN : 10 #RENAME_VARIABLES_DISJUNCTIVE : 124 #ADD_EQUALITY : 71 #DISJOIN_DISJUNCTIVE : 0 #ADD_DISEQUALITY : 5 * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 544). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 544). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 590). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 589). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 590). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 589). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - TimeoutResultAtElement [Line: 578]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 578). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 554). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 555). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 555). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 554). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 555). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 555). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 554). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 554). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 556). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 556). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 570). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 570). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 566). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 566). Cancelled while BasicCegarLoop was analyzing trace of length 42 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 49 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 6 procedures, 90 locations, 21 error locations. TIMEOUT Result, 55.5s OverallTime, 19 OverallIterations, 3 TraceHistogramMax, 10.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 1347 SDtfs, 948 SDslu, 5604 SDs, 0 SdLazy, 3007 SolverSat, 191 SolverUnsat, 1 SolverUnknown, 0 SolverNotchecked, 4.6s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 478 GetRequests, 202 SyntacticMatches, 12 SemanticMatches, 264 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1835 ImplicationChecksByTransitivity, 29.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=131occurred in iteration=9, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 2.5s AbstIntTime, 2 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 18 MinimizatonAttempts, 97 StatesRemovedByMinimization, 7 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 25.7s InterpolantComputationTime, 573 NumberOfCodeBlocks, 573 NumberOfCodeBlocksAsserted, 22 NumberOfCheckSat, 673 ConstructedInterpolants, 63 QuantifiedInterpolants, 192584 SizeOfPredicates, 69 NumberOfNonLiveVariables, 576 ConjunctsInSsa, 148 ConjunctsInUnsatCore, 26 InterpolantComputations, 16 PerfectInterpolantSequences, 2/22 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_cstrstr-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-24_15-23-26-530.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/openbsd_cstrstr-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ.epf_AutomizerC.xml/Csv-VPDomainBenchmark-0-2018-01-24_15-23-26-530.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/openbsd_cstrstr-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ.epf_AutomizerC.xml/Csv-BenchmarkWithCounters-0-2018-01-24_15-23-26-530.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/openbsd_cstrstr-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ.epf_AutomizerC.xml/Csv-VPDomainBenchmark-1-2018-01-24_15-23-26-530.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/openbsd_cstrstr-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ.epf_AutomizerC.xml/Csv-BenchmarkWithCounters-1-2018-01-24_15-23-26-530.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/openbsd_cstrstr-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-24_15-23-26-530.csv Completed graceful shutdown