./Ultimate.py --spec ../../sv-benchmarks/c/properties/valid-memsafety.prp --file ../../sv-benchmarks/c/termination-15/cstrchr_malloc.i --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for memory safety (deref-memtrack) Using default analysis Version 0e0057cc Calling Ultimate with: /usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/config/TaipanMemDerefMemtrack.xml -i ../../sv-benchmarks/c/termination-15/cstrchr_malloc.i -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/config/svcomp-DerefFreeMemtrack-64bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91 --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 c0210ef89ad3c98ea9fece5cf50381a477e80228bc6d486133df1f853ef1ed9e --- Real Ultimate output --- This is Ultimate 0.2.4-dev-0e0057c [2023-11-24 23:58:23,223 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-24 23:58:23,359 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/config/svcomp-DerefFreeMemtrack-64bit-Taipan_Default.epf [2023-11-24 23:58:23,370 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-24 23:58:23,371 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-24 23:58:23,417 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-24 23:58:23,418 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-24 23:58:23,419 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-24 23:58:23,420 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-24 23:58:23,425 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-24 23:58:23,425 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-24 23:58:23,426 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-24 23:58:23,426 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-24 23:58:23,428 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-24 23:58:23,428 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-24 23:58:23,429 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-24 23:58:23,429 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-24 23:58:23,430 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-24 23:58:23,431 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-24 23:58:23,431 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-24 23:58:23,431 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-24 23:58:23,432 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-24 23:58:23,433 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-11-24 23:58:23,433 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-11-24 23:58:23,434 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-24 23:58:23,435 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-24 23:58:23,435 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-24 23:58:23,435 INFO L153 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2023-11-24 23:58:23,436 INFO L153 SettingsManager]: * Bitprecise bitfields=true [2023-11-24 23:58:23,436 INFO L153 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2023-11-24 23:58:23,437 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-24 23:58:23,438 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2023-11-24 23:58:23,438 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2023-11-24 23:58:23,438 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-24 23:58:23,439 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-24 23:58:23,439 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-11-24 23:58:23,439 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-24 23:58:23,439 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-24 23:58:23,440 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-24 23:58:23,440 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-24 23:58:23,440 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-24 23:58:23,441 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-24 23:58:23,441 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-11-24 23:58:23,441 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-24 23:58:23,442 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-24 23:58:23,442 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_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/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_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91 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 -> c0210ef89ad3c98ea9fece5cf50381a477e80228bc6d486133df1f853ef1ed9e [2023-11-24 23:58:23,711 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-24 23:58:23,741 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-24 23:58:23,744 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-24 23:58:23,745 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-24 23:58:23,746 INFO L274 PluginConnector]: CDTParser initialized [2023-11-24 23:58:23,748 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/../../sv-benchmarks/c/termination-15/cstrchr_malloc.i [2023-11-24 23:58:26,885 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-24 23:58:27,182 INFO L384 CDTParser]: Found 1 translation units. [2023-11-24 23:58:27,183 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/sv-benchmarks/c/termination-15/cstrchr_malloc.i [2023-11-24 23:58:27,197 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/data/21000e7e4/c47bf446eccf41278d59d64e3cddd3ed/FLAGb4d752a27 [2023-11-24 23:58:27,212 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/data/21000e7e4/c47bf446eccf41278d59d64e3cddd3ed [2023-11-24 23:58:27,215 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-24 23:58:27,216 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-24 23:58:27,218 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-24 23:58:27,218 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-24 23:58:27,224 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-24 23:58:27,225 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.11 11:58:27" (1/1) ... [2023-11-24 23:58:27,226 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@534a8ec1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:58:27, skipping insertion in model container [2023-11-24 23:58:27,226 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.11 11:58:27" (1/1) ... [2023-11-24 23:58:27,266 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-24 23:58:27,679 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-24 23:58:27,691 INFO L202 MainTranslator]: Completed pre-run [2023-11-24 23:58:27,757 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-24 23:58:27,797 INFO L206 MainTranslator]: Completed translation [2023-11-24 23:58:27,797 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:58:27 WrapperNode [2023-11-24 23:58:27,798 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-24 23:58:27,799 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-24 23:58:27,799 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-24 23:58:27,799 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-24 23:58:27,808 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:58:27" (1/1) ... [2023-11-24 23:58:27,835 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:58:27" (1/1) ... [2023-11-24 23:58:27,867 INFO L138 Inliner]: procedures = 152, calls = 9, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 49 [2023-11-24 23:58:27,867 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-24 23:58:27,868 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-24 23:58:27,868 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-24 23:58:27,868 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-24 23:58:27,879 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:58:27" (1/1) ... [2023-11-24 23:58:27,880 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:58:27" (1/1) ... [2023-11-24 23:58:27,885 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:58:27" (1/1) ... [2023-11-24 23:58:27,885 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:58:27" (1/1) ... [2023-11-24 23:58:27,891 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:58:27" (1/1) ... [2023-11-24 23:58:27,894 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:58:27" (1/1) ... [2023-11-24 23:58:27,896 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:58:27" (1/1) ... [2023-11-24 23:58:27,897 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:58:27" (1/1) ... [2023-11-24 23:58:27,899 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-24 23:58:27,901 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-24 23:58:27,901 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-24 23:58:27,901 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-24 23:58:27,902 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:58:27" (1/1) ... [2023-11-24 23:58:27,909 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-24 23:58:27,927 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:58:27,958 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-24 23:58:27,977 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-24 23:58:28,017 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2023-11-24 23:58:28,017 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2023-11-24 23:58:28,018 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2023-11-24 23:58:28,018 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-11-24 23:58:28,018 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-24 23:58:28,018 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-24 23:58:28,128 INFO L241 CfgBuilder]: Building ICFG [2023-11-24 23:58:28,130 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-24 23:58:28,403 INFO L282 CfgBuilder]: Performing block encoding [2023-11-24 23:58:28,474 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-24 23:58:28,474 INFO L309 CfgBuilder]: Removed 1 assume(true) statements. [2023-11-24 23:58:28,476 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.11 11:58:28 BoogieIcfgContainer [2023-11-24 23:58:28,476 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-24 23:58:28,480 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-24 23:58:28,480 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-24 23:58:28,484 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-24 23:58:28,485 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 24.11 11:58:27" (1/3) ... [2023-11-24 23:58:28,486 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@b340ede and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.11 11:58:28, skipping insertion in model container [2023-11-24 23:58:28,486 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:58:27" (2/3) ... [2023-11-24 23:58:28,486 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@b340ede and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.11 11:58:28, skipping insertion in model container [2023-11-24 23:58:28,487 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.11 11:58:28" (3/3) ... [2023-11-24 23:58:28,488 INFO L112 eAbstractionObserver]: Analyzing ICFG cstrchr_malloc.i [2023-11-24 23:58:28,514 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-24 23:58:28,514 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 12 error locations. [2023-11-24 23:58:28,580 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-24 23:58:28,589 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;@553a4e0e, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-24 23:58:28,589 INFO L358 AbstractCegarLoop]: Starting to check reachability of 12 error locations. [2023-11-24 23:58:28,594 INFO L276 IsEmpty]: Start isEmpty. Operand has 24 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 23 states have internal predecessors, (26), 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-24 23:58:28,601 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 3 [2023-11-24 23:58:28,602 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:58:28,603 INFO L195 NwaCegarLoop]: trace histogram [1, 1] [2023-11-24 23:58:28,603 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 9 more)] === [2023-11-24 23:58:28,614 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:58:28,614 INFO L85 PathProgramCache]: Analyzing trace with hash 2987, now seen corresponding path program 1 times [2023-11-24 23:58:28,630 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:58:28,631 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1754134286] [2023-11-24 23:58:28,632 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:58:28,633 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:58:28,797 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:58:29,086 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-24 23:58:29,087 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:58:29,088 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1754134286] [2023-11-24 23:58:29,089 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1754134286] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:58:29,089 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-24 23:58:29,090 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-11-24 23:58:29,092 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1517693556] [2023-11-24 23:58:29,093 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:58:29,098 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-24 23:58:29,099 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:58:29,150 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-24 23:58:29,151 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-24 23:58:29,153 INFO L87 Difference]: Start difference. First operand has 24 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 23 states have internal predecessors, (26), 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-24 23:58:29,241 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:58:29,241 INFO L93 Difference]: Finished difference Result 22 states and 23 transitions. [2023-11-24 23:58:29,244 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-24 23:58:29,246 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-24 23:58:29,246 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:58:29,254 INFO L225 Difference]: With dead ends: 22 [2023-11-24 23:58:29,254 INFO L226 Difference]: Without dead ends: 21 [2023-11-24 23:58:29,256 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-24 23:58:29,260 INFO L413 NwaCegarLoop]: 10 mSDtfsCounter, 19 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 16 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 10 SdHoareTripleChecker+Invalid, 17 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 16 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-24 23:58:29,261 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 10 Invalid, 17 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 16 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-24 23:58:29,283 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2023-11-24 23:58:29,295 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2023-11-24 23:58:29,297 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 11 states have (on average 2.0) internal successors, (22), 20 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-24 23:58:29,298 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2023-11-24 23:58:29,299 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 2 [2023-11-24 23:58:29,300 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:58:29,300 INFO L495 AbstractCegarLoop]: Abstraction has 21 states and 22 transitions. [2023-11-24 23:58:29,300 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-24 23:58:29,301 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 22 transitions. [2023-11-24 23:58:29,301 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 3 [2023-11-24 23:58:29,301 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:58:29,302 INFO L195 NwaCegarLoop]: trace histogram [1, 1] [2023-11-24 23:58:29,302 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-24 23:58:29,302 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 9 more)] === [2023-11-24 23:58:29,303 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:58:29,303 INFO L85 PathProgramCache]: Analyzing trace with hash 2988, now seen corresponding path program 1 times [2023-11-24 23:58:29,304 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:58:29,304 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1610448824] [2023-11-24 23:58:29,304 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:58:29,305 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:58:29,340 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:58:29,562 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-24 23:58:29,569 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:58:29,569 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1610448824] [2023-11-24 23:58:29,573 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1610448824] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:58:29,574 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-24 23:58:29,574 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-11-24 23:58:29,574 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2023022216] [2023-11-24 23:58:29,575 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:58:29,576 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-24 23:58:29,577 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:58:29,578 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-24 23:58:29,579 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-24 23:58:29,579 INFO L87 Difference]: Start difference. First operand 21 states and 22 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-24 23:58:29,633 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:58:29,633 INFO L93 Difference]: Finished difference Result 20 states and 21 transitions. [2023-11-24 23:58:29,634 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-24 23:58:29,635 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-24 23:58:29,635 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:58:29,637 INFO L225 Difference]: With dead ends: 20 [2023-11-24 23:58:29,637 INFO L226 Difference]: Without dead ends: 20 [2023-11-24 23:58:29,642 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-24 23:58:29,645 INFO L413 NwaCegarLoop]: 8 mSDtfsCounter, 20 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 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.0s IncrementalHoareTripleChecker+Time [2023-11-24 23:58:29,645 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 8 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-24 23:58:29,649 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2023-11-24 23:58:29,652 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2023-11-24 23:58:29,653 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 11 states have (on average 1.9090909090909092) internal successors, (21), 19 states have internal predecessors, (21), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-24 23:58:29,655 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 21 transitions. [2023-11-24 23:58:29,655 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 21 transitions. Word has length 2 [2023-11-24 23:58:29,655 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:58:29,656 INFO L495 AbstractCegarLoop]: Abstraction has 20 states and 21 transitions. [2023-11-24 23:58:29,656 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-24 23:58:29,656 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 21 transitions. [2023-11-24 23:58:29,657 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2023-11-24 23:58:29,657 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:58:29,658 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1] [2023-11-24 23:58:29,658 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-24 23:58:29,658 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 9 more)] === [2023-11-24 23:58:29,659 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:58:29,659 INFO L85 PathProgramCache]: Analyzing trace with hash 94166, now seen corresponding path program 1 times [2023-11-24 23:58:29,659 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:58:29,659 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [949823337] [2023-11-24 23:58:29,660 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:58:29,660 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:58:29,687 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:58:29,768 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-24 23:58:29,769 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:58:29,769 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [949823337] [2023-11-24 23:58:29,769 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [949823337] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:58:29,770 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-24 23:58:29,770 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-24 23:58:29,770 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [884025252] [2023-11-24 23:58:29,770 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:58:29,771 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-24 23:58:29,771 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:58:29,771 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-24 23:58:29,772 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-24 23:58:29,772 INFO L87 Difference]: Start difference. First operand 20 states and 21 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-24 23:58:29,815 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:58:29,816 INFO L93 Difference]: Finished difference Result 17 states and 18 transitions. [2023-11-24 23:58:29,816 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-24 23:58:29,817 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-24 23:58:29,817 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:58:29,819 INFO L225 Difference]: With dead ends: 17 [2023-11-24 23:58:29,819 INFO L226 Difference]: Without dead ends: 17 [2023-11-24 23:58:29,820 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-24 23:58:29,829 INFO L413 NwaCegarLoop]: 9 mSDtfsCounter, 8 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 13 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-24 23:58:29,829 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 13 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-24 23:58:29,830 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states. [2023-11-24 23:58:29,835 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2023-11-24 23:58:29,835 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 11 states have (on average 1.6363636363636365) internal successors, (18), 16 states have internal predecessors, (18), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-24 23:58:29,836 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2023-11-24 23:58:29,836 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 3 [2023-11-24 23:58:29,839 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:58:29,839 INFO L495 AbstractCegarLoop]: Abstraction has 17 states and 18 transitions. [2023-11-24 23:58:29,839 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-24 23:58:29,844 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 18 transitions. [2023-11-24 23:58:29,844 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2023-11-24 23:58:29,845 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:58:29,845 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1] [2023-11-24 23:58:29,845 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2023-11-24 23:58:29,845 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 9 more)] === [2023-11-24 23:58:29,846 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:58:29,846 INFO L85 PathProgramCache]: Analyzing trace with hash 94167, now seen corresponding path program 1 times [2023-11-24 23:58:29,847 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:58:29,847 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [248322021] [2023-11-24 23:58:29,847 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:58:29,847 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:58:29,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:58:30,027 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-24 23:58:30,028 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:58:30,028 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [248322021] [2023-11-24 23:58:30,028 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [248322021] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:58:30,028 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-24 23:58:30,029 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-24 23:58:30,029 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [643839560] [2023-11-24 23:58:30,029 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:58:30,030 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-24 23:58:30,030 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:58:30,030 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-24 23:58:30,031 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-24 23:58:30,031 INFO L87 Difference]: Start difference. First operand 17 states and 18 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-24 23:58:30,083 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:58:30,083 INFO L93 Difference]: Finished difference Result 15 states and 16 transitions. [2023-11-24 23:58:30,084 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-24 23:58:30,084 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-24 23:58:30,084 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:58:30,084 INFO L225 Difference]: With dead ends: 15 [2023-11-24 23:58:30,085 INFO L226 Difference]: Without dead ends: 15 [2023-11-24 23:58:30,085 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2023-11-24 23:58:30,093 INFO L413 NwaCegarLoop]: 8 mSDtfsCounter, 20 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 12 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-24 23:58:30,094 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 12 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-24 23:58:30,097 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2023-11-24 23:58:30,100 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2023-11-24 23:58:30,101 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 15 states, 12 states have (on average 1.3333333333333333) 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-24 23:58:30,101 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2023-11-24 23:58:30,102 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 3 [2023-11-24 23:58:30,102 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:58:30,102 INFO L495 AbstractCegarLoop]: Abstraction has 15 states and 16 transitions. [2023-11-24 23:58:30,102 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-24 23:58:30,103 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 16 transitions. [2023-11-24 23:58:30,103 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2023-11-24 23:58:30,103 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:58:30,103 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2023-11-24 23:58:30,103 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2023-11-24 23:58:30,104 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 9 more)] === [2023-11-24 23:58:30,104 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:58:30,105 INFO L85 PathProgramCache]: Analyzing trace with hash -1488535757, now seen corresponding path program 1 times [2023-11-24 23:58:30,105 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:58:30,105 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [539184659] [2023-11-24 23:58:30,105 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:58:30,106 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:58:30,126 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:58:30,160 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-24 23:58:30,160 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:58:30,160 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [539184659] [2023-11-24 23:58:30,160 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [539184659] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:58:30,160 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-24 23:58:30,161 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-24 23:58:30,161 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [419484736] [2023-11-24 23:58:30,163 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:58:30,163 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-24 23:58:30,163 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:58:30,164 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-24 23:58:30,165 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-24 23:58:30,165 INFO L87 Difference]: Start difference. First operand 15 states and 16 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-24 23:58:30,191 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:58:30,192 INFO L93 Difference]: Finished difference Result 16 states and 17 transitions. [2023-11-24 23:58:30,192 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-24 23:58:30,192 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-24 23:58:30,193 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:58:30,193 INFO L225 Difference]: With dead ends: 16 [2023-11-24 23:58:30,193 INFO L226 Difference]: Without dead ends: 16 [2023-11-24 23:58:30,194 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-24 23:58:30,195 INFO L413 NwaCegarLoop]: 9 mSDtfsCounter, 0 mSDsluCounter, 6 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 15 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-24 23:58:30,195 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 15 Invalid, 14 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-24 23:58:30,196 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16 states. [2023-11-24 23:58:30,198 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16 to 16. [2023-11-24 23:58:30,198 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 16 states, 13 states have (on average 1.3076923076923077) 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-24 23:58:30,199 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 17 transitions. [2023-11-24 23:58:30,199 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 17 transitions. Word has length 6 [2023-11-24 23:58:30,199 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:58:30,200 INFO L495 AbstractCegarLoop]: Abstraction has 16 states and 17 transitions. [2023-11-24 23:58:30,200 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-24 23:58:30,200 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 17 transitions. [2023-11-24 23:58:30,201 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-11-24 23:58:30,201 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:58:30,201 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-11-24 23:58:30,201 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2023-11-24 23:58:30,202 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 9 more)] === [2023-11-24 23:58:30,202 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:58:30,202 INFO L85 PathProgramCache]: Analyzing trace with hash 1099873740, now seen corresponding path program 1 times [2023-11-24 23:58:30,203 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:58:30,203 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [868568303] [2023-11-24 23:58:30,203 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:58:30,203 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:58:30,224 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:58:30,604 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-24 23:58:30,604 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:58:30,604 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [868568303] [2023-11-24 23:58:30,605 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [868568303] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-24 23:58:30,605 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1496036201] [2023-11-24 23:58:30,605 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:58:30,605 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:58:30,606 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:58:30,609 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:58:30,645 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-24 23:58:30,693 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:58:30,696 INFO L262 TraceCheckSpWp]: Trace formula consists of 64 conjuncts, 26 conjunts are in the unsatisfiable core [2023-11-24 23:58:30,702 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:58:30,799 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-24 23:58:30,914 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-24 23:58:30,914 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 31 treesize of output 25 [2023-11-24 23:58:31,111 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-24 23:58:31,112 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-24 23:58:31,310 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-24 23:58:31,319 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-24 23:58:31,331 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 14 treesize of output 12 [2023-11-24 23:58:31,359 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-24 23:58:31,359 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1496036201] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-24 23:58:31,360 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [36589613] [2023-11-24 23:58:31,379 INFO L159 IcfgInterpreter]: Started Sifa with 7 locations of interest [2023-11-24 23:58:31,379 INFO L166 IcfgInterpreter]: Building call graph [2023-11-24 23:58:31,386 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-24 23:58:31,393 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-24 23:58:31,393 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-24 23:58:32,149 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-24 23:58:32,636 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '277#(and (<= (select |#length| |ULTIMATE.start_cstrchr_~s#1.base|) |ULTIMATE.start_cstrchr_~s#1.offset|) (<= 0 (+ |ULTIMATE.start_main_#t~nondet212#1| 2147483648)) (<= 1 |#StackHeapBarrier|) (<= |ULTIMATE.start_cstrchr_~c#1| 2147483647) (= |ULTIMATE.start_main_~nondetString~0#1.offset| 0) (<= |ULTIMATE.start_main_#t~nondet212#1| 2147483647) (<= 0 (+ |ULTIMATE.start_cstrchr_#in~c#1| 2147483648)) (= |ULTIMATE.start_cstrchr_#in~s#1.offset| 0) (<= 1 |ULTIMATE.start_main_~length~0#1|) (<= 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-24 23:58:32,637 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-24 23:58:32,637 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-24 23:58:32,637 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 15 [2023-11-24 23:58:32,637 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1806572314] [2023-11-24 23:58:32,638 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-24 23:58:32,639 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-11-24 23:58:32,640 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:58:32,641 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-11-24 23:58:32,643 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=377, Unknown=0, NotChecked=0, Total=462 [2023-11-24 23:58:32,643 INFO L87 Difference]: Start difference. First operand 16 states and 17 transitions. Second operand has 17 states, 16 states have (on average 1.3125) internal successors, (21), 16 states have internal predecessors, (21), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-24 23:58:33,145 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:58:33,145 INFO L93 Difference]: Finished difference Result 28 states and 33 transitions. [2023-11-24 23:58:33,145 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-24 23:58:33,145 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 16 states have (on average 1.3125) internal successors, (21), 16 states have internal predecessors, (21), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2023-11-24 23:58:33,146 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:58:33,149 INFO L225 Difference]: With dead ends: 28 [2023-11-24 23:58:33,149 INFO L226 Difference]: Without dead ends: 28 [2023-11-24 23:58:33,150 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 188 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=179, Invalid=691, Unknown=0, NotChecked=0, Total=870 [2023-11-24 23:58:33,151 INFO L413 NwaCegarLoop]: 4 mSDtfsCounter, 114 mSDsluCounter, 14 mSDsCounter, 0 mSdLazyCounter, 118 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 114 SdHoareTripleChecker+Valid, 18 SdHoareTripleChecker+Invalid, 123 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 118 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-24 23:58:33,151 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [114 Valid, 18 Invalid, 123 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 118 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-24 23:58:33,153 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2023-11-24 23:58:33,156 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 20. [2023-11-24 23:58:33,156 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 19 states have internal predecessors, (23), 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-24 23:58:33,157 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 23 transitions. [2023-11-24 23:58:33,158 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 23 transitions. Word has length 7 [2023-11-24 23:58:33,158 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:58:33,158 INFO L495 AbstractCegarLoop]: Abstraction has 20 states and 23 transitions. [2023-11-24 23:58:33,159 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 16 states have (on average 1.3125) internal successors, (21), 16 states have internal predecessors, (21), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-24 23:58:33,159 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 23 transitions. [2023-11-24 23:58:33,160 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2023-11-24 23:58:33,160 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:58:33,160 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2023-11-24 23:58:33,179 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-24 23:58:33,379 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2023-11-24 23:58:33,379 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr9ASSERT_VIOLATIONMEMORY_FREE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 9 more)] === [2023-11-24 23:58:33,380 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:58:33,380 INFO L85 PathProgramCache]: Analyzing trace with hash -258770624, now seen corresponding path program 1 times [2023-11-24 23:58:33,380 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:58:33,380 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1890674262] [2023-11-24 23:58:33,380 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:58:33,380 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:58:33,399 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:58:33,424 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-24 23:58:33,425 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:58:33,425 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1890674262] [2023-11-24 23:58:33,425 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1890674262] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:58:33,426 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-24 23:58:33,426 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2023-11-24 23:58:33,426 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [314414345] [2023-11-24 23:58:33,426 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:58:33,427 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-24 23:58:33,427 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:58:33,428 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-24 23:58:33,428 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-24 23:58:33,428 INFO L87 Difference]: Start difference. First operand 20 states and 23 transitions. Second operand has 3 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 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-24 23:58:33,446 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:58:33,446 INFO L93 Difference]: Finished difference Result 19 states and 22 transitions. [2023-11-24 23:58:33,447 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-24 23:58:33,447 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2023-11-24 23:58:33,447 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:58:33,449 INFO L225 Difference]: With dead ends: 19 [2023-11-24 23:58:33,450 INFO L226 Difference]: Without dead ends: 19 [2023-11-24 23:58:33,450 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-24 23:58:33,451 INFO L413 NwaCegarLoop]: 7 mSDtfsCounter, 7 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 7 SdHoareTripleChecker+Invalid, 7 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 7 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-24 23:58:33,452 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 7 Invalid, 7 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-24 23:58:33,453 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2023-11-24 23:58:33,463 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 19. [2023-11-24 23:58:33,463 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 19 states, 17 states have (on average 1.2941176470588236) 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-24 23:58:33,468 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 22 transitions. [2023-11-24 23:58:33,469 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 22 transitions. Word has length 8 [2023-11-24 23:58:33,469 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:58:33,469 INFO L495 AbstractCegarLoop]: Abstraction has 19 states and 22 transitions. [2023-11-24 23:58:33,470 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 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-24 23:58:33,470 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 22 transitions. [2023-11-24 23:58:33,470 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2023-11-24 23:58:33,470 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:58:33,471 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-24 23:58:33,471 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2023-11-24 23:58:33,472 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr11ASSERT_VIOLATIONMEMORY_LEAK === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 9 more)] === [2023-11-24 23:58:33,472 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:58:33,472 INFO L85 PathProgramCache]: Analyzing trace with hash 429536099, now seen corresponding path program 1 times [2023-11-24 23:58:33,473 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:58:33,473 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [668440337] [2023-11-24 23:58:33,473 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:58:33,473 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:58:33,492 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:58:33,612 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-24 23:58:33,612 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:58:33,613 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [668440337] [2023-11-24 23:58:33,613 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [668440337] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:58:33,613 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-24 23:58:33,613 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-24 23:58:33,613 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [337460628] [2023-11-24 23:58:33,614 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:58:33,614 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-24 23:58:33,615 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:58:33,616 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-24 23:58:33,617 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-24 23:58:33,617 INFO L87 Difference]: Start difference. First operand 19 states and 22 transitions. Second operand has 4 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-24 23:58:33,651 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:58:33,651 INFO L93 Difference]: Finished difference Result 18 states and 21 transitions. [2023-11-24 23:58:33,652 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-24 23:58:33,652 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 10 [2023-11-24 23:58:33,653 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:58:33,653 INFO L225 Difference]: With dead ends: 18 [2023-11-24 23:58:33,653 INFO L226 Difference]: Without dead ends: 12 [2023-11-24 23:58:33,653 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2023-11-24 23:58:33,655 INFO L413 NwaCegarLoop]: 6 mSDtfsCounter, 4 mSDsluCounter, 6 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 12 SdHoareTripleChecker+Invalid, 14 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-24 23:58:33,656 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 12 Invalid, 14 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-24 23:58:33,657 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 12 states. [2023-11-24 23:58:33,658 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 12 to 12. [2023-11-24 23:58:33,658 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-24 23:58:33,659 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2023-11-24 23:58:33,659 INFO L78 Accepts]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2023-11-24 23:58:33,661 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:58:33,662 INFO L495 AbstractCegarLoop]: Abstraction has 12 states and 12 transitions. [2023-11-24 23:58:33,662 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-24 23:58:33,662 INFO L276 IsEmpty]: Start isEmpty. Operand 12 states and 12 transitions. [2023-11-24 23:58:33,663 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2023-11-24 23:58:33,663 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:58:33,663 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1] [2023-11-24 23:58:33,663 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2023-11-24 23:58:33,664 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 9 more)] === [2023-11-24 23:58:33,665 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:58:33,666 INFO L85 PathProgramCache]: Analyzing trace with hash 1059719489, now seen corresponding path program 2 times [2023-11-24 23:58:33,666 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:58:33,666 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [998647528] [2023-11-24 23:58:33,666 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:58:33,667 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:58:33,716 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:58:34,440 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-24 23:58:34,440 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:58:34,440 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [998647528] [2023-11-24 23:58:34,440 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [998647528] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-24 23:58:34,440 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1530800670] [2023-11-24 23:58:34,441 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-24 23:58:34,441 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:58:34,441 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:58:34,442 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:58:34,461 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-24 23:58:34,523 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-11-24 23:58:34,523 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-24 23:58:34,525 INFO L262 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 36 conjunts are in the unsatisfiable core [2023-11-24 23:58:34,530 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:58:34,542 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2023-11-24 23:58:34,572 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-24 23:58:35,090 INFO L349 Elim1Store]: treesize reduction 8, result has 70.4 percent of original size [2023-11-24 23:58:35,091 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 26 treesize of output 30 [2023-11-24 23:58:35,174 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-24 23:58:35,174 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-24 23:58:35,713 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-24 23:58:35,730 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-24 23:58:35,730 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 35 treesize of output 39 [2023-11-24 23:58:35,798 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-24 23:58:35,798 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1530800670] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-24 23:58:35,798 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1089555449] [2023-11-24 23:58:35,801 INFO L159 IcfgInterpreter]: Started Sifa with 7 locations of interest [2023-11-24 23:58:35,801 INFO L166 IcfgInterpreter]: Building call graph [2023-11-24 23:58:35,801 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-24 23:58:35,802 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-24 23:58:35,802 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-24 23:58:36,270 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-24 23:58:36,812 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '510#(and (<= (select |#length| |ULTIMATE.start_cstrchr_~s#1.base|) |ULTIMATE.start_cstrchr_~s#1.offset|) (<= 0 (+ |ULTIMATE.start_main_#t~nondet212#1| 2147483648)) (<= 1 |#StackHeapBarrier|) (<= |ULTIMATE.start_cstrchr_~c#1| 2147483647) (= |ULTIMATE.start_main_~nondetString~0#1.offset| 0) (<= |ULTIMATE.start_main_#t~nondet212#1| 2147483647) (<= 0 (+ |ULTIMATE.start_cstrchr_#in~c#1| 2147483648)) (= |ULTIMATE.start_cstrchr_#in~s#1.offset| 0) (<= 1 |ULTIMATE.start_main_~length~0#1|) (<= 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-24 23:58:36,812 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-24 23:58:36,813 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-24 23:58:36,813 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 9, 9] total 25 [2023-11-24 23:58:36,813 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1693430829] [2023-11-24 23:58:36,813 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-24 23:58:36,814 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2023-11-24 23:58:36,814 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:58:36,815 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2023-11-24 23:58:36,815 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=141, Invalid=851, Unknown=0, NotChecked=0, Total=992 [2023-11-24 23:58:36,816 INFO L87 Difference]: Start difference. First operand 12 states and 12 transitions. Second operand has 27 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 26 states have internal predecessors, (33), 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-24 23:58:37,952 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:58:37,952 INFO L93 Difference]: Finished difference Result 27 states and 27 transitions. [2023-11-24 23:58:37,952 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2023-11-24 23:58:37,952 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 26 states have internal predecessors, (33), 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-24 23:58:37,953 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:58:37,953 INFO L225 Difference]: With dead ends: 27 [2023-11-24 23:58:37,953 INFO L226 Difference]: Without dead ends: 27 [2023-11-24 23:58:37,954 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 495 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=408, Invalid=1848, Unknown=0, NotChecked=0, Total=2256 [2023-11-24 23:58:37,955 INFO L413 NwaCegarLoop]: 0 mSDtfsCounter, 55 mSDsluCounter, 2 mSDsCounter, 0 mSdLazyCounter, 131 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 2 SdHoareTripleChecker+Invalid, 138 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 131 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-24 23:58:37,955 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [55 Valid, 2 Invalid, 138 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 131 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-24 23:58:37,956 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2023-11-24 23:58:37,957 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 24. [2023-11-24 23:58:37,958 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-24 23:58:37,958 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 24 transitions. [2023-11-24 23:58:37,958 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 24 transitions. Word has length 11 [2023-11-24 23:58:37,958 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:58:37,958 INFO L495 AbstractCegarLoop]: Abstraction has 24 states and 24 transitions. [2023-11-24 23:58:37,959 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 26 states have internal predecessors, (33), 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-24 23:58:37,959 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 24 transitions. [2023-11-24 23:58:37,959 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2023-11-24 23:58:37,959 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:58:37,960 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 1, 1, 1] [2023-11-24 23:58:37,969 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2023-11-24 23:58:38,160 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:58:38,160 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 9 more)] === [2023-11-24 23:58:38,161 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:58:38,161 INFO L85 PathProgramCache]: Analyzing trace with hash -219915104, now seen corresponding path program 3 times [2023-11-24 23:58:38,161 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:58:38,161 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [166913826] [2023-11-24 23:58:38,161 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:58:38,161 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:58:38,208 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:58:39,056 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-24 23:58:39,056 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:58:39,056 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [166913826] [2023-11-24 23:58:39,056 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [166913826] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-24 23:58:39,056 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1559331781] [2023-11-24 23:58:39,057 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-24 23:58:39,057 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:58:39,057 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:58:39,062 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:58:39,085 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-24 23:58:39,147 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-24 23:58:39,147 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-24 23:58:39,149 INFO L262 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 58 conjunts are in the unsatisfiable core [2023-11-24 23:58:39,153 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:58:39,186 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-24 23:58:40,438 INFO L349 Elim1Store]: treesize reduction 16, result has 61.0 percent of original size [2023-11-24 23:58:40,439 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-24 23:58:40,614 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-24 23:58:40,614 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-24 23:58:42,038 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-24 23:58:42,045 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-24 23:58:42,063 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-24 23:58:42,125 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-24 23:58:42,125 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1559331781] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-24 23:58:42,126 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1895645080] [2023-11-24 23:58:42,132 INFO L159 IcfgInterpreter]: Started Sifa with 7 locations of interest [2023-11-24 23:58:42,133 INFO L166 IcfgInterpreter]: Building call graph [2023-11-24 23:58:42,133 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-24 23:58:42,133 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-24 23:58:42,133 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-24 23:58:42,517 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-24 23:58:43,202 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '775#(and (<= (select |#length| |ULTIMATE.start_cstrchr_~s#1.base|) |ULTIMATE.start_cstrchr_~s#1.offset|) (<= 0 (+ |ULTIMATE.start_main_#t~nondet212#1| 2147483648)) (<= 1 |#StackHeapBarrier|) (<= |ULTIMATE.start_cstrchr_~c#1| 2147483647) (= |ULTIMATE.start_main_~nondetString~0#1.offset| 0) (<= |ULTIMATE.start_main_#t~nondet212#1| 2147483647) (<= 0 (+ |ULTIMATE.start_cstrchr_#in~c#1| 2147483648)) (= |ULTIMATE.start_cstrchr_#in~s#1.offset| 0) (<= 1 |ULTIMATE.start_main_~length~0#1|) (<= 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-24 23:58:43,203 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-24 23:58:43,203 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-24 23:58:43,203 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 17, 17] total 43 [2023-11-24 23:58:43,204 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [428003973] [2023-11-24 23:58:43,204 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-24 23:58:43,205 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 45 states [2023-11-24 23:58:43,205 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:58:43,206 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2023-11-24 23:58:43,208 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=293, Invalid=2157, Unknown=0, NotChecked=0, Total=2450 [2023-11-24 23:58:43,208 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-24 23:58:47,182 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:58:47,183 INFO L93 Difference]: Finished difference Result 47 states and 47 transitions. [2023-11-24 23:58:47,183 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2023-11-24 23:58:47,183 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-24 23:58:47,184 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:58:47,184 INFO L225 Difference]: With dead ends: 47 [2023-11-24 23:58:47,184 INFO L226 Difference]: Without dead ends: 47 [2023-11-24 23:58:47,188 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 81 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1626 ImplicationChecksByTransitivity, 6.1s TimeCoverageRelationStatistics Valid=976, Invalid=5830, Unknown=0, NotChecked=0, Total=6806 [2023-11-24 23:58:47,189 INFO L413 NwaCegarLoop]: 0 mSDtfsCounter, 133 mSDsluCounter, 2 mSDsCounter, 0 mSdLazyCounter, 519 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 133 SdHoareTripleChecker+Valid, 2 SdHoareTripleChecker+Invalid, 524 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 519 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2023-11-24 23:58:47,189 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [133 Valid, 2 Invalid, 524 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 519 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2023-11-24 23:58:47,190 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2023-11-24 23:58:47,193 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 44. [2023-11-24 23:58:47,193 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-24 23:58:47,194 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 44 transitions. [2023-11-24 23:58:47,194 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 44 transitions. Word has length 23 [2023-11-24 23:58:47,194 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:58:47,194 INFO L495 AbstractCegarLoop]: Abstraction has 44 states and 44 transitions. [2023-11-24 23:58:47,195 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-24 23:58:47,195 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 44 transitions. [2023-11-24 23:58:47,196 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2023-11-24 23:58:47,196 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:58:47,197 INFO L195 NwaCegarLoop]: trace histogram [10, 10, 10, 10, 1, 1, 1] [2023-11-24 23:58:47,207 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2023-11-24 23:58:47,402 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:58:47,403 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 9 more)] === [2023-11-24 23:58:47,403 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:58:47,403 INFO L85 PathProgramCache]: Analyzing trace with hash -2026763543, now seen corresponding path program 4 times [2023-11-24 23:58:47,403 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:58:47,403 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1951708178] [2023-11-24 23:58:47,403 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:58:47,404 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:58:47,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:58:49,155 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-24 23:58:49,156 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:58:49,156 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1951708178] [2023-11-24 23:58:49,156 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1951708178] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-24 23:58:49,156 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [334199782] [2023-11-24 23:58:49,156 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-11-24 23:58:49,156 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:58:49,157 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:58:49,157 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:58:49,161 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2b3e283b-412b-4052-9a4d-8bb5531ed9b2/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-24 23:58:49,260 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:58:49,263 INFO L262 TraceCheckSpWp]: Trace formula consists of 244 conjuncts, 95 conjunts are in the unsatisfiable core [2023-11-24 23:58:49,268 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:58:49,307 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-24 23:58:55,060 INFO L349 Elim1Store]: treesize reduction 36, result has 67.6 percent of original size [2023-11-24 23:58:55,060 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-24 23:58:55,102 WARN L667 sPolynomialRelations]: Constructing 512(two to the power of 9 dual juncts. [2023-11-24 23:58:55,216 WARN L667 sPolynomialRelations]: Constructing 1024(two to the power of 10 dual juncts. [2023-11-24 23:58:55,674 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-24 23:58:55,675 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-24 23:59:01,402 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-24 23:59:01,428 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-24 23:59:01,444 WARN L667 sPolynomialRelations]: Constructing 1024(two to the power of 10 dual juncts. [2023-11-24 23:59:01,584 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-24 23:59:01,606 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-24 23:59:01,607 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [334199782] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-24 23:59:01,607 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1198520040] [2023-11-24 23:59:01,609 INFO L159 IcfgInterpreter]: Started Sifa with 7 locations of interest [2023-11-24 23:59:01,609 INFO L166 IcfgInterpreter]: Building call graph [2023-11-24 23:59:01,610 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-24 23:59:01,610 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-24 23:59:01,610 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-24 23:59:01,933 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-24 23:59:02,884 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1268#(and (<= (select |#length| |ULTIMATE.start_cstrchr_~s#1.base|) |ULTIMATE.start_cstrchr_~s#1.offset|) (<= 0 (+ |ULTIMATE.start_main_#t~nondet212#1| 2147483648)) (<= 1 |#StackHeapBarrier|) (<= |ULTIMATE.start_cstrchr_~c#1| 2147483647) (= |ULTIMATE.start_main_~nondetString~0#1.offset| 0) (<= |ULTIMATE.start_main_#t~nondet212#1| 2147483647) (<= 0 (+ |ULTIMATE.start_cstrchr_#in~c#1| 2147483648)) (= |ULTIMATE.start_cstrchr_#in~s#1.offset| 0) (<= 1 |ULTIMATE.start_main_~length~0#1|) (<= 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-24 23:59:02,884 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-24 23:59:02,884 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-24 23:59:02,884 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 32, 32] total 77 [2023-11-24 23:59:02,884 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1751123823] [2023-11-24 23:59:02,885 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-24 23:59:02,885 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 79 states [2023-11-24 23:59:02,885 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:59:02,887 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 79 interpolants. [2023-11-24 23:59:02,891 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=804, Invalid=6168, Unknown=0, NotChecked=0, Total=6972 [2023-11-24 23:59:02,891 INFO L87 Difference]: Start difference. First operand 44 states and 44 transitions. Second operand has 79 states, 78 states have (on average 1.641025641025641) internal successors, (128), 78 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)