./Ultimate.py --spec ../../sv-benchmarks/c/properties/valid-memsafety.prp --file ../../sv-benchmarks/c/termination-memory-alloca/cstrchr-alloca-1.i --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for memory safety (deref-memtrack) Using default analysis Version 30e01a73 Calling Ultimate with: /usr/lib/jvm/java-11-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/config/TaipanMemDerefMemtrack.xml -i ../../sv-benchmarks/c/termination-memory-alloca/cstrchr-alloca-1.i -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/config/svcomp-DerefFreeMemtrack-64bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire --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 312f51ef4503f0fc4b94d177cfa21e5892ce6df837fb8c86c4b09d81ecb9ffbb --- Real Ultimate output --- This is Ultimate 0.2.3-dev-30e01a7 [2023-11-23 21:10:40,874 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-23 21:10:41,005 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/config/svcomp-DerefFreeMemtrack-64bit-Taipan_Default.epf [2023-11-23 21:10:41,019 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-23 21:10:41,020 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-23 21:10:41,048 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-23 21:10:41,048 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-23 21:10:41,049 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-23 21:10:41,050 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-23 21:10:41,051 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-23 21:10:41,051 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-23 21:10:41,052 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-23 21:10:41,053 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-23 21:10:41,053 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-23 21:10:41,054 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-23 21:10:41,054 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-23 21:10:41,055 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-23 21:10:41,056 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-23 21:10:41,056 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-23 21:10:41,057 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-23 21:10:41,057 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-23 21:10:41,058 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-23 21:10:41,059 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-11-23 21:10:41,059 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-11-23 21:10:41,060 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-23 21:10:41,060 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-23 21:10:41,061 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-23 21:10:41,061 INFO L153 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2023-11-23 21:10:41,061 INFO L153 SettingsManager]: * Bitprecise bitfields=true [2023-11-23 21:10:41,062 INFO L153 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2023-11-23 21:10:41,062 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-23 21:10:41,063 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2023-11-23 21:10:41,063 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2023-11-23 21:10:41,064 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-23 21:10:41,064 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-23 21:10:41,065 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-11-23 21:10:41,065 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-23 21:10:41,066 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-23 21:10:41,066 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-23 21:10:41,067 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-23 21:10:41,067 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-23 21:10:41,068 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-23 21:10:41,068 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-11-23 21:10:41,068 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-23 21:10:41,069 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-23 21:10:41,069 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire 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 -> 312f51ef4503f0fc4b94d177cfa21e5892ce6df837fb8c86c4b09d81ecb9ffbb [2023-11-23 21:10:41,393 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-23 21:10:41,430 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-23 21:10:41,433 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-23 21:10:41,434 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-23 21:10:41,435 INFO L274 PluginConnector]: CDTParser initialized [2023-11-23 21:10:41,437 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/../../sv-benchmarks/c/termination-memory-alloca/cstrchr-alloca-1.i [2023-11-23 21:10:44,876 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-23 21:10:45,245 INFO L384 CDTParser]: Found 1 translation units. [2023-11-23 21:10:45,246 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/sv-benchmarks/c/termination-memory-alloca/cstrchr-alloca-1.i [2023-11-23 21:10:45,265 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/data/9e1a52be8/50e0e20e4bc24cf385180bfebfe35f6b/FLAG02202fe66 [2023-11-23 21:10:45,283 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/data/9e1a52be8/50e0e20e4bc24cf385180bfebfe35f6b [2023-11-23 21:10:45,292 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-23 21:10:45,295 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-23 21:10:45,298 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-23 21:10:45,298 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-23 21:10:45,305 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-23 21:10:45,306 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.11 09:10:45" (1/1) ... [2023-11-23 21:10:45,307 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1b5bd591 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:10:45, skipping insertion in model container [2023-11-23 21:10:45,307 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.11 09:10:45" (1/1) ... [2023-11-23 21:10:45,382 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-23 21:10:45,658 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-23 21:10:45,678 INFO L202 MainTranslator]: Completed pre-run [2023-11-23 21:10:45,758 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-23 21:10:45,799 INFO L206 MainTranslator]: Completed translation [2023-11-23 21:10:45,800 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:10:45 WrapperNode [2023-11-23 21:10:45,800 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-23 21:10:45,802 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-23 21:10:45,802 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-23 21:10:45,802 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-23 21:10:45,812 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:10:45" (1/1) ... [2023-11-23 21:10:45,837 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:10:45" (1/1) ... [2023-11-23 21:10:45,865 INFO L138 Inliner]: procedures = 111, calls = 10, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 48 [2023-11-23 21:10:45,866 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-23 21:10:45,866 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-23 21:10:45,867 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-23 21:10:45,867 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-23 21:10:45,877 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:10:45" (1/1) ... [2023-11-23 21:10:45,877 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:10:45" (1/1) ... [2023-11-23 21:10:45,888 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:10:45" (1/1) ... [2023-11-23 21:10:45,889 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:10:45" (1/1) ... [2023-11-23 21:10:45,895 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:10:45" (1/1) ... [2023-11-23 21:10:45,898 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:10:45" (1/1) ... [2023-11-23 21:10:45,900 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:10:45" (1/1) ... [2023-11-23 21:10:45,909 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:10:45" (1/1) ... [2023-11-23 21:10:45,911 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-23 21:10:45,921 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-23 21:10:45,921 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-23 21:10:45,922 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-23 21:10:45,924 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:10:45" (1/1) ... [2023-11-23 21:10:45,934 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-23 21:10:45,946 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:10:45,962 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-23 21:10:46,002 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-23 21:10:46,017 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2023-11-23 21:10:46,018 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2023-11-23 21:10:46,018 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2023-11-23 21:10:46,018 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-11-23 21:10:46,018 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-23 21:10:46,018 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-23 21:10:46,202 INFO L241 CfgBuilder]: Building ICFG [2023-11-23 21:10:46,205 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-23 21:10:46,462 INFO L282 CfgBuilder]: Performing block encoding [2023-11-23 21:10:46,541 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-23 21:10:46,542 INFO L309 CfgBuilder]: Removed 1 assume(true) statements. [2023-11-23 21:10:46,544 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.11 09:10:46 BoogieIcfgContainer [2023-11-23 21:10:46,544 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-23 21:10:46,548 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-23 21:10:46,549 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-23 21:10:46,553 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-23 21:10:46,554 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 23.11 09:10:45" (1/3) ... [2023-11-23 21:10:46,555 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@f69e768 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.11 09:10:46, skipping insertion in model container [2023-11-23 21:10:46,555 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:10:45" (2/3) ... [2023-11-23 21:10:46,556 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@f69e768 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.11 09:10:46, skipping insertion in model container [2023-11-23 21:10:46,556 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.11 09:10:46" (3/3) ... [2023-11-23 21:10:46,558 INFO L112 eAbstractionObserver]: Analyzing ICFG cstrchr-alloca-1.i [2023-11-23 21:10:46,583 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-23 21:10:46,584 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 9 error locations. [2023-11-23 21:10:46,642 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-23 21:10:46,651 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=false, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@278f266d, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-23 21:10:46,652 INFO L358 AbstractCegarLoop]: Starting to check reachability of 9 error locations. [2023-11-23 21:10:46,657 INFO L276 IsEmpty]: Start isEmpty. Operand has 18 states, 8 states have (on average 2.5) internal successors, (20), 17 states have internal predecessors, (20), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:10:46,664 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 3 [2023-11-23 21:10:46,664 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:10:46,665 INFO L195 NwaCegarLoop]: trace histogram [1, 1] [2023-11-23 21:10:46,666 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 6 more)] === [2023-11-23 21:10:46,673 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:10:46,673 INFO L85 PathProgramCache]: Analyzing trace with hash 2801, now seen corresponding path program 1 times [2023-11-23 21:10:46,686 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:10:46,686 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1241092613] [2023-11-23 21:10:46,687 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:10:46,687 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:10:46,834 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:10:47,036 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 21:10:47,038 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:10:47,039 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1241092613] [2023-11-23 21:10:47,040 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1241092613] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 21:10:47,040 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 21:10:47,040 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-11-23 21:10:47,042 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [351334204] [2023-11-23 21:10:47,043 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 21:10:47,049 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-23 21:10:47,049 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:10:47,109 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-23 21:10:47,110 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-23 21:10:47,113 INFO L87 Difference]: Start difference. First operand has 18 states, 8 states have (on average 2.5) internal successors, (20), 17 states have internal predecessors, (20), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Second operand has 3 states, 2 states have (on average 1.0) internal successors, (2), 2 states have internal predecessors, (2), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:10:47,203 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:10:47,204 INFO L93 Difference]: Finished difference Result 17 states and 18 transitions. [2023-11-23 21:10:47,231 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-23 21:10:47,232 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 1.0) internal successors, (2), 2 states have internal predecessors, (2), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 2 [2023-11-23 21:10:47,233 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:10:47,250 INFO L225 Difference]: With dead ends: 17 [2023-11-23 21:10:47,250 INFO L226 Difference]: Without dead ends: 16 [2023-11-23 21:10:47,265 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 1 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-23 21:10:47,298 INFO L413 NwaCegarLoop]: 8 mSDtfsCounter, 14 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 8 SdHoareTripleChecker+Invalid, 13 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-23 21:10:47,299 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 8 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-23 21:10:47,341 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16 states. [2023-11-23 21:10:47,364 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16 to 16. [2023-11-23 21:10:47,366 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 16 states, 8 states have (on average 2.125) internal successors, (17), 15 states have internal predecessors, (17), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:10:47,367 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 17 transitions. [2023-11-23 21:10:47,368 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 17 transitions. Word has length 2 [2023-11-23 21:10:47,369 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:10:47,369 INFO L495 AbstractCegarLoop]: Abstraction has 16 states and 17 transitions. [2023-11-23 21:10:47,369 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 1.0) internal successors, (2), 2 states have internal predecessors, (2), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:10:47,371 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 17 transitions. [2023-11-23 21:10:47,371 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 3 [2023-11-23 21:10:47,371 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:10:47,372 INFO L195 NwaCegarLoop]: trace histogram [1, 1] [2023-11-23 21:10:47,372 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-23 21:10:47,373 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 6 more)] === [2023-11-23 21:10:47,374 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:10:47,374 INFO L85 PathProgramCache]: Analyzing trace with hash 2802, now seen corresponding path program 1 times [2023-11-23 21:10:47,375 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:10:47,375 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [6378322] [2023-11-23 21:10:47,375 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:10:47,375 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:10:47,428 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:10:47,794 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 21:10:47,794 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:10:47,795 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [6378322] [2023-11-23 21:10:47,795 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [6378322] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 21:10:47,796 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 21:10:47,797 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-11-23 21:10:47,797 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1948928678] [2023-11-23 21:10:47,798 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 21:10:47,800 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-23 21:10:47,800 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:10:47,801 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-23 21:10:47,802 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-23 21:10:47,802 INFO L87 Difference]: Start difference. First operand 16 states and 17 transitions. Second operand has 3 states, 2 states have (on average 1.0) internal successors, (2), 2 states have internal predecessors, (2), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:10:47,838 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:10:47,839 INFO L93 Difference]: Finished difference Result 15 states and 16 transitions. [2023-11-23 21:10:47,839 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-23 21:10:47,839 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 1.0) internal successors, (2), 2 states have internal predecessors, (2), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 2 [2023-11-23 21:10:47,840 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:10:47,841 INFO L225 Difference]: With dead ends: 15 [2023-11-23 21:10:47,842 INFO L226 Difference]: Without dead ends: 15 [2023-11-23 21:10:47,849 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 1 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-23 21:10:47,852 INFO L413 NwaCegarLoop]: 8 mSDtfsCounter, 15 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 8 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-23 21:10:47,854 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 8 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-23 21:10:47,857 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2023-11-23 21:10:47,859 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2023-11-23 21:10:47,860 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 15 states, 8 states have (on average 2.0) internal successors, (16), 14 states have internal predecessors, (16), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:10:47,860 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2023-11-23 21:10:47,861 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 2 [2023-11-23 21:10:47,861 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:10:47,861 INFO L495 AbstractCegarLoop]: Abstraction has 15 states and 16 transitions. [2023-11-23 21:10:47,861 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 1.0) internal successors, (2), 2 states have internal predecessors, (2), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:10:47,862 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 16 transitions. [2023-11-23 21:10:47,862 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2023-11-23 21:10:47,862 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:10:47,862 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1] [2023-11-23 21:10:47,863 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-23 21:10:47,863 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 6 more)] === [2023-11-23 21:10:47,864 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:10:47,864 INFO L85 PathProgramCache]: Analyzing trace with hash 88152, now seen corresponding path program 1 times [2023-11-23 21:10:47,864 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:10:47,864 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1092550368] [2023-11-23 21:10:47,865 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:10:47,865 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:10:47,895 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:10:47,989 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 21:10:47,990 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:10:47,990 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1092550368] [2023-11-23 21:10:47,990 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1092550368] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 21:10:47,991 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 21:10:47,991 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-23 21:10:47,993 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [112239146] [2023-11-23 21:10:47,993 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 21:10:47,994 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-23 21:10:47,994 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:10:47,995 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-23 21:10:47,995 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-23 21:10:47,996 INFO L87 Difference]: Start difference. First operand 15 states and 16 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) [2023-11-23 21:10:48,035 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:10:48,036 INFO L93 Difference]: Finished difference Result 12 states and 13 transitions. [2023-11-23 21:10:48,036 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-23 21:10:48,036 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 [2023-11-23 21:10:48,037 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:10:48,037 INFO L225 Difference]: With dead ends: 12 [2023-11-23 21:10:48,037 INFO L226 Difference]: Without dead ends: 12 [2023-11-23 21:10:48,038 INFO L412 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 [2023-11-23 21:10:48,039 INFO L413 NwaCegarLoop]: 4 mSDtfsCounter, 8 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 4 SdHoareTripleChecker+Invalid, 15 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-23 21:10:48,040 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 4 Invalid, 15 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-23 21:10:48,041 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 12 states. [2023-11-23 21:10:48,043 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 12 to 12. [2023-11-23 21:10:48,043 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 8 states have (on average 1.625) internal successors, (13), 11 states have internal predecessors, (13), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:10:48,044 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12 states to 12 states and 13 transitions. [2023-11-23 21:10:48,044 INFO L78 Accepts]: Start accepts. Automaton has 12 states and 13 transitions. Word has length 3 [2023-11-23 21:10:48,044 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:10:48,044 INFO L495 AbstractCegarLoop]: Abstraction has 12 states and 13 transitions. [2023-11-23 21:10:48,045 INFO L496 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) [2023-11-23 21:10:48,045 INFO L276 IsEmpty]: Start isEmpty. Operand 12 states and 13 transitions. [2023-11-23 21:10:48,045 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2023-11-23 21:10:48,045 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:10:48,046 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1] [2023-11-23 21:10:48,046 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2023-11-23 21:10:48,046 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 6 more)] === [2023-11-23 21:10:48,047 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:10:48,047 INFO L85 PathProgramCache]: Analyzing trace with hash 88153, now seen corresponding path program 1 times [2023-11-23 21:10:48,047 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:10:48,048 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1919669047] [2023-11-23 21:10:48,048 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:10:48,048 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:10:48,064 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:10:48,273 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 21:10:48,274 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:10:48,274 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1919669047] [2023-11-23 21:10:48,274 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1919669047] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 21:10:48,275 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 21:10:48,276 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-23 21:10:48,276 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1006009389] [2023-11-23 21:10:48,276 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 21:10:48,277 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-23 21:10:48,277 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:10:48,278 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-23 21:10:48,279 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-23 21:10:48,279 INFO L87 Difference]: Start difference. First operand 12 states and 13 transitions. Second operand has 4 states, 3 states have (on average 1.0) internal successors, (3), 3 states have internal predecessors, (3), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:10:48,377 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:10:48,378 INFO L93 Difference]: Finished difference Result 17 states and 20 transitions. [2023-11-23 21:10:48,378 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-23 21:10:48,379 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 1.0) internal successors, (3), 3 states have internal predecessors, (3), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 3 [2023-11-23 21:10:48,379 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:10:48,380 INFO L225 Difference]: With dead ends: 17 [2023-11-23 21:10:48,380 INFO L226 Difference]: Without dead ends: 17 [2023-11-23 21:10:48,381 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2023-11-23 21:10:48,387 INFO L413 NwaCegarLoop]: 4 mSDtfsCounter, 24 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 8 SdHoareTripleChecker+Invalid, 19 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-23 21:10:48,393 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [24 Valid, 8 Invalid, 19 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-23 21:10:48,396 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states. [2023-11-23 21:10:48,398 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2023-11-23 21:10:48,404 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 13 states have (on average 1.5384615384615385) internal successors, (20), 16 states have internal predecessors, (20), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:10:48,405 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 20 transitions. [2023-11-23 21:10:48,405 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 20 transitions. Word has length 3 [2023-11-23 21:10:48,405 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:10:48,406 INFO L495 AbstractCegarLoop]: Abstraction has 17 states and 20 transitions. [2023-11-23 21:10:48,406 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 1.0) internal successors, (3), 3 states have internal predecessors, (3), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:10:48,407 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 20 transitions. [2023-11-23 21:10:48,407 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2023-11-23 21:10:48,408 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:10:48,409 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2023-11-23 21:10:48,409 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2023-11-23 21:10:48,409 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 6 more)] === [2023-11-23 21:10:48,415 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:10:48,416 INFO L85 PathProgramCache]: Analyzing trace with hash -1667698831, now seen corresponding path program 1 times [2023-11-23 21:10:48,416 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:10:48,416 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1770756247] [2023-11-23 21:10:48,416 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:10:48,417 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:10:48,433 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:10:48,479 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 21:10:48,479 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:10:48,480 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1770756247] [2023-11-23 21:10:48,480 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1770756247] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 21:10:48,480 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 21:10:48,480 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-23 21:10:48,481 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2035964675] [2023-11-23 21:10:48,481 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 21:10:48,481 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-23 21:10:48,481 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:10:48,482 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-23 21:10:48,482 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-23 21:10:48,483 INFO L87 Difference]: Start difference. First operand 17 states and 20 transitions. Second operand has 3 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) [2023-11-23 21:10:48,507 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:10:48,507 INFO L93 Difference]: Finished difference Result 19 states and 22 transitions. [2023-11-23 21:10:48,508 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-23 21:10:48,508 INFO L78 Accepts]: Start accepts. Automaton has has 3 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 [2023-11-23 21:10:48,509 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:10:48,509 INFO L225 Difference]: With dead ends: 19 [2023-11-23 21:10:48,510 INFO L226 Difference]: Without dead ends: 19 [2023-11-23 21:10:48,511 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-23 21:10:48,512 INFO L413 NwaCegarLoop]: 7 mSDtfsCounter, 0 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 11 SdHoareTripleChecker+Invalid, 14 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-23 21:10:48,513 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 11 Invalid, 14 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-23 21:10:48,514 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2023-11-23 21:10:48,519 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 19. [2023-11-23 21:10:48,520 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) [2023-11-23 21:10:48,521 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 22 transitions. [2023-11-23 21:10:48,522 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 22 transitions. Word has length 6 [2023-11-23 21:10:48,522 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:10:48,522 INFO L495 AbstractCegarLoop]: Abstraction has 19 states and 22 transitions. [2023-11-23 21:10:48,522 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 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) [2023-11-23 21:10:48,523 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 22 transitions. [2023-11-23 21:10:48,524 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-11-23 21:10:48,524 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:10:48,524 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:10:48,525 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2023-11-23 21:10:48,525 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 6 more)] === [2023-11-23 21:10:48,526 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:10:48,526 INFO L85 PathProgramCache]: Analyzing trace with hash -159220985, now seen corresponding path program 1 times [2023-11-23 21:10:48,526 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:10:48,527 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [740645690] [2023-11-23 21:10:48,527 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:10:48,527 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:10:48,573 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:10:48,905 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 21:10:48,905 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:10:48,905 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [740645690] [2023-11-23 21:10:48,906 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [740645690] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 21:10:48,906 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [891521859] [2023-11-23 21:10:48,906 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:10:48,907 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:10:48,907 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:10:48,909 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:10:48,951 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-23 21:10:49,025 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:10:49,029 INFO L262 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 26 conjunts are in the unsatisfiable core [2023-11-23 21:10:49,036 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:10:49,201 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 10 [2023-11-23 21:10:49,383 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-23 21:10:49,383 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 32 treesize of output 29 [2023-11-23 21:10:49,539 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 21:10:49,540 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:10:49,759 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 11 [2023-11-23 21:10:49,772 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2023-11-23 21:10:49,790 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 20 [2023-11-23 21:10:49,813 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 21:10:49,814 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [891521859] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:10:49,814 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [423387603] [2023-11-23 21:10:49,839 INFO L159 IcfgInterpreter]: Started Sifa with 7 locations of interest [2023-11-23 21:10:49,839 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:10:49,844 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-23 21:10:49,852 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-23 21:10:49,852 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-23 21:10:50,616 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-23 21:10:51,519 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '249#(and (<= (select |#length| |ULTIMATE.start_cstrchr_~s#1.base|) |ULTIMATE.start_cstrchr_~s#1.offset|) (= |ULTIMATE.start_main_#t~malloc8#1.offset| 0) (<= 1 |#StackHeapBarrier|) (<= 2 |ULTIMATE.start_cstrchr_#in~s#1.base|) (<= 2 |ULTIMATE.start_main_~nondetString~0#1.base|) (<= |ULTIMATE.start_cstrchr_~c#1| 2147483647) (<= 0 (+ 2147483648 |ULTIMATE.start_main_#t~nondet9#1|)) (= |ULTIMATE.start_main_~nondetString~0#1.offset| 0) (<= 0 (+ |ULTIMATE.start_cstrchr_#in~c#1| 2147483648)) (= |ULTIMATE.start_cstrchr_#in~s#1.offset| 0) (<= 2 |ULTIMATE.start_main_#t~malloc8#1.base|) (<= |ULTIMATE.start_main_#t~nondet9#1| 2147483647) (<= 1 |ULTIMATE.start_main_~length~0#1|) (<= 2 |ULTIMATE.start_cstrchr_~s#1.base|) (<= 0 (+ |ULTIMATE.start_cstrchr_~c#1| 2147483648)) (<= 0 |ULTIMATE.start_cstrchr_~s#1.offset|) (<= |ULTIMATE.start_cstrchr_#in~c#1| 2147483647))' at error location [2023-11-23 21:10:51,520 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-23 21:10:51,520 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-23 21:10:51,520 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 13 [2023-11-23 21:10:51,520 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1890911523] [2023-11-23 21:10:51,521 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-23 21:10:51,521 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-23 21:10:51,521 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:10:51,523 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-23 21:10:51,525 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=347, Unknown=0, NotChecked=0, Total=420 [2023-11-23 21:10:51,525 INFO L87 Difference]: Start difference. First operand 19 states and 22 transitions. Second operand has 15 states, 14 states have (on average 1.3571428571428572) internal successors, (19), 14 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) [2023-11-23 21:10:52,024 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:10:52,024 INFO L93 Difference]: Finished difference Result 24 states and 29 transitions. [2023-11-23 21:10:52,025 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-23 21:10:52,025 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 1.3571428571428572) internal successors, (19), 14 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) Word has length 7 [2023-11-23 21:10:52,025 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:10:52,027 INFO L225 Difference]: With dead ends: 24 [2023-11-23 21:10:52,027 INFO L226 Difference]: Without dead ends: 24 [2023-11-23 21:10:52,028 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 4 SyntacticMatches, 1 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 161 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=144, Invalid=612, Unknown=0, NotChecked=0, Total=756 [2023-11-23 21:10:52,029 INFO L413 NwaCegarLoop]: 4 mSDtfsCounter, 77 mSDsluCounter, 14 mSDsCounter, 0 mSdLazyCounter, 89 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 77 SdHoareTripleChecker+Valid, 18 SdHoareTripleChecker+Invalid, 97 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 89 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-23 21:10:52,030 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [77 Valid, 18 Invalid, 97 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 89 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-23 21:10:52,030 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2023-11-23 21:10:52,033 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 16. [2023-11-23 21:10:52,034 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 16 states, 14 states have (on average 1.3571428571428572) internal successors, (19), 15 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) [2023-11-23 21:10:52,035 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 19 transitions. [2023-11-23 21:10:52,035 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 19 transitions. Word has length 7 [2023-11-23 21:10:52,035 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:10:52,035 INFO L495 AbstractCegarLoop]: Abstraction has 16 states and 19 transitions. [2023-11-23 21:10:52,036 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 1.3571428571428572) internal successors, (19), 14 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) [2023-11-23 21:10:52,036 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 19 transitions. [2023-11-23 21:10:52,036 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-11-23 21:10:52,037 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:10:52,037 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:10:52,064 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2023-11-23 21:10:52,257 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:10:52,258 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr8ASSERT_VIOLATIONMEMORY_LEAK === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 6 more)] === [2023-11-23 21:10:52,258 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:10:52,259 INFO L85 PathProgramCache]: Analyzing trace with hash -159056999, now seen corresponding path program 1 times [2023-11-23 21:10:52,259 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:10:52,259 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1382538539] [2023-11-23 21:10:52,259 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:10:52,259 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:10:52,289 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:10:52,355 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 21:10:52,355 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:10:52,355 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1382538539] [2023-11-23 21:10:52,355 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1382538539] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 21:10:52,356 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 21:10:52,356 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-23 21:10:52,356 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1035287409] [2023-11-23 21:10:52,356 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 21:10:52,356 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-23 21:10:52,356 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:10:52,357 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-23 21:10:52,357 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-23 21:10:52,358 INFO L87 Difference]: Start difference. First operand 16 states and 19 transitions. Second operand has 4 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 3 states have internal predecessors, (7), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:10:52,375 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:10:52,375 INFO L93 Difference]: Finished difference Result 15 states and 18 transitions. [2023-11-23 21:10:52,377 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-23 21:10:52,377 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 3 states have internal predecessors, (7), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2023-11-23 21:10:52,378 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:10:52,378 INFO L225 Difference]: With dead ends: 15 [2023-11-23 21:10:52,378 INFO L226 Difference]: Without dead ends: 12 [2023-11-23 21:10:52,378 INFO L412 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 [2023-11-23 21:10:52,379 INFO L413 NwaCegarLoop]: 5 mSDtfsCounter, 4 mSDsluCounter, 5 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 10 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-23 21:10:52,380 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 10 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-23 21:10:52,382 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 12 states. [2023-11-23 21:10:52,384 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 12 to 12. [2023-11-23 21:10:52,385 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 11 states have (on average 1.0909090909090908) internal successors, (12), 11 states have internal predecessors, (12), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:10:52,386 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2023-11-23 21:10:52,386 INFO L78 Accepts]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 7 [2023-11-23 21:10:52,387 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:10:52,387 INFO L495 AbstractCegarLoop]: Abstraction has 12 states and 12 transitions. [2023-11-23 21:10:52,387 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 3 states have internal predecessors, (7), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:10:52,387 INFO L276 IsEmpty]: Start isEmpty. Operand 12 states and 12 transitions. [2023-11-23 21:10:52,388 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2023-11-23 21:10:52,389 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:10:52,389 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1] [2023-11-23 21:10:52,389 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2023-11-23 21:10:52,389 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 6 more)] === [2023-11-23 21:10:52,390 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:10:52,390 INFO L85 PathProgramCache]: Analyzing trace with hash -1388931403, now seen corresponding path program 2 times [2023-11-23 21:10:52,390 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:10:52,391 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1029378615] [2023-11-23 21:10:52,391 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:10:52,391 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:10:52,413 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:10:52,881 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 21:10:52,882 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:10:52,882 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1029378615] [2023-11-23 21:10:52,882 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1029378615] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 21:10:52,882 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [598611859] [2023-11-23 21:10:52,882 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-23 21:10:52,883 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:10:52,883 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:10:52,898 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:10:52,906 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-23 21:10:52,996 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-11-23 21:10:52,997 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 21:10:52,998 INFO L262 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 35 conjunts are in the unsatisfiable core [2023-11-23 21:10:53,002 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:10:53,043 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 10 [2023-11-23 21:11:00,110 INFO L349 Elim1Store]: treesize reduction 8, result has 75.8 percent of original size [2023-11-23 21:11:00,111 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 27 treesize of output 36 [2023-11-23 21:11:00,211 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 21:11:00,211 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:11:00,771 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 23 [2023-11-23 21:11:00,791 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-23 21:11:00,792 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 43 treesize of output 47 [2023-11-23 21:11:00,807 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2023-11-23 21:11:00,834 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 21:11:00,835 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [598611859] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:11:00,835 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [850407186] [2023-11-23 21:11:00,840 INFO L159 IcfgInterpreter]: Started Sifa with 7 locations of interest [2023-11-23 21:11:00,841 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:11:00,844 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-23 21:11:00,844 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-23 21:11:00,844 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-23 21:11:01,271 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-23 21:11:02,058 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '425#(and (<= (select |#length| |ULTIMATE.start_cstrchr_~s#1.base|) |ULTIMATE.start_cstrchr_~s#1.offset|) (= |ULTIMATE.start_main_#t~malloc8#1.offset| 0) (<= 1 |#StackHeapBarrier|) (<= 2 |ULTIMATE.start_cstrchr_#in~s#1.base|) (<= 2 |ULTIMATE.start_main_~nondetString~0#1.base|) (<= |ULTIMATE.start_cstrchr_~c#1| 2147483647) (<= 0 (+ 2147483648 |ULTIMATE.start_main_#t~nondet9#1|)) (= |ULTIMATE.start_main_~nondetString~0#1.offset| 0) (<= 0 (+ |ULTIMATE.start_cstrchr_#in~c#1| 2147483648)) (= |ULTIMATE.start_cstrchr_#in~s#1.offset| 0) (<= 2 |ULTIMATE.start_main_#t~malloc8#1.base|) (<= |ULTIMATE.start_main_#t~nondet9#1| 2147483647) (<= 1 |ULTIMATE.start_main_~length~0#1|) (<= 2 |ULTIMATE.start_cstrchr_~s#1.base|) (<= 0 (+ |ULTIMATE.start_cstrchr_~c#1| 2147483648)) (<= 0 |ULTIMATE.start_cstrchr_~s#1.offset|) (<= |ULTIMATE.start_cstrchr_#in~c#1| 2147483647))' at error location [2023-11-23 21:11:02,058 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-23 21:11:02,058 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-23 21:11:02,058 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 9, 9] total 23 [2023-11-23 21:11:02,058 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [29903050] [2023-11-23 21:11:02,058 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-23 21:11:02,059 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2023-11-23 21:11:02,059 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:11:02,060 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2023-11-23 21:11:02,060 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=128, Invalid=799, Unknown=3, NotChecked=0, Total=930 [2023-11-23 21:11:02,061 INFO L87 Difference]: Start difference. First operand 12 states and 12 transitions. Second operand has 25 states, 24 states have (on average 1.3333333333333333) internal successors, (32), 24 states have internal predecessors, (32), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:11:04,673 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:11:04,673 INFO L93 Difference]: Finished difference Result 27 states and 27 transitions. [2023-11-23 21:11:04,673 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2023-11-23 21:11:04,674 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 24 states have (on average 1.3333333333333333) internal successors, (32), 24 states have internal predecessors, (32), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2023-11-23 21:11:04,674 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:11:04,674 INFO L225 Difference]: With dead ends: 27 [2023-11-23 21:11:04,674 INFO L226 Difference]: Without dead ends: 27 [2023-11-23 21:11:04,676 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 462 ImplicationChecksByTransitivity, 10.3s TimeCoverageRelationStatistics Valid=368, Invalid=1790, Unknown=4, NotChecked=0, Total=2162 [2023-11-23 21:11:04,677 INFO L413 NwaCegarLoop]: 0 mSDtfsCounter, 78 mSDsluCounter, 2 mSDsCounter, 0 mSdLazyCounter, 163 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 78 SdHoareTripleChecker+Valid, 2 SdHoareTripleChecker+Invalid, 179 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 163 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-23 21:11:04,677 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [78 Valid, 2 Invalid, 179 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 163 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-23 21:11:04,678 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2023-11-23 21:11:04,680 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 24. [2023-11-23 21:11:04,680 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 23 states have (on average 1.0434782608695652) internal successors, (24), 23 states have internal predecessors, (24), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:11:04,688 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 24 transitions. [2023-11-23 21:11:04,688 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 24 transitions. Word has length 11 [2023-11-23 21:11:04,688 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:11:04,689 INFO L495 AbstractCegarLoop]: Abstraction has 24 states and 24 transitions. [2023-11-23 21:11:04,690 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 24 states have (on average 1.3333333333333333) internal successors, (32), 24 states have internal predecessors, (32), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:11:04,690 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 24 transitions. [2023-11-23 21:11:04,691 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2023-11-23 21:11:04,692 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:11:04,692 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 1, 1, 1] [2023-11-23 21:11:04,732 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-23 21:11:04,924 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:11:04,925 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 6 more)] === [2023-11-23 21:11:04,926 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:11:04,926 INFO L85 PathProgramCache]: Analyzing trace with hash 1750581183, now seen corresponding path program 3 times [2023-11-23 21:11:04,926 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:11:04,926 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1719229969] [2023-11-23 21:11:04,926 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:11:04,927 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:11:04,960 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:11:05,727 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 21:11:05,728 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:11:05,728 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1719229969] [2023-11-23 21:11:05,728 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1719229969] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 21:11:05,728 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1317332412] [2023-11-23 21:11:05,728 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-23 21:11:05,728 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:11:05,729 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:11:05,741 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:11:05,748 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-23 21:11:05,831 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-23 21:11:05,831 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 21:11:05,833 INFO L262 TraceCheckSpWp]: Trace formula consists of 148 conjuncts, 61 conjunts are in the unsatisfiable core [2023-11-23 21:11:05,837 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:11:05,871 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2023-11-23 21:11:06,973 INFO L349 Elim1Store]: treesize reduction 16, result has 61.0 percent of original size [2023-11-23 21:11:06,974 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 6 select indices, 6 select index equivalence classes, 10 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 5 case distinctions, treesize of input 63 treesize of output 57 [2023-11-23 21:11:07,154 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 21:11:07,154 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:11:08,762 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 74 treesize of output 64 [2023-11-23 21:11:08,770 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 [2023-11-23 21:11:08,793 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 10 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 0 case distinctions, treesize of input 74 treesize of output 56 [2023-11-23 21:11:08,869 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 21:11:08,869 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1317332412] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:11:08,869 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [838995552] [2023-11-23 21:11:08,874 INFO L159 IcfgInterpreter]: Started Sifa with 7 locations of interest [2023-11-23 21:11:08,874 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:11:08,875 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-23 21:11:08,875 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-23 21:11:08,875 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-23 21:11:09,207 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-23 21:11:10,293 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '691#(and (<= (select |#length| |ULTIMATE.start_cstrchr_~s#1.base|) |ULTIMATE.start_cstrchr_~s#1.offset|) (= |ULTIMATE.start_main_#t~malloc8#1.offset| 0) (<= 1 |#StackHeapBarrier|) (<= 2 |ULTIMATE.start_cstrchr_#in~s#1.base|) (<= 2 |ULTIMATE.start_main_~nondetString~0#1.base|) (<= |ULTIMATE.start_cstrchr_~c#1| 2147483647) (<= 0 (+ 2147483648 |ULTIMATE.start_main_#t~nondet9#1|)) (= |ULTIMATE.start_main_~nondetString~0#1.offset| 0) (<= 0 (+ |ULTIMATE.start_cstrchr_#in~c#1| 2147483648)) (= |ULTIMATE.start_cstrchr_#in~s#1.offset| 0) (<= 2 |ULTIMATE.start_main_#t~malloc8#1.base|) (<= |ULTIMATE.start_main_#t~nondet9#1| 2147483647) (<= 1 |ULTIMATE.start_main_~length~0#1|) (<= 2 |ULTIMATE.start_cstrchr_~s#1.base|) (<= 0 (+ |ULTIMATE.start_cstrchr_~c#1| 2147483648)) (<= 0 |ULTIMATE.start_cstrchr_~s#1.offset|) (<= |ULTIMATE.start_cstrchr_#in~c#1| 2147483647))' at error location [2023-11-23 21:11:10,293 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-23 21:11:10,293 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-23 21:11:10,294 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 17, 17] total 43 [2023-11-23 21:11:10,294 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1982165446] [2023-11-23 21:11:10,294 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-23 21:11:10,295 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 45 states [2023-11-23 21:11:10,295 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:11:10,296 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2023-11-23 21:11:10,298 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=301, Invalid=2249, Unknown=0, NotChecked=0, Total=2550 [2023-11-23 21:11:10,298 INFO L87 Difference]: Start difference. First operand 24 states and 24 transitions. Second operand has 45 states, 44 states have (on average 1.5681818181818181) internal successors, (69), 44 states have internal predecessors, (69), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:11:14,410 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:11:14,411 INFO L93 Difference]: Finished difference Result 47 states and 47 transitions. [2023-11-23 21:11:14,411 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2023-11-23 21:11:14,411 INFO L78 Accepts]: Start accepts. Automaton has has 45 states, 44 states have (on average 1.5681818181818181) internal successors, (69), 44 states have internal predecessors, (69), 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 23 [2023-11-23 21:11:14,411 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:11:14,412 INFO L225 Difference]: With dead ends: 47 [2023-11-23 21:11:14,412 INFO L226 Difference]: Without dead ends: 47 [2023-11-23 21:11:14,415 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 82 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1694 ImplicationChecksByTransitivity, 6.6s TimeCoverageRelationStatistics Valid=984, Invalid=5988, Unknown=0, NotChecked=0, Total=6972 [2023-11-23 21:11:14,416 INFO L413 NwaCegarLoop]: 0 mSDtfsCounter, 140 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 535 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 140 SdHoareTripleChecker+Valid, 3 SdHoareTripleChecker+Invalid, 540 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 535 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2023-11-23 21:11:14,416 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [140 Valid, 3 Invalid, 540 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 535 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2023-11-23 21:11:14,417 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2023-11-23 21:11:14,420 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 44. [2023-11-23 21:11:14,420 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 43 states have (on average 1.0232558139534884) internal successors, (44), 43 states have internal predecessors, (44), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:11:14,421 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 44 transitions. [2023-11-23 21:11:14,421 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 44 transitions. Word has length 23 [2023-11-23 21:11:14,422 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:11:14,422 INFO L495 AbstractCegarLoop]: Abstraction has 44 states and 44 transitions. [2023-11-23 21:11:14,422 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 45 states, 44 states have (on average 1.5681818181818181) internal successors, (69), 44 states have internal predecessors, (69), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:11:14,422 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 44 transitions. [2023-11-23 21:11:14,423 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2023-11-23 21:11:14,424 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:11:14,424 INFO L195 NwaCegarLoop]: trace histogram [10, 10, 10, 10, 1, 1, 1] [2023-11-23 21:11:14,445 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-23 21:11:14,645 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2023-11-23 21:11:14,645 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 6 more)] === [2023-11-23 21:11:14,646 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:11:14,646 INFO L85 PathProgramCache]: Analyzing trace with hash -647595995, now seen corresponding path program 4 times [2023-11-23 21:11:14,646 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:11:14,646 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1108070067] [2023-11-23 21:11:14,646 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:11:14,646 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:11:14,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:11:16,400 INFO L134 CoverageAnalysis]: Checked inductivity of 190 backedges. 0 proven. 190 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 21:11:16,401 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:11:16,401 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1108070067] [2023-11-23 21:11:16,401 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1108070067] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 21:11:16,401 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [563225449] [2023-11-23 21:11:16,402 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-11-23 21:11:16,402 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:11:16,402 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:11:16,409 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:11:16,420 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b212b0cb-e7c4-41d9-bf99-8f41ef612706/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-23 21:11:16,519 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:11:16,522 INFO L262 TraceCheckSpWp]: Trace formula consists of 248 conjuncts, 98 conjunts are in the unsatisfiable core [2023-11-23 21:11:16,527 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:11:16,569 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 10 [2023-11-23 21:11:22,105 INFO L349 Elim1Store]: treesize reduction 36, result has 67.6 percent of original size [2023-11-23 21:11:22,105 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 11 select indices, 11 select index equivalence classes, 45 disjoint index pairs (out of 55 index pairs), introduced 11 new quantified variables, introduced 10 case distinctions, treesize of input 122 treesize of output 127 [2023-11-23 21:11:22,147 WARN L667 sPolynomialRelations]: Constructing 1024(two to the power of 10 dual juncts. [2023-11-23 21:11:22,355 WARN L667 sPolynomialRelations]: Constructing 512(two to the power of 9 dual juncts. [2023-11-23 21:11:22,676 INFO L134 CoverageAnalysis]: Checked inductivity of 190 backedges. 0 proven. 190 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 21:11:22,676 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:11:28,419 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 149 treesize of output 129 [2023-11-23 21:11:28,451 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 10 select indices, 10 select index equivalence classes, 45 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 0 case distinctions, treesize of input 229 treesize of output 191 [2023-11-23 21:11:28,465 WARN L667 sPolynomialRelations]: Constructing 1024(two to the power of 10 dual juncts. [2023-11-23 21:11:28,663 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2023-11-23 21:11:28,694 INFO L134 CoverageAnalysis]: Checked inductivity of 190 backedges. 0 proven. 190 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 21:11:28,694 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [563225449] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:11:28,694 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [108898325] [2023-11-23 21:11:28,697 INFO L159 IcfgInterpreter]: Started Sifa with 7 locations of interest [2023-11-23 21:11:28,697 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:11:28,697 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-23 21:11:28,697 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-23 21:11:28,697 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-23 21:11:29,040 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-23 21:11:30,675 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1187#(and (<= (select |#length| |ULTIMATE.start_cstrchr_~s#1.base|) |ULTIMATE.start_cstrchr_~s#1.offset|) (= |ULTIMATE.start_main_#t~malloc8#1.offset| 0) (<= 1 |#StackHeapBarrier|) (<= 2 |ULTIMATE.start_cstrchr_#in~s#1.base|) (<= 2 |ULTIMATE.start_main_~nondetString~0#1.base|) (<= |ULTIMATE.start_cstrchr_~c#1| 2147483647) (<= 0 (+ 2147483648 |ULTIMATE.start_main_#t~nondet9#1|)) (= |ULTIMATE.start_main_~nondetString~0#1.offset| 0) (<= 0 (+ |ULTIMATE.start_cstrchr_#in~c#1| 2147483648)) (= |ULTIMATE.start_cstrchr_#in~s#1.offset| 0) (<= 2 |ULTIMATE.start_main_#t~malloc8#1.base|) (<= |ULTIMATE.start_main_#t~nondet9#1| 2147483647) (<= 1 |ULTIMATE.start_main_~length~0#1|) (<= 2 |ULTIMATE.start_cstrchr_~s#1.base|) (<= 0 (+ |ULTIMATE.start_cstrchr_~c#1| 2147483648)) (<= 0 |ULTIMATE.start_cstrchr_~s#1.offset|) (<= |ULTIMATE.start_cstrchr_#in~c#1| 2147483647))' at error location [2023-11-23 21:11:30,676 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-23 21:11:30,676 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-23 21:11:30,676 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 32, 32] total 79 [2023-11-23 21:11:30,676 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [242854669] [2023-11-23 21:11:30,676 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-23 21:11:30,679 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 81 states [2023-11-23 21:11:30,679 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:11:30,684 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 81 interpolants. [2023-11-23 21:11:30,686 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=817, Invalid=6665, Unknown=0, NotChecked=0, Total=7482 [2023-11-23 21:11:30,689 INFO L87 Difference]: Start difference. First operand 44 states and 44 transitions. Second operand has 81 states, 80 states have (on average 1.6) internal successors, (128), 80 states have internal predecessors, (128), 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)