./Ultimate.py --spec ../../sv-benchmarks/c/properties/valid-memsafety.prp --file ../../sv-benchmarks/c/verifythis/elimination_max_rec.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for memory safety (deref-memtrack) Using default analysis Version 826ab2ba Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/config/TaipanMemDerefMemtrack.xml -i ../../sv-benchmarks/c/verifythis/elimination_max_rec.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-DerefFreeMemtrack-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G valid-free) ) CHECK( init(main()), LTL(G valid-deref) ) CHECK( init(main()), LTL(G valid-memtrack) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 1d89bfe4b4c4586e423a8e3ebdbb120ac074219803de53807cd9f075553c6e3a --- Real Ultimate output --- This is Ultimate 0.3.0-dev-826ab2b [2024-11-14 04:59:37,303 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-14 04:59:37,385 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-DerefFreeMemtrack-32bit-Taipan_Default.epf [2024-11-14 04:59:37,390 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-14 04:59:37,391 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-14 04:59:37,414 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-14 04:59:37,415 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-14 04:59:37,415 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-14 04:59:37,416 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-14 04:59:37,416 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-14 04:59:37,416 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-14 04:59:37,416 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-14 04:59:37,416 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-14 04:59:37,416 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-14 04:59:37,416 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-14 04:59:37,416 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-14 04:59:37,416 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-14 04:59:37,417 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-14 04:59:37,417 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-14 04:59:37,417 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-14 04:59:37,417 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-14 04:59:37,417 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-14 04:59:37,417 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-14 04:59:37,418 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-14 04:59:37,418 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-14 04:59:37,418 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-14 04:59:37,418 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-14 04:59:37,418 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-14 04:59:37,418 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-14 04:59:37,418 INFO L153 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2024-11-14 04:59:37,418 INFO L153 SettingsManager]: * Bitprecise bitfields=true [2024-11-14 04:59:37,419 INFO L153 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2024-11-14 04:59:37,419 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-14 04:59:37,419 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2024-11-14 04:59:37,419 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-14 04:59:37,419 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-14 04:59:37,419 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-14 04:59:37,419 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-14 04:59:37,419 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-14 04:59:37,419 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-14 04:59:37,420 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-14 04:59:37,420 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 04:59:37,420 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-14 04:59:37,420 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-14 04:59:37,420 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-14 04:59:37,420 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-14 04:59:37,420 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-14 04:59:37,420 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-14 04:59:37,420 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-14 04:59:37,421 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G valid-free) ) CHECK( init(main()), LTL(G valid-deref) ) CHECK( init(main()), LTL(G valid-memtrack) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Taipan Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 1d89bfe4b4c4586e423a8e3ebdbb120ac074219803de53807cd9f075553c6e3a [2024-11-14 04:59:37,776 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-14 04:59:37,788 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-14 04:59:37,790 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-14 04:59:37,791 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-14 04:59:37,792 INFO L274 PluginConnector]: CDTParser initialized [2024-11-14 04:59:37,794 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/../../sv-benchmarks/c/verifythis/elimination_max_rec.c Unable to find full path for "g++" [2024-11-14 04:59:39,738 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-14 04:59:40,043 INFO L384 CDTParser]: Found 1 translation units. [2024-11-14 04:59:40,044 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/sv-benchmarks/c/verifythis/elimination_max_rec.c [2024-11-14 04:59:40,054 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/data/ea7916e86/e18912c6d6b849f9970c0f5b4b1fd574/FLAG65e15f971 [2024-11-14 04:59:40,080 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/data/ea7916e86/e18912c6d6b849f9970c0f5b4b1fd574 [2024-11-14 04:59:40,083 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-14 04:59:40,085 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-14 04:59:40,089 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-14 04:59:40,089 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-14 04:59:40,097 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-14 04:59:40,098 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 04:59:40" (1/1) ... [2024-11-14 04:59:40,099 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@251fa999 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:59:40, skipping insertion in model container [2024-11-14 04:59:40,099 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 04:59:40" (1/1) ... [2024-11-14 04:59:40,116 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-14 04:59:40,302 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 04:59:40,318 INFO L200 MainTranslator]: Completed pre-run [2024-11-14 04:59:40,339 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 04:59:40,359 INFO L204 MainTranslator]: Completed translation [2024-11-14 04:59:40,359 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:59:40 WrapperNode [2024-11-14 04:59:40,360 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-14 04:59:40,361 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-14 04:59:40,361 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-14 04:59:40,362 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-14 04:59:40,370 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:59:40" (1/1) ... [2024-11-14 04:59:40,378 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:59:40" (1/1) ... [2024-11-14 04:59:40,398 INFO L138 Inliner]: procedures = 19, calls = 21, calls flagged for inlining = 4, calls inlined = 4, statements flattened = 34 [2024-11-14 04:59:40,399 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-14 04:59:40,399 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-14 04:59:40,399 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-14 04:59:40,399 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-14 04:59:40,407 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:59:40" (1/1) ... [2024-11-14 04:59:40,407 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:59:40" (1/1) ... [2024-11-14 04:59:40,409 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:59:40" (1/1) ... [2024-11-14 04:59:40,409 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:59:40" (1/1) ... [2024-11-14 04:59:40,418 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:59:40" (1/1) ... [2024-11-14 04:59:40,425 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:59:40" (1/1) ... [2024-11-14 04:59:40,426 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:59:40" (1/1) ... [2024-11-14 04:59:40,427 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:59:40" (1/1) ... [2024-11-14 04:59:40,428 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-14 04:59:40,433 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-14 04:59:40,433 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-14 04:59:40,433 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-14 04:59:40,434 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:59:40" (1/1) ... [2024-11-14 04:59:40,448 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 04:59:40,462 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:59:40,476 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-14 04:59:40,480 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-14 04:59:40,504 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-14 04:59:40,504 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-14 04:59:40,504 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-14 04:59:40,504 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-14 04:59:40,504 INFO L130 BoogieDeclarations]: Found specification of procedure check [2024-11-14 04:59:40,504 INFO L138 BoogieDeclarations]: Found implementation of procedure check [2024-11-14 04:59:40,505 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2024-11-14 04:59:40,505 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-14 04:59:40,505 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-14 04:59:40,505 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2024-11-14 04:59:40,506 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-14 04:59:40,506 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-14 04:59:40,506 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-14 04:59:40,609 INFO L238 CfgBuilder]: Building ICFG [2024-11-14 04:59:40,611 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-14 04:59:40,949 INFO L? ?]: Removed 42 outVars from TransFormulas that were not future-live. [2024-11-14 04:59:40,949 INFO L287 CfgBuilder]: Performing block encoding [2024-11-14 04:59:41,044 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-14 04:59:41,044 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-14 04:59:41,045 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 04:59:41 BoogieIcfgContainer [2024-11-14 04:59:41,045 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-14 04:59:41,049 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-14 04:59:41,050 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-14 04:59:41,057 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-14 04:59:41,058 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.11 04:59:40" (1/3) ... [2024-11-14 04:59:41,058 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@449996a5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 04:59:41, skipping insertion in model container [2024-11-14 04:59:41,058 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:59:40" (2/3) ... [2024-11-14 04:59:41,059 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@449996a5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 04:59:41, skipping insertion in model container [2024-11-14 04:59:41,059 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 04:59:41" (3/3) ... [2024-11-14 04:59:41,060 INFO L112 eAbstractionObserver]: Analyzing ICFG elimination_max_rec.c [2024-11-14 04:59:41,082 INFO L217 ceAbstractionStarter]: Automizer settings: Hoare:None NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-14 04:59:41,084 INFO L154 ceAbstractionStarter]: Applying trace abstraction to ICFG elimination_max_rec.c that has 4 procedures, 45 locations, 1 initial locations, 0 loop locations, and 13 error locations. [2024-11-14 04:59:41,137 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-14 04:59:41,154 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=None, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@5b32f775, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-14 04:59:41,154 INFO L334 AbstractCegarLoop]: Starting to check reachability of 13 error locations. [2024-11-14 04:59:41,159 INFO L276 IsEmpty]: Start isEmpty. Operand has 45 states, 22 states have (on average 1.6818181818181819) internal successors, (37), 35 states have internal predecessors, (37), 6 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-14 04:59:41,167 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2024-11-14 04:59:41,168 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:59:41,168 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:59:41,169 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONMEMORY_LEAK === [ULTIMATE.startErr0ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr2ASSERT_VIOLATIONMEMORY_FREE (and 10 more)] === [2024-11-14 04:59:41,173 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:59:41,174 INFO L85 PathProgramCache]: Analyzing trace with hash 1598295020, now seen corresponding path program 1 times [2024-11-14 04:59:41,183 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:59:41,184 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [527530406] [2024-11-14 04:59:41,184 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:59:41,185 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:59:41,295 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:59:41,744 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 04:59:41,745 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:59:41,745 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [527530406] [2024-11-14 04:59:41,746 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [527530406] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:59:41,746 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:59:41,746 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-14 04:59:41,749 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1587095299] [2024-11-14 04:59:41,749 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:59:41,753 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-14 04:59:41,753 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:59:41,780 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-14 04:59:41,780 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-14 04:59:41,782 INFO L87 Difference]: Start difference. First operand has 45 states, 22 states have (on average 1.6818181818181819) internal successors, (37), 35 states have internal predecessors, (37), 6 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-14 04:59:42,009 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:59:42,009 INFO L93 Difference]: Finished difference Result 72 states and 78 transitions. [2024-11-14 04:59:42,012 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-14 04:59:42,014 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2024-11-14 04:59:42,014 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:59:42,020 INFO L225 Difference]: With dead ends: 72 [2024-11-14 04:59:42,020 INFO L226 Difference]: Without dead ends: 71 [2024-11-14 04:59:42,022 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-14 04:59:42,025 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 26 mSDsluCounter, 121 mSDsCounter, 0 mSdLazyCounter, 88 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 151 SdHoareTripleChecker+Invalid, 90 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 88 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 04:59:42,029 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 151 Invalid, 90 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 88 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 04:59:42,040 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2024-11-14 04:59:42,068 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 63. [2024-11-14 04:59:42,070 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 35 states have (on average 1.6285714285714286) internal successors, (57), 47 states have internal predecessors, (57), 10 states have call successors, (10), 5 states have call predecessors, (10), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-14 04:59:42,076 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 77 transitions. [2024-11-14 04:59:42,077 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 77 transitions. Word has length 12 [2024-11-14 04:59:42,078 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:59:42,078 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 77 transitions. [2024-11-14 04:59:42,078 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-14 04:59:42,078 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 77 transitions. [2024-11-14 04:59:42,081 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2024-11-14 04:59:42,081 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:59:42,082 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:59:42,082 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-14 04:59:42,083 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONMEMORY_FREE === [ULTIMATE.startErr0ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr2ASSERT_VIOLATIONMEMORY_FREE (and 10 more)] === [2024-11-14 04:59:42,084 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:59:42,084 INFO L85 PathProgramCache]: Analyzing trace with hash 1596877707, now seen corresponding path program 1 times [2024-11-14 04:59:42,084 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:59:42,085 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1139930472] [2024-11-14 04:59:42,085 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:59:42,085 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:59:42,101 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:59:42,127 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 04:59:42,127 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:59:42,127 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1139930472] [2024-11-14 04:59:42,128 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1139930472] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:59:42,128 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:59:42,128 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-14 04:59:42,128 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1498743868] [2024-11-14 04:59:42,128 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:59:42,129 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-14 04:59:42,129 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:59:42,130 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-14 04:59:42,130 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 04:59:42,130 INFO L87 Difference]: Start difference. First operand 63 states and 77 transitions. Second operand has 3 states, 2 states have (on average 4.0) internal successors, (8), 3 states have internal predecessors, (8), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 04:59:42,161 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:59:42,162 INFO L93 Difference]: Finished difference Result 62 states and 76 transitions. [2024-11-14 04:59:42,162 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-14 04:59:42,162 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 4.0) internal successors, (8), 3 states have internal predecessors, (8), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 12 [2024-11-14 04:59:42,162 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:59:42,163 INFO L225 Difference]: With dead ends: 62 [2024-11-14 04:59:42,163 INFO L226 Difference]: Without dead ends: 62 [2024-11-14 04:59:42,163 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 04:59:42,164 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 0 mSDsluCounter, 37 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 76 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 [2024-11-14 04:59:42,165 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 76 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 04:59:42,165 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2024-11-14 04:59:42,170 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 62. [2024-11-14 04:59:42,170 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 35 states have (on average 1.6) internal successors, (56), 46 states have internal predecessors, (56), 10 states have call successors, (10), 5 states have call predecessors, (10), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-14 04:59:42,172 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 76 transitions. [2024-11-14 04:59:42,172 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 76 transitions. Word has length 12 [2024-11-14 04:59:42,172 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:59:42,172 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 76 transitions. [2024-11-14 04:59:42,173 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 4.0) internal successors, (8), 3 states have internal predecessors, (8), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 04:59:42,173 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 76 transitions. [2024-11-14 04:59:42,173 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2024-11-14 04:59:42,173 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:59:42,173 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:59:42,174 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-14 04:59:42,174 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_FREE === [ULTIMATE.startErr0ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr2ASSERT_VIOLATIONMEMORY_FREE (and 10 more)] === [2024-11-14 04:59:42,174 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:59:42,174 INFO L85 PathProgramCache]: Analyzing trace with hash -2036398593, now seen corresponding path program 1 times [2024-11-14 04:59:42,174 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:59:42,174 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [86725235] [2024-11-14 04:59:42,175 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:59:42,175 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:59:42,186 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:59:42,220 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 04:59:42,222 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:59:42,222 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [86725235] [2024-11-14 04:59:42,223 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [86725235] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:59:42,223 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:59:42,223 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-14 04:59:42,223 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [93702591] [2024-11-14 04:59:42,223 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:59:42,223 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-14 04:59:42,223 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:59:42,224 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-14 04:59:42,224 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 04:59:42,224 INFO L87 Difference]: Start difference. First operand 62 states and 76 transitions. Second operand has 3 states, 2 states have (on average 4.5) internal successors, (9), 3 states have internal predecessors, (9), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 04:59:42,252 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:59:42,253 INFO L93 Difference]: Finished difference Result 61 states and 75 transitions. [2024-11-14 04:59:42,253 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-14 04:59:42,253 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 4.5) internal successors, (9), 3 states have internal predecessors, (9), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 13 [2024-11-14 04:59:42,253 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:59:42,254 INFO L225 Difference]: With dead ends: 61 [2024-11-14 04:59:42,254 INFO L226 Difference]: Without dead ends: 61 [2024-11-14 04:59:42,254 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 04:59:42,258 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 1 mSDsluCounter, 32 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 68 SdHoareTripleChecker+Invalid, 17 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 04:59:42,259 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 68 Invalid, 17 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 04:59:42,259 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2024-11-14 04:59:42,264 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 61. [2024-11-14 04:59:42,264 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 61 states, 35 states have (on average 1.5714285714285714) internal successors, (55), 45 states have internal predecessors, (55), 10 states have call successors, (10), 5 states have call predecessors, (10), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-14 04:59:42,266 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 75 transitions. [2024-11-14 04:59:42,266 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 75 transitions. Word has length 13 [2024-11-14 04:59:42,266 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:59:42,266 INFO L471 AbstractCegarLoop]: Abstraction has 61 states and 75 transitions. [2024-11-14 04:59:42,266 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 4.5) internal successors, (9), 3 states have internal predecessors, (9), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 04:59:42,267 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 75 transitions. [2024-11-14 04:59:42,267 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2024-11-14 04:59:42,267 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:59:42,267 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:59:42,267 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-14 04:59:42,268 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONMEMORY_FREE === [ULTIMATE.startErr0ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr2ASSERT_VIOLATIONMEMORY_FREE (and 10 more)] === [2024-11-14 04:59:42,268 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:59:42,268 INFO L85 PathProgramCache]: Analyzing trace with hash 1296153101, now seen corresponding path program 1 times [2024-11-14 04:59:42,268 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:59:42,268 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1302718637] [2024-11-14 04:59:42,269 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:59:42,269 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:59:42,281 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:59:42,372 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 04:59:42,372 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:59:42,372 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1302718637] [2024-11-14 04:59:42,372 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1302718637] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:59:42,372 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:59:42,372 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-14 04:59:42,373 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1514932213] [2024-11-14 04:59:42,373 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:59:42,373 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-14 04:59:42,373 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:59:42,373 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-14 04:59:42,374 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 04:59:42,374 INFO L87 Difference]: Start difference. First operand 61 states and 75 transitions. Second operand has 3 states, 2 states have (on average 5.0) internal successors, (10), 3 states have internal predecessors, (10), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 04:59:42,417 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:59:42,418 INFO L93 Difference]: Finished difference Result 60 states and 74 transitions. [2024-11-14 04:59:42,419 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-14 04:59:42,419 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 5.0) internal successors, (10), 3 states have internal predecessors, (10), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 14 [2024-11-14 04:59:42,419 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:59:42,420 INFO L225 Difference]: With dead ends: 60 [2024-11-14 04:59:42,420 INFO L226 Difference]: Without dead ends: 60 [2024-11-14 04:59:42,420 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 04:59:42,421 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 0 mSDsluCounter, 26 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 62 SdHoareTripleChecker+Invalid, 21 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 04:59:42,421 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 62 Invalid, 21 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 04:59:42,425 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2024-11-14 04:59:42,433 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 60. [2024-11-14 04:59:42,433 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 60 states, 35 states have (on average 1.542857142857143) internal successors, (54), 44 states have internal predecessors, (54), 10 states have call successors, (10), 5 states have call predecessors, (10), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-14 04:59:42,435 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 74 transitions. [2024-11-14 04:59:42,435 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 74 transitions. Word has length 14 [2024-11-14 04:59:42,435 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:59:42,435 INFO L471 AbstractCegarLoop]: Abstraction has 60 states and 74 transitions. [2024-11-14 04:59:42,435 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 5.0) internal successors, (10), 3 states have internal predecessors, (10), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 04:59:42,436 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 74 transitions. [2024-11-14 04:59:42,436 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-14 04:59:42,436 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:59:42,436 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:59:42,436 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-14 04:59:42,437 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting checkErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr2ASSERT_VIOLATIONMEMORY_FREE (and 10 more)] === [2024-11-14 04:59:42,437 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:59:42,437 INFO L85 PathProgramCache]: Analyzing trace with hash 805322082, now seen corresponding path program 1 times [2024-11-14 04:59:42,437 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:59:42,437 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [320538820] [2024-11-14 04:59:42,438 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:59:42,438 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:59:42,449 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:59:42,524 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 04:59:42,524 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:59:42,524 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [320538820] [2024-11-14 04:59:42,525 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [320538820] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:59:42,525 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:59:42,525 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-14 04:59:42,525 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1136220025] [2024-11-14 04:59:42,525 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:59:42,525 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 04:59:42,525 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:59:42,526 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 04:59:42,526 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-14 04:59:42,526 INFO L87 Difference]: Start difference. First operand 60 states and 74 transitions. Second operand has 5 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 4 states have internal predecessors, (10), 3 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 04:59:42,625 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:59:42,625 INFO L93 Difference]: Finished difference Result 60 states and 71 transitions. [2024-11-14 04:59:42,626 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 04:59:42,626 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 4 states have internal predecessors, (10), 3 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 15 [2024-11-14 04:59:42,626 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:59:42,629 INFO L225 Difference]: With dead ends: 60 [2024-11-14 04:59:42,629 INFO L226 Difference]: Without dead ends: 60 [2024-11-14 04:59:42,629 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-14 04:59:42,630 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 25 mSDsluCounter, 33 mSDsCounter, 0 mSdLazyCounter, 66 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 57 SdHoareTripleChecker+Invalid, 77 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 66 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 04:59:42,630 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 57 Invalid, 77 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 66 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 04:59:42,631 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2024-11-14 04:59:42,653 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 56. [2024-11-14 04:59:42,653 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 35 states have (on average 1.3142857142857143) internal successors, (46), 40 states have internal predecessors, (46), 10 states have call successors, (10), 5 states have call predecessors, (10), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-14 04:59:42,654 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 66 transitions. [2024-11-14 04:59:42,654 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 66 transitions. Word has length 15 [2024-11-14 04:59:42,654 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:59:42,655 INFO L471 AbstractCegarLoop]: Abstraction has 56 states and 66 transitions. [2024-11-14 04:59:42,655 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 4 states have internal predecessors, (10), 3 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 04:59:42,655 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 66 transitions. [2024-11-14 04:59:42,655 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-14 04:59:42,655 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:59:42,655 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:59:42,655 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2024-11-14 04:59:42,656 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting checkErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr2ASSERT_VIOLATIONMEMORY_FREE (and 10 more)] === [2024-11-14 04:59:42,656 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:59:42,656 INFO L85 PathProgramCache]: Analyzing trace with hash 805322083, now seen corresponding path program 1 times [2024-11-14 04:59:42,656 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:59:42,656 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1513260048] [2024-11-14 04:59:42,657 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:59:42,659 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:59:42,690 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:59:43,088 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 04:59:43,088 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:59:43,088 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1513260048] [2024-11-14 04:59:43,089 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1513260048] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:59:43,089 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:59:43,089 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2024-11-14 04:59:43,089 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [672383951] [2024-11-14 04:59:43,089 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:59:43,089 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-14 04:59:43,089 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:59:43,090 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-14 04:59:43,090 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-11-14 04:59:43,090 INFO L87 Difference]: Start difference. First operand 56 states and 66 transitions. Second operand has 8 states, 5 states have (on average 2.0) internal successors, (10), 6 states have internal predecessors, (10), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 04:59:43,334 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:59:43,334 INFO L93 Difference]: Finished difference Result 59 states and 65 transitions. [2024-11-14 04:59:43,334 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-14 04:59:43,334 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 5 states have (on average 2.0) internal successors, (10), 6 states have internal predecessors, (10), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 15 [2024-11-14 04:59:43,335 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:59:43,335 INFO L225 Difference]: With dead ends: 59 [2024-11-14 04:59:43,335 INFO L226 Difference]: Without dead ends: 59 [2024-11-14 04:59:43,335 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2024-11-14 04:59:43,336 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 23 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 152 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 154 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 152 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 04:59:43,336 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 115 Invalid, 154 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 152 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 04:59:43,337 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2024-11-14 04:59:43,340 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 56. [2024-11-14 04:59:43,340 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 35 states have (on average 1.2857142857142858) internal successors, (45), 40 states have internal predecessors, (45), 10 states have call successors, (10), 5 states have call predecessors, (10), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-14 04:59:43,341 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 65 transitions. [2024-11-14 04:59:43,341 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 65 transitions. Word has length 15 [2024-11-14 04:59:43,341 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:59:43,341 INFO L471 AbstractCegarLoop]: Abstraction has 56 states and 65 transitions. [2024-11-14 04:59:43,342 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 5 states have (on average 2.0) internal successors, (10), 6 states have internal predecessors, (10), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 04:59:43,342 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 65 transitions. [2024-11-14 04:59:43,342 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-14 04:59:43,342 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:59:43,342 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:59:43,342 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-14 04:59:43,342 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr3ASSERT_VIOLATIONMEMORY_LEAK === [ULTIMATE.startErr0ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr2ASSERT_VIOLATIONMEMORY_FREE (and 10 more)] === [2024-11-14 04:59:43,343 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:59:43,343 INFO L85 PathProgramCache]: Analyzing trace with hash 1526040514, now seen corresponding path program 1 times [2024-11-14 04:59:43,343 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:59:43,343 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1884405774] [2024-11-14 04:59:43,343 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:59:43,343 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:59:43,355 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:59:43,432 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 04:59:43,432 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:59:43,432 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1884405774] [2024-11-14 04:59:43,432 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1884405774] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:59:43,432 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:59:43,433 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-14 04:59:43,433 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [521991976] [2024-11-14 04:59:43,433 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:59:43,433 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-14 04:59:43,433 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:59:43,434 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-14 04:59:43,434 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 04:59:43,434 INFO L87 Difference]: Start difference. First operand 56 states and 65 transitions. Second operand has 4 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 04:59:43,475 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:59:43,476 INFO L93 Difference]: Finished difference Result 55 states and 64 transitions. [2024-11-14 04:59:43,476 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-14 04:59:43,477 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 15 [2024-11-14 04:59:43,477 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:59:43,477 INFO L225 Difference]: With dead ends: 55 [2024-11-14 04:59:43,477 INFO L226 Difference]: Without dead ends: 47 [2024-11-14 04:59:43,478 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 04:59:43,480 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 0 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 04:59:43,480 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 81 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 04:59:43,481 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-11-14 04:59:43,485 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2024-11-14 04:59:43,485 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 28 states have (on average 1.3214285714285714) internal successors, (37), 33 states have internal predecessors, (37), 10 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-14 04:59:43,486 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 55 transitions. [2024-11-14 04:59:43,486 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 55 transitions. Word has length 15 [2024-11-14 04:59:43,486 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:59:43,486 INFO L471 AbstractCegarLoop]: Abstraction has 47 states and 55 transitions. [2024-11-14 04:59:43,489 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 04:59:43,489 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 55 transitions. [2024-11-14 04:59:43,489 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2024-11-14 04:59:43,489 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:59:43,489 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:59:43,490 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2024-11-14 04:59:43,490 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting checkErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr2ASSERT_VIOLATIONMEMORY_FREE (and 10 more)] === [2024-11-14 04:59:43,490 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:59:43,491 INFO L85 PathProgramCache]: Analyzing trace with hash -804819226, now seen corresponding path program 1 times [2024-11-14 04:59:43,491 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:59:43,491 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [794538211] [2024-11-14 04:59:43,491 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:59:43,491 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:59:43,515 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:59:43,835 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 04:59:43,835 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:59:43,836 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [794538211] [2024-11-14 04:59:43,836 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [794538211] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:59:43,836 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:59:43,836 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2024-11-14 04:59:43,836 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1038848725] [2024-11-14 04:59:43,836 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:59:43,837 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-14 04:59:43,837 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:59:43,837 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-14 04:59:43,838 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2024-11-14 04:59:43,838 INFO L87 Difference]: Start difference. First operand 47 states and 55 transitions. Second operand has 9 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 7 states have internal predecessors, (11), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 04:59:44,082 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:59:44,082 INFO L93 Difference]: Finished difference Result 49 states and 54 transitions. [2024-11-14 04:59:44,084 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-14 04:59:44,084 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 7 states have internal predecessors, (11), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 16 [2024-11-14 04:59:44,084 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:59:44,085 INFO L225 Difference]: With dead ends: 49 [2024-11-14 04:59:44,085 INFO L226 Difference]: Without dead ends: 49 [2024-11-14 04:59:44,085 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=29, Invalid=81, Unknown=0, NotChecked=0, Total=110 [2024-11-14 04:59:44,086 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 11 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 152 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 153 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 152 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 04:59:44,086 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 115 Invalid, 153 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 152 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 04:59:44,086 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2024-11-14 04:59:44,092 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 47. [2024-11-14 04:59:44,094 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 28 states have (on average 1.2857142857142858) internal successors, (36), 33 states have internal predecessors, (36), 10 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-14 04:59:44,095 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 54 transitions. [2024-11-14 04:59:44,095 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 54 transitions. Word has length 16 [2024-11-14 04:59:44,096 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:59:44,097 INFO L471 AbstractCegarLoop]: Abstraction has 47 states and 54 transitions. [2024-11-14 04:59:44,097 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 7 states have internal predecessors, (11), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 04:59:44,097 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 54 transitions. [2024-11-14 04:59:44,098 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2024-11-14 04:59:44,098 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:59:44,098 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:59:44,099 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2024-11-14 04:59:44,099 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONMEMORY_LEAK === [ULTIMATE.startErr0ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr2ASSERT_VIOLATIONMEMORY_FREE (and 10 more)] === [2024-11-14 04:59:44,100 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:59:44,100 INFO L85 PathProgramCache]: Analyzing trace with hash 522255046, now seen corresponding path program 1 times [2024-11-14 04:59:44,100 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:59:44,100 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [224486348] [2024-11-14 04:59:44,100 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:59:44,100 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:59:44,124 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:59:44,609 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 04:59:44,609 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:59:44,609 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [224486348] [2024-11-14 04:59:44,609 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [224486348] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 04:59:44,609 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1479427192] [2024-11-14 04:59:44,610 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:59:44,610 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:59:44,610 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:59:44,618 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:59:44,621 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-14 04:59:44,709 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:59:44,717 INFO L255 TraceCheckSpWp]: Trace formula consists of 123 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-14 04:59:44,726 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:59:44,892 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 49 treesize of output 33 [2024-11-14 04:59:45,277 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 04:59:45,277 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 04:59:45,278 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1479427192] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:59:45,278 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-14 04:59:45,279 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [10] total 16 [2024-11-14 04:59:45,279 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [900697737] [2024-11-14 04:59:45,279 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:59:45,279 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-14 04:59:45,280 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:59:45,281 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-14 04:59:45,281 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=200, Unknown=0, NotChecked=0, Total=240 [2024-11-14 04:59:45,281 INFO L87 Difference]: Start difference. First operand 47 states and 54 transitions. Second operand has 8 states, 8 states have (on average 2.0) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (5), 4 states have call predecessors, (5), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 04:59:45,536 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:59:45,536 INFO L93 Difference]: Finished difference Result 55 states and 60 transitions. [2024-11-14 04:59:45,537 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-14 04:59:45,537 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.0) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (5), 4 states have call predecessors, (5), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 23 [2024-11-14 04:59:45,537 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:59:45,538 INFO L225 Difference]: With dead ends: 55 [2024-11-14 04:59:45,538 INFO L226 Difference]: Without dead ends: 55 [2024-11-14 04:59:45,538 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=64, Invalid=316, Unknown=0, NotChecked=0, Total=380 [2024-11-14 04:59:45,539 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 42 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 132 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 42 SdHoareTripleChecker+Valid, 110 SdHoareTripleChecker+Invalid, 145 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 132 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 04:59:45,539 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [42 Valid, 110 Invalid, 145 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 132 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 04:59:45,540 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2024-11-14 04:59:45,543 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 51. [2024-11-14 04:59:45,543 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 31 states have (on average 1.2580645161290323) internal successors, (39), 36 states have internal predecessors, (39), 10 states have call successors, (10), 6 states have call predecessors, (10), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-14 04:59:45,544 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 57 transitions. [2024-11-14 04:59:45,544 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 57 transitions. Word has length 23 [2024-11-14 04:59:45,544 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:59:45,544 INFO L471 AbstractCegarLoop]: Abstraction has 51 states and 57 transitions. [2024-11-14 04:59:45,544 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.0) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (5), 4 states have call predecessors, (5), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 04:59:45,544 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 57 transitions. [2024-11-14 04:59:45,545 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2024-11-14 04:59:45,545 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:59:45,545 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:59:45,566 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-14 04:59:45,749 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:59:45,749 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting checkErr5REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr2ASSERT_VIOLATIONMEMORY_FREE (and 10 more)] === [2024-11-14 04:59:45,749 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:59:45,749 INFO L85 PathProgramCache]: Analyzing trace with hash -1287196587, now seen corresponding path program 1 times [2024-11-14 04:59:45,750 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:59:45,750 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [979454123] [2024-11-14 04:59:45,750 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:59:45,750 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:59:45,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:59:45,991 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-14 04:59:45,991 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:59:45,991 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [979454123] [2024-11-14 04:59:45,991 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [979454123] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 04:59:45,991 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1826939799] [2024-11-14 04:59:45,991 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:59:45,991 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:59:45,991 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:59:45,993 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:59:45,996 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-14 04:59:46,072 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:59:46,073 INFO L255 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-14 04:59:46,075 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:59:46,303 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-14 04:59:46,304 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:59:46,605 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 38 treesize of output 34 [2024-11-14 04:59:46,741 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-14 04:59:46,742 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1826939799] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:59:46,742 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1230739129] [2024-11-14 04:59:46,761 INFO L159 IcfgInterpreter]: Started Sifa with 23 locations of interest [2024-11-14 04:59:46,762 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:59:46,766 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:407) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:342) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:324) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:429) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:315) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:276) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:170) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:143) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2024-11-14 04:59:46,779 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 04:59:46,779 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 19 [2024-11-14 04:59:46,779 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [855294735] [2024-11-14 04:59:46,779 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 04:59:46,779 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-14 04:59:46,779 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:59:46,780 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-14 04:59:46,780 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=327, Unknown=0, NotChecked=0, Total=380 [2024-11-14 04:59:46,781 INFO L87 Difference]: Start difference. First operand 51 states and 57 transitions. Second operand has 20 states, 16 states have (on average 2.0) internal successors, (32), 14 states have internal predecessors, (32), 9 states have call successors, (13), 4 states have call predecessors, (13), 2 states have return successors, (10), 10 states have call predecessors, (10), 7 states have call successors, (10) [2024-11-14 04:59:47,223 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:59:47,223 INFO L93 Difference]: Finished difference Result 51 states and 55 transitions. [2024-11-14 04:59:47,223 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-14 04:59:47,223 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 16 states have (on average 2.0) internal successors, (32), 14 states have internal predecessors, (32), 9 states have call successors, (13), 4 states have call predecessors, (13), 2 states have return successors, (10), 10 states have call predecessors, (10), 7 states have call successors, (10) Word has length 26 [2024-11-14 04:59:47,224 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:59:47,224 INFO L225 Difference]: With dead ends: 51 [2024-11-14 04:59:47,224 INFO L226 Difference]: Without dead ends: 51 [2024-11-14 04:59:47,225 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 41 SyntacticMatches, 1 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 83 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=141, Invalid=615, Unknown=0, NotChecked=0, Total=756 [2024-11-14 04:59:47,225 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 51 mSDsluCounter, 141 mSDsCounter, 0 mSdLazyCounter, 209 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 52 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 235 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 209 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 04:59:47,226 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [52 Valid, 157 Invalid, 235 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 209 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 04:59:47,226 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2024-11-14 04:59:47,229 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 50. [2024-11-14 04:59:47,229 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 31 states have (on average 1.1935483870967742) internal successors, (37), 35 states have internal predecessors, (37), 10 states have call successors, (10), 6 states have call predecessors, (10), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-14 04:59:47,230 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 55 transitions. [2024-11-14 04:59:47,230 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 55 transitions. Word has length 26 [2024-11-14 04:59:47,230 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:59:47,230 INFO L471 AbstractCegarLoop]: Abstraction has 50 states and 55 transitions. [2024-11-14 04:59:47,230 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 16 states have (on average 2.0) internal successors, (32), 14 states have internal predecessors, (32), 9 states have call successors, (13), 4 states have call predecessors, (13), 2 states have return successors, (10), 10 states have call predecessors, (10), 7 states have call successors, (10) [2024-11-14 04:59:47,230 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 55 transitions. [2024-11-14 04:59:47,231 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2024-11-14 04:59:47,231 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:59:47,231 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:59:47,251 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-14 04:59:47,431 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-14 04:59:47,432 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting checkErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr2ASSERT_VIOLATIONMEMORY_FREE (and 10 more)] === [2024-11-14 04:59:47,432 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:59:47,432 INFO L85 PathProgramCache]: Analyzing trace with hash 2134353993, now seen corresponding path program 1 times [2024-11-14 04:59:47,432 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:59:47,432 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [744800669] [2024-11-14 04:59:47,432 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:59:47,433 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:59:47,453 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:59:47,898 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-14 04:59:47,898 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:59:47,898 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [744800669] [2024-11-14 04:59:47,899 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [744800669] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 04:59:47,899 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [681549848] [2024-11-14 04:59:47,899 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:59:47,899 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:59:47,899 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:59:47,901 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:59:47,903 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-14 04:59:47,985 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:59:47,987 INFO L255 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 29 conjuncts are in the unsatisfiable core [2024-11-14 04:59:47,989 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:59:48,284 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 3 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-14 04:59:48,285 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:59:48,619 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 36 treesize of output 32 [2024-11-14 04:59:48,834 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 3 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-14 04:59:48,835 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [681549848] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:59:48,835 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1888716803] [2024-11-14 04:59:48,837 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2024-11-14 04:59:48,840 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:59:48,841 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:407) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:342) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:324) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:429) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:315) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:276) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:170) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:143) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2024-11-14 04:59:48,841 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 04:59:48,841 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 10, 10] total 24 [2024-11-14 04:59:48,841 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [85199451] [2024-11-14 04:59:48,842 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 04:59:48,842 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-14 04:59:48,842 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:59:48,842 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-14 04:59:48,843 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=537, Unknown=0, NotChecked=0, Total=600 [2024-11-14 04:59:48,843 INFO L87 Difference]: Start difference. First operand 50 states and 55 transitions. Second operand has 25 states, 20 states have (on average 1.95) internal successors, (39), 19 states have internal predecessors, (39), 12 states have call successors, (13), 7 states have call predecessors, (13), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-14 04:59:50,342 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:59:50,342 INFO L93 Difference]: Finished difference Result 87 states and 100 transitions. [2024-11-14 04:59:50,343 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-14 04:59:50,343 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 20 states have (on average 1.95) internal successors, (39), 19 states have internal predecessors, (39), 12 states have call successors, (13), 7 states have call predecessors, (13), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Word has length 26 [2024-11-14 04:59:50,343 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:59:50,348 INFO L225 Difference]: With dead ends: 87 [2024-11-14 04:59:50,348 INFO L226 Difference]: Without dead ends: 87 [2024-11-14 04:59:50,349 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 78 GetRequests, 35 SyntacticMatches, 1 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 230 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=325, Invalid=1567, Unknown=0, NotChecked=0, Total=1892 [2024-11-14 04:59:50,352 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 192 mSDsluCounter, 209 mSDsCounter, 0 mSdLazyCounter, 508 mSolverCounterSat, 127 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 192 SdHoareTripleChecker+Valid, 229 SdHoareTripleChecker+Invalid, 635 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 127 IncrementalHoareTripleChecker+Valid, 508 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-14 04:59:50,352 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [192 Valid, 229 Invalid, 635 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [127 Valid, 508 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-14 04:59:50,356 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2024-11-14 04:59:50,363 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 78. [2024-11-14 04:59:50,371 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 78 states, 51 states have (on average 1.1568627450980393) internal successors, (59), 53 states have internal predecessors, (59), 18 states have call successors, (18), 8 states have call predecessors, (18), 7 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-14 04:59:50,372 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 93 transitions. [2024-11-14 04:59:50,372 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 93 transitions. Word has length 26 [2024-11-14 04:59:50,372 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:59:50,372 INFO L471 AbstractCegarLoop]: Abstraction has 78 states and 93 transitions. [2024-11-14 04:59:50,372 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 20 states have (on average 1.95) internal successors, (39), 19 states have internal predecessors, (39), 12 states have call successors, (13), 7 states have call predecessors, (13), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-14 04:59:50,372 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 93 transitions. [2024-11-14 04:59:50,373 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-11-14 04:59:50,373 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:59:50,373 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:59:50,399 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-14 04:59:50,573 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-14 04:59:50,574 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting checkErr7REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr2ASSERT_VIOLATIONMEMORY_FREE (and 10 more)] === [2024-11-14 04:59:50,574 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:59:50,574 INFO L85 PathProgramCache]: Analyzing trace with hash -1248387362, now seen corresponding path program 1 times [2024-11-14 04:59:50,575 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:59:50,575 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [412913399] [2024-11-14 04:59:50,575 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:59:50,575 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:59:50,601 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:59:51,060 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 04:59:51,060 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:59:51,060 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [412913399] [2024-11-14 04:59:51,060 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [412913399] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 04:59:51,060 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [260462120] [2024-11-14 04:59:51,060 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:59:51,061 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:59:51,061 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:59:51,064 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:59:51,066 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-14 04:59:51,133 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:59:51,135 INFO L255 TraceCheckSpWp]: Trace formula consists of 138 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-11-14 04:59:51,137 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:59:51,299 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 49 treesize of output 33 [2024-11-14 04:59:51,830 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 04:59:51,831 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:59:52,237 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 55 treesize of output 39 [2024-11-14 04:59:52,248 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 29 treesize of output 25 [2024-11-14 04:59:52,493 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 04:59:52,493 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [260462120] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:59:52,493 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [874960036] [2024-11-14 04:59:52,496 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2024-11-14 04:59:52,497 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:59:52,497 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:407) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:342) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:324) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:429) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:315) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:276) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:170) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:143) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2024-11-14 04:59:52,499 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 04:59:52,500 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 10] total 29 [2024-11-14 04:59:52,500 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1320477937] [2024-11-14 04:59:52,500 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 04:59:52,500 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2024-11-14 04:59:52,500 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:59:52,503 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2024-11-14 04:59:52,503 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=105, Invalid=765, Unknown=0, NotChecked=0, Total=870 [2024-11-14 04:59:52,504 INFO L87 Difference]: Start difference. First operand 78 states and 93 transitions. Second operand has 30 states, 24 states have (on average 1.7083333333333333) internal successors, (41), 24 states have internal predecessors, (41), 12 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-14 04:59:54,577 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-14 04:59:55,742 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:59:55,742 INFO L93 Difference]: Finished difference Result 101 states and 120 transitions. [2024-11-14 04:59:55,743 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-14 04:59:55,743 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 24 states have (on average 1.7083333333333333) internal successors, (41), 24 states have internal predecessors, (41), 12 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Word has length 27 [2024-11-14 04:59:55,744 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:59:55,744 INFO L225 Difference]: With dead ends: 101 [2024-11-14 04:59:55,744 INFO L226 Difference]: Without dead ends: 101 [2024-11-14 04:59:55,745 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 78 GetRequests, 34 SyntacticMatches, 2 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 371 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=283, Invalid=1609, Unknown=0, NotChecked=0, Total=1892 [2024-11-14 04:59:55,746 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 101 mSDsluCounter, 243 mSDsCounter, 0 mSdLazyCounter, 533 mSolverCounterSat, 60 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 101 SdHoareTripleChecker+Valid, 263 SdHoareTripleChecker+Invalid, 594 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 60 IncrementalHoareTripleChecker+Valid, 533 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.6s IncrementalHoareTripleChecker+Time [2024-11-14 04:59:55,746 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [101 Valid, 263 Invalid, 594 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [60 Valid, 533 Invalid, 1 Unknown, 0 Unchecked, 2.6s Time] [2024-11-14 04:59:55,749 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 101 states. [2024-11-14 04:59:55,759 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 101 to 100. [2024-11-14 04:59:55,759 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 100 states, 66 states have (on average 1.121212121212121) internal successors, (74), 67 states have internal predecessors, (74), 22 states have call successors, (22), 8 states have call predecessors, (22), 10 states have return successors, (24), 24 states have call predecessors, (24), 20 states have call successors, (24) [2024-11-14 04:59:55,760 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 120 transitions. [2024-11-14 04:59:55,764 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 120 transitions. Word has length 27 [2024-11-14 04:59:55,764 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:59:55,764 INFO L471 AbstractCegarLoop]: Abstraction has 100 states and 120 transitions. [2024-11-14 04:59:55,765 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 24 states have (on average 1.7083333333333333) internal successors, (41), 24 states have internal predecessors, (41), 12 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-14 04:59:55,765 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 120 transitions. [2024-11-14 04:59:55,765 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-11-14 04:59:55,766 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:59:55,766 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:59:55,790 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-14 04:59:55,966 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2024-11-14 04:59:55,966 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONMEMORY_LEAK === [ULTIMATE.startErr0ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr2ASSERT_VIOLATIONMEMORY_FREE (and 10 more)] === [2024-11-14 04:59:55,967 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:59:55,967 INFO L85 PathProgramCache]: Analyzing trace with hash -955795702, now seen corresponding path program 1 times [2024-11-14 04:59:55,967 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:59:55,967 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [298156459] [2024-11-14 04:59:55,967 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:59:55,967 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:59:55,983 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:59:56,174 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 04:59:56,174 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:59:56,175 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [298156459] [2024-11-14 04:59:56,175 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [298156459] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 04:59:56,175 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1999429324] [2024-11-14 04:59:56,175 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:59:56,176 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:59:56,176 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:59:56,178 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:59:56,180 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-14 04:59:56,252 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:59:56,255 INFO L255 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-14 04:59:56,259 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:59:56,266 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 7 treesize of output 6 [2024-11-14 04:59:56,583 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 23 [2024-11-14 04:59:56,673 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 04:59:56,673 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:59:58,789 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1999429324] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 04:59:58,789 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1780687796] [2024-11-14 04:59:58,791 INFO L159 IcfgInterpreter]: Started Sifa with 26 locations of interest [2024-11-14 04:59:58,791 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:59:58,792 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:407) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:342) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:324) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:429) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:315) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:276) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:170) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:143) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2024-11-14 04:59:58,792 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 04:59:58,792 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 13] total 19 [2024-11-14 04:59:58,792 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1651663148] [2024-11-14 04:59:58,792 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 04:59:58,792 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-14 04:59:58,793 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:59:58,793 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-14 04:59:58,793 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=397, Unknown=0, NotChecked=0, Total=462 [2024-11-14 04:59:58,793 INFO L87 Difference]: Start difference. First operand 100 states and 120 transitions. Second operand has 19 states, 16 states have (on average 2.125) internal successors, (34), 15 states have internal predecessors, (34), 7 states have call successors, (11), 6 states have call predecessors, (11), 3 states have return successors, (7), 3 states have call predecessors, (7), 4 states have call successors, (7) [2024-11-14 04:59:59,135 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:59:59,135 INFO L93 Difference]: Finished difference Result 100 states and 119 transitions. [2024-11-14 04:59:59,136 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-14 04:59:59,137 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 16 states have (on average 2.125) internal successors, (34), 15 states have internal predecessors, (34), 7 states have call successors, (11), 6 states have call predecessors, (11), 3 states have return successors, (7), 3 states have call predecessors, (7), 4 states have call successors, (7) Word has length 31 [2024-11-14 04:59:59,137 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:59:59,138 INFO L225 Difference]: With dead ends: 100 [2024-11-14 04:59:59,138 INFO L226 Difference]: Without dead ends: 93 [2024-11-14 04:59:59,139 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 25 SyntacticMatches, 5 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 146 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=121, Invalid=635, Unknown=0, NotChecked=0, Total=756 [2024-11-14 04:59:59,143 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 29 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 231 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 87 SdHoareTripleChecker+Invalid, 247 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 231 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 04:59:59,144 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 87 Invalid, 247 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 231 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 04:59:59,144 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2024-11-14 04:59:59,149 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2024-11-14 04:59:59,150 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 62 states have (on average 1.0806451612903225) internal successors, (67), 61 states have internal predecessors, (67), 20 states have call successors, (20), 9 states have call predecessors, (20), 10 states have return successors, (22), 22 states have call predecessors, (22), 19 states have call successors, (22) [2024-11-14 04:59:59,151 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 109 transitions. [2024-11-14 04:59:59,151 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 109 transitions. Word has length 31 [2024-11-14 04:59:59,151 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:59:59,151 INFO L471 AbstractCegarLoop]: Abstraction has 93 states and 109 transitions. [2024-11-14 04:59:59,151 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 16 states have (on average 2.125) internal successors, (34), 15 states have internal predecessors, (34), 7 states have call successors, (11), 6 states have call predecessors, (11), 3 states have return successors, (7), 3 states have call predecessors, (7), 4 states have call successors, (7) [2024-11-14 04:59:59,151 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 109 transitions. [2024-11-14 04:59:59,152 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2024-11-14 04:59:59,152 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:59:59,157 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:59:59,176 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-14 04:59:59,357 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-14 04:59:59,357 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting checkErr7REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr2ASSERT_VIOLATIONMEMORY_FREE (and 10 more)] === [2024-11-14 04:59:59,358 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:59:59,358 INFO L85 PathProgramCache]: Analyzing trace with hash 330124194, now seen corresponding path program 1 times [2024-11-14 04:59:59,358 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:59:59,358 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1353431660] [2024-11-14 04:59:59,358 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:59:59,358 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:59:59,387 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:00:00,602 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2024-11-14 05:00:00,602 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:00:00,602 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1353431660] [2024-11-14 05:00:00,603 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1353431660] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:00:00,603 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [308256638] [2024-11-14 05:00:00,603 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:00:00,603 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:00:00,603 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:00:00,605 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:00:00,608 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-14 05:00:00,699 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:00:00,701 INFO L255 TraceCheckSpWp]: Trace formula consists of 223 conjuncts, 37 conjuncts are in the unsatisfiable core [2024-11-14 05:00:00,704 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:00:01,978 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 7 proven. 19 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-11-14 05:00:01,978 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:00:02,490 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 35 treesize of output 19 [2024-11-14 05:00:03,088 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [308256638] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:00:03,089 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [406810823] [2024-11-14 05:00:03,091 INFO L159 IcfgInterpreter]: Started Sifa with 26 locations of interest [2024-11-14 05:00:03,091 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:00:03,091 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:407) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:342) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:324) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:429) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:315) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:276) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:170) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:143) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2024-11-14 05:00:03,092 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 05:00:03,092 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 20] total 37 [2024-11-14 05:00:03,092 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1333646108] [2024-11-14 05:00:03,092 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 05:00:03,093 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 38 states [2024-11-14 05:00:03,093 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:00:03,094 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 38 interpolants. [2024-11-14 05:00:03,094 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=105, Invalid=1701, Unknown=0, NotChecked=0, Total=1806 [2024-11-14 05:00:03,094 INFO L87 Difference]: Start difference. First operand 93 states and 109 transitions. Second operand has 38 states, 30 states have (on average 1.7666666666666666) internal successors, (53), 32 states have internal predecessors, (53), 17 states have call successors, (17), 4 states have call predecessors, (17), 7 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-14 05:00:05,183 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-14 05:00:09,075 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:00:09,075 INFO L93 Difference]: Finished difference Result 109 states and 127 transitions. [2024-11-14 05:00:09,075 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2024-11-14 05:00:09,076 INFO L78 Accepts]: Start accepts. Automaton has has 38 states, 30 states have (on average 1.7666666666666666) internal successors, (53), 32 states have internal predecessors, (53), 17 states have call successors, (17), 4 states have call predecessors, (17), 7 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) Word has length 52 [2024-11-14 05:00:09,076 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:00:09,077 INFO L225 Difference]: With dead ends: 109 [2024-11-14 05:00:09,077 INFO L226 Difference]: Without dead ends: 71 [2024-11-14 05:00:09,079 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 38 SyntacticMatches, 1 SemanticMatches, 81 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1077 ImplicationChecksByTransitivity, 4.8s TimeCoverageRelationStatistics Valid=633, Invalid=6173, Unknown=0, NotChecked=0, Total=6806 [2024-11-14 05:00:09,079 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 142 mSDsluCounter, 312 mSDsCounter, 0 mSdLazyCounter, 922 mSolverCounterSat, 121 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 142 SdHoareTripleChecker+Valid, 327 SdHoareTripleChecker+Invalid, 1044 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 121 IncrementalHoareTripleChecker+Valid, 922 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.8s IncrementalHoareTripleChecker+Time [2024-11-14 05:00:09,080 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [142 Valid, 327 Invalid, 1044 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [121 Valid, 922 Invalid, 1 Unknown, 0 Unchecked, 2.8s Time] [2024-11-14 05:00:09,080 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2024-11-14 05:00:09,085 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 67. [2024-11-14 05:00:09,085 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 45 states have (on average 1.0444444444444445) internal successors, (47), 45 states have internal predecessors, (47), 14 states have call successors, (14), 9 states have call predecessors, (14), 7 states have return successors, (12), 12 states have call predecessors, (12), 11 states have call successors, (12) [2024-11-14 05:00:09,086 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 73 transitions. [2024-11-14 05:00:09,086 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 73 transitions. Word has length 52 [2024-11-14 05:00:09,086 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:00:09,086 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 73 transitions. [2024-11-14 05:00:09,086 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 38 states, 30 states have (on average 1.7666666666666666) internal successors, (53), 32 states have internal predecessors, (53), 17 states have call successors, (17), 4 states have call predecessors, (17), 7 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-14 05:00:09,086 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 73 transitions. [2024-11-14 05:00:09,091 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2024-11-14 05:00:09,094 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:00:09,094 INFO L215 NwaCegarLoop]: trace histogram [7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 05:00:09,107 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-14 05:00:09,294 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-11-14 05:00:09,294 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting checkErr7REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [ULTIMATE.startErr0ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_FREE, ULTIMATE.startErr2ASSERT_VIOLATIONMEMORY_FREE (and 10 more)] === [2024-11-14 05:00:09,295 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:00:09,295 INFO L85 PathProgramCache]: Analyzing trace with hash 603890466, now seen corresponding path program 2 times [2024-11-14 05:00:09,295 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:00:09,295 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1338149065] [2024-11-14 05:00:09,295 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:00:09,295 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:00:09,343 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:00:12,271 INFO L134 CoverageAnalysis]: Checked inductivity of 213 backedges. 46 proven. 76 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2024-11-14 05:00:12,271 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:00:12,271 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1338149065] [2024-11-14 05:00:12,272 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1338149065] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:00:12,272 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1399335320] [2024-11-14 05:00:12,272 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 05:00:12,272 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:00:12,272 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:00:12,274 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:00:12,290 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-14 05:00:12,413 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-14 05:00:12,413 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 05:00:12,415 INFO L255 TraceCheckSpWp]: Trace formula consists of 223 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-14 05:00:12,422 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:00:13,171 INFO L134 CoverageAnalysis]: Checked inductivity of 213 backedges. 42 proven. 8 refuted. 0 times theorem prover too weak. 163 trivial. 0 not checked. [2024-11-14 05:00:13,171 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:00:14,160 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1399335320] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:00:14,160 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [691906973] [2024-11-14 05:00:14,162 INFO L159 IcfgInterpreter]: Started Sifa with 26 locations of interest [2024-11-14 05:00:14,163 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:00:14,163 FATAL L? ?]: Ignoring exception! java.lang.IllegalArgumentException: Recursive programs are not supported. at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.topsortRelevant(CallGraph.java:132) at de.uni_freiburg.informatik.ultimate.lib.sifa.CallGraph.(CallGraph.java:97) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.(IcfgInterpreter.java:92) at de.uni_freiburg.informatik.ultimate.plugins.sifa.SifaBuilder.construct(SifaBuilder.java:96) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:98) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:407) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:342) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:324) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:429) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:315) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:276) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:170) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:143) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2024-11-14 05:00:14,164 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 05:00:14,164 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [30, 14] total 43 [2024-11-14 05:00:14,164 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [979668522] [2024-11-14 05:00:14,164 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 05:00:14,165 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 44 states [2024-11-14 05:00:14,165 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:00:14,166 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 44 interpolants. [2024-11-14 05:00:14,166 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=140, Invalid=2022, Unknown=0, NotChecked=0, Total=2162 [2024-11-14 05:00:14,166 INFO L87 Difference]: Start difference. First operand 67 states and 73 transitions. Second operand has 44 states, 38 states have (on average 1.868421052631579) internal successors, (71), 35 states have internal predecessors, (71), 19 states have call successors, (26), 7 states have call predecessors, (26), 6 states have return successors, (19), 18 states have call predecessors, (19), 18 states have call successors, (19) [2024-11-14 05:00:16,242 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-14 05:00:20,816 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:00:20,816 INFO L93 Difference]: Finished difference Result 87 states and 97 transitions. [2024-11-14 05:00:20,817 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2024-11-14 05:00:20,817 INFO L78 Accepts]: Start accepts. Automaton has has 44 states, 38 states have (on average 1.868421052631579) internal successors, (71), 35 states have internal predecessors, (71), 19 states have call successors, (26), 7 states have call predecessors, (26), 6 states have return successors, (19), 18 states have call predecessors, (19), 18 states have call successors, (19) Word has length 96 [2024-11-14 05:00:20,818 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:00:20,818 INFO L225 Difference]: With dead ends: 87 [2024-11-14 05:00:20,818 INFO L226 Difference]: Without dead ends: 0 [2024-11-14 05:00:20,820 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 180 GetRequests, 94 SyntacticMatches, 1 SemanticMatches, 85 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1348 ImplicationChecksByTransitivity, 4.8s TimeCoverageRelationStatistics Valid=939, Invalid=6543, Unknown=0, NotChecked=0, Total=7482 [2024-11-14 05:00:20,821 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 134 mSDsluCounter, 481 mSDsCounter, 0 mSdLazyCounter, 1849 mSolverCounterSat, 85 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 134 SdHoareTripleChecker+Valid, 512 SdHoareTripleChecker+Invalid, 1935 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 85 IncrementalHoareTripleChecker+Valid, 1849 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.4s IncrementalHoareTripleChecker+Time [2024-11-14 05:00:20,821 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [134 Valid, 512 Invalid, 1935 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [85 Valid, 1849 Invalid, 1 Unknown, 0 Unchecked, 3.4s Time] [2024-11-14 05:00:20,822 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2024-11-14 05:00:20,822 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2024-11-14 05:00:20,823 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 05:00:20,823 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2024-11-14 05:00:20,823 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 96 [2024-11-14 05:00:20,823 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:00:20,823 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-14 05:00:20,824 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 44 states, 38 states have (on average 1.868421052631579) internal successors, (71), 35 states have internal predecessors, (71), 19 states have call successors, (26), 7 states have call predecessors, (26), 6 states have return successors, (19), 18 states have call predecessors, (19), 18 states have call successors, (19) [2024-11-14 05:00:20,824 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2024-11-14 05:00:20,824 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2024-11-14 05:00:20,827 INFO L782 garLoopResultBuilder]: Registering result SAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONMEMORY_FREE (12 of 13 remaining) [2024-11-14 05:00:20,828 INFO L782 garLoopResultBuilder]: Registering result SAFE for location ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_FREE (11 of 13 remaining) [2024-11-14 05:00:20,828 INFO L782 garLoopResultBuilder]: Registering result SAFE for location ULTIMATE.startErr2ASSERT_VIOLATIONMEMORY_FREE (10 of 13 remaining) [2024-11-14 05:00:20,828 INFO L782 garLoopResultBuilder]: Registering result SAFE for location ULTIMATE.startErr3ASSERT_VIOLATIONMEMORY_LEAK (9 of 13 remaining) [2024-11-14 05:00:20,828 INFO L782 garLoopResultBuilder]: Registering result SAFE for location checkErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (8 of 13 remaining) [2024-11-14 05:00:20,828 INFO L782 garLoopResultBuilder]: Registering result SAFE for location checkErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE (7 of 13 remaining) [2024-11-14 05:00:20,828 INFO L782 garLoopResultBuilder]: Registering result SAFE for location checkErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE (6 of 13 remaining) [2024-11-14 05:00:20,828 INFO L782 garLoopResultBuilder]: Registering result SAFE for location checkErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE (5 of 13 remaining) [2024-11-14 05:00:20,828 INFO L782 garLoopResultBuilder]: Registering result SAFE for location checkErr4REQUIRES_VIOLATIONMEMORY_DEREFERENCE (4 of 13 remaining) [2024-11-14 05:00:20,828 INFO L782 garLoopResultBuilder]: Registering result SAFE for location checkErr5REQUIRES_VIOLATIONMEMORY_DEREFERENCE (3 of 13 remaining) [2024-11-14 05:00:20,829 INFO L782 garLoopResultBuilder]: Registering result SAFE for location checkErr6REQUIRES_VIOLATIONMEMORY_DEREFERENCE (2 of 13 remaining) [2024-11-14 05:00:20,829 INFO L782 garLoopResultBuilder]: Registering result SAFE for location checkErr7REQUIRES_VIOLATIONMEMORY_DEREFERENCE (1 of 13 remaining) [2024-11-14 05:00:20,829 INFO L782 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONMEMORY_LEAK (0 of 13 remaining) [2024-11-14 05:00:20,853 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-14 05:00:21,033 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-11-14 05:00:21,036 INFO L407 BasicCegarLoop]: Path program histogram: [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 05:00:21,038 INFO L173 ceAbstractionStarter]: Computing trace abstraction results [2024-11-14 05:00:21,042 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 14.11 05:00:21 BoogieIcfgContainer [2024-11-14 05:00:21,042 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-14 05:00:21,043 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-14 05:00:21,043 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-14 05:00:21,043 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-14 05:00:21,044 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 04:59:41" (3/4) ... [2024-11-14 05:00:21,047 INFO L142 WitnessPrinter]: Generating witness for correct program [2024-11-14 05:00:21,051 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure assume_abort_if_not [2024-11-14 05:00:21,051 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure check [2024-11-14 05:00:21,051 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2024-11-14 05:00:21,056 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 29 nodes and edges [2024-11-14 05:00:21,056 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 8 nodes and edges [2024-11-14 05:00:21,056 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 4 nodes and edges [2024-11-14 05:00:21,056 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2024-11-14 05:00:21,168 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/witness.graphml [2024-11-14 05:00:21,168 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/witness.yml [2024-11-14 05:00:21,168 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-14 05:00:21,170 INFO L158 Benchmark]: Toolchain (without parser) took 41084.81ms. Allocated memory was 117.4MB in the beginning and 218.1MB in the end (delta: 100.7MB). Free memory was 92.2MB in the beginning and 103.3MB in the end (delta: -11.1MB). Peak memory consumption was 91.8MB. Max. memory is 16.1GB. [2024-11-14 05:00:21,172 INFO L158 Benchmark]: CDTParser took 1.03ms. Allocated memory is still 167.8MB. Free memory is still 103.9MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 05:00:21,173 INFO L158 Benchmark]: CACSL2BoogieTranslator took 271.14ms. Allocated memory is still 117.4MB. Free memory was 92.2MB in the beginning and 81.1MB in the end (delta: 11.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-14 05:00:21,173 INFO L158 Benchmark]: Boogie Procedure Inliner took 37.51ms. Allocated memory is still 117.4MB. Free memory was 81.1MB in the beginning and 80.0MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 05:00:21,175 INFO L158 Benchmark]: Boogie Preprocessor took 29.25ms. Allocated memory is still 117.4MB. Free memory was 80.0MB in the beginning and 79.1MB in the end (delta: 879.9kB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-14 05:00:21,175 INFO L158 Benchmark]: RCFGBuilder took 611.69ms. Allocated memory is still 117.4MB. Free memory was 79.1MB in the beginning and 62.0MB in the end (delta: 17.1MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. [2024-11-14 05:00:21,175 INFO L158 Benchmark]: TraceAbstraction took 39992.42ms. Allocated memory was 117.4MB in the beginning and 218.1MB in the end (delta: 100.7MB). Free memory was 61.2MB in the beginning and 108.6MB in the end (delta: -47.3MB). Peak memory consumption was 49.8MB. Max. memory is 16.1GB. [2024-11-14 05:00:21,176 INFO L158 Benchmark]: Witness Printer took 125.73ms. Allocated memory is still 218.1MB. Free memory was 108.6MB in the beginning and 103.3MB in the end (delta: 5.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-14 05:00:21,180 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 1.03ms. Allocated memory is still 167.8MB. Free memory is still 103.9MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 271.14ms. Allocated memory is still 117.4MB. Free memory was 92.2MB in the beginning and 81.1MB in the end (delta: 11.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 37.51ms. Allocated memory is still 117.4MB. Free memory was 81.1MB in the beginning and 80.0MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 29.25ms. Allocated memory is still 117.4MB. Free memory was 80.0MB in the beginning and 79.1MB in the end (delta: 879.9kB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * RCFGBuilder took 611.69ms. Allocated memory is still 117.4MB. Free memory was 79.1MB in the beginning and 62.0MB in the end (delta: 17.1MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. * TraceAbstraction took 39992.42ms. Allocated memory was 117.4MB in the beginning and 218.1MB in the end (delta: 100.7MB). Free memory was 61.2MB in the beginning and 108.6MB in the end (delta: -47.3MB). Peak memory consumption was 49.8MB. Max. memory is 16.1GB. * Witness Printer took 125.73ms. Allocated memory is still 218.1MB. Free memory was 108.6MB in the beginning and 103.3MB in the end (delta: 5.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 48]: free always succeeds For all program executions holds that free always succeeds at this location - PositiveResult [Line: 48]: free always succeeds For all program executions holds that free always succeeds at this location - PositiveResult [Line: 48]: free always succeeds For all program executions holds that free always succeeds at this location - PositiveResult [Line: 41]: all allocated memory was freed For all program executions holds that all allocated memory was freed at this location - PositiveResult [Line: -1]: pointer dereference always succeeds For all program executions holds that pointer dereference always succeeds at this location - PositiveResult [Line: -1]: pointer dereference always succeeds For all program executions holds that pointer dereference always succeeds at this location - PositiveResult [Line: -1]: pointer dereference always succeeds For all program executions holds that pointer dereference always succeeds at this location - PositiveResult [Line: -1]: pointer dereference always succeeds For all program executions holds that pointer dereference always succeeds at this location - PositiveResult [Line: -1]: pointer dereference always succeeds For all program executions holds that pointer dereference always succeeds at this location - PositiveResult [Line: -1]: pointer dereference always succeeds For all program executions holds that pointer dereference always succeeds at this location - PositiveResult [Line: -1]: pointer dereference always succeeds For all program executions holds that pointer dereference always succeeds at this location - PositiveResult [Line: -1]: pointer dereference always succeeds For all program executions holds that pointer dereference always succeeds at this location - PositiveResult [Line: 5]: all allocated memory was freed For all program executions holds that all allocated memory was freed at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 45 locations, 13 error locations. Started 1 CEGAR loops. OverallTime: 39.9s, OverallIterations: 15, TraceHistogramMax: 7, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 19.5s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 3 mSolverCounterUnknown, 790 SdHoareTripleChecker+Valid, 10.6s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 777 mSDsluCounter, 2410 SdHoareTripleChecker+Invalid, 10.0s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2032 mSDsCounter, 464 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 4921 IncrementalHoareTripleChecker+Invalid, 5388 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 464 mSolverCounterUnsat, 378 mSDtfsCounter, 4921 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 659 GetRequests, 296 SyntacticMatches, 11 SemanticMatches, 352 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3299 ImplicationChecksByTransitivity, 16.4s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=100occurred in iteration=12, InterpolantAutomatonStates: 208, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.2s AutomataMinimizationTime, 15 MinimizatonAttempts, 36 StatesRemovedByMinimization, 9 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.4s SatisfiabilityAnalysisTime, 17.5s InterpolantComputationTime, 674 NumberOfCodeBlocks, 630 NumberOfCodeBlocksAsserted, 26 NumberOfCheckSat, 728 ConstructedInterpolants, 29 QuantifiedInterpolants, 5512 SizeOfPredicates, 65 NumberOfNonLiveVariables, 1119 ConjunctsInSsa, 162 ConjunctsInUnsatCore, 25 InterpolantComputations, 9 PerfectInterpolantSequences, 414/569 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 13 specifications checked. All of them hold RESULT: Ultimate proved your program to be correct! [2024-11-14 05:00:21,208 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1a90195e-b4ab-4421-bebf-ef00bd66ddba/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE