./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/combinations/Problem05_label45+token_ring.03.cil-1.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version cf1a7837 Calling Ultimate with: /usr/lib/jvm/java-11-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/config/TaipanReach.xml -i ../../sv-benchmarks/c/combinations/Problem05_label45+token_ring.03.cil-1.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 7ec37a095871269c822e7d35e6d840f2de134a68f657807281a5c0e96980df26 --- Real Ultimate output --- This is Ultimate 0.2.3-dev-cf1a783 [2023-11-12 00:11:27,739 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-12 00:11:27,851 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-12 00:11:27,862 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-12 00:11:27,863 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-12 00:11:27,901 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-12 00:11:27,902 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-12 00:11:27,902 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-12 00:11:27,903 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-12 00:11:27,908 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-12 00:11:27,909 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-12 00:11:27,910 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-12 00:11:27,910 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-12 00:11:27,912 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-12 00:11:27,912 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-12 00:11:27,913 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-12 00:11:27,913 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-12 00:11:27,914 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-12 00:11:27,915 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-12 00:11:27,915 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-12 00:11:27,916 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-12 00:11:27,916 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-12 00:11:27,917 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-12 00:11:27,918 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-12 00:11:27,918 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-12 00:11:27,919 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-12 00:11:27,920 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-12 00:11:27,920 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-12 00:11:27,920 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-12 00:11:27,921 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-12 00:11:27,922 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-12 00:11:27,923 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-12 00:11:27,923 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-12 00:11:27,923 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-12 00:11:27,924 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-12 00:11:27,924 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-12 00:11:27,924 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 00:11:27,925 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-12 00:11:27,925 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-12 00:11:27,925 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-12 00:11:27,926 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-12 00:11:27,926 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-12 00:11:27,926 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-12 00:11:27,927 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-12 00:11:27,927 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-12 00:11:27,928 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX 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 ! call(reach_error())) ) 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 -> 7ec37a095871269c822e7d35e6d840f2de134a68f657807281a5c0e96980df26 [2023-11-12 00:11:28,235 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-12 00:11:28,260 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-12 00:11:28,265 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-12 00:11:28,267 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-12 00:11:28,267 INFO L274 PluginConnector]: CDTParser initialized [2023-11-12 00:11:28,270 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/../../sv-benchmarks/c/combinations/Problem05_label45+token_ring.03.cil-1.c [2023-11-12 00:11:31,359 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-12 00:11:32,072 INFO L384 CDTParser]: Found 1 translation units. [2023-11-12 00:11:32,073 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/sv-benchmarks/c/combinations/Problem05_label45+token_ring.03.cil-1.c [2023-11-12 00:11:32,149 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/data/450c7973c/2a0794cbe2364a838a00bd3287021625/FLAG888e3982b [2023-11-12 00:11:32,167 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/data/450c7973c/2a0794cbe2364a838a00bd3287021625 [2023-11-12 00:11:32,172 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-12 00:11:32,175 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-12 00:11:32,178 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-12 00:11:32,178 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-12 00:11:32,184 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-12 00:11:32,185 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 12:11:32" (1/1) ... [2023-11-12 00:11:32,186 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@61411b9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:11:32, skipping insertion in model container [2023-11-12 00:11:32,186 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 12:11:32" (1/1) ... [2023-11-12 00:11:32,497 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-12 00:11:34,794 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/sv-benchmarks/c/combinations/Problem05_label45+token_ring.03.cil-1.c[380323,380336] [2023-11-12 00:11:34,829 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/sv-benchmarks/c/combinations/Problem05_label45+token_ring.03.cil-1.c[383339,383352] [2023-11-12 00:11:35,086 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 00:11:35,098 INFO L202 MainTranslator]: Completed pre-run [2023-11-12 00:11:36,367 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/sv-benchmarks/c/combinations/Problem05_label45+token_ring.03.cil-1.c[380323,380336] [2023-11-12 00:11:36,373 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/sv-benchmarks/c/combinations/Problem05_label45+token_ring.03.cil-1.c[383339,383352] [2023-11-12 00:11:36,387 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 00:11:36,461 INFO L206 MainTranslator]: Completed translation [2023-11-12 00:11:36,462 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:11:36 WrapperNode [2023-11-12 00:11:36,462 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-12 00:11:36,463 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-12 00:11:36,464 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-12 00:11:36,464 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-12 00:11:36,471 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:11:36" (1/1) ... [2023-11-12 00:11:36,585 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:11:36" (1/1) ... [2023-11-12 00:11:36,984 INFO L138 Inliner]: procedures = 50, calls = 51, calls flagged for inlining = 27, calls inlined = 27, statements flattened = 12694 [2023-11-12 00:11:36,984 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-12 00:11:36,985 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-12 00:11:36,985 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-12 00:11:36,985 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-12 00:11:36,995 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:11:36" (1/1) ... [2023-11-12 00:11:36,995 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:11:36" (1/1) ... [2023-11-12 00:11:37,033 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:11:36" (1/1) ... [2023-11-12 00:11:37,034 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:11:36" (1/1) ... [2023-11-12 00:11:37,358 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:11:36" (1/1) ... [2023-11-12 00:11:37,416 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:11:36" (1/1) ... [2023-11-12 00:11:37,449 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:11:36" (1/1) ... [2023-11-12 00:11:37,490 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:11:36" (1/1) ... [2023-11-12 00:11:37,568 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-12 00:11:37,569 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-12 00:11:37,570 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-12 00:11:37,570 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-12 00:11:37,571 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:11:36" (1/1) ... [2023-11-12 00:11:37,579 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 00:11:37,608 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:11:37,645 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-12 00:11:37,727 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-12 00:11:37,791 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-12 00:11:37,792 INFO L130 BoogieDeclarations]: Found specification of procedure activate_threads [2023-11-12 00:11:37,792 INFO L138 BoogieDeclarations]: Found implementation of procedure activate_threads [2023-11-12 00:11:37,793 INFO L130 BoogieDeclarations]: Found specification of procedure immediate_notify [2023-11-12 00:11:37,794 INFO L138 BoogieDeclarations]: Found implementation of procedure immediate_notify [2023-11-12 00:11:37,794 INFO L130 BoogieDeclarations]: Found specification of procedure update_channels [2023-11-12 00:11:37,795 INFO L138 BoogieDeclarations]: Found implementation of procedure update_channels [2023-11-12 00:11:37,795 INFO L130 BoogieDeclarations]: Found specification of procedure error [2023-11-12 00:11:37,795 INFO L138 BoogieDeclarations]: Found implementation of procedure error [2023-11-12 00:11:37,795 INFO L130 BoogieDeclarations]: Found specification of procedure fire_delta_events [2023-11-12 00:11:37,795 INFO L138 BoogieDeclarations]: Found implementation of procedure fire_delta_events [2023-11-12 00:11:37,795 INFO L130 BoogieDeclarations]: Found specification of procedure exists_runnable_thread [2023-11-12 00:11:37,796 INFO L138 BoogieDeclarations]: Found implementation of procedure exists_runnable_thread [2023-11-12 00:11:37,796 INFO L130 BoogieDeclarations]: Found specification of procedure reset_delta_events [2023-11-12 00:11:37,796 INFO L138 BoogieDeclarations]: Found implementation of procedure reset_delta_events [2023-11-12 00:11:37,796 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-12 00:11:37,797 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-12 00:11:37,797 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-12 00:11:37,993 INFO L236 CfgBuilder]: Building ICFG [2023-11-12 00:11:38,009 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-12 00:11:47,231 INFO L277 CfgBuilder]: Performing block encoding [2023-11-12 00:11:49,536 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-12 00:11:49,536 INFO L302 CfgBuilder]: Removed 7 assume(true) statements. [2023-11-12 00:11:49,543 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 12:11:49 BoogieIcfgContainer [2023-11-12 00:11:49,543 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-12 00:11:49,546 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-12 00:11:49,546 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-12 00:11:49,549 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-12 00:11:49,550 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.11 12:11:32" (1/3) ... [2023-11-12 00:11:49,551 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1c54adf4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 12:11:49, skipping insertion in model container [2023-11-12 00:11:49,551 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:11:36" (2/3) ... [2023-11-12 00:11:49,551 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1c54adf4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 12:11:49, skipping insertion in model container [2023-11-12 00:11:49,551 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 12:11:49" (3/3) ... [2023-11-12 00:11:49,553 INFO L112 eAbstractionObserver]: Analyzing ICFG Problem05_label45+token_ring.03.cil-1.c [2023-11-12 00:11:49,574 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-12 00:11:49,574 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 2 error locations. [2023-11-12 00:11:49,683 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-12 00:11:49,690 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, 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;@2fa962bb, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-12 00:11:49,690 INFO L358 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2023-11-12 00:11:49,705 INFO L276 IsEmpty]: Start isEmpty. Operand has 1742 states, 1713 states have (on average 1.9725627553998832) internal successors, (3379), 1718 states have internal predecessors, (3379), 19 states have call successors, (19), 7 states have call predecessors, (19), 7 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2023-11-12 00:11:49,724 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2023-11-12 00:11:49,724 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:11:49,725 INFO L195 NwaCegarLoop]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:11:49,726 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:11:49,731 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:11:49,732 INFO L85 PathProgramCache]: Analyzing trace with hash 838533184, now seen corresponding path program 1 times [2023-11-12 00:11:49,739 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:11:49,739 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1432428854] [2023-11-12 00:11:49,740 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:11:49,740 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:11:49,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:11:50,161 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-12 00:11:50,161 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:11:50,162 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1432428854] [2023-11-12 00:11:50,162 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1432428854] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:11:50,163 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:11:50,163 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-11-12 00:11:50,164 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [27102405] [2023-11-12 00:11:50,166 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:11:50,171 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-12 00:11:50,171 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:11:50,208 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-12 00:11:50,209 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-12 00:11:50,216 INFO L87 Difference]: Start difference. First operand has 1742 states, 1713 states have (on average 1.9725627553998832) internal successors, (3379), 1718 states have internal predecessors, (3379), 19 states have call successors, (19), 7 states have call predecessors, (19), 7 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) Second operand has 4 states, 4 states have (on average 7.5) internal successors, (30), 4 states have internal predecessors, (30), 2 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-11-12 00:11:51,171 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:11:51,171 INFO L93 Difference]: Finished difference Result 3559 states and 6955 transitions. [2023-11-12 00:11:51,176 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-12 00:11:51,177 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 7.5) internal successors, (30), 4 states have internal predecessors, (30), 2 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 41 [2023-11-12 00:11:51,178 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:11:51,210 INFO L225 Difference]: With dead ends: 3559 [2023-11-12 00:11:51,210 INFO L226 Difference]: Without dead ends: 1816 [2023-11-12 00:11:51,222 INFO L412 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 [2023-11-12 00:11:51,226 INFO L413 NwaCegarLoop]: 3256 mSDtfsCounter, 3498 mSDsluCounter, 3192 mSDsCounter, 0 mSdLazyCounter, 586 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3498 SdHoareTripleChecker+Valid, 6448 SdHoareTripleChecker+Invalid, 600 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.1s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 586 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2023-11-12 00:11:51,228 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3498 Valid, 6448 Invalid, 600 Unknown, 0 Unchecked, 0.1s Time], IncrementalHoareTripleChecker [14 Valid, 586 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2023-11-12 00:11:51,251 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1816 states. [2023-11-12 00:11:51,391 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1816 to 1815. [2023-11-12 00:11:51,399 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1815 states, 1769 states have (on average 1.9479932165065008) internal successors, (3446), 1773 states have internal predecessors, (3446), 32 states have call successors, (32), 13 states have call predecessors, (32), 12 states have return successors, (30), 29 states have call predecessors, (30), 30 states have call successors, (30) [2023-11-12 00:11:51,413 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1815 states to 1815 states and 3508 transitions. [2023-11-12 00:11:51,415 INFO L78 Accepts]: Start accepts. Automaton has 1815 states and 3508 transitions. Word has length 41 [2023-11-12 00:11:51,415 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:11:51,415 INFO L495 AbstractCegarLoop]: Abstraction has 1815 states and 3508 transitions. [2023-11-12 00:11:51,416 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 7.5) internal successors, (30), 4 states have internal predecessors, (30), 2 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-11-12 00:11:51,416 INFO L276 IsEmpty]: Start isEmpty. Operand 1815 states and 3508 transitions. [2023-11-12 00:11:51,429 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2023-11-12 00:11:51,429 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:11:51,429 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:11:51,430 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-12 00:11:51,430 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:11:51,431 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:11:51,431 INFO L85 PathProgramCache]: Analyzing trace with hash 766175791, now seen corresponding path program 1 times [2023-11-12 00:11:51,432 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:11:51,432 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1861606204] [2023-11-12 00:11:51,433 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:11:51,433 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:11:51,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:11:51,685 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2023-11-12 00:11:51,686 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:11:51,686 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1861606204] [2023-11-12 00:11:51,686 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1861606204] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:11:51,687 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [179974657] [2023-11-12 00:11:51,687 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:11:51,687 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:11:51,687 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:11:51,691 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:11:51,724 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-12 00:11:51,948 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:11:51,952 INFO L262 TraceCheckSpWp]: Trace formula consists of 424 conjuncts, 2 conjunts are in the unsatisfiable core [2023-11-12 00:11:51,962 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:11:52,025 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 11 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-11-12 00:11:52,025 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 00:11:52,026 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [179974657] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:11:52,026 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 00:11:52,026 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [5] total 6 [2023-11-12 00:11:52,027 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [93558354] [2023-11-12 00:11:52,027 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:11:52,028 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-12 00:11:52,028 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:11:52,029 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-12 00:11:52,029 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-11-12 00:11:52,030 INFO L87 Difference]: Start difference. First operand 1815 states and 3508 transitions. Second operand has 3 states, 3 states have (on average 16.666666666666668) internal successors, (50), 2 states have internal predecessors, (50), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2023-11-12 00:11:52,542 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:11:52,542 INFO L93 Difference]: Finished difference Result 2146 states and 3973 transitions. [2023-11-12 00:11:52,542 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-12 00:11:52,543 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 16.666666666666668) internal successors, (50), 2 states have internal predecessors, (50), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 75 [2023-11-12 00:11:52,543 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:11:52,558 INFO L225 Difference]: With dead ends: 2146 [2023-11-12 00:11:52,559 INFO L226 Difference]: Without dead ends: 1977 [2023-11-12 00:11:52,560 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 75 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-11-12 00:11:52,562 INFO L413 NwaCegarLoop]: 3207 mSDtfsCounter, 3375 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 265 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3375 SdHoareTripleChecker+Valid, 3308 SdHoareTripleChecker+Invalid, 267 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 265 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-12 00:11:52,562 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3375 Valid, 3308 Invalid, 267 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 265 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-12 00:11:52,567 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1977 states. [2023-11-12 00:11:52,620 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1977 to 1971. [2023-11-12 00:11:52,625 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1971 states, 1889 states have (on average 1.9105346744309157) internal successors, (3609), 1894 states have internal predecessors, (3609), 56 states have call successors, (56), 25 states have call predecessors, (56), 24 states have return successors, (54), 52 states have call predecessors, (54), 54 states have call successors, (54) [2023-11-12 00:11:52,639 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1971 states to 1971 states and 3719 transitions. [2023-11-12 00:11:52,639 INFO L78 Accepts]: Start accepts. Automaton has 1971 states and 3719 transitions. Word has length 75 [2023-11-12 00:11:52,640 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:11:52,640 INFO L495 AbstractCegarLoop]: Abstraction has 1971 states and 3719 transitions. [2023-11-12 00:11:52,640 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 16.666666666666668) internal successors, (50), 2 states have internal predecessors, (50), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2023-11-12 00:11:52,640 INFO L276 IsEmpty]: Start isEmpty. Operand 1971 states and 3719 transitions. [2023-11-12 00:11:52,642 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2023-11-12 00:11:52,642 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:11:52,643 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:11:52,656 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-12 00:11:52,849 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:11:52,850 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:11:52,850 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:11:52,851 INFO L85 PathProgramCache]: Analyzing trace with hash 1895410417, now seen corresponding path program 1 times [2023-11-12 00:11:52,851 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:11:52,851 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1187917521] [2023-11-12 00:11:52,851 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:11:52,851 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:11:52,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:11:53,047 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2023-11-12 00:11:53,048 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:11:53,048 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1187917521] [2023-11-12 00:11:53,048 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1187917521] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:11:53,049 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1485230276] [2023-11-12 00:11:53,049 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:11:53,049 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:11:53,050 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:11:53,051 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:11:53,055 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-12 00:11:53,189 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:11:53,192 INFO L262 TraceCheckSpWp]: Trace formula consists of 418 conjuncts, 2 conjunts are in the unsatisfiable core [2023-11-12 00:11:53,196 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:11:53,245 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-11-12 00:11:53,245 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 00:11:53,245 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1485230276] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:11:53,245 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 00:11:53,246 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [5] total 6 [2023-11-12 00:11:53,246 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [839825020] [2023-11-12 00:11:53,246 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:11:53,247 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-12 00:11:53,247 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:11:53,248 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-12 00:11:53,248 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-11-12 00:11:53,248 INFO L87 Difference]: Start difference. First operand 1971 states and 3719 transitions. Second operand has 3 states, 3 states have (on average 15.666666666666666) internal successors, (47), 2 states have internal predecessors, (47), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2023-11-12 00:11:53,751 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:11:53,751 INFO L93 Difference]: Finished difference Result 2608 states and 4606 transitions. [2023-11-12 00:11:53,752 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-12 00:11:53,752 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 15.666666666666666) internal successors, (47), 2 states have internal predecessors, (47), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 75 [2023-11-12 00:11:53,752 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:11:53,768 INFO L225 Difference]: With dead ends: 2608 [2023-11-12 00:11:53,768 INFO L226 Difference]: Without dead ends: 2283 [2023-11-12 00:11:53,770 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 75 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-11-12 00:11:53,774 INFO L413 NwaCegarLoop]: 3205 mSDtfsCounter, 3378 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 265 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3378 SdHoareTripleChecker+Valid, 3306 SdHoareTripleChecker+Invalid, 267 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 265 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-12 00:11:53,775 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3378 Valid, 3306 Invalid, 267 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 265 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-12 00:11:53,780 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2283 states. [2023-11-12 00:11:53,860 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2283 to 2275. [2023-11-12 00:11:53,867 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2275 states, 2123 states have (on average 1.8478568064060292) internal successors, (3923), 2130 states have internal predecessors, (3923), 102 states have call successors, (102), 49 states have call predecessors, (102), 48 states have return successors, (100), 96 states have call predecessors, (100), 100 states have call successors, (100) [2023-11-12 00:11:53,886 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2275 states to 2275 states and 4125 transitions. [2023-11-12 00:11:53,887 INFO L78 Accepts]: Start accepts. Automaton has 2275 states and 4125 transitions. Word has length 75 [2023-11-12 00:11:53,887 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:11:53,887 INFO L495 AbstractCegarLoop]: Abstraction has 2275 states and 4125 transitions. [2023-11-12 00:11:53,887 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 15.666666666666666) internal successors, (47), 2 states have internal predecessors, (47), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2023-11-12 00:11:53,888 INFO L276 IsEmpty]: Start isEmpty. Operand 2275 states and 4125 transitions. [2023-11-12 00:11:53,891 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2023-11-12 00:11:53,892 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:11:53,892 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:11:53,899 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-12 00:11:54,098 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:11:54,098 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:11:54,099 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:11:54,099 INFO L85 PathProgramCache]: Analyzing trace with hash 445324015, now seen corresponding path program 1 times [2023-11-12 00:11:54,099 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:11:54,100 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [945425639] [2023-11-12 00:11:54,100 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:11:54,100 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:11:54,128 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:11:54,595 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2023-11-12 00:11:54,597 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:11:54,597 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [945425639] [2023-11-12 00:11:54,597 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [945425639] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:11:54,598 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:11:54,598 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2023-11-12 00:11:54,598 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [596555693] [2023-11-12 00:11:54,598 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:11:54,599 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-11-12 00:11:54,599 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:11:54,600 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-11-12 00:11:54,600 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2023-11-12 00:11:54,600 INFO L87 Difference]: Start difference. First operand 2275 states and 4125 transitions. Second operand has 6 states, 6 states have (on average 7.333333333333333) internal successors, (44), 6 states have internal predecessors, (44), 4 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2023-11-12 00:11:55,814 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:11:55,814 INFO L93 Difference]: Finished difference Result 3579 states and 5883 transitions. [2023-11-12 00:11:55,815 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-12 00:11:55,815 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 7.333333333333333) internal successors, (44), 6 states have internal predecessors, (44), 4 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) Word has length 75 [2023-11-12 00:11:55,817 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:11:55,840 INFO L225 Difference]: With dead ends: 3579 [2023-11-12 00:11:55,840 INFO L226 Difference]: Without dead ends: 2951 [2023-11-12 00:11:55,846 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=41, Invalid=69, Unknown=0, NotChecked=0, Total=110 [2023-11-12 00:11:55,849 INFO L413 NwaCegarLoop]: 3175 mSDtfsCounter, 3577 mSDsluCounter, 9412 mSDsCounter, 0 mSdLazyCounter, 1054 mSolverCounterSat, 82 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3589 SdHoareTripleChecker+Valid, 12587 SdHoareTripleChecker+Invalid, 1136 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.1s SdHoareTripleChecker+Time, 82 IncrementalHoareTripleChecker+Valid, 1054 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2023-11-12 00:11:55,850 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3589 Valid, 12587 Invalid, 1136 Unknown, 0 Unchecked, 0.1s Time], IncrementalHoareTripleChecker [82 Valid, 1054 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2023-11-12 00:11:55,857 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2951 states. [2023-11-12 00:11:55,987 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2951 to 2851. [2023-11-12 00:11:55,994 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2851 states, 2563 states have (on average 1.7569254779555208) internal successors, (4503), 2574 states have internal predecessors, (4503), 190 states have call successors, (190), 97 states have call predecessors, (190), 96 states have return successors, (188), 180 states have call predecessors, (188), 188 states have call successors, (188) [2023-11-12 00:11:56,013 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2851 states to 2851 states and 4881 transitions. [2023-11-12 00:11:56,013 INFO L78 Accepts]: Start accepts. Automaton has 2851 states and 4881 transitions. Word has length 75 [2023-11-12 00:11:56,014 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:11:56,014 INFO L495 AbstractCegarLoop]: Abstraction has 2851 states and 4881 transitions. [2023-11-12 00:11:56,015 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 7.333333333333333) internal successors, (44), 6 states have internal predecessors, (44), 4 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2023-11-12 00:11:56,015 INFO L276 IsEmpty]: Start isEmpty. Operand 2851 states and 4881 transitions. [2023-11-12 00:11:56,018 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2023-11-12 00:11:56,018 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:11:56,019 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:11:56,019 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2023-11-12 00:11:56,019 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:11:56,019 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:11:56,020 INFO L85 PathProgramCache]: Analyzing trace with hash -1850500433, now seen corresponding path program 1 times [2023-11-12 00:11:56,020 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:11:56,025 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2146079302] [2023-11-12 00:11:56,026 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:11:56,026 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:11:56,049 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:11:56,289 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 10 proven. 14 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2023-11-12 00:11:56,289 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:11:56,289 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2146079302] [2023-11-12 00:11:56,290 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2146079302] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:11:56,290 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1077553148] [2023-11-12 00:11:56,290 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:11:56,290 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:11:56,290 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:11:56,291 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:11:56,319 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-12 00:11:56,457 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:11:56,460 INFO L262 TraceCheckSpWp]: Trace formula consists of 443 conjuncts, 2 conjunts are in the unsatisfiable core [2023-11-12 00:11:56,464 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:11:56,618 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 19 proven. 0 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2023-11-12 00:11:56,618 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 00:11:56,618 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1077553148] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:11:56,618 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 00:11:56,619 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [6] total 7 [2023-11-12 00:11:56,619 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1262164410] [2023-11-12 00:11:56,619 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:11:56,620 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-12 00:11:56,620 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:11:56,620 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-12 00:11:56,621 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2023-11-12 00:11:56,621 INFO L87 Difference]: Start difference. First operand 2851 states and 4881 transitions. Second operand has 3 states, 3 states have (on average 17.666666666666668) internal successors, (53), 3 states have internal predecessors, (53), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2023-11-12 00:11:57,334 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:11:57,334 INFO L93 Difference]: Finished difference Result 3802 states and 6174 transitions. [2023-11-12 00:11:57,335 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-12 00:11:57,335 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 17.666666666666668) internal successors, (53), 3 states have internal predecessors, (53), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 89 [2023-11-12 00:11:57,336 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:11:57,357 INFO L225 Difference]: With dead ends: 3802 [2023-11-12 00:11:57,357 INFO L226 Difference]: Without dead ends: 3166 [2023-11-12 00:11:57,361 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 91 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2023-11-12 00:11:57,362 INFO L413 NwaCegarLoop]: 3218 mSDtfsCounter, 47 mSDsluCounter, 3168 mSDsCounter, 0 mSdLazyCounter, 482 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 6386 SdHoareTripleChecker+Invalid, 482 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 482 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-12 00:11:57,362 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 6386 Invalid, 482 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 482 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-12 00:11:57,368 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3166 states. [2023-11-12 00:11:57,514 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3166 to 3035. [2023-11-12 00:11:57,522 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3035 states, 2731 states have (on average 1.7396558037348957) internal successors, (4751), 2742 states have internal predecessors, (4751), 198 states have call successors, (198), 105 states have call predecessors, (198), 104 states have return successors, (196), 188 states have call predecessors, (196), 196 states have call successors, (196) [2023-11-12 00:11:57,551 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3035 states to 3035 states and 5145 transitions. [2023-11-12 00:11:57,552 INFO L78 Accepts]: Start accepts. Automaton has 3035 states and 5145 transitions. Word has length 89 [2023-11-12 00:11:57,554 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:11:57,554 INFO L495 AbstractCegarLoop]: Abstraction has 3035 states and 5145 transitions. [2023-11-12 00:11:57,554 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 17.666666666666668) internal successors, (53), 3 states have internal predecessors, (53), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2023-11-12 00:11:57,555 INFO L276 IsEmpty]: Start isEmpty. Operand 3035 states and 5145 transitions. [2023-11-12 00:11:57,567 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2023-11-12 00:11:57,567 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:11:57,567 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 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, 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, 1, 1, 1, 1] [2023-11-12 00:11:57,575 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-12 00:11:57,774 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:11:57,774 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:11:57,774 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:11:57,775 INFO L85 PathProgramCache]: Analyzing trace with hash 1458882092, now seen corresponding path program 1 times [2023-11-12 00:11:57,775 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:11:57,775 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [251086100] [2023-11-12 00:11:57,775 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:11:57,775 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:11:57,803 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:11:57,865 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2023-11-12 00:11:57,865 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:11:57,866 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [251086100] [2023-11-12 00:11:57,866 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [251086100] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:11:57,866 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:11:57,866 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-12 00:11:57,867 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1735406935] [2023-11-12 00:11:57,867 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:11:57,867 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-12 00:11:57,868 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:11:57,868 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-12 00:11:57,868 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-12 00:11:57,869 INFO L87 Difference]: Start difference. First operand 3035 states and 5145 transitions. Second operand has 3 states, 3 states have (on average 17.333333333333332) internal successors, (52), 3 states have internal predecessors, (52), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2023-11-12 00:11:58,467 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:11:58,467 INFO L93 Difference]: Finished difference Result 5116 states and 7974 transitions. [2023-11-12 00:11:58,468 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-12 00:11:58,468 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 17.333333333333332) internal successors, (52), 3 states have internal predecessors, (52), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 99 [2023-11-12 00:11:58,468 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:11:58,493 INFO L225 Difference]: With dead ends: 5116 [2023-11-12 00:11:58,494 INFO L226 Difference]: Without dead ends: 3727 [2023-11-12 00:11:58,500 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-12 00:11:58,501 INFO L413 NwaCegarLoop]: 3207 mSDtfsCounter, 3370 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 265 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3370 SdHoareTripleChecker+Valid, 3308 SdHoareTripleChecker+Invalid, 267 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 265 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-12 00:11:58,501 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3370 Valid, 3308 Invalid, 267 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 265 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-12 00:11:58,509 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3727 states. [2023-11-12 00:11:58,713 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3727 to 3711. [2023-11-12 00:11:58,724 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3711 states, 3263 states have (on average 1.6705485749310451) internal successors, (5451), 3278 states have internal predecessors, (5451), 290 states have call successors, (290), 157 states have call predecessors, (290), 156 states have return successors, (288), 276 states have call predecessors, (288), 288 states have call successors, (288) [2023-11-12 00:11:58,750 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3711 states to 3711 states and 6029 transitions. [2023-11-12 00:11:58,751 INFO L78 Accepts]: Start accepts. Automaton has 3711 states and 6029 transitions. Word has length 99 [2023-11-12 00:11:58,752 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:11:58,752 INFO L495 AbstractCegarLoop]: Abstraction has 3711 states and 6029 transitions. [2023-11-12 00:11:58,752 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 17.333333333333332) internal successors, (52), 3 states have internal predecessors, (52), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2023-11-12 00:11:58,752 INFO L276 IsEmpty]: Start isEmpty. Operand 3711 states and 6029 transitions. [2023-11-12 00:11:58,762 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 114 [2023-11-12 00:11:58,762 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:11:58,763 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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, 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] [2023-11-12 00:11:58,763 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2023-11-12 00:11:58,764 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:11:58,766 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:11:58,766 INFO L85 PathProgramCache]: Analyzing trace with hash -259389972, now seen corresponding path program 1 times [2023-11-12 00:11:58,766 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:11:58,766 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [591761937] [2023-11-12 00:11:58,767 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:11:58,767 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:11:58,796 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:11:59,094 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 10 proven. 27 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2023-11-12 00:11:59,095 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:11:59,095 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [591761937] [2023-11-12 00:11:59,095 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [591761937] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:11:59,096 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [672026936] [2023-11-12 00:11:59,096 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:11:59,096 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:11:59,097 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:11:59,098 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:11:59,123 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-12 00:11:59,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:11:59,269 INFO L262 TraceCheckSpWp]: Trace formula consists of 544 conjuncts, 3 conjunts are in the unsatisfiable core [2023-11-12 00:11:59,274 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:11:59,318 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 62 proven. 0 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2023-11-12 00:11:59,318 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 00:11:59,319 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [672026936] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:11:59,319 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 00:11:59,319 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [6] total 7 [2023-11-12 00:11:59,319 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1270561767] [2023-11-12 00:11:59,320 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:11:59,320 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-12 00:11:59,320 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:11:59,321 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-12 00:11:59,321 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2023-11-12 00:11:59,322 INFO L87 Difference]: Start difference. First operand 3711 states and 6029 transitions. Second operand has 3 states, 3 states have (on average 27.0) internal successors, (81), 3 states have internal predecessors, (81), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2023-11-12 00:12:00,061 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:12:00,061 INFO L93 Difference]: Finished difference Result 5111 states and 7995 transitions. [2023-11-12 00:12:00,061 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-12 00:12:00,062 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 27.0) internal successors, (81), 3 states have internal predecessors, (81), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 113 [2023-11-12 00:12:00,062 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:12:00,087 INFO L225 Difference]: With dead ends: 5111 [2023-11-12 00:12:00,087 INFO L226 Difference]: Without dead ends: 3723 [2023-11-12 00:12:00,093 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 115 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2023-11-12 00:12:00,094 INFO L413 NwaCegarLoop]: 3221 mSDtfsCounter, 102 mSDsluCounter, 3158 mSDsCounter, 0 mSdLazyCounter, 482 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 102 SdHoareTripleChecker+Valid, 6379 SdHoareTripleChecker+Invalid, 484 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 482 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-12 00:12:00,095 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [102 Valid, 6379 Invalid, 484 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 482 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-12 00:12:00,101 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3723 states. [2023-11-12 00:12:00,301 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3723 to 3703. [2023-11-12 00:12:00,311 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3703 states, 3255 states have (on average 1.6599078341013824) internal successors, (5403), 3270 states have internal predecessors, (5403), 290 states have call successors, (290), 157 states have call predecessors, (290), 156 states have return successors, (288), 276 states have call predecessors, (288), 288 states have call successors, (288) [2023-11-12 00:12:00,479 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3703 states to 3703 states and 5981 transitions. [2023-11-12 00:12:00,480 INFO L78 Accepts]: Start accepts. Automaton has 3703 states and 5981 transitions. Word has length 113 [2023-11-12 00:12:00,480 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:12:00,480 INFO L495 AbstractCegarLoop]: Abstraction has 3703 states and 5981 transitions. [2023-11-12 00:12:00,481 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 27.0) internal successors, (81), 3 states have internal predecessors, (81), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2023-11-12 00:12:00,481 INFO L276 IsEmpty]: Start isEmpty. Operand 3703 states and 5981 transitions. [2023-11-12 00:12:00,489 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 114 [2023-11-12 00:12:00,489 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:12:00,489 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:12:00,498 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2023-11-12 00:12:00,698 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:12:00,698 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:12:00,698 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:12:00,699 INFO L85 PathProgramCache]: Analyzing trace with hash 905882892, now seen corresponding path program 1 times [2023-11-12 00:12:00,699 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:12:00,699 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1731980285] [2023-11-12 00:12:00,699 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:12:00,699 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:12:00,723 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:12:00,958 INFO L134 CoverageAnalysis]: Checked inductivity of 71 backedges. 10 proven. 25 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2023-11-12 00:12:00,958 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:12:00,958 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1731980285] [2023-11-12 00:12:00,959 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1731980285] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:12:00,959 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1204823489] [2023-11-12 00:12:00,959 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:12:00,959 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:12:00,959 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:12:00,961 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:12:00,968 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-12 00:12:01,119 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:12:01,122 INFO L262 TraceCheckSpWp]: Trace formula consists of 550 conjuncts, 2 conjunts are in the unsatisfiable core [2023-11-12 00:12:01,127 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:12:01,157 INFO L134 CoverageAnalysis]: Checked inductivity of 71 backedges. 51 proven. 0 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2023-11-12 00:12:01,157 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 00:12:01,158 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1204823489] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:12:01,158 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 00:12:01,158 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [6] total 7 [2023-11-12 00:12:01,158 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1564637232] [2023-11-12 00:12:01,158 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:12:01,159 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-12 00:12:01,159 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:12:01,160 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-12 00:12:01,160 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2023-11-12 00:12:01,160 INFO L87 Difference]: Start difference. First operand 3703 states and 5981 transitions. Second operand has 3 states, 3 states have (on average 25.0) internal successors, (75), 3 states have internal predecessors, (75), 3 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (10), 2 states have call predecessors, (10), 3 states have call successors, (10) [2023-11-12 00:12:01,673 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:12:01,674 INFO L93 Difference]: Finished difference Result 5523 states and 8362 transitions. [2023-11-12 00:12:01,674 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-12 00:12:01,675 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 25.0) internal successors, (75), 3 states have internal predecessors, (75), 3 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (10), 2 states have call predecessors, (10), 3 states have call successors, (10) Word has length 113 [2023-11-12 00:12:01,675 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:12:01,699 INFO L225 Difference]: With dead ends: 5523 [2023-11-12 00:12:01,700 INFO L226 Difference]: Without dead ends: 4151 [2023-11-12 00:12:01,705 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 115 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2023-11-12 00:12:01,706 INFO L413 NwaCegarLoop]: 3178 mSDtfsCounter, 3380 mSDsluCounter, 24 mSDsCounter, 0 mSdLazyCounter, 242 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3380 SdHoareTripleChecker+Valid, 3202 SdHoareTripleChecker+Invalid, 246 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 242 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-12 00:12:01,706 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3380 Valid, 3202 Invalid, 246 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 242 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-12 00:12:01,713 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4151 states. [2023-11-12 00:12:01,887 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4151 to 4151. [2023-11-12 00:12:01,910 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4151 states, 3639 states have (on average 1.606760098928277) internal successors, (5847), 3654 states have internal predecessors, (5847), 310 states have call successors, (310), 201 states have call predecessors, (310), 200 states have return successors, (308), 296 states have call predecessors, (308), 308 states have call successors, (308) [2023-11-12 00:12:01,922 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4151 states to 4151 states and 6465 transitions. [2023-11-12 00:12:01,923 INFO L78 Accepts]: Start accepts. Automaton has 4151 states and 6465 transitions. Word has length 113 [2023-11-12 00:12:01,923 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:12:01,923 INFO L495 AbstractCegarLoop]: Abstraction has 4151 states and 6465 transitions. [2023-11-12 00:12:01,924 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 25.0) internal successors, (75), 3 states have internal predecessors, (75), 3 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (10), 2 states have call predecessors, (10), 3 states have call successors, (10) [2023-11-12 00:12:01,924 INFO L276 IsEmpty]: Start isEmpty. Operand 4151 states and 6465 transitions. [2023-11-12 00:12:01,932 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2023-11-12 00:12:01,932 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:12:01,932 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:12:01,944 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-12 00:12:02,139 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:12:02,140 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:12:02,140 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:12:02,140 INFO L85 PathProgramCache]: Analyzing trace with hash -734517839, now seen corresponding path program 1 times [2023-11-12 00:12:02,140 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:12:02,141 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [750858241] [2023-11-12 00:12:02,141 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:12:02,141 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:12:02,158 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:12:02,379 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 10 proven. 26 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2023-11-12 00:12:02,380 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:12:02,380 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [750858241] [2023-11-12 00:12:02,380 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [750858241] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:12:02,380 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1216764272] [2023-11-12 00:12:02,381 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:12:02,381 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:12:02,381 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:12:02,382 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:12:02,388 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-12 00:12:02,547 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:12:02,550 INFO L262 TraceCheckSpWp]: Trace formula consists of 549 conjuncts, 3 conjunts are in the unsatisfiable core [2023-11-12 00:12:02,555 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:12:02,583 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 54 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2023-11-12 00:12:02,583 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 00:12:02,583 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1216764272] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:12:02,584 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 00:12:02,584 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [6] total 7 [2023-11-12 00:12:02,584 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [860138957] [2023-11-12 00:12:02,584 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:12:02,585 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-12 00:12:02,585 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:12:02,585 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-12 00:12:02,586 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2023-11-12 00:12:02,586 INFO L87 Difference]: Start difference. First operand 4151 states and 6465 transitions. Second operand has 3 states, 3 states have (on average 26.333333333333332) internal successors, (79), 3 states have internal predecessors, (79), 3 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2023-11-12 00:12:03,256 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:12:03,257 INFO L93 Difference]: Finished difference Result 7559 states and 10884 transitions. [2023-11-12 00:12:03,257 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-12 00:12:03,258 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 26.333333333333332) internal successors, (79), 3 states have internal predecessors, (79), 3 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 114 [2023-11-12 00:12:03,258 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:12:03,281 INFO L225 Difference]: With dead ends: 7559 [2023-11-12 00:12:03,281 INFO L226 Difference]: Without dead ends: 5055 [2023-11-12 00:12:03,289 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 116 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2023-11-12 00:12:03,290 INFO L413 NwaCegarLoop]: 3181 mSDtfsCounter, 60 mSDsluCounter, 3149 mSDsCounter, 0 mSdLazyCounter, 472 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 60 SdHoareTripleChecker+Valid, 6330 SdHoareTripleChecker+Invalid, 474 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 472 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-12 00:12:03,290 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [60 Valid, 6330 Invalid, 474 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 472 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-12 00:12:03,298 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 5055 states. [2023-11-12 00:12:03,664 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 5055 to 4415. [2023-11-12 00:12:03,671 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4415 states, 3875 states have (on average 1.5976774193548386) internal successors, (6191), 3891 states have internal predecessors, (6191), 324 states have call successors, (324), 215 states have call predecessors, (324), 214 states have return successors, (322), 309 states have call predecessors, (322), 322 states have call successors, (322) [2023-11-12 00:12:03,684 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4415 states to 4415 states and 6837 transitions. [2023-11-12 00:12:03,684 INFO L78 Accepts]: Start accepts. Automaton has 4415 states and 6837 transitions. Word has length 114 [2023-11-12 00:12:03,685 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:12:03,685 INFO L495 AbstractCegarLoop]: Abstraction has 4415 states and 6837 transitions. [2023-11-12 00:12:03,685 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 26.333333333333332) internal successors, (79), 3 states have internal predecessors, (79), 3 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2023-11-12 00:12:03,685 INFO L276 IsEmpty]: Start isEmpty. Operand 4415 states and 6837 transitions. [2023-11-12 00:12:03,696 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2023-11-12 00:12:03,696 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:12:03,697 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:12:03,711 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-12 00:12:03,904 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:12:03,904 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:12:03,904 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:12:03,905 INFO L85 PathProgramCache]: Analyzing trace with hash -360799152, now seen corresponding path program 1 times [2023-11-12 00:12:03,905 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:12:03,905 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1366781378] [2023-11-12 00:12:03,905 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:12:03,905 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:12:03,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:12:04,021 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 23 proven. 1 refuted. 0 times theorem prover too weak. 49 trivial. 0 not checked. [2023-11-12 00:12:04,021 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:12:04,022 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1366781378] [2023-11-12 00:12:04,024 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1366781378] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:12:04,024 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [186964414] [2023-11-12 00:12:04,024 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:12:04,024 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:12:04,025 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:12:04,031 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:12:04,035 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-12 00:12:04,193 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:12:04,196 INFO L262 TraceCheckSpWp]: Trace formula consists of 546 conjuncts, 2 conjunts are in the unsatisfiable core [2023-11-12 00:12:04,198 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:12:04,223 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 59 proven. 0 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2023-11-12 00:12:04,223 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 00:12:04,223 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [186964414] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:12:04,223 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 00:12:04,224 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [5] total 6 [2023-11-12 00:12:04,224 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1045094908] [2023-11-12 00:12:04,224 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:12:04,225 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-12 00:12:04,225 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:12:04,225 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-12 00:12:04,225 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2023-11-12 00:12:04,226 INFO L87 Difference]: Start difference. First operand 4415 states and 6837 transitions. Second operand has 3 states, 3 states have (on average 26.0) internal successors, (78), 3 states have internal predecessors, (78), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2023-11-12 00:12:04,930 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:12:04,931 INFO L93 Difference]: Finished difference Result 6851 states and 10037 transitions. [2023-11-12 00:12:04,931 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-12 00:12:04,932 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 26.0) internal successors, (78), 3 states have internal predecessors, (78), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 114 [2023-11-12 00:12:04,932 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:12:04,948 INFO L225 Difference]: With dead ends: 6851 [2023-11-12 00:12:04,948 INFO L226 Difference]: Without dead ends: 5013 [2023-11-12 00:12:04,955 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 118 GetRequests, 114 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2023-11-12 00:12:04,956 INFO L413 NwaCegarLoop]: 3216 mSDtfsCounter, 63 mSDsluCounter, 3168 mSDsCounter, 0 mSdLazyCounter, 479 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 63 SdHoareTripleChecker+Valid, 6384 SdHoareTripleChecker+Invalid, 479 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 479 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-12 00:12:04,956 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [63 Valid, 6384 Invalid, 479 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 479 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-12 00:12:04,964 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 5013 states. [2023-11-12 00:12:05,165 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 5013 to 4735. [2023-11-12 00:12:05,173 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4735 states, 4163 states have (on average 1.5909200096084555) internal successors, (6623), 4179 states have internal predecessors, (6623), 340 states have call successors, (340), 231 states have call predecessors, (340), 230 states have return successors, (338), 325 states have call predecessors, (338), 338 states have call successors, (338) [2023-11-12 00:12:05,187 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4735 states to 4735 states and 7301 transitions. [2023-11-12 00:12:05,188 INFO L78 Accepts]: Start accepts. Automaton has 4735 states and 7301 transitions. Word has length 114 [2023-11-12 00:12:05,188 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:12:05,188 INFO L495 AbstractCegarLoop]: Abstraction has 4735 states and 7301 transitions. [2023-11-12 00:12:05,188 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 26.0) internal successors, (78), 3 states have internal predecessors, (78), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2023-11-12 00:12:05,189 INFO L276 IsEmpty]: Start isEmpty. Operand 4735 states and 7301 transitions. [2023-11-12 00:12:05,198 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2023-11-12 00:12:05,198 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:12:05,198 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:12:05,212 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-12 00:12:05,405 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-11-12 00:12:05,405 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:12:05,406 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:12:05,406 INFO L85 PathProgramCache]: Analyzing trace with hash -910457734, now seen corresponding path program 1 times [2023-11-12 00:12:05,406 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:12:05,406 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1710680843] [2023-11-12 00:12:05,406 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:12:05,406 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:12:05,426 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:12:05,663 INFO L134 CoverageAnalysis]: Checked inductivity of 75 backedges. 19 proven. 26 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-11-12 00:12:05,663 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:12:05,663 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1710680843] [2023-11-12 00:12:05,663 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1710680843] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:12:05,663 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [902390414] [2023-11-12 00:12:05,663 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:12:05,664 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:12:05,664 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:12:05,665 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:12:05,668 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-12 00:12:05,827 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:12:05,830 INFO L262 TraceCheckSpWp]: Trace formula consists of 555 conjuncts, 9 conjunts are in the unsatisfiable core [2023-11-12 00:12:05,834 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:12:05,973 INFO L134 CoverageAnalysis]: Checked inductivity of 75 backedges. 49 proven. 0 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2023-11-12 00:12:05,973 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 00:12:05,974 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [902390414] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:12:05,974 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 00:12:05,974 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 7 [2023-11-12 00:12:05,975 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1763468234] [2023-11-12 00:12:05,975 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:12:05,976 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-11-12 00:12:05,976 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:12:05,976 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-11-12 00:12:05,977 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2023-11-12 00:12:05,977 INFO L87 Difference]: Start difference. First operand 4735 states and 7301 transitions. Second operand has 6 states, 6 states have (on average 12.5) internal successors, (75), 6 states have internal predecessors, (75), 3 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2023-11-12 00:12:07,155 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:12:07,155 INFO L93 Difference]: Finished difference Result 9247 states and 13153 transitions. [2023-11-12 00:12:07,156 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-11-12 00:12:07,156 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 12.5) internal successors, (75), 6 states have internal predecessors, (75), 3 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 116 [2023-11-12 00:12:07,156 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:12:07,181 INFO L225 Difference]: With dead ends: 9247 [2023-11-12 00:12:07,181 INFO L226 Difference]: Without dead ends: 6159 [2023-11-12 00:12:07,190 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 118 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2023-11-12 00:12:07,191 INFO L413 NwaCegarLoop]: 3171 mSDtfsCounter, 3554 mSDsluCounter, 6310 mSDsCounter, 0 mSdLazyCounter, 789 mSolverCounterSat, 85 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3566 SdHoareTripleChecker+Valid, 9481 SdHoareTripleChecker+Invalid, 874 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 85 IncrementalHoareTripleChecker+Valid, 789 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2023-11-12 00:12:07,191 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3566 Valid, 9481 Invalid, 874 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [85 Valid, 789 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2023-11-12 00:12:07,201 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 6159 states. [2023-11-12 00:12:07,510 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 6159 to 6155. [2023-11-12 00:12:07,520 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6155 states, 5313 states have (on average 1.5187276491624317) internal successors, (8069), 5335 states have internal predecessors, (8069), 498 states have call successors, (498), 343 states have call predecessors, (498), 342 states have return successors, (496), 477 states have call predecessors, (496), 496 states have call successors, (496) [2023-11-12 00:12:07,538 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6155 states to 6155 states and 9063 transitions. [2023-11-12 00:12:07,539 INFO L78 Accepts]: Start accepts. Automaton has 6155 states and 9063 transitions. Word has length 116 [2023-11-12 00:12:07,539 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:12:07,540 INFO L495 AbstractCegarLoop]: Abstraction has 6155 states and 9063 transitions. [2023-11-12 00:12:07,540 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 12.5) internal successors, (75), 6 states have internal predecessors, (75), 3 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2023-11-12 00:12:07,540 INFO L276 IsEmpty]: Start isEmpty. Operand 6155 states and 9063 transitions. [2023-11-12 00:12:07,552 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 118 [2023-11-12 00:12:07,553 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:12:07,553 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:12:07,564 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-11-12 00:12:07,758 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:12:07,759 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:12:07,759 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:12:07,759 INFO L85 PathProgramCache]: Analyzing trace with hash -758350572, now seen corresponding path program 1 times [2023-11-12 00:12:07,759 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:12:07,760 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [493561888] [2023-11-12 00:12:07,760 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:12:07,760 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:12:07,787 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:12:07,876 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 22 proven. 4 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2023-11-12 00:12:07,876 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:12:07,876 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [493561888] [2023-11-12 00:12:07,876 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [493561888] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:12:07,876 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1576534586] [2023-11-12 00:12:07,876 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:12:07,877 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:12:07,877 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:12:07,878 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:12:07,907 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-11-12 00:12:08,041 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:12:08,044 INFO L262 TraceCheckSpWp]: Trace formula consists of 559 conjuncts, 2 conjunts are in the unsatisfiable core [2023-11-12 00:12:08,048 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:12:08,076 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 59 proven. 0 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2023-11-12 00:12:08,076 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 00:12:08,076 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1576534586] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:12:08,076 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 00:12:08,076 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [5] total 6 [2023-11-12 00:12:08,077 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [478753483] [2023-11-12 00:12:08,077 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:12:08,077 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-12 00:12:08,077 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:12:08,078 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-12 00:12:08,078 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2023-11-12 00:12:08,078 INFO L87 Difference]: Start difference. First operand 6155 states and 9063 transitions. Second operand has 3 states, 3 states have (on average 27.0) internal successors, (81), 3 states have internal predecessors, (81), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2023-11-12 00:12:09,030 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:12:09,031 INFO L93 Difference]: Finished difference Result 10223 states and 14395 transitions. [2023-11-12 00:12:09,031 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-12 00:12:09,031 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 27.0) internal successors, (81), 3 states have internal predecessors, (81), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 117 [2023-11-12 00:12:09,032 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:12:09,055 INFO L225 Difference]: With dead ends: 10223 [2023-11-12 00:12:09,055 INFO L226 Difference]: Without dead ends: 7215 [2023-11-12 00:12:09,064 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 117 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2023-11-12 00:12:09,065 INFO L413 NwaCegarLoop]: 3222 mSDtfsCounter, 67 mSDsluCounter, 3168 mSDsCounter, 0 mSdLazyCounter, 481 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 67 SdHoareTripleChecker+Valid, 6390 SdHoareTripleChecker+Invalid, 481 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 481 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-12 00:12:09,065 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [67 Valid, 6390 Invalid, 481 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 481 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-12 00:12:09,074 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7215 states. [2023-11-12 00:12:09,439 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7215 to 6707. [2023-11-12 00:12:09,448 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6707 states, 5801 states have (on average 1.5095673159800034) internal successors, (8757), 5823 states have internal predecessors, (8757), 530 states have call successors, (530), 375 states have call predecessors, (530), 374 states have return successors, (528), 509 states have call predecessors, (528), 528 states have call successors, (528) [2023-11-12 00:12:09,468 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6707 states to 6707 states and 9815 transitions. [2023-11-12 00:12:09,468 INFO L78 Accepts]: Start accepts. Automaton has 6707 states and 9815 transitions. Word has length 117 [2023-11-12 00:12:09,469 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:12:09,469 INFO L495 AbstractCegarLoop]: Abstraction has 6707 states and 9815 transitions. [2023-11-12 00:12:09,469 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 27.0) internal successors, (81), 3 states have internal predecessors, (81), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2023-11-12 00:12:09,469 INFO L276 IsEmpty]: Start isEmpty. Operand 6707 states and 9815 transitions. [2023-11-12 00:12:09,484 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 124 [2023-11-12 00:12:09,484 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:12:09,484 INFO L195 NwaCegarLoop]: trace histogram [5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 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, 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, 1, 1, 1, 1, 1] [2023-11-12 00:12:09,494 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-11-12 00:12:09,690 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:12:09,691 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:12:09,691 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:12:09,691 INFO L85 PathProgramCache]: Analyzing trace with hash -677666488, now seen corresponding path program 1 times [2023-11-12 00:12:09,691 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:12:09,691 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1136956695] [2023-11-12 00:12:09,691 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:12:09,692 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:12:09,715 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:12:10,095 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 12 proven. 26 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2023-11-12 00:12:10,095 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:12:10,095 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1136956695] [2023-11-12 00:12:10,095 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1136956695] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:12:10,096 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [450806059] [2023-11-12 00:12:10,096 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:12:10,096 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:12:10,096 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:12:10,097 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:12:10,131 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_df62914a-9ed3-4a5d-866f-b22aaf422013/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-11-12 00:12:10,289 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:12:10,293 INFO L262 TraceCheckSpWp]: Trace formula consists of 627 conjuncts, 15 conjunts are in the unsatisfiable core [2023-11-12 00:12:10,297 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:12:10,444 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 62 proven. 14 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-11-12 00:12:10,444 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:12:10,869 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 17 proven. 3 refuted. 0 times theorem prover too weak. 62 trivial. 0 not checked. [2023-11-12 00:12:10,869 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [450806059] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:12:10,870 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [723035369] [2023-11-12 00:12:10,897 INFO L159 IcfgInterpreter]: Started Sifa with 71 locations of interest [2023-11-12 00:12:10,898 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:12:10,902 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:12:10,907 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:12:10,908 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs