./Ultimate.py --spec ../../sv-benchmarks/c/properties/valid-memsafety.prp --file ../../sv-benchmarks/c/termination-15/cstrpbrk_malloc.i --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for memory safety (deref-memtrack) Using default analysis Version 0e0057cc Calling Ultimate with: /usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/config/TaipanMemDerefMemtrack.xml -i ../../sv-benchmarks/c/termination-15/cstrpbrk_malloc.i -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/config/svcomp-DerefFreeMemtrack-64bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G valid-free) ) CHECK( init(main()), LTL(G valid-deref) ) CHECK( init(main()), LTL(G valid-memtrack) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 64bit --witnessprinter.graph.data.programhash 8edf581f64d166b4408dcbe4d1c200d90abc56f787561a55f3b270257b320de9 --- Real Ultimate output --- This is Ultimate 0.2.4-dev-0e0057c [2023-12-02 15:56:33,844 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-12-02 15:56:33,909 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/config/svcomp-DerefFreeMemtrack-64bit-Taipan_Default.epf [2023-12-02 15:56:33,913 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-12-02 15:56:33,914 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-12-02 15:56:33,939 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-12-02 15:56:33,940 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-12-02 15:56:33,940 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-12-02 15:56:33,941 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-12-02 15:56:33,941 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-12-02 15:56:33,942 INFO L153 SettingsManager]: * User list type=DISABLED [2023-12-02 15:56:33,942 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-12-02 15:56:33,943 INFO L153 SettingsManager]: * Explicit value domain=true [2023-12-02 15:56:33,943 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-12-02 15:56:33,944 INFO L153 SettingsManager]: * Octagon Domain=false [2023-12-02 15:56:33,944 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-12-02 15:56:33,945 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-12-02 15:56:33,945 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-12-02 15:56:33,946 INFO L153 SettingsManager]: * Interval Domain=false [2023-12-02 15:56:33,946 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-12-02 15:56:33,947 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-12-02 15:56:33,947 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-12-02 15:56:33,948 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-12-02 15:56:33,948 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-12-02 15:56:33,949 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-12-02 15:56:33,949 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-12-02 15:56:33,950 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-12-02 15:56:33,950 INFO L153 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2023-12-02 15:56:33,950 INFO L153 SettingsManager]: * Bitprecise bitfields=true [2023-12-02 15:56:33,951 INFO L153 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2023-12-02 15:56:33,951 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-12-02 15:56:33,952 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2023-12-02 15:56:33,952 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2023-12-02 15:56:33,953 INFO L153 SettingsManager]: * Use constant arrays=true [2023-12-02 15:56:33,953 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-12-02 15:56:33,953 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-12-02 15:56:33,954 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-12-02 15:56:33,954 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-12-02 15:56:33,955 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-12-02 15:56:33,955 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-12-02 15:56:33,955 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-12-02 15:56:33,956 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-12-02 15:56:33,956 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-12-02 15:56:33,956 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-12-02 15:56:33,957 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-12-02 15:56:33,957 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G valid-free) ) CHECK( init(main()), LTL(G valid-deref) ) CHECK( init(main()), LTL(G valid-memtrack) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Taipan Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 64bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 8edf581f64d166b4408dcbe4d1c200d90abc56f787561a55f3b270257b320de9 [2023-12-02 15:56:34,174 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-12-02 15:56:34,195 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-12-02 15:56:34,197 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-12-02 15:56:34,198 INFO L270 PluginConnector]: Initializing CDTParser... [2023-12-02 15:56:34,199 INFO L274 PluginConnector]: CDTParser initialized [2023-12-02 15:56:34,200 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/../../sv-benchmarks/c/termination-15/cstrpbrk_malloc.i [2023-12-02 15:56:36,944 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-12-02 15:56:37,144 INFO L384 CDTParser]: Found 1 translation units. [2023-12-02 15:56:37,145 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/sv-benchmarks/c/termination-15/cstrpbrk_malloc.i [2023-12-02 15:56:37,154 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/data/e8ef09f7a/885c70e6406447109bc6f2c0b819286f/FLAG1ba5aabc7 [2023-12-02 15:56:37,165 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/data/e8ef09f7a/885c70e6406447109bc6f2c0b819286f [2023-12-02 15:56:37,168 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-12-02 15:56:37,169 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-12-02 15:56:37,170 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-12-02 15:56:37,170 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-12-02 15:56:37,175 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-12-02 15:56:37,175 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.12 03:56:37" (1/1) ... [2023-12-02 15:56:37,176 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@77ddaf96 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 03:56:37, skipping insertion in model container [2023-12-02 15:56:37,176 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.12 03:56:37" (1/1) ... [2023-12-02 15:56:37,210 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-12-02 15:56:37,458 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-02 15:56:37,466 INFO L202 MainTranslator]: Completed pre-run [2023-12-02 15:56:37,505 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-02 15:56:37,534 INFO L206 MainTranslator]: Completed translation [2023-12-02 15:56:37,535 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 03:56:37 WrapperNode [2023-12-02 15:56:37,535 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-12-02 15:56:37,536 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-12-02 15:56:37,536 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-12-02 15:56:37,536 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-12-02 15:56:37,542 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 03:56:37" (1/1) ... [2023-12-02 15:56:37,554 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 03:56:37" (1/1) ... [2023-12-02 15:56:37,575 INFO L138 Inliner]: procedures = 152, calls = 14, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 82 [2023-12-02 15:56:37,576 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-12-02 15:56:37,577 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-12-02 15:56:37,577 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-12-02 15:56:37,577 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-12-02 15:56:37,584 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 03:56:37" (1/1) ... [2023-12-02 15:56:37,584 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 03:56:37" (1/1) ... [2023-12-02 15:56:37,586 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 03:56:37" (1/1) ... [2023-12-02 15:56:37,587 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 03:56:37" (1/1) ... [2023-12-02 15:56:37,592 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 03:56:37" (1/1) ... [2023-12-02 15:56:37,596 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 03:56:37" (1/1) ... [2023-12-02 15:56:37,597 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 03:56:37" (1/1) ... [2023-12-02 15:56:37,598 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 03:56:37" (1/1) ... [2023-12-02 15:56:37,601 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-12-02 15:56:37,602 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-12-02 15:56:37,602 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-12-02 15:56:37,602 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-12-02 15:56:37,603 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 03:56:37" (1/1) ... [2023-12-02 15:56:37,609 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-12-02 15:56:37,617 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 15:56:37,629 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-12-02 15:56:37,632 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-12-02 15:56:37,661 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2023-12-02 15:56:37,661 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2023-12-02 15:56:37,661 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2023-12-02 15:56:37,661 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-12-02 15:56:37,662 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-12-02 15:56:37,662 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-12-02 15:56:37,735 INFO L241 CfgBuilder]: Building ICFG [2023-12-02 15:56:37,737 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-12-02 15:56:37,934 INFO L282 CfgBuilder]: Performing block encoding [2023-12-02 15:56:37,992 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-12-02 15:56:37,992 INFO L309 CfgBuilder]: Removed 2 assume(true) statements. [2023-12-02 15:56:37,994 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.12 03:56:37 BoogieIcfgContainer [2023-12-02 15:56:37,994 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-12-02 15:56:37,997 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-12-02 15:56:37,997 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-12-02 15:56:38,000 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-12-02 15:56:38,000 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 02.12 03:56:37" (1/3) ... [2023-12-02 15:56:38,001 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3f77a07c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.12 03:56:38, skipping insertion in model container [2023-12-02 15:56:38,001 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 03:56:37" (2/3) ... [2023-12-02 15:56:38,002 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3f77a07c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.12 03:56:38, skipping insertion in model container [2023-12-02 15:56:38,002 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.12 03:56:37" (3/3) ... [2023-12-02 15:56:38,003 INFO L112 eAbstractionObserver]: Analyzing ICFG cstrpbrk_malloc.i [2023-12-02 15:56:38,023 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-12-02 15:56:38,023 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 21 error locations. [2023-12-02 15:56:38,059 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-12-02 15:56:38,064 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=false, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@10bca5a4, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-12-02 15:56:38,064 INFO L358 AbstractCegarLoop]: Starting to check reachability of 21 error locations. [2023-12-02 15:56:38,068 INFO L276 IsEmpty]: Start isEmpty. Operand has 43 states, 21 states have (on average 2.2857142857142856) internal successors, (48), 42 states have internal predecessors, (48), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:38,072 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 3 [2023-12-02 15:56:38,072 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:56:38,073 INFO L195 NwaCegarLoop]: trace histogram [1, 1] [2023-12-02 15:56:38,073 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:56:38,077 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:56:38,077 INFO L85 PathProgramCache]: Analyzing trace with hash 4295, now seen corresponding path program 1 times [2023-12-02 15:56:38,096 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:56:38,096 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [252481775] [2023-12-02 15:56:38,097 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:56:38,097 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:56:38,203 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:56:38,359 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:56:38,359 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:56:38,360 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [252481775] [2023-12-02 15:56:38,360 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [252481775] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 15:56:38,361 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 15:56:38,361 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-12-02 15:56:38,362 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [670337237] [2023-12-02 15:56:38,363 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 15:56:38,367 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-12-02 15:56:38,368 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:56:38,394 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-12-02 15:56:38,395 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-12-02 15:56:38,396 INFO L87 Difference]: Start difference. First operand has 43 states, 21 states have (on average 2.2857142857142856) internal successors, (48), 42 states have internal predecessors, (48), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Second operand has 3 states, 2 states have (on average 1.0) internal successors, (2), 2 states have internal predecessors, (2), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:38,451 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 15:56:38,451 INFO L93 Difference]: Finished difference Result 41 states and 44 transitions. [2023-12-02 15:56:38,452 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-12-02 15:56:38,453 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 1.0) internal successors, (2), 2 states have internal predecessors, (2), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 2 [2023-12-02 15:56:38,454 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 15:56:38,461 INFO L225 Difference]: With dead ends: 41 [2023-12-02 15:56:38,461 INFO L226 Difference]: Without dead ends: 40 [2023-12-02 15:56:38,462 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 1 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-12-02 15:56:38,466 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 34 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 28 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 15:56:38,467 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 28 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 15:56:38,483 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2023-12-02 15:56:38,494 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 40. [2023-12-02 15:56:38,496 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 39 states have internal predecessors, (43), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:38,497 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 43 transitions. [2023-12-02 15:56:38,498 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 43 transitions. Word has length 2 [2023-12-02 15:56:38,498 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 15:56:38,498 INFO L495 AbstractCegarLoop]: Abstraction has 40 states and 43 transitions. [2023-12-02 15:56:38,498 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 1.0) internal successors, (2), 2 states have internal predecessors, (2), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:38,499 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 43 transitions. [2023-12-02 15:56:38,499 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 3 [2023-12-02 15:56:38,499 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:56:38,499 INFO L195 NwaCegarLoop]: trace histogram [1, 1] [2023-12-02 15:56:38,499 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-12-02 15:56:38,500 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:56:38,500 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:56:38,500 INFO L85 PathProgramCache]: Analyzing trace with hash 4296, now seen corresponding path program 1 times [2023-12-02 15:56:38,501 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:56:38,501 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [673873912] [2023-12-02 15:56:38,501 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:56:38,501 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:56:38,526 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:56:38,708 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:56:38,709 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:56:38,709 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [673873912] [2023-12-02 15:56:38,709 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [673873912] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 15:56:38,709 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 15:56:38,709 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-12-02 15:56:38,709 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [404591842] [2023-12-02 15:56:38,710 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 15:56:38,711 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-12-02 15:56:38,711 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:56:38,712 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-12-02 15:56:38,712 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-12-02 15:56:38,712 INFO L87 Difference]: Start difference. First operand 40 states and 43 transitions. Second operand has 3 states, 2 states have (on average 1.0) internal successors, (2), 2 states have internal predecessors, (2), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:38,755 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 15:56:38,756 INFO L93 Difference]: Finished difference Result 38 states and 41 transitions. [2023-12-02 15:56:38,756 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-12-02 15:56:38,756 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 1.0) internal successors, (2), 2 states have internal predecessors, (2), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 2 [2023-12-02 15:56:38,757 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 15:56:38,757 INFO L225 Difference]: With dead ends: 38 [2023-12-02 15:56:38,757 INFO L226 Difference]: Without dead ends: 38 [2023-12-02 15:56:38,758 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 1 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-12-02 15:56:38,759 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 40 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 22 SdHoareTripleChecker+Invalid, 20 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 15:56:38,760 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 22 Invalid, 20 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 15:56:38,761 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2023-12-02 15:56:38,764 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 38. [2023-12-02 15:56:38,764 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 21 states have (on average 1.9523809523809523) internal successors, (41), 37 states have internal predecessors, (41), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:38,765 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 41 transitions. [2023-12-02 15:56:38,765 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 41 transitions. Word has length 2 [2023-12-02 15:56:38,766 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 15:56:38,766 INFO L495 AbstractCegarLoop]: Abstraction has 38 states and 41 transitions. [2023-12-02 15:56:38,766 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 1.0) internal successors, (2), 2 states have internal predecessors, (2), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:38,766 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 41 transitions. [2023-12-02 15:56:38,766 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2023-12-02 15:56:38,766 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:56:38,767 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1] [2023-12-02 15:56:38,767 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-12-02 15:56:38,767 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:56:38,767 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:56:38,768 INFO L85 PathProgramCache]: Analyzing trace with hash 133134, now seen corresponding path program 1 times [2023-12-02 15:56:38,768 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:56:38,768 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1639561905] [2023-12-02 15:56:38,768 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:56:38,768 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:56:38,783 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:56:38,857 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:56:38,857 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:56:38,857 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1639561905] [2023-12-02 15:56:38,857 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1639561905] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 15:56:38,857 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 15:56:38,858 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-12-02 15:56:38,858 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [318911819] [2023-12-02 15:56:38,858 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 15:56:38,858 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-12-02 15:56:38,858 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:56:38,859 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-12-02 15:56:38,859 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-12-02 15:56:38,859 INFO L87 Difference]: Start difference. First operand 38 states and 41 transitions. Second operand has 4 states, 3 states have (on average 1.0) internal successors, (3), 3 states have internal predecessors, (3), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:38,911 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 15:56:38,911 INFO L93 Difference]: Finished difference Result 37 states and 40 transitions. [2023-12-02 15:56:38,912 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-12-02 15:56:38,912 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 1.0) internal successors, (3), 3 states have internal predecessors, (3), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 3 [2023-12-02 15:56:38,912 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 15:56:38,913 INFO L225 Difference]: With dead ends: 37 [2023-12-02 15:56:38,913 INFO L226 Difference]: Without dead ends: 37 [2023-12-02 15:56:38,913 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2023-12-02 15:56:38,915 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 61 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 61 SdHoareTripleChecker+Valid, 26 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 15:56:38,916 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [61 Valid, 26 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 15:56:38,916 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2023-12-02 15:56:38,919 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2023-12-02 15:56:38,919 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 21 states have (on average 1.9047619047619047) internal successors, (40), 36 states have internal predecessors, (40), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:38,920 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 40 transitions. [2023-12-02 15:56:38,920 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 40 transitions. Word has length 3 [2023-12-02 15:56:38,920 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 15:56:38,921 INFO L495 AbstractCegarLoop]: Abstraction has 37 states and 40 transitions. [2023-12-02 15:56:38,921 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 1.0) internal successors, (3), 3 states have internal predecessors, (3), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:38,921 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 40 transitions. [2023-12-02 15:56:38,921 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2023-12-02 15:56:38,921 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:56:38,921 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1] [2023-12-02 15:56:38,922 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2023-12-02 15:56:38,922 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:56:38,922 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:56:38,923 INFO L85 PathProgramCache]: Analyzing trace with hash 133135, now seen corresponding path program 1 times [2023-12-02 15:56:38,923 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:56:38,923 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [882705993] [2023-12-02 15:56:38,923 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:56:38,923 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:56:38,938 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:56:39,090 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:56:39,091 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:56:39,091 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [882705993] [2023-12-02 15:56:39,091 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [882705993] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 15:56:39,091 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 15:56:39,091 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-12-02 15:56:39,091 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [344656607] [2023-12-02 15:56:39,092 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 15:56:39,092 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-12-02 15:56:39,092 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:56:39,092 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-12-02 15:56:39,093 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-12-02 15:56:39,093 INFO L87 Difference]: Start difference. First operand 37 states and 40 transitions. Second operand has 3 states, 2 states have (on average 1.5) internal successors, (3), 2 states have internal predecessors, (3), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:39,132 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 15:56:39,133 INFO L93 Difference]: Finished difference Result 36 states and 39 transitions. [2023-12-02 15:56:39,133 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-12-02 15:56:39,133 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 1.5) internal successors, (3), 2 states have internal predecessors, (3), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 3 [2023-12-02 15:56:39,133 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 15:56:39,134 INFO L225 Difference]: With dead ends: 36 [2023-12-02 15:56:39,134 INFO L226 Difference]: Without dead ends: 36 [2023-12-02 15:56:39,134 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 1 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-12-02 15:56:39,136 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 37 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 20 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 19 SdHoareTripleChecker+Invalid, 20 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 20 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 15:56:39,136 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 19 Invalid, 20 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 20 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 15:56:39,137 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2023-12-02 15:56:39,139 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2023-12-02 15:56:39,140 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 21 states have (on average 1.8571428571428572) internal successors, (39), 35 states have internal predecessors, (39), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:39,140 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 39 transitions. [2023-12-02 15:56:39,140 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 39 transitions. Word has length 3 [2023-12-02 15:56:39,141 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 15:56:39,141 INFO L495 AbstractCegarLoop]: Abstraction has 36 states and 39 transitions. [2023-12-02 15:56:39,141 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 1.5) internal successors, (3), 2 states have internal predecessors, (3), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:39,141 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 39 transitions. [2023-12-02 15:56:39,141 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 5 [2023-12-02 15:56:39,141 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:56:39,142 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1] [2023-12-02 15:56:39,142 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2023-12-02 15:56:39,142 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr4REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:56:39,142 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:56:39,142 INFO L85 PathProgramCache]: Analyzing trace with hash 4129537, now seen corresponding path program 1 times [2023-12-02 15:56:39,143 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:56:39,143 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [55164013] [2023-12-02 15:56:39,143 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:56:39,143 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:56:39,154 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:56:39,190 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:56:39,190 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:56:39,190 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [55164013] [2023-12-02 15:56:39,191 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [55164013] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 15:56:39,191 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 15:56:39,191 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-12-02 15:56:39,191 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [942108361] [2023-12-02 15:56:39,191 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 15:56:39,192 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-12-02 15:56:39,192 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:56:39,192 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-12-02 15:56:39,192 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-12-02 15:56:39,193 INFO L87 Difference]: Start difference. First operand 36 states and 39 transitions. Second operand has 4 states, 3 states have (on average 1.3333333333333333) internal successors, (4), 4 states have internal predecessors, (4), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:39,240 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 15:56:39,240 INFO L93 Difference]: Finished difference Result 34 states and 37 transitions. [2023-12-02 15:56:39,241 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-12-02 15:56:39,241 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 1.3333333333333333) internal successors, (4), 4 states have internal predecessors, (4), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 4 [2023-12-02 15:56:39,241 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 15:56:39,242 INFO L225 Difference]: With dead ends: 34 [2023-12-02 15:56:39,242 INFO L226 Difference]: Without dead ends: 34 [2023-12-02 15:56:39,242 INFO L412 NwaCegarLoop]: 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 [2023-12-02 15:56:39,243 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 48 mSDsluCounter, 9 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 28 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 15:56:39,244 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 28 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 15:56:39,245 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2023-12-02 15:56:39,247 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 34. [2023-12-02 15:56:39,247 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 21 states have (on average 1.7619047619047619) internal successors, (37), 33 states have internal predecessors, (37), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:39,248 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 37 transitions. [2023-12-02 15:56:39,248 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 37 transitions. Word has length 4 [2023-12-02 15:56:39,248 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 15:56:39,248 INFO L495 AbstractCegarLoop]: Abstraction has 34 states and 37 transitions. [2023-12-02 15:56:39,248 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 1.3333333333333333) internal successors, (4), 4 states have internal predecessors, (4), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:39,249 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 37 transitions. [2023-12-02 15:56:39,249 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 5 [2023-12-02 15:56:39,249 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:56:39,249 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1] [2023-12-02 15:56:39,249 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2023-12-02 15:56:39,249 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr5REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:56:39,250 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:56:39,250 INFO L85 PathProgramCache]: Analyzing trace with hash 4129538, now seen corresponding path program 1 times [2023-12-02 15:56:39,250 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:56:39,250 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [449938349] [2023-12-02 15:56:39,250 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:56:39,251 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:56:39,262 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:56:39,339 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:56:39,340 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:56:39,340 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [449938349] [2023-12-02 15:56:39,340 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [449938349] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 15:56:39,340 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 15:56:39,340 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-12-02 15:56:39,340 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2122730498] [2023-12-02 15:56:39,341 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 15:56:39,341 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-02 15:56:39,341 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:56:39,341 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-02 15:56:39,342 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-12-02 15:56:39,342 INFO L87 Difference]: Start difference. First operand 34 states and 37 transitions. Second operand has 5 states, 4 states have (on average 1.0) internal successors, (4), 4 states have internal predecessors, (4), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:39,420 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 15:56:39,420 INFO L93 Difference]: Finished difference Result 51 states and 58 transitions. [2023-12-02 15:56:39,420 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-12-02 15:56:39,420 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 1.0) internal successors, (4), 4 states have internal predecessors, (4), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 4 [2023-12-02 15:56:39,421 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 15:56:39,421 INFO L225 Difference]: With dead ends: 51 [2023-12-02 15:56:39,421 INFO L226 Difference]: Without dead ends: 51 [2023-12-02 15:56:39,422 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2023-12-02 15:56:39,423 INFO L413 NwaCegarLoop]: 18 mSDtfsCounter, 131 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 131 SdHoareTripleChecker+Valid, 35 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 15:56:39,423 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [131 Valid, 35 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 15:56:39,424 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2023-12-02 15:56:39,427 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 37. [2023-12-02 15:56:39,427 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 24 states have (on average 1.7083333333333333) internal successors, (41), 36 states have internal predecessors, (41), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:39,428 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 41 transitions. [2023-12-02 15:56:39,428 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 41 transitions. Word has length 4 [2023-12-02 15:56:39,428 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 15:56:39,428 INFO L495 AbstractCegarLoop]: Abstraction has 37 states and 41 transitions. [2023-12-02 15:56:39,428 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 1.0) internal successors, (4), 4 states have internal predecessors, (4), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:39,429 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 41 transitions. [2023-12-02 15:56:39,429 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-12-02 15:56:39,429 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:56:39,429 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-12-02 15:56:39,429 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2023-12-02 15:56:39,430 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr8REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:56:39,430 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:56:39,430 INFO L85 PathProgramCache]: Analyzing trace with hash -1531009783, now seen corresponding path program 1 times [2023-12-02 15:56:39,430 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:56:39,430 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [866201689] [2023-12-02 15:56:39,430 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:56:39,431 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:56:39,443 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:56:39,490 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:56:39,490 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:56:39,490 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [866201689] [2023-12-02 15:56:39,490 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [866201689] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 15:56:39,490 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 15:56:39,491 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-12-02 15:56:39,491 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2102333150] [2023-12-02 15:56:39,491 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 15:56:39,491 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-12-02 15:56:39,491 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:56:39,492 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-12-02 15:56:39,492 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-12-02 15:56:39,492 INFO L87 Difference]: Start difference. First operand 37 states and 41 transitions. Second operand has 4 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 4 states have internal predecessors, (7), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:39,539 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 15:56:39,539 INFO L93 Difference]: Finished difference Result 36 states and 40 transitions. [2023-12-02 15:56:39,540 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-12-02 15:56:39,540 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 4 states have internal predecessors, (7), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2023-12-02 15:56:39,540 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 15:56:39,540 INFO L225 Difference]: With dead ends: 36 [2023-12-02 15:56:39,541 INFO L226 Difference]: Without dead ends: 36 [2023-12-02 15:56:39,541 INFO L412 NwaCegarLoop]: 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 [2023-12-02 15:56:39,542 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 34 mSDsluCounter, 16 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 40 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 15:56:39,542 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 40 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 15:56:39,543 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2023-12-02 15:56:39,545 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 34. [2023-12-02 15:56:39,545 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 24 states have (on average 1.5833333333333333) internal successors, (38), 33 states have internal predecessors, (38), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:39,546 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 38 transitions. [2023-12-02 15:56:39,546 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 38 transitions. Word has length 7 [2023-12-02 15:56:39,546 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 15:56:39,546 INFO L495 AbstractCegarLoop]: Abstraction has 34 states and 38 transitions. [2023-12-02 15:56:39,546 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 4 states have internal predecessors, (7), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:39,547 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 38 transitions. [2023-12-02 15:56:39,547 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-12-02 15:56:39,547 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:56:39,547 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-12-02 15:56:39,547 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2023-12-02 15:56:39,547 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr9REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:56:39,548 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:56:39,548 INFO L85 PathProgramCache]: Analyzing trace with hash -1531009782, now seen corresponding path program 1 times [2023-12-02 15:56:39,548 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:56:39,548 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [537093913] [2023-12-02 15:56:39,548 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:56:39,548 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:56:39,562 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:56:39,668 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:56:39,669 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:56:39,669 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [537093913] [2023-12-02 15:56:39,669 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [537093913] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 15:56:39,669 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 15:56:39,669 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-12-02 15:56:39,669 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [854487179] [2023-12-02 15:56:39,669 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 15:56:39,670 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-02 15:56:39,670 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:56:39,670 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-02 15:56:39,670 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-12-02 15:56:39,671 INFO L87 Difference]: Start difference. First operand 34 states and 38 transitions. Second operand has 5 states, 4 states have (on average 1.75) internal successors, (7), 4 states have internal predecessors, (7), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:39,740 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 15:56:39,740 INFO L93 Difference]: Finished difference Result 34 states and 38 transitions. [2023-12-02 15:56:39,741 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-12-02 15:56:39,741 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 1.75) internal successors, (7), 4 states have internal predecessors, (7), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2023-12-02 15:56:39,742 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 15:56:39,742 INFO L225 Difference]: With dead ends: 34 [2023-12-02 15:56:39,742 INFO L226 Difference]: Without dead ends: 34 [2023-12-02 15:56:39,742 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2023-12-02 15:56:39,743 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 60 mSDsluCounter, 20 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 60 SdHoareTripleChecker+Valid, 40 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 15:56:39,743 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [60 Valid, 40 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 15:56:39,744 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2023-12-02 15:56:39,746 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 32. [2023-12-02 15:56:39,746 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 25 states have (on average 1.44) internal successors, (36), 31 states have internal predecessors, (36), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:39,746 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 36 transitions. [2023-12-02 15:56:39,747 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 36 transitions. Word has length 7 [2023-12-02 15:56:39,747 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 15:56:39,747 INFO L495 AbstractCegarLoop]: Abstraction has 32 states and 36 transitions. [2023-12-02 15:56:39,747 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 1.75) internal successors, (7), 4 states have internal predecessors, (7), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:39,747 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 36 transitions. [2023-12-02 15:56:39,748 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2023-12-02 15:56:39,748 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:56:39,748 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 15:56:39,748 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2023-12-02 15:56:39,748 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr15ASSERT_VIOLATIONMEMORY_FREE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:56:39,749 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:56:39,749 INFO L85 PathProgramCache]: Analyzing trace with hash 1870915810, now seen corresponding path program 1 times [2023-12-02 15:56:39,749 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:56:39,749 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1741149937] [2023-12-02 15:56:39,749 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:56:39,749 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:56:39,777 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:56:39,794 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:56:39,794 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:56:39,794 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1741149937] [2023-12-02 15:56:39,794 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1741149937] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 15:56:39,794 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 15:56:39,794 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-12-02 15:56:39,795 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1918194771] [2023-12-02 15:56:39,795 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 15:56:39,795 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-12-02 15:56:39,795 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:56:39,796 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-12-02 15:56:39,796 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-12-02 15:56:39,796 INFO L87 Difference]: Start difference. First operand 32 states and 36 transitions. Second operand has 3 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:39,813 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 15:56:39,813 INFO L93 Difference]: Finished difference Result 31 states and 35 transitions. [2023-12-02 15:56:39,813 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-12-02 15:56:39,813 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2023-12-02 15:56:39,814 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 15:56:39,814 INFO L225 Difference]: With dead ends: 31 [2023-12-02 15:56:39,814 INFO L226 Difference]: Without dead ends: 31 [2023-12-02 15:56:39,814 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 1 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-12-02 15:56:39,815 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 22 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 19 SdHoareTripleChecker+Invalid, 11 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 15:56:39,815 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 19 Invalid, 11 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 15:56:39,816 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2023-12-02 15:56:39,817 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2023-12-02 15:56:39,818 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 25 states have (on average 1.4) internal successors, (35), 30 states have internal predecessors, (35), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:39,818 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 35 transitions. [2023-12-02 15:56:39,818 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 35 transitions. Word has length 9 [2023-12-02 15:56:39,818 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 15:56:39,818 INFO L495 AbstractCegarLoop]: Abstraction has 31 states and 35 transitions. [2023-12-02 15:56:39,819 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:39,819 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 35 transitions. [2023-12-02 15:56:39,819 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2023-12-02 15:56:39,819 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:56:39,819 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 15:56:39,819 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8 [2023-12-02 15:56:39,820 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr9REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:56:39,820 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:56:39,820 INFO L85 PathProgramCache]: Analyzing trace with hash -2052977244, now seen corresponding path program 1 times [2023-12-02 15:56:39,820 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:56:39,820 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1943525996] [2023-12-02 15:56:39,821 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:56:39,821 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:56:39,833 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:56:39,847 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:56:39,848 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:56:39,848 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1943525996] [2023-12-02 15:56:39,848 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1943525996] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 15:56:39,848 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 15:56:39,848 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-12-02 15:56:39,848 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1824528118] [2023-12-02 15:56:39,848 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 15:56:39,849 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-12-02 15:56:39,849 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:56:39,849 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-12-02 15:56:39,849 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-12-02 15:56:39,849 INFO L87 Difference]: Start difference. First operand 31 states and 35 transitions. Second operand has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:39,867 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 15:56:39,867 INFO L93 Difference]: Finished difference Result 32 states and 36 transitions. [2023-12-02 15:56:39,868 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-12-02 15:56:39,868 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 10 [2023-12-02 15:56:39,868 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 15:56:39,868 INFO L225 Difference]: With dead ends: 32 [2023-12-02 15:56:39,868 INFO L226 Difference]: Without dead ends: 32 [2023-12-02 15:56:39,869 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-12-02 15:56:39,869 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 0 mSDsluCounter, 19 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 42 SdHoareTripleChecker+Invalid, 17 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 15:56:39,870 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 42 Invalid, 17 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 15:56:39,870 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2023-12-02 15:56:39,872 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2023-12-02 15:56:39,872 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 26 states have (on average 1.3846153846153846) internal successors, (36), 31 states have internal predecessors, (36), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:39,872 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 36 transitions. [2023-12-02 15:56:39,872 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 36 transitions. Word has length 10 [2023-12-02 15:56:39,873 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 15:56:39,873 INFO L495 AbstractCegarLoop]: Abstraction has 32 states and 36 transitions. [2023-12-02 15:56:39,873 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:39,873 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 36 transitions. [2023-12-02 15:56:39,873 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2023-12-02 15:56:39,873 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:56:39,874 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 15:56:39,874 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9 [2023-12-02 15:56:39,874 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr9REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:56:39,874 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:56:39,874 INFO L85 PathProgramCache]: Analyzing trace with hash 782076071, now seen corresponding path program 1 times [2023-12-02 15:56:39,875 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:56:39,875 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [395398487] [2023-12-02 15:56:39,875 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:56:39,875 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:56:39,897 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:56:40,194 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:56:40,195 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:56:40,195 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [395398487] [2023-12-02 15:56:40,195 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [395398487] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 15:56:40,195 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2036102280] [2023-12-02 15:56:40,196 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:56:40,196 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 15:56:40,196 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 15:56:40,199 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 15:56:40,200 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-12-02 15:56:40,276 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:56:40,279 INFO L262 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 24 conjunts are in the unsatisfiable core [2023-12-02 15:56:40,284 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 15:56:40,358 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 10 [2023-12-02 15:56:40,597 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-02 15:56:40,598 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 32 treesize of output 29 [2023-12-02 15:56:40,703 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:56:40,703 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 15:56:40,954 INFO L378 Elim1Store]: Elim1 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 [2023-12-02 15:56:40,961 INFO L378 Elim1Store]: Elim1 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 15 treesize of output 11 [2023-12-02 15:56:40,972 INFO L378 Elim1Store]: Elim1 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 22 treesize of output 20 [2023-12-02 15:56:40,983 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:56:40,983 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2036102280] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 15:56:40,983 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [136475683] [2023-12-02 15:56:41,002 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2023-12-02 15:56:41,002 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 15:56:41,008 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 15:56:41,013 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 15:56:41,013 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 15:56:42,500 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 15:56:44,299 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '893#(and (<= 1 |#StackHeapBarrier|) (<= (select |#length| |ULTIMATE.start_cstrpbrk_~s~0#1.base|) |ULTIMATE.start_cstrpbrk_~s~0#1.offset|) (<= 0 |ULTIMATE.start_cstrpbrk_~s~0#1.offset|) (= |ULTIMATE.start_main_~nondetString2~0#1.offset| 0) (= |ULTIMATE.start_cstrpbrk_~sc1~0#1.offset| 0) (<= 1 |ULTIMATE.start_main_~length1~0#1|) (= |ULTIMATE.start_cstrpbrk_#in~s1#1.offset| 0) (= |ULTIMATE.start_cstrpbrk_~s2#1.offset| 0) (= |ULTIMATE.start_main_~nondetString1~0#1.offset| 0) (= 0 |ULTIMATE.start_cstrpbrk_~s1#1.offset|) (<= 1 |ULTIMATE.start_main_~length2~0#1|) (= |ULTIMATE.start_cstrpbrk_#in~s2#1.offset| 0))' at error location [2023-12-02 15:56:44,299 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 15:56:44,299 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 15:56:44,299 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 15 [2023-12-02 15:56:44,300 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1415076084] [2023-12-02 15:56:44,300 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 15:56:44,300 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-12-02 15:56:44,300 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:56:44,301 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-12-02 15:56:44,301 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=102, Invalid=496, Unknown=2, NotChecked=0, Total=600 [2023-12-02 15:56:44,302 INFO L87 Difference]: Start difference. First operand 32 states and 36 transitions. Second operand has 17 states, 16 states have (on average 1.75) internal successors, (28), 16 states have internal predecessors, (28), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:44,956 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 15:56:44,956 INFO L93 Difference]: Finished difference Result 64 states and 78 transitions. [2023-12-02 15:56:44,956 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-12-02 15:56:44,957 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 16 states have (on average 1.75) internal successors, (28), 16 states have internal predecessors, (28), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2023-12-02 15:56:44,957 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 15:56:44,958 INFO L225 Difference]: With dead ends: 64 [2023-12-02 15:56:44,959 INFO L226 Difference]: Without dead ends: 64 [2023-12-02 15:56:44,959 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 13 SyntacticMatches, 1 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 248 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=219, Invalid=901, Unknown=2, NotChecked=0, Total=1122 [2023-12-02 15:56:44,960 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 226 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 175 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 226 SdHoareTripleChecker+Valid, 110 SdHoareTripleChecker+Invalid, 178 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 175 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 15:56:44,960 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [226 Valid, 110 Invalid, 178 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 175 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 15:56:44,961 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2023-12-02 15:56:44,964 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 36. [2023-12-02 15:56:44,964 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 30 states have (on average 1.4) internal successors, (42), 35 states have internal predecessors, (42), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:44,965 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 42 transitions. [2023-12-02 15:56:44,965 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 42 transitions. Word has length 11 [2023-12-02 15:56:44,965 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 15:56:44,965 INFO L495 AbstractCegarLoop]: Abstraction has 36 states and 42 transitions. [2023-12-02 15:56:44,965 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 16 states have (on average 1.75) internal successors, (28), 16 states have internal predecessors, (28), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:44,965 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 42 transitions. [2023-12-02 15:56:44,966 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2023-12-02 15:56:44,966 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:56:44,966 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 15:56:44,972 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-12-02 15:56:45,171 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2023-12-02 15:56:45,171 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr5REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:56:45,172 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:56:45,172 INFO L85 PathProgramCache]: Analyzing trace with hash -1521179792, now seen corresponding path program 1 times [2023-12-02 15:56:45,172 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:56:45,172 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1034854129] [2023-12-02 15:56:45,172 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:56:45,172 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:56:45,185 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:56:45,274 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:56:45,274 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:56:45,274 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1034854129] [2023-12-02 15:56:45,275 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1034854129] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 15:56:45,275 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 15:56:45,275 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2023-12-02 15:56:45,275 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1407760105] [2023-12-02 15:56:45,275 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 15:56:45,275 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-12-02 15:56:45,276 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:56:45,276 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-12-02 15:56:45,276 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2023-12-02 15:56:45,276 INFO L87 Difference]: Start difference. First operand 36 states and 42 transitions. Second operand has 8 states, 8 states have (on average 1.5) internal successors, (12), 8 states have internal predecessors, (12), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:45,385 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 15:56:45,385 INFO L93 Difference]: Finished difference Result 42 states and 48 transitions. [2023-12-02 15:56:45,385 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-12-02 15:56:45,385 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 1.5) internal successors, (12), 8 states have internal predecessors, (12), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 12 [2023-12-02 15:56:45,386 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 15:56:45,386 INFO L225 Difference]: With dead ends: 42 [2023-12-02 15:56:45,386 INFO L226 Difference]: Without dead ends: 42 [2023-12-02 15:56:45,386 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=110, Unknown=0, NotChecked=0, Total=156 [2023-12-02 15:56:45,387 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 38 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 94 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 87 SdHoareTripleChecker+Invalid, 94 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 94 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 15:56:45,387 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 87 Invalid, 94 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 94 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 15:56:45,388 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2023-12-02 15:56:45,390 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 38. [2023-12-02 15:56:45,390 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 32 states have (on average 1.375) internal successors, (44), 37 states have internal predecessors, (44), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:45,390 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 44 transitions. [2023-12-02 15:56:45,391 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 44 transitions. Word has length 12 [2023-12-02 15:56:45,391 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 15:56:45,391 INFO L495 AbstractCegarLoop]: Abstraction has 38 states and 44 transitions. [2023-12-02 15:56:45,391 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 1.5) internal successors, (12), 8 states have internal predecessors, (12), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:45,391 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 44 transitions. [2023-12-02 15:56:45,392 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2023-12-02 15:56:45,392 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:56:45,392 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 15:56:45,392 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11 [2023-12-02 15:56:45,392 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr18ASSERT_VIOLATIONMEMORY_FREE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:56:45,392 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:56:45,393 INFO L85 PathProgramCache]: Analyzing trace with hash 662409779, now seen corresponding path program 1 times [2023-12-02 15:56:45,393 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:56:45,393 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1623237751] [2023-12-02 15:56:45,393 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:56:45,393 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:56:45,404 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:56:45,421 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:56:45,421 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:56:45,421 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1623237751] [2023-12-02 15:56:45,422 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1623237751] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 15:56:45,422 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 15:56:45,422 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-12-02 15:56:45,422 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1814231119] [2023-12-02 15:56:45,422 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 15:56:45,422 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-12-02 15:56:45,422 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:56:45,423 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-12-02 15:56:45,423 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-12-02 15:56:45,423 INFO L87 Difference]: Start difference. First operand 38 states and 44 transitions. Second operand has 3 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:45,437 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 15:56:45,437 INFO L93 Difference]: Finished difference Result 37 states and 43 transitions. [2023-12-02 15:56:45,437 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-12-02 15:56:45,437 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 12 [2023-12-02 15:56:45,437 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 15:56:45,438 INFO L225 Difference]: With dead ends: 37 [2023-12-02 15:56:45,438 INFO L226 Difference]: Without dead ends: 37 [2023-12-02 15:56:45,438 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 1 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-12-02 15:56:45,439 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 18 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 19 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 15:56:45,439 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 19 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 15:56:45,440 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2023-12-02 15:56:45,441 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2023-12-02 15:56:45,441 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 32 states have (on average 1.34375) internal successors, (43), 36 states have internal predecessors, (43), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:45,442 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 43 transitions. [2023-12-02 15:56:45,442 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 43 transitions. Word has length 12 [2023-12-02 15:56:45,442 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 15:56:45,442 INFO L495 AbstractCegarLoop]: Abstraction has 37 states and 43 transitions. [2023-12-02 15:56:45,442 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:45,442 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 43 transitions. [2023-12-02 15:56:45,443 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2023-12-02 15:56:45,443 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:56:45,443 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 15:56:45,443 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12 [2023-12-02 15:56:45,443 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr5REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:56:45,443 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:56:45,444 INFO L85 PathProgramCache]: Analyzing trace with hash -44209741, now seen corresponding path program 1 times [2023-12-02 15:56:45,444 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:56:45,444 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [254581355] [2023-12-02 15:56:45,444 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:56:45,444 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:56:45,459 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:56:45,713 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:56:45,713 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:56:45,713 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [254581355] [2023-12-02 15:56:45,713 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [254581355] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 15:56:45,713 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [853404903] [2023-12-02 15:56:45,714 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:56:45,714 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 15:56:45,714 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 15:56:45,715 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 15:56:45,718 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-12-02 15:56:45,785 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:56:45,787 INFO L262 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 41 conjunts are in the unsatisfiable core [2023-12-02 15:56:45,789 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 15:56:45,794 INFO L378 Elim1Store]: Elim1 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 10 treesize of output 8 [2023-12-02 15:56:45,817 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 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 14 treesize of output 10 [2023-12-02 15:56:45,866 INFO L378 Elim1Store]: Elim1 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 19 treesize of output 14 [2023-12-02 15:56:46,334 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-02 15:56:46,334 INFO L378 Elim1Store]: Elim1 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 1 case distinctions, treesize of input 33 treesize of output 26 [2023-12-02 15:56:46,416 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:56:46,416 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 15:56:46,764 WARN L854 $PredicateComparison]: unable to prove that (forall ((|ULTIMATE.start_cstrpbrk_~s~0#1.offset| Int) (|v_ULTIMATE.start_cstrpbrk_~sc1~0#1.offset_23| Int) (v_ArrVal_121 (Array Int Int))) (let ((.cse0 (select v_ArrVal_121 |ULTIMATE.start_cstrpbrk_~s~0#1.offset|))) (or (< |c_ULTIMATE.start_main_~nondetString1~0#1.offset| |v_ULTIMATE.start_cstrpbrk_~sc1~0#1.offset_23|) (= .cse0 0) (< (+ |v_ULTIMATE.start_cstrpbrk_~sc1~0#1.offset_23| 1) (select |c_#length| |c_ULTIMATE.start_main_~nondetString1~0#1.base|)) (not (= .cse0 (select (select (store |c_#memory_int| |c_ULTIMATE.start_main_~nondetString2~0#1.base| v_ArrVal_121) |c_ULTIMATE.start_main_~nondetString1~0#1.base|) |v_ULTIMATE.start_cstrpbrk_~sc1~0#1.offset_23|))) (< |v_ULTIMATE.start_cstrpbrk_~sc1~0#1.offset_23| 0)))) is different from false [2023-12-02 15:56:46,790 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-02 15:56:46,790 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 24 treesize of output 25 [2023-12-02 15:56:46,803 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-02 15:56:46,804 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 40 treesize of output 41 [2023-12-02 15:56:46,817 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-02 15:56:46,818 INFO L378 Elim1Store]: Elim1 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 2 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 30 [2023-12-02 15:56:46,825 INFO L378 Elim1Store]: Elim1 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 15 treesize of output 11 [2023-12-02 15:56:46,896 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:56:46,896 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [853404903] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 15:56:46,896 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1910638400] [2023-12-02 15:56:46,899 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2023-12-02 15:56:46,899 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 15:56:46,899 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 15:56:46,899 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 15:56:46,899 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 15:56:49,557 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 15:56:56,871 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1294#(and (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start_main_~nondetString2~0#1.offset| 0) (<= 1 |ULTIMATE.start_main_~length1~0#1|) (<= 1 |ULTIMATE.start_cstrpbrk_~sc1~0#1.offset|) (= |ULTIMATE.start_cstrpbrk_#in~s1#1.offset| 0) (= |ULTIMATE.start_cstrpbrk_~s2#1.offset| 0) (= |ULTIMATE.start_main_~nondetString1~0#1.offset| 0) (= 0 |ULTIMATE.start_cstrpbrk_~s1#1.offset|) (<= 1 |ULTIMATE.start_main_~length2~0#1|) (= |ULTIMATE.start_cstrpbrk_~s~0#1.offset| 0) (<= (select |#length| |ULTIMATE.start_cstrpbrk_~sc1~0#1.base|) |ULTIMATE.start_cstrpbrk_~sc1~0#1.offset|) (= |ULTIMATE.start_cstrpbrk_#in~s2#1.offset| 0))' at error location [2023-12-02 15:56:56,872 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 15:56:56,872 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 15:56:56,872 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 10, 10] total 26 [2023-12-02 15:56:56,872 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1204569304] [2023-12-02 15:56:56,872 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 15:56:56,873 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2023-12-02 15:56:56,873 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:56:56,873 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2023-12-02 15:56:56,874 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=186, Invalid=1298, Unknown=2, NotChecked=74, Total=1560 [2023-12-02 15:56:56,874 INFO L87 Difference]: Start difference. First operand 37 states and 43 transitions. Second operand has 28 states, 27 states have (on average 1.4444444444444444) internal successors, (39), 27 states have internal predecessors, (39), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:58,339 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 15:56:58,339 INFO L93 Difference]: Finished difference Result 97 states and 120 transitions. [2023-12-02 15:56:58,340 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2023-12-02 15:56:58,340 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 27 states have (on average 1.4444444444444444) internal successors, (39), 27 states have internal predecessors, (39), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 13 [2023-12-02 15:56:58,340 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 15:56:58,341 INFO L225 Difference]: With dead ends: 97 [2023-12-02 15:56:58,341 INFO L226 Difference]: Without dead ends: 97 [2023-12-02 15:56:58,342 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 5 SyntacticMatches, 1 SemanticMatches, 56 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 845 ImplicationChecksByTransitivity, 8.9s TimeCoverageRelationStatistics Valid=558, Invalid=2636, Unknown=2, NotChecked=110, Total=3306 [2023-12-02 15:56:58,343 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 451 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 432 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 451 SdHoareTripleChecker+Valid, 86 SdHoareTripleChecker+Invalid, 537 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 432 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 87 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-12-02 15:56:58,343 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [451 Valid, 86 Invalid, 537 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 432 Invalid, 0 Unknown, 87 Unchecked, 0.4s Time] [2023-12-02 15:56:58,344 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states. [2023-12-02 15:56:58,347 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 62. [2023-12-02 15:56:58,347 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 58 states have (on average 1.396551724137931) internal successors, (81), 61 states have internal predecessors, (81), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:58,348 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 81 transitions. [2023-12-02 15:56:58,348 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 81 transitions. Word has length 13 [2023-12-02 15:56:58,349 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 15:56:58,349 INFO L495 AbstractCegarLoop]: Abstraction has 62 states and 81 transitions. [2023-12-02 15:56:58,349 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 27 states have (on average 1.4444444444444444) internal successors, (39), 27 states have internal predecessors, (39), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:58,349 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 81 transitions. [2023-12-02 15:56:58,350 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2023-12-02 15:56:58,350 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:56:58,350 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 15:56:58,355 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2023-12-02 15:56:58,555 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2023-12-02 15:56:58,555 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr19ASSERT_VIOLATIONMEMORY_FREE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:56:58,555 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:56:58,555 INFO L85 PathProgramCache]: Analyzing trace with hash -940133210, now seen corresponding path program 1 times [2023-12-02 15:56:58,556 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:56:58,556 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1586880442] [2023-12-02 15:56:58,556 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:56:58,556 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:56:58,565 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:56:58,649 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:56:58,649 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:56:58,649 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1586880442] [2023-12-02 15:56:58,649 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1586880442] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 15:56:58,650 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 15:56:58,650 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-12-02 15:56:58,650 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [198940981] [2023-12-02 15:56:58,650 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 15:56:58,650 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-02 15:56:58,651 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:56:58,651 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-02 15:56:58,651 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2023-12-02 15:56:58,651 INFO L87 Difference]: Start difference. First operand 62 states and 81 transitions. Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:58,680 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 15:56:58,680 INFO L93 Difference]: Finished difference Result 61 states and 80 transitions. [2023-12-02 15:56:58,681 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-12-02 15:56:58,681 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 13 [2023-12-02 15:56:58,681 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 15:56:58,681 INFO L225 Difference]: With dead ends: 61 [2023-12-02 15:56:58,681 INFO L226 Difference]: Without dead ends: 61 [2023-12-02 15:56:58,682 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2023-12-02 15:56:58,682 INFO L413 NwaCegarLoop]: 14 mSDtfsCounter, 48 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 15 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 14 SdHoareTripleChecker+Invalid, 18 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 15 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 15:56:58,683 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 14 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 15 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 15:56:58,683 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2023-12-02 15:56:58,685 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 61. [2023-12-02 15:56:58,685 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 61 states, 58 states have (on average 1.3793103448275863) internal successors, (80), 60 states have internal predecessors, (80), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:58,686 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 80 transitions. [2023-12-02 15:56:58,686 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 80 transitions. Word has length 13 [2023-12-02 15:56:58,686 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 15:56:58,686 INFO L495 AbstractCegarLoop]: Abstraction has 61 states and 80 transitions. [2023-12-02 15:56:58,686 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:58,687 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 80 transitions. [2023-12-02 15:56:58,687 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2023-12-02 15:56:58,687 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:56:58,687 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 15:56:58,687 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14 [2023-12-02 15:56:58,688 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr20ASSERT_VIOLATIONMEMORY_LEAK === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:56:58,688 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:56:58,688 INFO L85 PathProgramCache]: Analyzing trace with hash 920641686, now seen corresponding path program 1 times [2023-12-02 15:56:58,688 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:56:58,688 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1238525338] [2023-12-02 15:56:58,688 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:56:58,688 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:56:58,699 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:56:58,830 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:56:58,830 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:56:58,830 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1238525338] [2023-12-02 15:56:58,830 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1238525338] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 15:56:58,831 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 15:56:58,831 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-12-02 15:56:58,831 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [93529462] [2023-12-02 15:56:58,831 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 15:56:58,831 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-02 15:56:58,831 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:56:58,832 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-02 15:56:58,832 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-12-02 15:56:58,832 INFO L87 Difference]: Start difference. First operand 61 states and 80 transitions. Second operand has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:58,894 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 15:56:58,894 INFO L93 Difference]: Finished difference Result 60 states and 79 transitions. [2023-12-02 15:56:58,894 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-12-02 15:56:58,894 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 14 [2023-12-02 15:56:58,894 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 15:56:58,895 INFO L225 Difference]: With dead ends: 60 [2023-12-02 15:56:58,895 INFO L226 Difference]: Without dead ends: 48 [2023-12-02 15:56:58,895 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2023-12-02 15:56:58,896 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 15 mSDsluCounter, 25 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 38 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 15:56:58,896 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 38 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 15:56:58,897 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2023-12-02 15:56:58,898 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2023-12-02 15:56:58,899 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 46 states have (on average 1.2173913043478262) internal successors, (56), 47 states have internal predecessors, (56), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:58,899 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 56 transitions. [2023-12-02 15:56:58,899 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 56 transitions. Word has length 14 [2023-12-02 15:56:58,900 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 15:56:58,900 INFO L495 AbstractCegarLoop]: Abstraction has 48 states and 56 transitions. [2023-12-02 15:56:58,900 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:56:58,900 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 56 transitions. [2023-12-02 15:56:58,900 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2023-12-02 15:56:58,901 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:56:58,901 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 15:56:58,901 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15 [2023-12-02 15:56:58,901 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting ULTIMATE.startErr9REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:56:58,902 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:56:58,902 INFO L85 PathProgramCache]: Analyzing trace with hash 553080260, now seen corresponding path program 2 times [2023-12-02 15:56:58,902 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:56:58,902 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [362906536] [2023-12-02 15:56:58,902 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:56:58,902 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:56:58,920 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:56:59,310 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:56:59,310 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:56:59,310 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [362906536] [2023-12-02 15:56:59,310 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [362906536] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 15:56:59,310 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [683631043] [2023-12-02 15:56:59,310 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-02 15:56:59,311 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 15:56:59,311 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 15:56:59,311 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 15:56:59,312 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-12-02 15:56:59,388 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-12-02 15:56:59,388 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 15:56:59,390 INFO L262 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 34 conjunts are in the unsatisfiable core [2023-12-02 15:56:59,392 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 15:56:59,400 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 1 [2023-12-02 15:56:59,425 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 10 [2023-12-02 15:57:03,428 INFO L349 Elim1Store]: treesize reduction 8, result has 75.8 percent of original size [2023-12-02 15:57:03,428 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 27 treesize of output 36 [2023-12-02 15:57:03,496 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:57:03,497 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 15:57:04,013 INFO L378 Elim1Store]: Elim1 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 27 treesize of output 23 [2023-12-02 15:57:04,026 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-02 15:57:04,027 INFO L378 Elim1Store]: Elim1 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 2 new quantified variables, introduced 1 case distinctions, treesize of input 43 treesize of output 47 [2023-12-02 15:57:04,088 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:57:04,088 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [683631043] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 15:57:04,088 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [470169372] [2023-12-02 15:57:04,090 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2023-12-02 15:57:04,090 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 15:57:04,090 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 15:57:04,091 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 15:57:04,091 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 15:57:04,782 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 15:57:06,398 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1860#(and (<= 1 |#StackHeapBarrier|) (<= (select |#length| |ULTIMATE.start_cstrpbrk_~s~0#1.base|) |ULTIMATE.start_cstrpbrk_~s~0#1.offset|) (<= 0 |ULTIMATE.start_cstrpbrk_~s~0#1.offset|) (= |ULTIMATE.start_main_~nondetString2~0#1.offset| 0) (= |ULTIMATE.start_cstrpbrk_~sc1~0#1.offset| 0) (<= 1 |ULTIMATE.start_main_~length1~0#1|) (= |ULTIMATE.start_cstrpbrk_#in~s1#1.offset| 0) (= |ULTIMATE.start_cstrpbrk_~s2#1.offset| 0) (= |ULTIMATE.start_main_~nondetString1~0#1.offset| 0) (= 0 |ULTIMATE.start_cstrpbrk_~s1#1.offset|) (<= 1 |ULTIMATE.start_main_~length2~0#1|) (= |ULTIMATE.start_cstrpbrk_#in~s2#1.offset| 0))' at error location [2023-12-02 15:57:06,398 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 15:57:06,398 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 15:57:06,399 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 10, 10] total 28 [2023-12-02 15:57:06,399 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [478462138] [2023-12-02 15:57:06,399 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 15:57:06,399 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2023-12-02 15:57:06,399 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:57:06,400 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2023-12-02 15:57:06,401 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=181, Invalid=1222, Unknown=3, NotChecked=0, Total=1406 [2023-12-02 15:57:06,401 INFO L87 Difference]: Start difference. First operand 48 states and 56 transitions. Second operand has 30 states, 29 states have (on average 1.5517241379310345) internal successors, (45), 29 states have internal predecessors, (45), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:57:09,271 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 15:57:09,271 INFO L93 Difference]: Finished difference Result 153 states and 173 transitions. [2023-12-02 15:57:09,271 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2023-12-02 15:57:09,272 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 29 states have (on average 1.5517241379310345) internal successors, (45), 29 states have internal predecessors, (45), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 15 [2023-12-02 15:57:09,272 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 15:57:09,273 INFO L225 Difference]: With dead ends: 153 [2023-12-02 15:57:09,273 INFO L226 Difference]: Without dead ends: 153 [2023-12-02 15:57:09,274 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 673 ImplicationChecksByTransitivity, 8.0s TimeCoverageRelationStatistics Valid=510, Invalid=2457, Unknown=3, NotChecked=0, Total=2970 [2023-12-02 15:57:09,275 INFO L413 NwaCegarLoop]: 3 mSDtfsCounter, 423 mSDsluCounter, 21 mSDsCounter, 0 mSdLazyCounter, 387 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 423 SdHoareTripleChecker+Valid, 24 SdHoareTripleChecker+Invalid, 397 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 387 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2023-12-02 15:57:09,275 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [423 Valid, 24 Invalid, 397 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 387 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2023-12-02 15:57:09,275 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 153 states. [2023-12-02 15:57:09,279 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 153 to 84. [2023-12-02 15:57:09,279 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 84 states, 82 states have (on average 1.2317073170731707) internal successors, (101), 83 states have internal predecessors, (101), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:57:09,280 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 101 transitions. [2023-12-02 15:57:09,280 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 101 transitions. Word has length 15 [2023-12-02 15:57:09,280 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 15:57:09,280 INFO L495 AbstractCegarLoop]: Abstraction has 84 states and 101 transitions. [2023-12-02 15:57:09,281 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 29 states have (on average 1.5517241379310345) internal successors, (45), 29 states have internal predecessors, (45), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:57:09,281 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 101 transitions. [2023-12-02 15:57:09,282 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2023-12-02 15:57:09,282 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:57:09,282 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 15:57:09,288 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2023-12-02 15:57:09,487 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2023-12-02 15:57:09,487 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting ULTIMATE.startErr9REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:57:09,488 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:57:09,488 INFO L85 PathProgramCache]: Analyzing trace with hash -786516453, now seen corresponding path program 3 times [2023-12-02 15:57:09,488 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:57:09,488 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [761325022] [2023-12-02 15:57:09,488 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:57:09,488 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:57:09,510 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:57:10,151 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:57:10,151 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:57:10,152 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [761325022] [2023-12-02 15:57:10,152 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [761325022] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 15:57:10,152 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1554944983] [2023-12-02 15:57:10,152 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-02 15:57:10,152 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 15:57:10,152 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 15:57:10,153 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 15:57:10,159 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-12-02 15:57:10,245 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-02 15:57:10,245 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 15:57:10,247 INFO L262 TraceCheckSpWp]: Trace formula consists of 188 conjuncts, 56 conjunts are in the unsatisfiable core [2023-12-02 15:57:10,249 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 15:57:10,277 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 10 [2023-12-02 15:57:11,612 INFO L349 Elim1Store]: treesize reduction 16, result has 71.4 percent of original size [2023-12-02 15:57:11,613 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 6 select indices, 6 select index equivalence classes, 10 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 5 case distinctions, treesize of input 72 treesize of output 72 [2023-12-02 15:57:11,791 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:57:11,791 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 15:57:12,990 INFO L378 Elim1Store]: Elim1 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 74 treesize of output 64 [2023-12-02 15:57:13,001 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 10 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 0 case distinctions, treesize of input 114 treesize of output 96 [2023-12-02 15:57:13,012 INFO L378 Elim1Store]: Elim1 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 13 treesize of output 9 [2023-12-02 15:57:13,028 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:57:13,028 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1554944983] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 15:57:13,028 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [690032401] [2023-12-02 15:57:13,030 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2023-12-02 15:57:13,030 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 15:57:13,030 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 15:57:13,030 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 15:57:13,031 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 15:57:13,554 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 15:57:15,629 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2343#(and (<= 1 |#StackHeapBarrier|) (<= (select |#length| |ULTIMATE.start_cstrpbrk_~s~0#1.base|) |ULTIMATE.start_cstrpbrk_~s~0#1.offset|) (<= 0 |ULTIMATE.start_cstrpbrk_~s~0#1.offset|) (= |ULTIMATE.start_main_~nondetString2~0#1.offset| 0) (= |ULTIMATE.start_cstrpbrk_~sc1~0#1.offset| 0) (<= 1 |ULTIMATE.start_main_~length1~0#1|) (= |ULTIMATE.start_cstrpbrk_#in~s1#1.offset| 0) (= |ULTIMATE.start_cstrpbrk_~s2#1.offset| 0) (= |ULTIMATE.start_main_~nondetString1~0#1.offset| 0) (= 0 |ULTIMATE.start_cstrpbrk_~s1#1.offset|) (<= 1 |ULTIMATE.start_main_~length2~0#1|) (= |ULTIMATE.start_cstrpbrk_#in~s2#1.offset| 0))' at error location [2023-12-02 15:57:15,629 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 15:57:15,629 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 15:57:15,629 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 18, 18] total 46 [2023-12-02 15:57:15,630 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [645035315] [2023-12-02 15:57:15,630 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 15:57:15,630 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 48 states [2023-12-02 15:57:15,630 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:57:15,631 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2023-12-02 15:57:15,632 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=328, Invalid=2751, Unknown=1, NotChecked=0, Total=3080 [2023-12-02 15:57:15,633 INFO L87 Difference]: Start difference. First operand 84 states and 101 transitions. Second operand has 48 states, 47 states have (on average 1.6808510638297873) internal successors, (79), 47 states have internal predecessors, (79), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:57:23,155 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 15:57:23,155 INFO L93 Difference]: Finished difference Result 273 states and 308 transitions. [2023-12-02 15:57:23,155 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2023-12-02 15:57:23,155 INFO L78 Accepts]: Start accepts. Automaton has has 48 states, 47 states have (on average 1.6808510638297873) internal successors, (79), 47 states have internal predecessors, (79), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 27 [2023-12-02 15:57:23,156 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 15:57:23,157 INFO L225 Difference]: With dead ends: 273 [2023-12-02 15:57:23,157 INFO L226 Difference]: Without dead ends: 273 [2023-12-02 15:57:23,160 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 125 GetRequests, 35 SyntacticMatches, 1 SemanticMatches, 89 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1902 ImplicationChecksByTransitivity, 10.2s TimeCoverageRelationStatistics Valid=1162, Invalid=7027, Unknown=1, NotChecked=0, Total=8190 [2023-12-02 15:57:23,160 INFO L413 NwaCegarLoop]: 6 mSDtfsCounter, 803 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 1218 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 803 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 1223 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 1218 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2023-12-02 15:57:23,161 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [803 Valid, 91 Invalid, 1223 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 1218 Invalid, 0 Unknown, 0 Unchecked, 1.4s Time] [2023-12-02 15:57:23,161 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 273 states. [2023-12-02 15:57:23,166 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 273 to 144. [2023-12-02 15:57:23,167 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 144 states, 142 states have (on average 1.2394366197183098) internal successors, (176), 143 states have internal predecessors, (176), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:57:23,168 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 144 states to 144 states and 176 transitions. [2023-12-02 15:57:23,168 INFO L78 Accepts]: Start accepts. Automaton has 144 states and 176 transitions. Word has length 27 [2023-12-02 15:57:23,168 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 15:57:23,168 INFO L495 AbstractCegarLoop]: Abstraction has 144 states and 176 transitions. [2023-12-02 15:57:23,169 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 48 states, 47 states have (on average 1.6808510638297873) internal successors, (79), 47 states have internal predecessors, (79), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:57:23,169 INFO L276 IsEmpty]: Start isEmpty. Operand 144 states and 176 transitions. [2023-12-02 15:57:23,170 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2023-12-02 15:57:23,170 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:57:23,170 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1] [2023-12-02 15:57:23,179 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2023-12-02 15:57:23,379 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2023-12-02 15:57:23,379 INFO L420 AbstractCegarLoop]: === Iteration 19 === Targeting ULTIMATE.startErr5REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:57:23,380 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:57:23,380 INFO L85 PathProgramCache]: Analyzing trace with hash 1396143763, now seen corresponding path program 2 times [2023-12-02 15:57:23,380 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:57:23,380 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1473921800] [2023-12-02 15:57:23,380 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:57:23,380 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:57:23,399 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:57:23,911 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:57:23,911 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:57:23,911 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1473921800] [2023-12-02 15:57:23,911 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1473921800] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 15:57:23,911 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1011241077] [2023-12-02 15:57:23,911 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-02 15:57:23,911 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 15:57:23,911 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 15:57:23,912 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 15:57:23,914 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-12-02 15:57:24,005 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2023-12-02 15:57:24,005 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 15:57:24,008 INFO L262 TraceCheckSpWp]: Trace formula consists of 206 conjuncts, 83 conjunts are in the unsatisfiable core [2023-12-02 15:57:24,013 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 15:57:24,019 INFO L378 Elim1Store]: Elim1 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 10 treesize of output 8 [2023-12-02 15:57:24,043 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 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 13 treesize of output 9 [2023-12-02 15:57:24,099 INFO L378 Elim1Store]: Elim1 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 18 treesize of output 13 [2023-12-02 15:57:25,489 INFO L349 Elim1Store]: treesize reduction 16, result has 69.8 percent of original size [2023-12-02 15:57:25,490 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 5 select indices, 5 select index equivalence classes, 1 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 6 case distinctions, treesize of input 54 treesize of output 56 [2023-12-02 15:57:25,648 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:57:25,649 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 15:57:26,996 WARN L854 $PredicateComparison]: unable to prove that (forall ((|v_ULTIMATE.start_cstrpbrk_~sc1~0#1.offset_33| Int) (|v_ULTIMATE.start_cstrpbrk_~sc1~0#1.offset_34| Int) (v_ArrVal_195 (Array Int Int))) (let ((.cse0 (select v_ArrVal_195 |c_ULTIMATE.start_main_~nondetString2~0#1.offset|)) (.cse1 (select (store |c_#memory_int| |c_ULTIMATE.start_main_~nondetString2~0#1.base| v_ArrVal_195) |c_ULTIMATE.start_main_~nondetString1~0#1.base|))) (or (not (= .cse0 (select .cse1 |v_ULTIMATE.start_cstrpbrk_~sc1~0#1.offset_33|))) (= .cse0 0) (< (+ |c_ULTIMATE.start_main_~nondetString1~0#1.offset| 1) |v_ULTIMATE.start_cstrpbrk_~sc1~0#1.offset_34|) (not (= .cse0 (select .cse1 |c_ULTIMATE.start_main_~nondetString1~0#1.offset|))) (not (= .cse0 (select .cse1 |v_ULTIMATE.start_cstrpbrk_~sc1~0#1.offset_34|))) (< |v_ULTIMATE.start_cstrpbrk_~sc1~0#1.offset_33| 0) (< (+ |v_ULTIMATE.start_cstrpbrk_~sc1~0#1.offset_33| 1) (select |c_#length| |c_ULTIMATE.start_main_~nondetString1~0#1.base|)) (< (+ |v_ULTIMATE.start_cstrpbrk_~sc1~0#1.offset_34| 1) |v_ULTIMATE.start_cstrpbrk_~sc1~0#1.offset_33|)))) is different from false [2023-12-02 15:57:27,019 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-02 15:57:27,019 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 73 treesize of output 51 [2023-12-02 15:57:27,059 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-02 15:57:27,060 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 96 treesize of output 133 [2023-12-02 15:57:27,103 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-02 15:57:27,104 INFO L378 Elim1Store]: Elim1 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 4 new quantified variables, introduced 6 case distinctions, treesize of input 78 treesize of output 106 [2023-12-02 15:57:27,116 INFO L378 Elim1Store]: Elim1 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 15 treesize of output 11 [2023-12-02 15:57:27,438 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:57:27,438 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1011241077] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 15:57:27,438 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1658938912] [2023-12-02 15:57:27,440 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2023-12-02 15:57:27,440 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 15:57:27,441 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 15:57:27,441 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 15:57:27,441 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 15:57:29,384 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 15:57:37,276 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3062#(and (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start_main_~nondetString2~0#1.offset| 0) (<= 1 |ULTIMATE.start_main_~length1~0#1|) (<= 1 |ULTIMATE.start_cstrpbrk_~sc1~0#1.offset|) (= |ULTIMATE.start_cstrpbrk_#in~s1#1.offset| 0) (= |ULTIMATE.start_cstrpbrk_~s2#1.offset| 0) (= |ULTIMATE.start_main_~nondetString1~0#1.offset| 0) (= 0 |ULTIMATE.start_cstrpbrk_~s1#1.offset|) (<= 1 |ULTIMATE.start_main_~length2~0#1|) (= |ULTIMATE.start_cstrpbrk_~s~0#1.offset| 0) (<= (select |#length| |ULTIMATE.start_cstrpbrk_~sc1~0#1.base|) |ULTIMATE.start_cstrpbrk_~sc1~0#1.offset|) (= |ULTIMATE.start_cstrpbrk_#in~s2#1.offset| 0))' at error location [2023-12-02 15:57:37,276 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 15:57:37,276 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 15:57:37,276 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 17, 17] total 42 [2023-12-02 15:57:37,276 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [800749215] [2023-12-02 15:57:37,276 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 15:57:37,277 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 44 states [2023-12-02 15:57:37,277 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:57:37,278 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 44 interpolants. [2023-12-02 15:57:37,279 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=272, Invalid=2700, Unknown=2, NotChecked=106, Total=3080 [2023-12-02 15:57:37,279 INFO L87 Difference]: Start difference. First operand 144 states and 176 transitions. Second operand has 44 states, 43 states have (on average 2.1627906976744184) internal successors, (93), 43 states have internal predecessors, (93), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:57:51,839 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 15:57:51,839 INFO L93 Difference]: Finished difference Result 686 states and 826 transitions. [2023-12-02 15:57:51,839 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 83 states. [2023-12-02 15:57:51,839 INFO L78 Accepts]: Start accepts. Automaton has has 44 states, 43 states have (on average 2.1627906976744184) internal successors, (93), 43 states have internal predecessors, (93), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 31 [2023-12-02 15:57:51,840 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 15:57:51,843 INFO L225 Difference]: With dead ends: 686 [2023-12-02 15:57:51,843 INFO L226 Difference]: Without dead ends: 686 [2023-12-02 15:57:51,848 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 181 GetRequests, 45 SyntacticMatches, 1 SemanticMatches, 135 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 5719 ImplicationChecksByTransitivity, 22.7s TimeCoverageRelationStatistics Valid=2660, Invalid=15702, Unknown=2, NotChecked=268, Total=18632 [2023-12-02 15:57:51,849 INFO L413 NwaCegarLoop]: 5 mSDtfsCounter, 1391 mSDsluCounter, 148 mSDsCounter, 0 mSdLazyCounter, 1014 mSolverCounterSat, 41 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1391 SdHoareTripleChecker+Valid, 153 SdHoareTripleChecker+Invalid, 1296 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 1014 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 241 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2023-12-02 15:57:51,849 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [1391 Valid, 153 Invalid, 1296 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 1014 Invalid, 0 Unknown, 241 Unchecked, 1.4s Time] [2023-12-02 15:57:51,850 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 686 states. [2023-12-02 15:57:51,856 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 686 to 239. [2023-12-02 15:57:51,857 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 239 states, 237 states have (on average 1.2151898734177216) internal successors, (288), 238 states have internal predecessors, (288), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:57:51,857 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 239 states to 239 states and 288 transitions. [2023-12-02 15:57:51,858 INFO L78 Accepts]: Start accepts. Automaton has 239 states and 288 transitions. Word has length 31 [2023-12-02 15:57:51,858 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 15:57:51,858 INFO L495 AbstractCegarLoop]: Abstraction has 239 states and 288 transitions. [2023-12-02 15:57:51,858 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 44 states, 43 states have (on average 2.1627906976744184) internal successors, (93), 43 states have internal predecessors, (93), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:57:51,858 INFO L276 IsEmpty]: Start isEmpty. Operand 239 states and 288 transitions. [2023-12-02 15:57:51,859 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2023-12-02 15:57:51,859 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:57:51,859 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1] [2023-12-02 15:57:51,864 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2023-12-02 15:57:52,060 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 15:57:52,060 INFO L420 AbstractCegarLoop]: === Iteration 20 === Targeting ULTIMATE.startErr5REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:57:52,061 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:57:52,061 INFO L85 PathProgramCache]: Analyzing trace with hash -61429755, now seen corresponding path program 1 times [2023-12-02 15:57:52,061 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:57:52,061 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1060261466] [2023-12-02 15:57:52,061 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:57:52,061 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:57:52,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:57:52,819 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 0 proven. 70 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-12-02 15:57:52,820 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:57:52,820 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1060261466] [2023-12-02 15:57:52,820 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1060261466] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 15:57:52,820 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [466286981] [2023-12-02 15:57:52,820 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:57:52,820 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 15:57:52,821 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 15:57:52,822 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 15:57:52,824 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-12-02 15:57:52,917 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:57:52,919 INFO L262 TraceCheckSpWp]: Trace formula consists of 271 conjuncts, 76 conjunts are in the unsatisfiable core [2023-12-02 15:57:52,923 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 15:57:52,926 INFO L378 Elim1Store]: Elim1 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 10 treesize of output 8 [2023-12-02 15:57:52,948 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 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 14 treesize of output 10 [2023-12-02 15:57:52,989 INFO L378 Elim1Store]: Elim1 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 19 treesize of output 14 [2023-12-02 15:57:55,273 INFO L349 Elim1Store]: treesize reduction 46, result has 79.2 percent of original size [2023-12-02 15:57:55,273 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 8 select indices, 8 select index equivalence classes, 7 disjoint index pairs (out of 28 index pairs), introduced 8 new quantified variables, introduced 17 case distinctions, treesize of input 81 treesize of output 202 [2023-12-02 15:57:55,674 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 3 proven. 70 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-12-02 15:57:55,675 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 15:57:58,285 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-02 15:57:58,286 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 174 treesize of output 97 [2023-12-02 15:57:58,392 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-02 15:57:58,392 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 7 select indices, 7 select index equivalence classes, 6 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 15 case distinctions, treesize of input 263 treesize of output 387 [2023-12-02 15:57:58,508 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-02 15:57:58,508 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 7 select indices, 7 select index equivalence classes, 6 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 15 case distinctions, treesize of input 175 treesize of output 273 [2023-12-02 15:57:58,539 INFO L378 Elim1Store]: Elim1 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 15 treesize of output 11 [2023-12-02 15:58:38,022 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 0 proven. 73 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-12-02 15:58:38,022 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [466286981] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 15:58:38,022 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1482173651] [2023-12-02 15:58:38,024 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2023-12-02 15:58:38,024 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 15:58:38,024 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 15:58:38,024 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 15:58:38,024 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 15:58:39,929 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 15:58:43,930 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4477#(and (<= 1 |#StackHeapBarrier|) (<= 0 |ULTIMATE.start_cstrpbrk_~s~0#1.offset|) (= |ULTIMATE.start_main_~nondetString2~0#1.offset| 0) (<= 1 |ULTIMATE.start_main_~length1~0#1|) (<= 1 |ULTIMATE.start_cstrpbrk_~sc1~0#1.offset|) (= |ULTIMATE.start_cstrpbrk_#in~s1#1.offset| 0) (= |ULTIMATE.start_cstrpbrk_~s2#1.offset| 0) (= |ULTIMATE.start_main_~nondetString1~0#1.offset| 0) (= 0 |ULTIMATE.start_cstrpbrk_~s1#1.offset|) (<= 1 |ULTIMATE.start_main_~length2~0#1|) (<= (select |#length| |ULTIMATE.start_cstrpbrk_~sc1~0#1.base|) |ULTIMATE.start_cstrpbrk_~sc1~0#1.offset|) (= |ULTIMATE.start_cstrpbrk_#in~s2#1.offset| 0))' at error location [2023-12-02 15:58:43,930 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 15:58:43,930 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 15:58:43,931 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 23, 23] total 55 [2023-12-02 15:58:43,931 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1767647165] [2023-12-02 15:58:43,931 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 15:58:43,931 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 57 states [2023-12-02 15:58:43,931 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:58:43,932 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 57 interpolants. [2023-12-02 15:58:43,934 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=440, Invalid=4091, Unknown=25, NotChecked=0, Total=4556 [2023-12-02 15:58:43,934 INFO L87 Difference]: Start difference. First operand 239 states and 288 transitions. Second operand has 57 states, 56 states have (on average 2.3035714285714284) internal successors, (129), 56 states have internal predecessors, (129), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:58:55,905 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 15:58:55,905 INFO L93 Difference]: Finished difference Result 549 states and 658 transitions. [2023-12-02 15:58:55,906 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 54 states. [2023-12-02 15:58:55,906 INFO L78 Accepts]: Start accepts. Automaton has has 57 states, 56 states have (on average 2.3035714285714284) internal successors, (129), 56 states have internal predecessors, (129), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 44 [2023-12-02 15:58:55,906 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 15:58:55,914 INFO L225 Difference]: With dead ends: 549 [2023-12-02 15:58:55,914 INFO L226 Difference]: Without dead ends: 549 [2023-12-02 15:58:55,919 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 190 GetRequests, 68 SyntacticMatches, 5 SemanticMatches, 117 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3926 ImplicationChecksByTransitivity, 17.8s TimeCoverageRelationStatistics Valid=2043, Invalid=11974, Unknown=25, NotChecked=0, Total=14042 [2023-12-02 15:58:55,919 INFO L413 NwaCegarLoop]: 5 mSDtfsCounter, 632 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 1130 mSolverCounterSat, 57 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 632 SdHoareTripleChecker+Valid, 95 SdHoareTripleChecker+Invalid, 1187 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 57 IncrementalHoareTripleChecker+Valid, 1130 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.7s IncrementalHoareTripleChecker+Time [2023-12-02 15:58:55,920 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [632 Valid, 95 Invalid, 1187 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [57 Valid, 1130 Invalid, 0 Unknown, 0 Unchecked, 1.7s Time] [2023-12-02 15:58:55,921 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 549 states. [2023-12-02 15:58:55,928 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 549 to 374. [2023-12-02 15:58:55,929 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 374 states, 372 states have (on average 1.239247311827957) internal successors, (461), 373 states have internal predecessors, (461), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:58:55,931 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 374 states to 374 states and 461 transitions. [2023-12-02 15:58:55,931 INFO L78 Accepts]: Start accepts. Automaton has 374 states and 461 transitions. Word has length 44 [2023-12-02 15:58:55,931 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 15:58:55,931 INFO L495 AbstractCegarLoop]: Abstraction has 374 states and 461 transitions. [2023-12-02 15:58:55,932 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 57 states, 56 states have (on average 2.3035714285714284) internal successors, (129), 56 states have internal predecessors, (129), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:58:55,932 INFO L276 IsEmpty]: Start isEmpty. Operand 374 states and 461 transitions. [2023-12-02 15:58:55,933 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2023-12-02 15:58:55,933 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:58:55,933 INFO L195 NwaCegarLoop]: trace histogram [10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 15:58:55,938 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2023-12-02 15:58:56,133 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 15:58:56,134 INFO L420 AbstractCegarLoop]: === Iteration 21 === Targeting ULTIMATE.startErr9REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:58:56,134 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:58:56,134 INFO L85 PathProgramCache]: Analyzing trace with hash 200578220, now seen corresponding path program 4 times [2023-12-02 15:58:56,134 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:58:56,134 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1144959083] [2023-12-02 15:58:56,135 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:58:56,135 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:58:56,155 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:58:57,190 INFO L134 CoverageAnalysis]: Checked inductivity of 190 backedges. 0 proven. 190 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:58:57,190 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:58:57,190 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1144959083] [2023-12-02 15:58:57,190 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1144959083] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 15:58:57,190 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [696211469] [2023-12-02 15:58:57,190 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-12-02 15:58:57,190 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 15:58:57,190 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 15:58:57,191 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 15:58:57,192 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-12-02 15:58:57,291 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:58:57,294 INFO L262 TraceCheckSpWp]: Trace formula consists of 288 conjuncts, 100 conjunts are in the unsatisfiable core [2023-12-02 15:58:57,298 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 15:58:57,337 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 9 [2023-12-02 15:59:00,228 INFO L349 Elim1Store]: treesize reduction 36, result has 55.6 percent of original size [2023-12-02 15:59:00,228 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 11 select indices, 11 select index equivalence classes, 45 disjoint index pairs (out of 55 index pairs), introduced 11 new quantified variables, introduced 10 case distinctions, treesize of input 103 treesize of output 97 [2023-12-02 15:59:00,243 WARN L667 sPolynomialRelations]: Constructing 512(two to the power of 9 dual juncts. [2023-12-02 15:59:00,267 WARN L667 sPolynomialRelations]: Constructing 1024(two to the power of 10 dual juncts. [2023-12-02 15:59:00,515 INFO L134 CoverageAnalysis]: Checked inductivity of 190 backedges. 0 proven. 190 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:59:00,515 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 15:59:04,558 INFO L378 Elim1Store]: Elim1 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 149 treesize of output 129 [2023-12-02 15:59:04,561 INFO L378 Elim1Store]: Elim1 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 15 treesize of output 11 [2023-12-02 15:59:04,576 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 10 select indices, 10 select index equivalence classes, 45 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 0 case distinctions, treesize of input 149 treesize of output 111 [2023-12-02 15:59:04,751 INFO L134 CoverageAnalysis]: Checked inductivity of 190 backedges. 0 proven. 190 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:59:04,751 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [696211469] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 15:59:04,751 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [447524404] [2023-12-02 15:59:04,752 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2023-12-02 15:59:04,752 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 15:59:04,753 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 15:59:04,753 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 15:59:04,753 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 15:59:05,246 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 15:59:07,970 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5873#(and (<= 1 |#StackHeapBarrier|) (<= (select |#length| |ULTIMATE.start_cstrpbrk_~s~0#1.base|) |ULTIMATE.start_cstrpbrk_~s~0#1.offset|) (<= 0 |ULTIMATE.start_cstrpbrk_~s~0#1.offset|) (= |ULTIMATE.start_main_~nondetString2~0#1.offset| 0) (= |ULTIMATE.start_cstrpbrk_~sc1~0#1.offset| 0) (<= 1 |ULTIMATE.start_main_~length1~0#1|) (= |ULTIMATE.start_cstrpbrk_#in~s1#1.offset| 0) (= |ULTIMATE.start_cstrpbrk_~s2#1.offset| 0) (= |ULTIMATE.start_main_~nondetString1~0#1.offset| 0) (= 0 |ULTIMATE.start_cstrpbrk_~s1#1.offset|) (<= 1 |ULTIMATE.start_main_~length2~0#1|) (= |ULTIMATE.start_cstrpbrk_#in~s2#1.offset| 0))' at error location [2023-12-02 15:59:07,970 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 15:59:07,970 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 15:59:07,971 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 33, 33] total 82 [2023-12-02 15:59:07,971 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [485005574] [2023-12-02 15:59:07,971 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 15:59:07,971 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 84 states [2023-12-02 15:59:07,971 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:59:07,973 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 84 interpolants. [2023-12-02 15:59:07,973 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=878, Invalid=7492, Unknown=2, NotChecked=0, Total=8372 [2023-12-02 15:59:07,974 INFO L87 Difference]: Start difference. First operand 374 states and 461 transitions. Second operand has 84 states, 83 states have (on average 1.6987951807228916) internal successors, (141), 83 states have internal predecessors, (141), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:59:25,964 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 15:59:25,964 INFO L93 Difference]: Finished difference Result 1358 states and 1533 transitions. [2023-12-02 15:59:25,964 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 72 states. [2023-12-02 15:59:25,965 INFO L78 Accepts]: Start accepts. Automaton has has 84 states, 83 states have (on average 1.6987951807228916) internal successors, (141), 83 states have internal predecessors, (141), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 47 [2023-12-02 15:59:25,965 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 15:59:25,971 INFO L225 Difference]: With dead ends: 1358 [2023-12-02 15:59:25,972 INFO L226 Difference]: Without dead ends: 1358 [2023-12-02 15:59:25,974 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 225 GetRequests, 65 SyntacticMatches, 0 SemanticMatches, 160 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6490 ImplicationChecksByTransitivity, 23.8s TimeCoverageRelationStatistics Valid=3384, Invalid=22696, Unknown=2, NotChecked=0, Total=26082 [2023-12-02 15:59:25,975 INFO L413 NwaCegarLoop]: 11 mSDtfsCounter, 2301 mSDsluCounter, 268 mSDsCounter, 0 mSdLazyCounter, 3677 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2301 SdHoareTripleChecker+Valid, 279 SdHoareTripleChecker+Invalid, 3688 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 3677 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.7s IncrementalHoareTripleChecker+Time [2023-12-02 15:59:25,975 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2301 Valid, 279 Invalid, 3688 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 3677 Invalid, 0 Unknown, 0 Unchecked, 2.7s Time] [2023-12-02 15:59:25,977 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1358 states. [2023-12-02 15:59:26,004 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1358 to 694. [2023-12-02 15:59:26,006 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 694 states, 692 states have (on average 1.2442196531791907) internal successors, (861), 693 states have internal predecessors, (861), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:59:26,009 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 694 states to 694 states and 861 transitions. [2023-12-02 15:59:26,009 INFO L78 Accepts]: Start accepts. Automaton has 694 states and 861 transitions. Word has length 47 [2023-12-02 15:59:26,009 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 15:59:26,009 INFO L495 AbstractCegarLoop]: Abstraction has 694 states and 861 transitions. [2023-12-02 15:59:26,009 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 84 states, 83 states have (on average 1.6987951807228916) internal successors, (141), 83 states have internal predecessors, (141), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 15:59:26,010 INFO L276 IsEmpty]: Start isEmpty. Operand 694 states and 861 transitions. [2023-12-02 15:59:26,011 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2023-12-02 15:59:26,011 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 15:59:26,011 INFO L195 NwaCegarLoop]: trace histogram [8, 8, 8, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1] [2023-12-02 15:59:26,017 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2023-12-02 15:59:26,211 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 15:59:26,212 INFO L420 AbstractCegarLoop]: === Iteration 22 === Targeting ULTIMATE.startErr5REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 15:59:26,212 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 15:59:26,212 INFO L85 PathProgramCache]: Analyzing trace with hash 2040115074, now seen corresponding path program 3 times [2023-12-02 15:59:26,212 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 15:59:26,212 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [528720414] [2023-12-02 15:59:26,213 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 15:59:26,213 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 15:59:26,242 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 15:59:27,430 INFO L134 CoverageAnalysis]: Checked inductivity of 260 backedges. 0 proven. 260 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:59:27,430 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 15:59:27,430 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [528720414] [2023-12-02 15:59:27,430 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [528720414] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 15:59:27,430 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1269735511] [2023-12-02 15:59:27,430 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-02 15:59:27,430 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 15:59:27,430 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 15:59:27,431 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 15:59:27,433 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-12-02 15:59:27,541 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-02 15:59:27,541 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 15:59:27,545 INFO L262 TraceCheckSpWp]: Trace formula consists of 431 conjuncts, 147 conjunts are in the unsatisfiable core [2023-12-02 15:59:27,550 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 15:59:27,555 INFO L378 Elim1Store]: Elim1 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 18 treesize of output 16 [2023-12-02 15:59:27,584 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 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 13 treesize of output 9 [2023-12-02 15:59:27,634 INFO L378 Elim1Store]: Elim1 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 18 treesize of output 13 [2023-12-02 15:59:32,096 INFO L349 Elim1Store]: treesize reduction 48, result has 43.5 percent of original size [2023-12-02 15:59:32,096 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 10 select indices, 10 select index equivalence classes, 28 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 17 case distinctions, treesize of input 109 treesize of output 71 [2023-12-02 15:59:32,101 WARN L667 sPolynomialRelations]: Constructing 128(two to the power of 7 dual juncts. [2023-12-02 15:59:32,107 WARN L667 sPolynomialRelations]: Constructing 256(two to the power of 8 dual juncts. [2023-12-02 15:59:32,246 INFO L134 CoverageAnalysis]: Checked inductivity of 260 backedges. 0 proven. 260 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:59:32,246 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 15:59:37,832 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-02 15:59:37,833 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 356 treesize of output 180 [2023-12-02 15:59:37,951 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-02 15:59:37,951 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 10 select indices, 10 select index equivalence classes, 28 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 17 case distinctions, treesize of input 649 treesize of output 663 [2023-12-02 15:59:38,075 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-12-02 15:59:38,075 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 9 select indices, 9 select index equivalence classes, 28 disjoint index pairs (out of 36 index pairs), introduced 9 new quantified variables, introduced 8 case distinctions, treesize of input 470 treesize of output 454 [2023-12-02 15:59:38,112 INFO L378 Elim1Store]: Elim1 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 15 treesize of output 11 [2023-12-02 15:59:40,301 WARN L667 sPolynomialRelations]: Constructing 256(two to the power of 8 dual juncts. [2023-12-02 15:59:40,419 INFO L134 CoverageAnalysis]: Checked inductivity of 260 backedges. 0 proven. 260 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 15:59:40,419 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1269735511] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 15:59:40,419 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1013083709] [2023-12-02 15:59:40,421 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2023-12-02 15:59:40,421 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 15:59:40,421 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 15:59:40,421 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 15:59:40,421 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 15:59:42,304 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 15:59:52,566 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '8613#(and (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start_main_~nondetString2~0#1.offset| 0) (<= 1 |ULTIMATE.start_main_~length1~0#1|) (<= 1 |ULTIMATE.start_cstrpbrk_~sc1~0#1.offset|) (= |ULTIMATE.start_cstrpbrk_#in~s1#1.offset| 0) (= |ULTIMATE.start_cstrpbrk_~s2#1.offset| 0) (= |ULTIMATE.start_main_~nondetString1~0#1.offset| 0) (= 0 |ULTIMATE.start_cstrpbrk_~s1#1.offset|) (<= 1 |ULTIMATE.start_main_~length2~0#1|) (= |ULTIMATE.start_cstrpbrk_~s~0#1.offset| 0) (<= (select |#length| |ULTIMATE.start_cstrpbrk_~sc1~0#1.base|) |ULTIMATE.start_cstrpbrk_~sc1~0#1.offset|) (= |ULTIMATE.start_cstrpbrk_#in~s2#1.offset| 0))' at error location [2023-12-02 15:59:52,566 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 15:59:52,566 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-12-02 15:59:52,566 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 37, 38] total 88 [2023-12-02 15:59:52,566 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1076764452] [2023-12-02 15:59:52,566 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-12-02 15:59:52,567 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 90 states [2023-12-02 15:59:52,567 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 15:59:52,568 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 90 interpolants. [2023-12-02 15:59:52,569 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=868, Invalid=9433, Unknown=1, NotChecked=0, Total=10302 [2023-12-02 15:59:52,569 INFO L87 Difference]: Start difference. First operand 694 states and 861 transitions. Second operand has 90 states, 89 states have (on average 2.561797752808989) internal successors, (228), 89 states have internal predecessors, (228), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 16:03:36,630 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 16:03:36,630 INFO L93 Difference]: Finished difference Result 6710 states and 8210 transitions. [2023-12-02 16:03:36,630 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 447 states. [2023-12-02 16:03:36,631 INFO L78 Accepts]: Start accepts. Automaton has has 90 states, 89 states have (on average 2.561797752808989) internal successors, (228), 89 states have internal predecessors, (228), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 76 [2023-12-02 16:03:36,631 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 16:03:36,655 INFO L225 Difference]: With dead ends: 6710 [2023-12-02 16:03:36,656 INFO L226 Difference]: Without dead ends: 6710 [2023-12-02 16:03:36,672 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 684 GetRequests, 139 SyntacticMatches, 0 SemanticMatches, 545 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 120440 ImplicationChecksByTransitivity, 229.2s TimeCoverageRelationStatistics Valid=23449, Invalid=275212, Unknown=1, NotChecked=0, Total=298662 [2023-12-02 16:03:36,672 INFO L413 NwaCegarLoop]: 16 mSDtfsCounter, 5031 mSDsluCounter, 1521 mSDsCounter, 0 mSdLazyCounter, 9153 mSolverCounterSat, 121 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 10.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5031 SdHoareTripleChecker+Valid, 1537 SdHoareTripleChecker+Invalid, 9274 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.1s SdHoareTripleChecker+Time, 121 IncrementalHoareTripleChecker+Valid, 9153 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 10.9s IncrementalHoareTripleChecker+Time [2023-12-02 16:03:36,673 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [5031 Valid, 1537 Invalid, 9274 Unknown, 0 Unchecked, 0.1s Time], IncrementalHoareTripleChecker [121 Valid, 9153 Invalid, 0 Unknown, 0 Unchecked, 10.9s Time] [2023-12-02 16:03:36,679 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 6710 states. [2023-12-02 16:03:36,716 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 6710 to 1294. [2023-12-02 16:03:36,717 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1294 states, 1292 states have (on average 1.2051083591331269) internal successors, (1557), 1293 states have internal predecessors, (1557), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 16:03:36,720 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1294 states to 1294 states and 1557 transitions. [2023-12-02 16:03:36,720 INFO L78 Accepts]: Start accepts. Automaton has 1294 states and 1557 transitions. Word has length 76 [2023-12-02 16:03:36,720 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 16:03:36,720 INFO L495 AbstractCegarLoop]: Abstraction has 1294 states and 1557 transitions. [2023-12-02 16:03:36,720 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 90 states, 89 states have (on average 2.561797752808989) internal successors, (228), 89 states have internal predecessors, (228), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 16:03:36,720 INFO L276 IsEmpty]: Start isEmpty. Operand 1294 states and 1557 transitions. [2023-12-02 16:03:36,722 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2023-12-02 16:03:36,722 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 16:03:36,722 INFO L195 NwaCegarLoop]: trace histogram [20, 20, 20, 20, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 16:03:36,727 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2023-12-02 16:03:36,927 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable21 [2023-12-02 16:03:36,927 INFO L420 AbstractCegarLoop]: === Iteration 23 === Targeting ULTIMATE.startErr9REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 18 more)] === [2023-12-02 16:03:36,928 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 16:03:36,928 INFO L85 PathProgramCache]: Analyzing trace with hash -542459314, now seen corresponding path program 5 times [2023-12-02 16:03:36,928 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 16:03:36,928 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1086819360] [2023-12-02 16:03:36,928 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 16:03:36,928 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 16:03:36,958 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 16:03:38,775 INFO L134 CoverageAnalysis]: Checked inductivity of 780 backedges. 0 proven. 780 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 16:03:38,775 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 16:03:38,775 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1086819360] [2023-12-02 16:03:38,775 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1086819360] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-02 16:03:38,775 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [100500486] [2023-12-02 16:03:38,775 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-02 16:03:38,775 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 16:03:38,775 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 16:03:38,776 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 16:03:38,777 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_098dea1a-6285-45f1-a516-f03c16d6fcd1/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-12-02 16:03:39,007 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 21 check-sat command(s) [2023-12-02 16:03:39,008 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 16:03:39,013 INFO L262 TraceCheckSpWp]: Trace formula consists of 488 conjuncts, 164 conjunts are in the unsatisfiable core [2023-12-02 16:03:39,017 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 16:03:39,051 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 10