./Ultimate.py --spec ../../sv-benchmarks/c/properties/valid-memsafety.prp --file ../../sv-benchmarks/c/termination-memory-alloca/strreplace-alloca-1.i --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for memory safety (deref-memtrack) Using default analysis Version 826ab2ba Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/config/TaipanMemDerefMemtrack.xml -i ../../sv-benchmarks/c/termination-memory-alloca/strreplace-alloca-1.i -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-DerefFreeMemtrack-64bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E --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 d4de5096855b305f822a5b563f81ee8d3b63add498dc60d311755a4f31b28f6b --- Real Ultimate output --- This is Ultimate 0.3.0-dev-826ab2b [2024-11-14 05:15:26,255 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-14 05:15:26,351 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-DerefFreeMemtrack-64bit-Taipan_Default.epf [2024-11-14 05:15:26,357 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-14 05:15:26,358 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-14 05:15:26,385 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-14 05:15:26,386 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-14 05:15:26,386 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-14 05:15:26,387 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-14 05:15:26,387 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-14 05:15:26,387 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-14 05:15:26,387 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-14 05:15:26,388 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-14 05:15:26,388 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-14 05:15:26,388 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-14 05:15:26,388 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-14 05:15:26,388 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-14 05:15:26,388 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-14 05:15:26,389 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-14 05:15:26,389 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-14 05:15:26,389 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-14 05:15:26,389 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-14 05:15:26,390 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-14 05:15:26,390 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-14 05:15:26,390 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-14 05:15:26,390 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-14 05:15:26,390 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-14 05:15:26,390 INFO L153 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2024-11-14 05:15:26,390 INFO L153 SettingsManager]: * Bitprecise bitfields=true [2024-11-14 05:15:26,391 INFO L153 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2024-11-14 05:15:26,391 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-14 05:15:26,391 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2024-11-14 05:15:26,391 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-14 05:15:26,391 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-14 05:15:26,391 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-14 05:15:26,391 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-14 05:15:26,391 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-14 05:15:26,392 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-14 05:15:26,392 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 05:15:26,392 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-14 05:15:26,392 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-14 05:15:26,392 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-14 05:15:26,392 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-14 05:15:26,392 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-14 05:15:26,393 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-14 05:15:26,393 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-14 05:15:26,393 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES 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_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E 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 -> d4de5096855b305f822a5b563f81ee8d3b63add498dc60d311755a4f31b28f6b [2024-11-14 05:15:26,854 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-14 05:15:26,869 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-14 05:15:26,875 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-14 05:15:26,880 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-14 05:15:26,881 INFO L274 PluginConnector]: CDTParser initialized [2024-11-14 05:15:26,882 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/../../sv-benchmarks/c/termination-memory-alloca/strreplace-alloca-1.i Unable to find full path for "g++" [2024-11-14 05:15:29,162 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-14 05:15:29,538 INFO L384 CDTParser]: Found 1 translation units. [2024-11-14 05:15:29,541 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/sv-benchmarks/c/termination-memory-alloca/strreplace-alloca-1.i [2024-11-14 05:15:29,568 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/data/5ea4e8efd/c66409131f22469aa1489f17674db845/FLAGe6bd837d0 [2024-11-14 05:15:29,599 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/data/5ea4e8efd/c66409131f22469aa1489f17674db845 [2024-11-14 05:15:29,602 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-14 05:15:29,606 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-14 05:15:29,608 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-14 05:15:29,608 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-14 05:15:29,614 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-14 05:15:29,615 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 05:15:29" (1/1) ... [2024-11-14 05:15:29,619 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4ba8f8d3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:15:29, skipping insertion in model container [2024-11-14 05:15:29,619 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 05:15:29" (1/1) ... [2024-11-14 05:15:29,674 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-14 05:15:30,030 WARN L1072 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-14 05:15:30,033 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 05:15:30,044 INFO L200 MainTranslator]: Completed pre-run [2024-11-14 05:15:30,082 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 05:15:30,107 INFO L204 MainTranslator]: Completed translation [2024-11-14 05:15:30,108 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:15:30 WrapperNode [2024-11-14 05:15:30,108 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-14 05:15:30,109 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-14 05:15:30,110 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-14 05:15:30,110 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-14 05:15:30,117 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:15:30" (1/1) ... [2024-11-14 05:15:30,127 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:15:30" (1/1) ... [2024-11-14 05:15:30,150 INFO L138 Inliner]: procedures = 111, calls = 10, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 55 [2024-11-14 05:15:30,150 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-14 05:15:30,151 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-14 05:15:30,151 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-14 05:15:30,151 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-14 05:15:30,159 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:15:30" (1/1) ... [2024-11-14 05:15:30,160 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:15:30" (1/1) ... [2024-11-14 05:15:30,164 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:15:30" (1/1) ... [2024-11-14 05:15:30,168 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:15:30" (1/1) ... [2024-11-14 05:15:30,177 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:15:30" (1/1) ... [2024-11-14 05:15:30,185 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:15:30" (1/1) ... [2024-11-14 05:15:30,186 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:15:30" (1/1) ... [2024-11-14 05:15:30,187 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:15:30" (1/1) ... [2024-11-14 05:15:30,192 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-14 05:15:30,193 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-14 05:15:30,193 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-14 05:15:30,193 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-14 05:15:30,194 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:15:30" (1/1) ... [2024-11-14 05:15:30,203 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 05:15:30,219 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:15:30,235 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-14 05:15:30,239 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-14 05:15:30,275 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2024-11-14 05:15:30,275 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2024-11-14 05:15:30,275 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-14 05:15:30,277 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-14 05:15:30,278 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-14 05:15:30,278 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-14 05:15:30,426 INFO L238 CfgBuilder]: Building ICFG [2024-11-14 05:15:30,428 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-14 05:15:30,717 INFO L? ?]: Removed 31 outVars from TransFormulas that were not future-live. [2024-11-14 05:15:30,717 INFO L287 CfgBuilder]: Performing block encoding [2024-11-14 05:15:30,811 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-14 05:15:30,811 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-14 05:15:30,811 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 05:15:30 BoogieIcfgContainer [2024-11-14 05:15:30,812 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-14 05:15:30,815 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-14 05:15:30,815 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-14 05:15:30,822 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-14 05:15:30,823 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.11 05:15:29" (1/3) ... [2024-11-14 05:15:30,824 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4fd2cb9b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 05:15:30, skipping insertion in model container [2024-11-14 05:15:30,824 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:15:30" (2/3) ... [2024-11-14 05:15:30,825 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4fd2cb9b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 05:15:30, skipping insertion in model container [2024-11-14 05:15:30,826 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 05:15:30" (3/3) ... [2024-11-14 05:15:30,827 INFO L112 eAbstractionObserver]: Analyzing ICFG strreplace-alloca-1.i [2024-11-14 05:15:30,848 INFO L217 ceAbstractionStarter]: Automizer settings: Hoare:None NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-14 05:15:30,853 INFO L154 ceAbstractionStarter]: Applying trace abstraction to ICFG strreplace-alloca-1.i that has 1 procedures, 20 locations, 1 initial locations, 1 loop locations, and 9 error locations. [2024-11-14 05:15:30,913 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-14 05:15:30,935 INFO L333 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, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=None, 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;@3cdd4579, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-14 05:15:30,937 INFO L334 AbstractCegarLoop]: Starting to check reachability of 9 error locations. [2024-11-14 05:15:30,944 INFO L276 IsEmpty]: Start isEmpty. Operand has 20 states, 10 states have (on average 2.2) internal successors, (22), 19 states have internal predecessors, (22), 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) [2024-11-14 05:15:30,952 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 3 [2024-11-14 05:15:30,954 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:15:30,955 INFO L215 NwaCegarLoop]: trace histogram [1, 1] [2024-11-14 05:15:30,956 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 6 more)] === [2024-11-14 05:15:30,965 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:15:30,965 INFO L85 PathProgramCache]: Analyzing trace with hash 2708, now seen corresponding path program 1 times [2024-11-14 05:15:30,973 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:15:30,973 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [521303835] [2024-11-14 05:15:30,974 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:15:30,975 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:15:31,095 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:15:31,225 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:15:31,227 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:15:31,227 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [521303835] [2024-11-14 05:15:31,228 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [521303835] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 05:15:31,228 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 05:15:31,229 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2024-11-14 05:15:31,232 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1130156665] [2024-11-14 05:15:31,233 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 05:15:31,237 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-14 05:15:31,238 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:15:31,265 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-14 05:15:31,266 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 05:15:31,268 INFO L87 Difference]: Start difference. First operand has 20 states, 10 states have (on average 2.2) internal successors, (22), 19 states have internal predecessors, (22), 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) [2024-11-14 05:15:31,366 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:15:31,367 INFO L93 Difference]: Finished difference Result 19 states and 20 transitions. [2024-11-14 05:15:31,370 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-14 05:15:31,371 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 [2024-11-14 05:15:31,372 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:15:31,380 INFO L225 Difference]: With dead ends: 19 [2024-11-14 05:15:31,380 INFO L226 Difference]: Without dead ends: 18 [2024-11-14 05:15:31,382 INFO L431 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 [2024-11-14 05:15:31,386 INFO L432 NwaCegarLoop]: 14 mSDtfsCounter, 0 mSDsluCounter, 8 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 22 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.1s IncrementalHoareTripleChecker+Time [2024-11-14 05:15:31,387 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 22 Invalid, 17 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 05:15:31,404 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states. [2024-11-14 05:15:31,418 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 18. [2024-11-14 05:15:31,419 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 18 states, 10 states have (on average 1.9) internal successors, (19), 17 states have internal predecessors, (19), 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) [2024-11-14 05:15:31,422 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 19 transitions. [2024-11-14 05:15:31,424 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 19 transitions. Word has length 2 [2024-11-14 05:15:31,424 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:15:31,424 INFO L471 AbstractCegarLoop]: Abstraction has 18 states and 19 transitions. [2024-11-14 05:15:31,424 INFO L472 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) [2024-11-14 05:15:31,425 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 19 transitions. [2024-11-14 05:15:31,425 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 3 [2024-11-14 05:15:31,425 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:15:31,425 INFO L215 NwaCegarLoop]: trace histogram [1, 1] [2024-11-14 05:15:31,425 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-14 05:15:31,426 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 6 more)] === [2024-11-14 05:15:31,426 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:15:31,427 INFO L85 PathProgramCache]: Analyzing trace with hash 2709, now seen corresponding path program 1 times [2024-11-14 05:15:31,427 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:15:31,427 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1732498615] [2024-11-14 05:15:31,427 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:15:31,427 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:15:31,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:15:31,748 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:15:31,748 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:15:31,748 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1732498615] [2024-11-14 05:15:31,748 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1732498615] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 05:15:31,748 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 05:15:31,748 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2024-11-14 05:15:31,748 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [679159777] [2024-11-14 05:15:31,749 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 05:15:31,750 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-14 05:15:31,750 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:15:31,751 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-14 05:15:31,751 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 05:15:31,751 INFO L87 Difference]: Start difference. First operand 18 states and 19 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) [2024-11-14 05:15:31,799 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:15:31,799 INFO L93 Difference]: Finished difference Result 17 states and 18 transitions. [2024-11-14 05:15:31,800 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-14 05:15:31,800 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 [2024-11-14 05:15:31,801 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:15:31,801 INFO L225 Difference]: With dead ends: 17 [2024-11-14 05:15:31,801 INFO L226 Difference]: Without dead ends: 17 [2024-11-14 05:15:31,801 INFO L431 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 [2024-11-14 05:15:31,803 INFO L432 NwaCegarLoop]: 14 mSDtfsCounter, 0 mSDsluCounter, 9 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 23 SdHoareTripleChecker+Invalid, 12 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 05:15:31,803 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 23 Invalid, 12 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 05:15:31,804 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states. [2024-11-14 05:15:31,806 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2024-11-14 05:15:31,806 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 10 states have (on average 1.8) internal successors, (18), 16 states have internal predecessors, (18), 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) [2024-11-14 05:15:31,807 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2024-11-14 05:15:31,807 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 2 [2024-11-14 05:15:31,807 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:15:31,808 INFO L471 AbstractCegarLoop]: Abstraction has 17 states and 18 transitions. [2024-11-14 05:15:31,808 INFO L472 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) [2024-11-14 05:15:31,808 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 18 transitions. [2024-11-14 05:15:31,808 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2024-11-14 05:15:31,808 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:15:31,809 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1] [2024-11-14 05:15:31,809 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-14 05:15:31,809 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 6 more)] === [2024-11-14 05:15:31,810 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:15:31,810 INFO L85 PathProgramCache]: Analyzing trace with hash 85144, now seen corresponding path program 1 times [2024-11-14 05:15:31,810 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:15:31,810 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1008056729] [2024-11-14 05:15:31,810 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:15:31,810 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:15:31,832 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:15:31,901 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:15:31,901 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:15:31,901 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1008056729] [2024-11-14 05:15:31,901 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1008056729] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 05:15:31,902 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 05:15:31,902 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-14 05:15:31,902 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [358853751] [2024-11-14 05:15:31,902 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 05:15:31,903 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-14 05:15:31,903 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:15:31,903 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-14 05:15:31,904 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 05:15:31,904 INFO L87 Difference]: Start difference. First operand 17 states and 18 transitions. Second operand has 3 states, 2 states have (on average 1.5) 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) [2024-11-14 05:15:31,946 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:15:31,947 INFO L93 Difference]: Finished difference Result 14 states and 15 transitions. [2024-11-14 05:15:31,947 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-14 05:15:31,947 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 1.5) 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 [2024-11-14 05:15:31,948 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:15:31,948 INFO L225 Difference]: With dead ends: 14 [2024-11-14 05:15:31,948 INFO L226 Difference]: Without dead ends: 14 [2024-11-14 05:15:31,948 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 05:15:31,949 INFO L432 NwaCegarLoop]: 5 mSDtfsCounter, 7 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 16 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 5 SdHoareTripleChecker+Invalid, 19 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 16 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 05:15:31,950 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 5 Invalid, 19 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 16 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 05:15:31,950 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 14 states. [2024-11-14 05:15:31,952 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 14 to 14. [2024-11-14 05:15:31,952 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 14 states, 10 states have (on average 1.5) internal successors, (15), 13 states have internal predecessors, (15), 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) [2024-11-14 05:15:31,953 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 15 transitions. [2024-11-14 05:15:31,953 INFO L78 Accepts]: Start accepts. Automaton has 14 states and 15 transitions. Word has length 3 [2024-11-14 05:15:31,953 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:15:31,954 INFO L471 AbstractCegarLoop]: Abstraction has 14 states and 15 transitions. [2024-11-14 05:15:31,954 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 1.5) 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) [2024-11-14 05:15:31,954 INFO L276 IsEmpty]: Start isEmpty. Operand 14 states and 15 transitions. [2024-11-14 05:15:31,954 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2024-11-14 05:15:31,955 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:15:31,955 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1] [2024-11-14 05:15:31,955 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-14 05:15:31,955 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 6 more)] === [2024-11-14 05:15:31,956 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:15:31,956 INFO L85 PathProgramCache]: Analyzing trace with hash 85145, now seen corresponding path program 1 times [2024-11-14 05:15:31,956 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:15:31,956 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [753064045] [2024-11-14 05:15:31,956 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:15:31,957 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:15:31,979 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:15:32,286 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:15:32,287 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:15:32,287 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [753064045] [2024-11-14 05:15:32,287 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [753064045] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 05:15:32,287 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 05:15:32,287 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-14 05:15:32,287 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1779460385] [2024-11-14 05:15:32,287 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 05:15:32,288 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-14 05:15:32,288 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:15:32,288 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-14 05:15:32,289 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 05:15:32,289 INFO L87 Difference]: Start difference. First operand 14 states and 15 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) [2024-11-14 05:15:32,347 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:15:32,347 INFO L93 Difference]: Finished difference Result 21 states and 24 transitions. [2024-11-14 05:15:32,348 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-14 05:15:32,348 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 [2024-11-14 05:15:32,348 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:15:32,348 INFO L225 Difference]: With dead ends: 21 [2024-11-14 05:15:32,349 INFO L226 Difference]: Without dead ends: 21 [2024-11-14 05:15:32,349 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 05:15:32,350 INFO L432 NwaCegarLoop]: 8 mSDtfsCounter, 7 mSDsluCounter, 10 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 18 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 05:15:32,350 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 18 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 05:15:32,351 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2024-11-14 05:15:32,352 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 19. [2024-11-14 05:15:32,353 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 19 states, 15 states have (on average 1.4666666666666666) internal successors, (22), 18 states have internal predecessors, (22), 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) [2024-11-14 05:15:32,353 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 22 transitions. [2024-11-14 05:15:32,354 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 22 transitions. Word has length 3 [2024-11-14 05:15:32,354 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:15:32,354 INFO L471 AbstractCegarLoop]: Abstraction has 19 states and 22 transitions. [2024-11-14 05:15:32,354 INFO L472 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) [2024-11-14 05:15:32,354 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 22 transitions. [2024-11-14 05:15:32,354 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2024-11-14 05:15:32,355 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:15:32,355 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2024-11-14 05:15:32,355 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-14 05:15:32,355 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr8ASSERT_VIOLATIONMEMORY_LEAK === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 6 more)] === [2024-11-14 05:15:32,355 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:15:32,356 INFO L85 PathProgramCache]: Analyzing trace with hash -1758449445, now seen corresponding path program 1 times [2024-11-14 05:15:32,356 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:15:32,356 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1141840628] [2024-11-14 05:15:32,356 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:15:32,356 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:15:32,386 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:15:32,506 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:15:32,506 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:15:32,506 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1141840628] [2024-11-14 05:15:32,506 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1141840628] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 05:15:32,506 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 05:15:32,506 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-14 05:15:32,506 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1793760456] [2024-11-14 05:15:32,507 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 05:15:32,507 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-14 05:15:32,507 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:15:32,507 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-14 05:15:32,507 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 05:15:32,507 INFO L87 Difference]: Start difference. First operand 19 states and 22 transitions. Second operand has 4 states, 3 states have (on average 2.0) internal successors, (6), 3 states have internal predecessors, (6), 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) [2024-11-14 05:15:32,532 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:15:32,533 INFO L93 Difference]: Finished difference Result 18 states and 21 transitions. [2024-11-14 05:15:32,534 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-14 05:15:32,534 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 2.0) internal successors, (6), 3 states have internal predecessors, (6), 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 6 [2024-11-14 05:15:32,534 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:15:32,535 INFO L225 Difference]: With dead ends: 18 [2024-11-14 05:15:32,535 INFO L226 Difference]: Without dead ends: 16 [2024-11-14 05:15:32,535 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 05:15:32,536 INFO L432 NwaCegarLoop]: 8 mSDtfsCounter, 9 mSDsluCounter, 8 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 16 SdHoareTripleChecker+Invalid, 12 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 05:15:32,536 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 16 Invalid, 12 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 05:15:32,537 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16 states. [2024-11-14 05:15:32,542 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16 to 16. [2024-11-14 05:15:32,542 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 16 states, 13 states have (on average 1.3846153846153846) internal successors, (18), 15 states have internal predecessors, (18), 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) [2024-11-14 05:15:32,543 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 18 transitions. [2024-11-14 05:15:32,543 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 18 transitions. Word has length 6 [2024-11-14 05:15:32,543 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:15:32,543 INFO L471 AbstractCegarLoop]: Abstraction has 16 states and 18 transitions. [2024-11-14 05:15:32,543 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 2.0) internal successors, (6), 3 states have internal predecessors, (6), 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) [2024-11-14 05:15:32,543 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 18 transitions. [2024-11-14 05:15:32,543 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2024-11-14 05:15:32,543 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:15:32,543 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 05:15:32,544 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2024-11-14 05:15:32,545 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 6 more)] === [2024-11-14 05:15:32,546 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:15:32,546 INFO L85 PathProgramCache]: Analyzing trace with hash -1946675463, now seen corresponding path program 1 times [2024-11-14 05:15:32,546 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:15:32,546 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [424614324] [2024-11-14 05:15:32,546 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:15:32,547 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:15:32,575 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:15:33,135 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:15:33,136 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:15:33,136 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [424614324] [2024-11-14 05:15:33,136 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [424614324] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:15:33,137 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [528693937] [2024-11-14 05:15:33,137 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:15:33,137 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:15:33,137 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:15:33,139 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:15:33,142 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-14 05:15:33,236 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:15:33,239 INFO L255 TraceCheckSpWp]: Trace formula consists of 64 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-14 05:15:33,245 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:15:33,364 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 [2024-11-14 05:15:33,508 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-14 05:15:33,508 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 18 treesize of output 19 [2024-11-14 05:15:33,703 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:15:33,703 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:15:34,004 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 [2024-11-14 05:15:34,027 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 [2024-11-14 05:15:34,054 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 [2024-11-14 05:15:34,073 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:15:34,074 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [528693937] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 05:15:34,074 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1032505178] [2024-11-14 05:15:34,108 INFO L159 IcfgInterpreter]: Started Sifa with 8 locations of interest [2024-11-14 05:15:34,108 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:15:34,116 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:15:34,121 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:15:34,122 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:15:36,329 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:15:38,349 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '270#(exists ((|v_ULTIMATE.start_cstrreplace_~p~0#1.base_28| Int) (|v_ULTIMATE.start_cstrreplace_~p~0#1.offset_25| Int)) (and (= |v_ULTIMATE.start_cstrreplace_~p~0#1.offset_25| (select |#length| |v_ULTIMATE.start_cstrreplace_~p~0#1.base_28|)) (<= 1 |#StackHeapBarrier|) (<= 2 |ULTIMATE.start_main_#t~malloc7#1.base|) (not (= (select (select |#memory_int| |v_ULTIMATE.start_cstrreplace_~p~0#1.base_28|) (+ (- 1) |v_ULTIMATE.start_cstrreplace_~p~0#1.offset_25|)) |ULTIMATE.start_cstrreplace_~old#1|)) (= |ULTIMATE.start_cstrreplace_~numReplaced~0#1| 0) (= (select |#valid| |v_ULTIMATE.start_cstrreplace_~p~0#1.base_28|) 1) (<= 2 |v_ULTIMATE.start_cstrreplace_~p~0#1.base_28|) (<= 1 |v_ULTIMATE.start_cstrreplace_~p~0#1.offset_25|)))' at error location [2024-11-14 05:15:38,349 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:15:38,349 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 05:15:38,349 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 13 [2024-11-14 05:15:38,349 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1996235042] [2024-11-14 05:15:38,350 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 05:15:38,350 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-14 05:15:38,350 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:15:38,351 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-14 05:15:38,352 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=392, Unknown=1, NotChecked=0, Total=462 [2024-11-14 05:15:38,352 INFO L87 Difference]: Start difference. First operand 16 states and 18 transitions. Second operand has 15 states, 14 states have (on average 1.5) internal successors, (21), 14 states have internal predecessors, (21), 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) [2024-11-14 05:15:38,585 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:15:38,585 INFO L93 Difference]: Finished difference Result 22 states and 25 transitions. [2024-11-14 05:15:38,585 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-14 05:15:38,585 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 1.5) internal successors, (21), 14 states have internal predecessors, (21), 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 8 [2024-11-14 05:15:38,585 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:15:38,586 INFO L225 Difference]: With dead ends: 22 [2024-11-14 05:15:38,586 INFO L226 Difference]: Without dead ends: 22 [2024-11-14 05:15:38,586 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 6 SyntacticMatches, 1 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 128 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=98, Invalid=501, Unknown=1, NotChecked=0, Total=600 [2024-11-14 05:15:38,587 INFO L432 NwaCegarLoop]: 6 mSDtfsCounter, 37 mSDsluCounter, 18 mSDsCounter, 0 mSdLazyCounter, 59 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 24 SdHoareTripleChecker+Invalid, 66 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 59 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 05:15:38,587 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 24 Invalid, 66 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 59 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 05:15:38,588 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2024-11-14 05:15:38,589 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 16. [2024-11-14 05:15:38,589 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 16 states, 15 states have (on average 1.2) internal successors, (18), 15 states have internal predecessors, (18), 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) [2024-11-14 05:15:38,590 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 18 transitions. [2024-11-14 05:15:38,590 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 18 transitions. Word has length 8 [2024-11-14 05:15:38,590 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:15:38,590 INFO L471 AbstractCegarLoop]: Abstraction has 16 states and 18 transitions. [2024-11-14 05:15:38,590 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 1.5) internal successors, (21), 14 states have internal predecessors, (21), 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) [2024-11-14 05:15:38,590 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 18 transitions. [2024-11-14 05:15:38,590 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2024-11-14 05:15:38,591 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:15:38,591 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1] [2024-11-14 05:15:38,612 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-14 05:15:38,795 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2024-11-14 05:15:38,795 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 6 more)] === [2024-11-14 05:15:38,796 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:15:38,796 INFO L85 PathProgramCache]: Analyzing trace with hash 1619052697, now seen corresponding path program 2 times [2024-11-14 05:15:38,796 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:15:38,796 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1517203695] [2024-11-14 05:15:38,796 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:15:38,796 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:15:38,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:15:39,458 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:15:39,458 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:15:39,458 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1517203695] [2024-11-14 05:15:39,458 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1517203695] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:15:39,458 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1641342719] [2024-11-14 05:15:39,458 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 05:15:39,458 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:15:39,459 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:15:39,461 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:15:39,462 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-14 05:15:39,539 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-14 05:15:39,540 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 05:15:39,541 INFO L255 TraceCheckSpWp]: Trace formula consists of 82 conjuncts, 31 conjuncts are in the unsatisfiable core [2024-11-14 05:15:39,543 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:15:39,573 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 [2024-11-14 05:15:40,026 INFO L349 Elim1Store]: treesize reduction 8, result has 52.9 percent of original size [2024-11-14 05:15:40,026 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 2 case distinctions, treesize of input 26 treesize of output 20 [2024-11-14 05:15:40,096 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:15:40,096 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:15:40,454 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 29 treesize of output 25 [2024-11-14 05:15:40,461 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 21 treesize of output 17 [2024-11-14 05:15:40,470 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 23 [2024-11-14 05:15:40,513 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:15:40,514 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1641342719] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 05:15:40,514 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [80469401] [2024-11-14 05:15:40,516 INFO L159 IcfgInterpreter]: Started Sifa with 8 locations of interest [2024-11-14 05:15:40,516 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:15:40,516 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:15:40,516 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:15:40,516 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:15:41,765 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:15:43,838 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '418#(exists ((|v_ULTIMATE.start_cstrreplace_~p~0#1.base_38| Int) (|v_ULTIMATE.start_cstrreplace_~p~0#1.offset_35| Int)) (and (<= 1 |#StackHeapBarrier|) (<= 2 |ULTIMATE.start_main_#t~malloc7#1.base|) (<= 1 |v_ULTIMATE.start_cstrreplace_~p~0#1.offset_35|) (<= 2 |v_ULTIMATE.start_cstrreplace_~p~0#1.base_38|) (not (= (select (select |#memory_int| |v_ULTIMATE.start_cstrreplace_~p~0#1.base_38|) (+ (- 1) |v_ULTIMATE.start_cstrreplace_~p~0#1.offset_35|)) |ULTIMATE.start_cstrreplace_~old#1|)) (= |ULTIMATE.start_cstrreplace_~numReplaced~0#1| 0) (= (select |#valid| |v_ULTIMATE.start_cstrreplace_~p~0#1.base_38|) 1) (= |v_ULTIMATE.start_cstrreplace_~p~0#1.offset_35| (select |#length| |v_ULTIMATE.start_cstrreplace_~p~0#1.base_38|))))' at error location [2024-11-14 05:15:43,839 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:15:43,839 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 05:15:43,839 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 9, 8] total 23 [2024-11-14 05:15:43,839 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [124548183] [2024-11-14 05:15:43,839 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 05:15:43,840 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-14 05:15:43,841 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:15:43,841 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-14 05:15:43,845 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=137, Invalid=854, Unknown=1, NotChecked=0, Total=992 [2024-11-14 05:15:43,846 INFO L87 Difference]: Start difference. First operand 16 states and 18 transitions. Second operand has 25 states, 24 states have (on average 1.625) internal successors, (39), 24 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) [2024-11-14 05:15:45,017 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:15:45,018 INFO L93 Difference]: Finished difference Result 53 states and 61 transitions. [2024-11-14 05:15:45,018 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-11-14 05:15:45,019 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 24 states have (on average 1.625) internal successors, (39), 24 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 [2024-11-14 05:15:45,019 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:15:45,020 INFO L225 Difference]: With dead ends: 53 [2024-11-14 05:15:45,020 INFO L226 Difference]: Without dead ends: 53 [2024-11-14 05:15:45,021 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 497 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=334, Invalid=1827, Unknown=1, NotChecked=0, Total=2162 [2024-11-14 05:15:45,022 INFO L432 NwaCegarLoop]: 7 mSDtfsCounter, 52 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 237 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 52 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 250 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 237 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-14 05:15:45,023 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [52 Valid, 83 Invalid, 250 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 237 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-14 05:15:45,024 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2024-11-14 05:15:45,027 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 32. [2024-11-14 05:15:45,027 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 31 states have (on average 1.1935483870967742) internal successors, (37), 31 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) [2024-11-14 05:15:45,027 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 37 transitions. [2024-11-14 05:15:45,028 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 37 transitions. Word has length 13 [2024-11-14 05:15:45,028 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:15:45,028 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 37 transitions. [2024-11-14 05:15:45,028 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 24 states have (on average 1.625) internal successors, (39), 24 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) [2024-11-14 05:15:45,028 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 37 transitions. [2024-11-14 05:15:45,029 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-14 05:15:45,029 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:15:45,029 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 2, 1, 1, 1, 1, 1] [2024-11-14 05:15:45,048 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-14 05:15:45,232 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:15:45,232 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 6 more)] === [2024-11-14 05:15:45,233 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:15:45,233 INFO L85 PathProgramCache]: Analyzing trace with hash -1565860644, now seen corresponding path program 1 times [2024-11-14 05:15:45,233 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:15:45,233 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [19106262] [2024-11-14 05:15:45,233 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:15:45,234 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:15:45,260 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:15:46,063 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:15:46,063 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:15:46,064 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [19106262] [2024-11-14 05:15:46,064 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [19106262] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:15:46,064 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [342432271] [2024-11-14 05:15:46,064 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:15:46,064 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:15:46,064 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:15:46,069 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:15:46,073 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-14 05:15:46,165 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:15:46,168 INFO L255 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 37 conjuncts are in the unsatisfiable core [2024-11-14 05:15:46,171 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:15:46,202 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 [2024-11-14 05:15:46,519 INFO L349 Elim1Store]: treesize reduction 35, result has 35.2 percent of original size [2024-11-14 05:15:46,519 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 34 treesize of output 26 [2024-11-14 05:15:47,200 INFO L349 Elim1Store]: treesize reduction 4, result has 82.6 percent of original size [2024-11-14 05:15:47,201 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 28 treesize of output 29 [2024-11-14 05:15:47,393 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:15:47,393 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:15:48,114 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 44 treesize of output 38 [2024-11-14 05:15:48,132 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 68 treesize of output 58 [2024-11-14 05:15:48,147 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 [2024-11-14 05:15:48,163 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:15:48,163 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [342432271] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 05:15:48,163 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1192423781] [2024-11-14 05:15:48,167 INFO L159 IcfgInterpreter]: Started Sifa with 9 locations of interest [2024-11-14 05:15:48,167 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:15:48,168 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:15:48,168 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:15:48,168 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:15:48,953 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:15:49,578 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '679#(and (<= 1 |#StackHeapBarrier|) (<= 2 |ULTIMATE.start_main_#t~malloc7#1.base|) (<= 0 |ULTIMATE.start_cstrreplace_~numReplaced~0#1|))' at error location [2024-11-14 05:15:49,578 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:15:49,578 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 05:15:49,578 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 12, 11] total 29 [2024-11-14 05:15:49,578 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2018314146] [2024-11-14 05:15:49,578 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 05:15:49,579 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2024-11-14 05:15:49,579 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:15:49,582 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2024-11-14 05:15:49,583 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=171, Invalid=1161, Unknown=0, NotChecked=0, Total=1332 [2024-11-14 05:15:49,583 INFO L87 Difference]: Start difference. First operand 32 states and 37 transitions. Second operand has 31 states, 30 states have (on average 1.8666666666666667) internal successors, (56), 30 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) [2024-11-14 05:15:51,610 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:15:51,610 INFO L93 Difference]: Finished difference Result 88 states and 101 transitions. [2024-11-14 05:15:51,610 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2024-11-14 05:15:51,611 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 30 states have (on average 1.8666666666666667) internal successors, (56), 30 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) Word has length 19 [2024-11-14 05:15:51,611 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:15:51,612 INFO L225 Difference]: With dead ends: 88 [2024-11-14 05:15:51,612 INFO L226 Difference]: Without dead ends: 88 [2024-11-14 05:15:51,614 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 27 SyntacticMatches, 1 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 888 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=488, Invalid=3052, Unknown=0, NotChecked=0, Total=3540 [2024-11-14 05:15:51,615 INFO L432 NwaCegarLoop]: 9 mSDtfsCounter, 129 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 342 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 129 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 371 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 342 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-14 05:15:51,616 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [129 Valid, 119 Invalid, 371 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 342 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-14 05:15:51,617 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2024-11-14 05:15:51,621 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 40. [2024-11-14 05:15:51,621 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 39 states have (on average 1.1794871794871795) internal successors, (46), 39 states have internal predecessors, (46), 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) [2024-11-14 05:15:51,622 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 46 transitions. [2024-11-14 05:15:51,622 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 46 transitions. Word has length 19 [2024-11-14 05:15:51,623 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:15:51,623 INFO L471 AbstractCegarLoop]: Abstraction has 40 states and 46 transitions. [2024-11-14 05:15:51,623 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 30 states have (on average 1.8666666666666667) internal successors, (56), 30 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) [2024-11-14 05:15:51,623 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 46 transitions. [2024-11-14 05:15:51,624 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2024-11-14 05:15:51,624 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:15:51,625 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 6, 6, 1, 1, 1] [2024-11-14 05:15:51,653 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-14 05:15:51,825 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:15:51,826 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 6 more)] === [2024-11-14 05:15:51,826 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:15:51,827 INFO L85 PathProgramCache]: Analyzing trace with hash 1992212633, now seen corresponding path program 3 times [2024-11-14 05:15:51,827 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:15:51,827 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1826031728] [2024-11-14 05:15:51,827 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:15:51,827 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:15:51,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:15:53,057 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 0 proven. 81 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:15:53,057 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:15:53,057 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1826031728] [2024-11-14 05:15:53,057 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1826031728] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:15:53,057 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1549294555] [2024-11-14 05:15:53,058 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-14 05:15:53,058 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:15:53,058 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:15:53,061 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:15:53,064 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-14 05:15:53,187 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-14 05:15:53,187 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 05:15:53,192 INFO L255 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 54 conjuncts are in the unsatisfiable core [2024-11-14 05:15:53,197 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:15:53,234 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 [2024-11-14 05:15:55,362 INFO L349 Elim1Store]: treesize reduction 20, result has 70.1 percent of original size [2024-11-14 05:15:55,363 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 7 select indices, 7 select index equivalence classes, 15 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 6 case distinctions, treesize of input 68 treesize of output 73 [2024-11-14 05:15:55,392 WARN L672 sPolynomialRelations]: Constructing 64(two to the power of 6 dual juncts. [2024-11-14 05:15:55,603 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 0 proven. 81 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:15:55,603 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:15:57,370 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 89 treesize of output 77 [2024-11-14 05:15:57,384 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 6 select indices, 6 select index equivalence classes, 15 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 0 case distinctions, treesize of input 137 treesize of output 115 [2024-11-14 05:15:57,393 WARN L672 sPolynomialRelations]: Constructing 64(two to the power of 6 dual juncts. [2024-11-14 05:15:57,408 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 [2024-11-14 05:15:57,428 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 0 proven. 81 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:15:57,428 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1549294555] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 05:15:57,428 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [57600797] [2024-11-14 05:15:57,430 INFO L159 IcfgInterpreter]: Started Sifa with 8 locations of interest [2024-11-14 05:15:57,430 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:15:57,430 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:15:57,430 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:15:57,430 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:15:57,979 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:15:59,906 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1102#(exists ((|v_ULTIMATE.start_cstrreplace_~p~0#1.offset_65| Int) (|v_ULTIMATE.start_cstrreplace_~p~0#1.base_68| Int)) (and (<= 1 |v_ULTIMATE.start_cstrreplace_~p~0#1.offset_65|) (<= 2 |v_ULTIMATE.start_cstrreplace_~p~0#1.base_68|) (<= 1 |#StackHeapBarrier|) (<= 2 |ULTIMATE.start_main_#t~malloc7#1.base|) (not (= (select (select |#memory_int| |v_ULTIMATE.start_cstrreplace_~p~0#1.base_68|) (+ (- 1) |v_ULTIMATE.start_cstrreplace_~p~0#1.offset_65|)) |ULTIMATE.start_cstrreplace_~old#1|)) (= |ULTIMATE.start_cstrreplace_~numReplaced~0#1| 0) (= 1 (select |#valid| |v_ULTIMATE.start_cstrreplace_~p~0#1.base_68|)) (= |v_ULTIMATE.start_cstrreplace_~p~0#1.offset_65| (select |#length| |v_ULTIMATE.start_cstrreplace_~p~0#1.base_68|))))' at error location [2024-11-14 05:15:59,906 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:15:59,906 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 05:15:59,906 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 20, 20] total 49 [2024-11-14 05:15:59,907 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1727669450] [2024-11-14 05:15:59,907 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 05:15:59,907 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 51 states [2024-11-14 05:15:59,907 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:15:59,909 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2024-11-14 05:15:59,911 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=363, Invalid=2942, Unknown=1, NotChecked=0, Total=3306 [2024-11-14 05:15:59,911 INFO L87 Difference]: Start difference. First operand 40 states and 46 transitions. Second operand has 51 states, 50 states have (on average 1.96) internal successors, (98), 50 states have internal predecessors, (98), 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) [2024-11-14 05:16:07,821 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:16:07,821 INFO L93 Difference]: Finished difference Result 123 states and 142 transitions. [2024-11-14 05:16:07,822 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 62 states. [2024-11-14 05:16:07,822 INFO L78 Accepts]: Start accepts. Automaton has has 51 states, 50 states have (on average 1.96) internal successors, (98), 50 states have internal predecessors, (98), 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 33 [2024-11-14 05:16:07,823 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:16:07,823 INFO L225 Difference]: With dead ends: 123 [2024-11-14 05:16:07,823 INFO L226 Difference]: Without dead ends: 123 [2024-11-14 05:16:07,828 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 163 GetRequests, 50 SyntacticMatches, 1 SemanticMatches, 112 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3318 ImplicationChecksByTransitivity, 11.2s TimeCoverageRelationStatistics Valid=1478, Invalid=11402, Unknown=2, NotChecked=0, Total=12882 [2024-11-14 05:16:07,828 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 299 mSDsluCounter, 360 mSDsCounter, 0 mSdLazyCounter, 1048 mSolverCounterSat, 152 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 299 SdHoareTripleChecker+Valid, 375 SdHoareTripleChecker+Invalid, 1200 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 152 IncrementalHoareTripleChecker+Valid, 1048 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2024-11-14 05:16:07,829 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [299 Valid, 375 Invalid, 1200 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [152 Valid, 1048 Invalid, 0 Unknown, 0 Unchecked, 1.5s Time] [2024-11-14 05:16:07,830 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2024-11-14 05:16:07,837 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 76. [2024-11-14 05:16:07,841 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 76 states, 75 states have (on average 1.1733333333333333) internal successors, (88), 75 states have internal predecessors, (88), 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) [2024-11-14 05:16:07,842 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 76 states to 76 states and 88 transitions. [2024-11-14 05:16:07,842 INFO L78 Accepts]: Start accepts. Automaton has 76 states and 88 transitions. Word has length 33 [2024-11-14 05:16:07,842 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:16:07,842 INFO L471 AbstractCegarLoop]: Abstraction has 76 states and 88 transitions. [2024-11-14 05:16:07,842 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 51 states, 50 states have (on average 1.96) internal successors, (98), 50 states have internal predecessors, (98), 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) [2024-11-14 05:16:07,842 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 88 transitions. [2024-11-14 05:16:07,843 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2024-11-14 05:16:07,843 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:16:07,843 INFO L215 NwaCegarLoop]: trace histogram [12, 12, 12, 12, 12, 1, 1, 1] [2024-11-14 05:16:07,870 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-14 05:16:08,044 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:16:08,044 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 6 more)] === [2024-11-14 05:16:08,044 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:16:08,045 INFO L85 PathProgramCache]: Analyzing trace with hash -1082575719, now seen corresponding path program 4 times [2024-11-14 05:16:08,045 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:16:08,045 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1448853328] [2024-11-14 05:16:08,045 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:16:08,045 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:16:08,094 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:16:09,788 INFO L134 CoverageAnalysis]: Checked inductivity of 342 backedges. 0 proven. 342 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:16:09,788 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:16:09,788 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1448853328] [2024-11-14 05:16:09,789 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1448853328] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:16:09,789 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1372237584] [2024-11-14 05:16:09,789 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-14 05:16:09,789 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:16:09,789 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:16:09,793 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:16:09,795 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-14 05:16:09,938 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:16:09,943 INFO L255 TraceCheckSpWp]: Trace formula consists of 262 conjuncts, 98 conjuncts are in the unsatisfiable core [2024-11-14 05:16:09,948 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:16:10,000 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 [2024-11-14 05:16:18,023 INFO L349 Elim1Store]: treesize reduction 44, result has 66.9 percent of original size [2024-11-14 05:16:18,023 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 13 select indices, 13 select index equivalence classes, 66 disjoint index pairs (out of 78 index pairs), introduced 13 new quantified variables, introduced 12 case distinctions, treesize of input 128 treesize of output 139 [2024-11-14 05:16:18,034 WARN L672 sPolynomialRelations]: Constructing 4096(two to the power of 12 dual juncts. [2024-11-14 05:16:18,515 WARN L672 sPolynomialRelations]: Constructing 2048(two to the power of 11 dual juncts. [2024-11-14 05:16:19,142 INFO L134 CoverageAnalysis]: Checked inductivity of 342 backedges. 0 proven. 342 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:16:19,143 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:16:28,175 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 179 treesize of output 155 [2024-11-14 05:16:28,214 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 12 select indices, 12 select index equivalence classes, 66 disjoint index pairs (out of 66 index pairs), introduced 12 new quantified variables, introduced 0 case distinctions, treesize of input 275 treesize of output 229 [2024-11-14 05:16:28,227 WARN L672 sPolynomialRelations]: Constructing 4096(two to the power of 12 dual juncts. [2024-11-14 05:16:28,850 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 [2024-11-14 05:16:28,889 INFO L134 CoverageAnalysis]: Checked inductivity of 342 backedges. 0 proven. 342 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:16:28,889 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1372237584] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 05:16:28,889 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [219564416] [2024-11-14 05:16:28,894 INFO L159 IcfgInterpreter]: Started Sifa with 8 locations of interest [2024-11-14 05:16:28,894 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:16:28,895 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:16:28,895 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:16:28,895 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:16:29,687 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:16:32,716 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1885#(exists ((|v_ULTIMATE.start_cstrreplace_~p~0#1.offset_95| Int) (|v_ULTIMATE.start_cstrreplace_~p~0#1.base_98| Int)) (and (<= 1 |#StackHeapBarrier|) (<= 2 |ULTIMATE.start_main_#t~malloc7#1.base|) (not (= (select (select |#memory_int| |v_ULTIMATE.start_cstrreplace_~p~0#1.base_98|) (+ (- 1) |v_ULTIMATE.start_cstrreplace_~p~0#1.offset_95|)) |ULTIMATE.start_cstrreplace_~old#1|)) (= (select |#length| |v_ULTIMATE.start_cstrreplace_~p~0#1.base_98|) |v_ULTIMATE.start_cstrreplace_~p~0#1.offset_95|) (= (select |#valid| |v_ULTIMATE.start_cstrreplace_~p~0#1.base_98|) 1) (= |ULTIMATE.start_cstrreplace_~numReplaced~0#1| 0) (<= 2 |v_ULTIMATE.start_cstrreplace_~p~0#1.base_98|) (<= 1 |v_ULTIMATE.start_cstrreplace_~p~0#1.offset_95|)))' at error location [2024-11-14 05:16:32,716 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:16:32,716 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 05:16:32,716 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 38, 38] total 91 [2024-11-14 05:16:32,717 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [44471239] [2024-11-14 05:16:32,717 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 05:16:32,717 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 93 states [2024-11-14 05:16:32,717 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:16:32,719 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 93 interpolants. [2024-11-14 05:16:32,723 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1101, Invalid=8798, Unknown=1, NotChecked=0, Total=9900 [2024-11-14 05:16:32,723 INFO L87 Difference]: Start difference. First operand 76 states and 88 transitions. Second operand has 93 states, 92 states have (on average 2.0434782608695654) internal successors, (188), 92 states have internal predecessors, (188), 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) [2024-11-14 05:17:07,814 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:17:07,814 INFO L93 Difference]: Finished difference Result 237 states and 274 transitions. [2024-11-14 05:17:07,815 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 122 states. [2024-11-14 05:17:07,815 INFO L78 Accepts]: Start accepts. Automaton has has 93 states, 92 states have (on average 2.0434782608695654) internal successors, (188), 92 states have internal predecessors, (188), 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 63 [2024-11-14 05:17:07,815 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:17:07,816 INFO L225 Difference]: With dead ends: 237 [2024-11-14 05:17:07,817 INFO L226 Difference]: Without dead ends: 237 [2024-11-14 05:17:07,824 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 319 GetRequests, 104 SyntacticMatches, 1 SemanticMatches, 214 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12747 ImplicationChecksByTransitivity, 45.3s TimeCoverageRelationStatistics Valid=4869, Invalid=41570, Unknown=1, NotChecked=0, Total=46440 [2024-11-14 05:17:07,824 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 1147 mSDsluCounter, 1010 mSDsCounter, 0 mSdLazyCounter, 2828 mSolverCounterSat, 773 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1147 SdHoareTripleChecker+Valid, 1037 SdHoareTripleChecker+Invalid, 3601 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 773 IncrementalHoareTripleChecker+Valid, 2828 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 6.2s IncrementalHoareTripleChecker+Time [2024-11-14 05:17:07,824 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1147 Valid, 1037 Invalid, 3601 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [773 Valid, 2828 Invalid, 0 Unknown, 0 Unchecked, 6.2s Time] [2024-11-14 05:17:07,826 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 237 states. [2024-11-14 05:17:07,843 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 237 to 148. [2024-11-14 05:17:07,844 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 148 states, 147 states have (on average 1.1700680272108843) internal successors, (172), 147 states have internal predecessors, (172), 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) [2024-11-14 05:17:07,845 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 172 transitions. [2024-11-14 05:17:07,845 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 172 transitions. Word has length 63 [2024-11-14 05:17:07,845 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:17:07,846 INFO L471 AbstractCegarLoop]: Abstraction has 148 states and 172 transitions. [2024-11-14 05:17:07,846 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 93 states, 92 states have (on average 2.0434782608695654) internal successors, (188), 92 states have internal predecessors, (188), 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) [2024-11-14 05:17:07,846 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 172 transitions. [2024-11-14 05:17:07,851 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 124 [2024-11-14 05:17:07,851 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:17:07,852 INFO L215 NwaCegarLoop]: trace histogram [24, 24, 24, 24, 24, 1, 1, 1] [2024-11-14 05:17:07,871 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-14 05:17:08,056 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:17:08,056 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 6 more)] === [2024-11-14 05:17:08,057 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:17:08,057 INFO L85 PathProgramCache]: Analyzing trace with hash 870653081, now seen corresponding path program 5 times [2024-11-14 05:17:08,057 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:17:08,057 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [82075786] [2024-11-14 05:17:08,057 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:17:08,057 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:17:08,109 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:17:11,747 INFO L134 CoverageAnalysis]: Checked inductivity of 1404 backedges. 0 proven. 1404 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 05:17:11,747 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:17:11,747 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [82075786] [2024-11-14 05:17:11,747 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [82075786] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:17:11,747 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [139093824] [2024-11-14 05:17:11,748 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 05:17:11,748 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:17:11,748 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:17:11,750 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:17:11,753 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_0bcf4087-59d2-4ba6-98af-16eebf9ebcbe/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-14 05:17:12,105 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 25 check-sat command(s) [2024-11-14 05:17:12,105 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 05:17:12,117 INFO L255 TraceCheckSpWp]: Trace formula consists of 478 conjuncts, 162 conjuncts are in the unsatisfiable core [2024-11-14 05:17:12,125 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:17:12,138 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-14 05:17:12,205 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