./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/combinations/Problem05_label46+token_ring.15.cil.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 9bd2c7ff 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_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/config/TaipanReach.xml -i ../../sv-benchmarks/c/combinations/Problem05_label46+token_ring.15.cil.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ --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 5a40438206222cb8b2973fadc665b92d328ce78e3a9921112a2f9717aab2538e --- Real Ultimate output --- This is Ultimate 0.2.3-dev-9bd2c7f [2023-11-19 05:02:57,879 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-19 05:02:58,035 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-19 05:02:58,046 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-19 05:02:58,050 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-19 05:02:58,099 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-19 05:02:58,100 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-19 05:02:58,101 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-19 05:02:58,103 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-19 05:02:58,109 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-19 05:02:58,109 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-19 05:02:58,110 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-19 05:02:58,111 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-19 05:02:58,113 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-19 05:02:58,113 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-19 05:02:58,114 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-19 05:02:58,115 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-19 05:02:58,115 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-19 05:02:58,116 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-19 05:02:58,117 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-19 05:02:58,117 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-19 05:02:58,118 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-19 05:02:58,119 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-19 05:02:58,120 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-19 05:02:58,121 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-19 05:02:58,121 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-19 05:02:58,122 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-19 05:02:58,122 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-19 05:02:58,123 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-19 05:02:58,123 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-19 05:02:58,125 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-19 05:02:58,125 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-19 05:02:58,126 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-19 05:02:58,126 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-19 05:02:58,126 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-19 05:02:58,127 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-19 05:02:58,127 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-19 05:02:58,127 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-19 05:02:58,128 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-19 05:02:58,128 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-19 05:02:58,128 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-19 05:02:58,130 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-19 05:02:58,130 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-19 05:02:58,130 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-19 05:02:58,131 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-19 05:02:58,131 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_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/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_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ 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 -> 5a40438206222cb8b2973fadc665b92d328ce78e3a9921112a2f9717aab2538e [2023-11-19 05:02:58,503 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-19 05:02:58,531 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-19 05:02:58,534 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-19 05:02:58,536 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-19 05:02:58,536 INFO L274 PluginConnector]: CDTParser initialized [2023-11-19 05:02:58,539 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/../../sv-benchmarks/c/combinations/Problem05_label46+token_ring.15.cil.c [2023-11-19 05:03:02,140 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-19 05:03:03,112 INFO L384 CDTParser]: Found 1 translation units. [2023-11-19 05:03:03,114 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/sv-benchmarks/c/combinations/Problem05_label46+token_ring.15.cil.c [2023-11-19 05:03:03,180 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/data/f9156fec2/b865f26c7406488e932a5fc88cfcba93/FLAG416998ee2 [2023-11-19 05:03:03,203 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/data/f9156fec2/b865f26c7406488e932a5fc88cfcba93 [2023-11-19 05:03:03,206 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-19 05:03:03,207 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-19 05:03:03,209 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-19 05:03:03,209 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-19 05:03:03,221 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-19 05:03:03,222 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 05:03:03" (1/1) ... [2023-11-19 05:03:03,223 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@19005c5d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:03:03, skipping insertion in model container [2023-11-19 05:03:03,224 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 05:03:03" (1/1) ... [2023-11-19 05:03:03,623 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-19 05:03:06,262 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_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/sv-benchmarks/c/combinations/Problem05_label46+token_ring.15.cil.c[382357,382370] [2023-11-19 05:03:06,300 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_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/sv-benchmarks/c/combinations/Problem05_label46+token_ring.15.cil.c[383339,383352] [2023-11-19 05:03:06,820 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-19 05:03:06,837 INFO L202 MainTranslator]: Completed pre-run [2023-11-19 05:03:08,369 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_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/sv-benchmarks/c/combinations/Problem05_label46+token_ring.15.cil.c[382357,382370] [2023-11-19 05:03:08,374 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_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/sv-benchmarks/c/combinations/Problem05_label46+token_ring.15.cil.c[383339,383352] [2023-11-19 05:03:08,440 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-19 05:03:08,563 INFO L206 MainTranslator]: Completed translation [2023-11-19 05:03:08,564 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:03:08 WrapperNode [2023-11-19 05:03:08,565 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-19 05:03:08,566 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-19 05:03:08,567 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-19 05:03:08,567 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-19 05:03:08,577 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:03:08" (1/1) ... [2023-11-19 05:03:08,700 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:03:08" (1/1) ... [2023-11-19 05:03:09,243 INFO L138 Inliner]: procedures = 70, calls = 81, calls flagged for inlining = 47, calls inlined = 47, statements flattened = 13292 [2023-11-19 05:03:09,243 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-19 05:03:09,244 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-19 05:03:09,244 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-19 05:03:09,245 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-19 05:03:09,256 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:03:08" (1/1) ... [2023-11-19 05:03:09,256 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:03:08" (1/1) ... [2023-11-19 05:03:09,343 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:03:08" (1/1) ... [2023-11-19 05:03:09,343 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:03:08" (1/1) ... [2023-11-19 05:03:09,621 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:03:08" (1/1) ... [2023-11-19 05:03:09,803 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:03:08" (1/1) ... [2023-11-19 05:03:09,893 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:03:08" (1/1) ... [2023-11-19 05:03:09,924 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:03:08" (1/1) ... [2023-11-19 05:03:10,092 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-19 05:03:10,095 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-19 05:03:10,095 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-19 05:03:10,095 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-19 05:03:10,096 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:03:08" (1/1) ... [2023-11-19 05:03:10,103 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-19 05:03:10,118 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:03:10,152 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-19 05:03:10,219 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-19 05:03:10,275 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-19 05:03:10,275 INFO L130 BoogieDeclarations]: Found specification of procedure activate_threads [2023-11-19 05:03:10,276 INFO L138 BoogieDeclarations]: Found implementation of procedure activate_threads [2023-11-19 05:03:10,278 INFO L130 BoogieDeclarations]: Found specification of procedure immediate_notify [2023-11-19 05:03:10,278 INFO L138 BoogieDeclarations]: Found implementation of procedure immediate_notify [2023-11-19 05:03:10,279 INFO L130 BoogieDeclarations]: Found specification of procedure update_channels [2023-11-19 05:03:10,279 INFO L138 BoogieDeclarations]: Found implementation of procedure update_channels [2023-11-19 05:03:10,279 INFO L130 BoogieDeclarations]: Found specification of procedure error [2023-11-19 05:03:10,279 INFO L138 BoogieDeclarations]: Found implementation of procedure error [2023-11-19 05:03:10,279 INFO L130 BoogieDeclarations]: Found specification of procedure fire_delta_events [2023-11-19 05:03:10,280 INFO L138 BoogieDeclarations]: Found implementation of procedure fire_delta_events [2023-11-19 05:03:10,280 INFO L130 BoogieDeclarations]: Found specification of procedure exists_runnable_thread [2023-11-19 05:03:10,280 INFO L138 BoogieDeclarations]: Found implementation of procedure exists_runnable_thread [2023-11-19 05:03:10,280 INFO L130 BoogieDeclarations]: Found specification of procedure reset_delta_events [2023-11-19 05:03:10,280 INFO L138 BoogieDeclarations]: Found implementation of procedure reset_delta_events [2023-11-19 05:03:10,281 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-19 05:03:10,281 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-19 05:03:10,282 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-19 05:03:10,546 INFO L236 CfgBuilder]: Building ICFG [2023-11-19 05:03:10,551 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-19 05:03:20,872 INFO L277 CfgBuilder]: Performing block encoding [2023-11-19 05:03:24,169 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-19 05:03:24,170 INFO L302 CfgBuilder]: Removed 17 assume(true) statements. [2023-11-19 05:03:24,191 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 05:03:24 BoogieIcfgContainer [2023-11-19 05:03:24,191 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-19 05:03:24,194 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-19 05:03:24,194 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-19 05:03:24,198 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-19 05:03:24,200 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.11 05:03:03" (1/3) ... [2023-11-19 05:03:24,201 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@345b6d61 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 05:03:24, skipping insertion in model container [2023-11-19 05:03:24,201 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:03:08" (2/3) ... [2023-11-19 05:03:24,202 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@345b6d61 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 05:03:24, skipping insertion in model container [2023-11-19 05:03:24,202 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 05:03:24" (3/3) ... [2023-11-19 05:03:24,203 INFO L112 eAbstractionObserver]: Analyzing ICFG Problem05_label46+token_ring.15.cil.c [2023-11-19 05:03:24,226 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-19 05:03:24,226 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 2 error locations. [2023-11-19 05:03:24,419 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-19 05:03:24,431 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;@2b1f43c6, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-19 05:03:24,431 INFO L358 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2023-11-19 05:03:24,448 INFO L276 IsEmpty]: Start isEmpty. Operand has 1862 states, 1823 states have (on average 1.9467910038398244) internal successors, (3549), 1828 states have internal predecessors, (3549), 29 states have call successors, (29), 7 states have call predecessors, (29), 7 states have return successors, (29), 28 states have call predecessors, (29), 29 states have call successors, (29) [2023-11-19 05:03:24,482 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2023-11-19 05:03:24,483 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:03:24,484 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, 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-19 05:03:24,499 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:03:24,505 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:03:24,505 INFO L85 PathProgramCache]: Analyzing trace with hash -293172014, now seen corresponding path program 1 times [2023-11-19 05:03:24,531 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:03:24,531 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1150911529] [2023-11-19 05:03:24,532 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:03:24,532 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:03:24,811 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:03:25,225 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-19 05:03:25,226 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:03:25,226 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1150911529] [2023-11-19 05:03:25,227 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1150911529] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 05:03:25,227 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 05:03:25,228 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-11-19 05:03:25,230 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [685277669] [2023-11-19 05:03:25,232 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 05:03:25,239 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-19 05:03:25,239 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:03:25,285 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-19 05:03:25,286 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-19 05:03:25,294 INFO L87 Difference]: Start difference. First operand has 1862 states, 1823 states have (on average 1.9467910038398244) internal successors, (3549), 1828 states have internal predecessors, (3549), 29 states have call successors, (29), 7 states have call predecessors, (29), 7 states have return successors, (29), 28 states have call predecessors, (29), 29 states have call successors, (29) Second operand has 4 states, 4 states have (on average 15.0) internal successors, (60), 4 states have internal predecessors, (60), 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-19 05:03:26,678 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:03:26,678 INFO L93 Difference]: Finished difference Result 3919 states and 7545 transitions. [2023-11-19 05:03:26,680 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-19 05:03:26,681 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 15.0) internal successors, (60), 4 states have internal predecessors, (60), 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 71 [2023-11-19 05:03:26,682 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:03:26,714 INFO L225 Difference]: With dead ends: 3919 [2023-11-19 05:03:26,715 INFO L226 Difference]: Without dead ends: 2056 [2023-11-19 05:03:26,725 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-19 05:03:26,728 INFO L413 NwaCegarLoop]: 3577 mSDtfsCounter, 3848 mSDsluCounter, 3473 mSDsCounter, 0 mSdLazyCounter, 744 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3848 SdHoareTripleChecker+Valid, 7050 SdHoareTripleChecker+Invalid, 758 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.1s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 744 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2023-11-19 05:03:26,730 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3848 Valid, 7050 Invalid, 758 Unknown, 0 Unchecked, 0.1s Time], IncrementalHoareTripleChecker [14 Valid, 744 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2023-11-19 05:03:26,756 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2056 states. [2023-11-19 05:03:26,888 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2056 to 2055. [2023-11-19 05:03:26,895 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2055 states, 1989 states have (on average 1.903469079939668) internal successors, (3786), 1993 states have internal predecessors, (3786), 52 states have call successors, (52), 13 states have call predecessors, (52), 12 states have return successors, (50), 49 states have call predecessors, (50), 50 states have call successors, (50) [2023-11-19 05:03:26,912 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2055 states to 2055 states and 3888 transitions. [2023-11-19 05:03:26,913 INFO L78 Accepts]: Start accepts. Automaton has 2055 states and 3888 transitions. Word has length 71 [2023-11-19 05:03:26,914 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:03:26,914 INFO L495 AbstractCegarLoop]: Abstraction has 2055 states and 3888 transitions. [2023-11-19 05:03:26,915 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 15.0) internal successors, (60), 4 states have internal predecessors, (60), 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-19 05:03:26,915 INFO L276 IsEmpty]: Start isEmpty. Operand 2055 states and 3888 transitions. [2023-11-19 05:03:26,926 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 146 [2023-11-19 05:03:26,926 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:03:26,927 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, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:03:26,927 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-19 05:03:26,931 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:03:26,932 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:03:26,932 INFO L85 PathProgramCache]: Analyzing trace with hash -1950865949, now seen corresponding path program 1 times [2023-11-19 05:03:26,933 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:03:26,934 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [847299051] [2023-11-19 05:03:26,935 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:03:26,935 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:03:26,996 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:03:27,403 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2023-11-19 05:03:27,403 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:03:27,403 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [847299051] [2023-11-19 05:03:27,404 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [847299051] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 05:03:27,404 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [654561845] [2023-11-19 05:03:27,404 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:03:27,405 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:03:27,405 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:03:27,407 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:03:27,454 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-19 05:03:27,752 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:03:27,763 INFO L262 TraceCheckSpWp]: Trace formula consists of 1114 conjuncts, 2 conjunts are in the unsatisfiable core [2023-11-19 05:03:27,776 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:03:27,891 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 29 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-11-19 05:03:27,893 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-19 05:03:27,894 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [654561845] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 05:03:27,896 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-19 05:03:27,897 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [5] total 6 [2023-11-19 05:03:27,898 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [944725491] [2023-11-19 05:03:27,898 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 05:03:27,899 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-19 05:03:27,900 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:03:27,901 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-19 05:03:27,902 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-11-19 05:03:27,902 INFO L87 Difference]: Start difference. First operand 2055 states and 3888 transitions. Second operand has 3 states, 3 states have (on average 36.0) internal successors, (108), 2 states have internal predecessors, (108), 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-19 05:03:28,530 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:03:28,530 INFO L93 Difference]: Finished difference Result 2866 states and 5133 transitions. [2023-11-19 05:03:28,531 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-19 05:03:28,531 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 36.0) internal successors, (108), 2 states have internal predecessors, (108), 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 145 [2023-11-19 05:03:28,532 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:03:28,552 INFO L225 Difference]: With dead ends: 2866 [2023-11-19 05:03:28,552 INFO L226 Difference]: Without dead ends: 2457 [2023-11-19 05:03:28,555 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 145 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-19 05:03:28,557 INFO L413 NwaCegarLoop]: 3389 mSDtfsCounter, 3547 mSDsluCounter, 262 mSDsCounter, 0 mSdLazyCounter, 322 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3547 SdHoareTripleChecker+Valid, 3651 SdHoareTripleChecker+Invalid, 324 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 322 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-19 05:03:28,557 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3547 Valid, 3651 Invalid, 324 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 322 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-19 05:03:28,563 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2457 states. [2023-11-19 05:03:28,653 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2457 to 2451. [2023-11-19 05:03:28,662 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2451 states, 2329 states have (on average 1.841562902533276) internal successors, (4289), 2334 states have internal predecessors, (4289), 96 states have call successors, (96), 25 states have call predecessors, (96), 24 states have return successors, (94), 92 states have call predecessors, (94), 94 states have call successors, (94) [2023-11-19 05:03:28,684 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2451 states to 2451 states and 4479 transitions. [2023-11-19 05:03:28,685 INFO L78 Accepts]: Start accepts. Automaton has 2451 states and 4479 transitions. Word has length 145 [2023-11-19 05:03:28,687 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:03:28,687 INFO L495 AbstractCegarLoop]: Abstraction has 2451 states and 4479 transitions. [2023-11-19 05:03:28,688 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 36.0) internal successors, (108), 2 states have internal predecessors, (108), 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-19 05:03:28,688 INFO L276 IsEmpty]: Start isEmpty. Operand 2451 states and 4479 transitions. [2023-11-19 05:03:28,701 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 146 [2023-11-19 05:03:28,701 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:03:28,702 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, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:03:28,733 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-19 05:03:28,922 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:03:28,923 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:03:28,923 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:03:28,924 INFO L85 PathProgramCache]: Analyzing trace with hash 1821720933, now seen corresponding path program 1 times [2023-11-19 05:03:28,924 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:03:28,924 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [680971626] [2023-11-19 05:03:28,924 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:03:28,924 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:03:28,958 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:03:29,152 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2023-11-19 05:03:29,152 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:03:29,153 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [680971626] [2023-11-19 05:03:29,153 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [680971626] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 05:03:29,153 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1650453702] [2023-11-19 05:03:29,153 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:03:29,153 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:03:29,154 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:03:29,159 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:03:29,178 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-19 05:03:29,456 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:03:29,461 INFO L262 TraceCheckSpWp]: Trace formula consists of 1108 conjuncts, 2 conjunts are in the unsatisfiable core [2023-11-19 05:03:29,469 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:03:29,553 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 38 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-11-19 05:03:29,554 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-19 05:03:29,554 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1650453702] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 05:03:29,555 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-19 05:03:29,555 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [5] total 6 [2023-11-19 05:03:29,555 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1759908526] [2023-11-19 05:03:29,555 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 05:03:29,556 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-19 05:03:29,556 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:03:29,557 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-19 05:03:29,558 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-11-19 05:03:29,558 INFO L87 Difference]: Start difference. First operand 2451 states and 4479 transitions. Second operand has 3 states, 3 states have (on average 39.0) internal successors, (117), 2 states have internal predecessors, (117), 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-19 05:03:30,396 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:03:30,397 INFO L93 Difference]: Finished difference Result 4048 states and 6926 transitions. [2023-11-19 05:03:30,398 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-19 05:03:30,398 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 39.0) internal successors, (117), 2 states have internal predecessors, (117), 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 145 [2023-11-19 05:03:30,399 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:03:30,428 INFO L225 Difference]: With dead ends: 4048 [2023-11-19 05:03:30,428 INFO L226 Difference]: Without dead ends: 3243 [2023-11-19 05:03:30,433 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 145 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-19 05:03:30,437 INFO L413 NwaCegarLoop]: 3344 mSDtfsCounter, 3538 mSDsluCounter, 262 mSDsCounter, 0 mSdLazyCounter, 322 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3538 SdHoareTripleChecker+Valid, 3606 SdHoareTripleChecker+Invalid, 324 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 322 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2023-11-19 05:03:30,439 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3538 Valid, 3606 Invalid, 324 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 322 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2023-11-19 05:03:30,449 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3243 states. [2023-11-19 05:03:30,611 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3243 to 3235. [2023-11-19 05:03:30,624 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3235 states, 3003 states have (on average 1.7592407592407593) internal successors, (5283), 3010 states have internal predecessors, (5283), 182 states have call successors, (182), 49 states have call predecessors, (182), 48 states have return successors, (180), 176 states have call predecessors, (180), 180 states have call successors, (180) [2023-11-19 05:03:30,654 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3235 states to 3235 states and 5645 transitions. [2023-11-19 05:03:30,655 INFO L78 Accepts]: Start accepts. Automaton has 3235 states and 5645 transitions. Word has length 145 [2023-11-19 05:03:30,657 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:03:30,657 INFO L495 AbstractCegarLoop]: Abstraction has 3235 states and 5645 transitions. [2023-11-19 05:03:30,657 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 39.0) internal successors, (117), 2 states have internal predecessors, (117), 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-19 05:03:30,658 INFO L276 IsEmpty]: Start isEmpty. Operand 3235 states and 5645 transitions. [2023-11-19 05:03:30,667 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 146 [2023-11-19 05:03:30,667 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:03:30,667 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, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:03:30,697 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-19 05:03:30,882 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:03:30,883 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:03:30,883 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:03:30,883 INFO L85 PathProgramCache]: Analyzing trace with hash 475843491, now seen corresponding path program 1 times [2023-11-19 05:03:30,884 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:03:30,884 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [247024534] [2023-11-19 05:03:30,884 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:03:30,884 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:03:30,926 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:03:31,154 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2023-11-19 05:03:31,155 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:03:31,155 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [247024534] [2023-11-19 05:03:31,155 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [247024534] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 05:03:31,156 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [368447268] [2023-11-19 05:03:31,156 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:03:31,156 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:03:31,157 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:03:31,158 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:03:31,186 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-19 05:03:31,449 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:03:31,454 INFO L262 TraceCheckSpWp]: Trace formula consists of 1102 conjuncts, 2 conjunts are in the unsatisfiable core [2023-11-19 05:03:31,461 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:03:31,533 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 17 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2023-11-19 05:03:31,534 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-19 05:03:31,534 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [368447268] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 05:03:31,535 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-19 05:03:31,535 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [5] total 6 [2023-11-19 05:03:31,535 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1129506744] [2023-11-19 05:03:31,535 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 05:03:31,537 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-19 05:03:31,538 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:03:31,538 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-19 05:03:31,539 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-11-19 05:03:31,539 INFO L87 Difference]: Start difference. First operand 3235 states and 5645 transitions. Second operand has 3 states, 3 states have (on average 32.0) internal successors, (96), 2 states have internal predecessors, (96), 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-19 05:03:32,259 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:03:32,261 INFO L93 Difference]: Finished difference Result 6388 states and 10462 transitions. [2023-11-19 05:03:32,261 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-19 05:03:32,262 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 32.0) internal successors, (96), 2 states have internal predecessors, (96), 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 145 [2023-11-19 05:03:32,262 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:03:32,300 INFO L225 Difference]: With dead ends: 6388 [2023-11-19 05:03:32,301 INFO L226 Difference]: Without dead ends: 4799 [2023-11-19 05:03:32,310 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 145 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-19 05:03:32,314 INFO L413 NwaCegarLoop]: 3385 mSDtfsCounter, 3559 mSDsluCounter, 262 mSDsCounter, 0 mSdLazyCounter, 322 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3559 SdHoareTripleChecker+Valid, 3647 SdHoareTripleChecker+Invalid, 324 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 322 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-19 05:03:32,316 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3559 Valid, 3647 Invalid, 324 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 322 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-19 05:03:32,326 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4799 states. [2023-11-19 05:03:32,561 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4799 to 4787. [2023-11-19 05:03:32,575 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4787 states, 4339 states have (on average 1.6702005070292694) internal successors, (7247), 4350 states have internal predecessors, (7247), 350 states have call successors, (350), 97 states have call predecessors, (350), 96 states have return successors, (348), 340 states have call predecessors, (348), 348 states have call successors, (348) [2023-11-19 05:03:32,609 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4787 states to 4787 states and 7945 transitions. [2023-11-19 05:03:32,611 INFO L78 Accepts]: Start accepts. Automaton has 4787 states and 7945 transitions. Word has length 145 [2023-11-19 05:03:32,613 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:03:32,613 INFO L495 AbstractCegarLoop]: Abstraction has 4787 states and 7945 transitions. [2023-11-19 05:03:32,616 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 32.0) internal successors, (96), 2 states have internal predecessors, (96), 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-19 05:03:32,616 INFO L276 IsEmpty]: Start isEmpty. Operand 4787 states and 7945 transitions. [2023-11-19 05:03:32,629 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 146 [2023-11-19 05:03:32,630 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:03:32,630 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, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:03:32,660 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-19 05:03:32,846 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:03:32,847 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:03:32,847 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:03:32,848 INFO L85 PathProgramCache]: Analyzing trace with hash -1980582875, now seen corresponding path program 1 times [2023-11-19 05:03:32,848 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:03:32,848 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1392237030] [2023-11-19 05:03:32,848 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:03:32,848 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:03:32,890 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:03:33,160 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2023-11-19 05:03:33,161 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:03:33,161 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1392237030] [2023-11-19 05:03:33,161 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1392237030] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 05:03:33,161 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [933600340] [2023-11-19 05:03:33,162 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:03:33,162 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:03:33,162 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:03:33,163 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:03:33,186 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-19 05:03:33,468 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:03:33,474 INFO L262 TraceCheckSpWp]: Trace formula consists of 1096 conjuncts, 2 conjunts are in the unsatisfiable core [2023-11-19 05:03:33,481 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:03:33,533 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 11 proven. 0 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2023-11-19 05:03:33,533 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-19 05:03:33,533 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [933600340] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 05:03:33,534 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-19 05:03:33,534 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [5] total 6 [2023-11-19 05:03:33,534 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [258684312] [2023-11-19 05:03:33,535 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 05:03:33,535 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-19 05:03:33,536 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:03:33,537 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-19 05:03:33,537 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-11-19 05:03:33,537 INFO L87 Difference]: Start difference. First operand 4787 states and 7945 transitions. Second operand has 3 states, 3 states have (on average 30.0) internal successors, (90), 2 states have internal predecessors, (90), 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-19 05:03:34,436 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:03:34,436 INFO L93 Difference]: Finished difference Result 11020 states and 17434 transitions. [2023-11-19 05:03:34,437 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-19 05:03:34,437 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 30.0) internal successors, (90), 2 states have internal predecessors, (90), 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 145 [2023-11-19 05:03:34,438 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:03:34,499 INFO L225 Difference]: With dead ends: 11020 [2023-11-19 05:03:34,499 INFO L226 Difference]: Without dead ends: 7879 [2023-11-19 05:03:34,518 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 145 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-19 05:03:34,519 INFO L413 NwaCegarLoop]: 3365 mSDtfsCounter, 3565 mSDsluCounter, 262 mSDsCounter, 0 mSdLazyCounter, 319 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3565 SdHoareTripleChecker+Valid, 3627 SdHoareTripleChecker+Invalid, 321 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 319 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-19 05:03:34,519 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3565 Valid, 3627 Invalid, 321 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 319 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-19 05:03:34,532 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7879 states. [2023-11-19 05:03:35,043 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7879 to 7859. [2023-11-19 05:03:35,068 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7859 states, 6987 states have (on average 1.5925289823958781) internal successors, (11127), 7006 states have internal predecessors, (11127), 678 states have call successors, (678), 193 states have call predecessors, (678), 192 states have return successors, (676), 660 states have call predecessors, (676), 676 states have call successors, (676) [2023-11-19 05:03:35,136 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7859 states to 7859 states and 12481 transitions. [2023-11-19 05:03:35,136 INFO L78 Accepts]: Start accepts. Automaton has 7859 states and 12481 transitions. Word has length 145 [2023-11-19 05:03:35,137 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:03:35,137 INFO L495 AbstractCegarLoop]: Abstraction has 7859 states and 12481 transitions. [2023-11-19 05:03:35,138 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 30.0) internal successors, (90), 2 states have internal predecessors, (90), 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-19 05:03:35,138 INFO L276 IsEmpty]: Start isEmpty. Operand 7859 states and 12481 transitions. [2023-11-19 05:03:35,152 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 146 [2023-11-19 05:03:35,152 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:03:35,153 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, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:03:35,178 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-19 05:03:35,373 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:03:35,374 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:03:35,374 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:03:35,374 INFO L85 PathProgramCache]: Analyzing trace with hash 912569127, now seen corresponding path program 1 times [2023-11-19 05:03:35,374 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:03:35,374 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [226393785] [2023-11-19 05:03:35,375 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:03:35,375 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:03:35,405 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:03:35,565 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2023-11-19 05:03:35,565 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:03:35,565 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [226393785] [2023-11-19 05:03:35,565 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [226393785] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 05:03:35,565 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1609255336] [2023-11-19 05:03:35,566 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:03:35,566 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:03:35,566 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:03:35,567 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:03:35,586 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-19 05:03:35,826 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:03:35,831 INFO L262 TraceCheckSpWp]: Trace formula consists of 1090 conjuncts, 2 conjunts are in the unsatisfiable core [2023-11-19 05:03:35,835 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:03:35,888 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 23 proven. 0 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-11-19 05:03:35,888 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-19 05:03:35,889 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1609255336] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 05:03:35,889 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-19 05:03:35,889 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [5] total 6 [2023-11-19 05:03:35,889 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [430600678] [2023-11-19 05:03:35,890 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 05:03:35,890 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-19 05:03:35,890 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:03:35,891 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-19 05:03:35,891 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-11-19 05:03:35,891 INFO L87 Difference]: Start difference. First operand 7859 states and 12481 transitions. Second operand has 3 states, 3 states have (on average 34.0) internal successors, (102), 2 states have internal predecessors, (102), 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-19 05:03:36,834 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:03:36,834 INFO L93 Difference]: Finished difference Result 20188 states and 31178 transitions. [2023-11-19 05:03:36,835 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-19 05:03:36,835 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 34.0) internal successors, (102), 2 states have internal predecessors, (102), 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 145 [2023-11-19 05:03:36,836 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:03:36,917 INFO L225 Difference]: With dead ends: 20188 [2023-11-19 05:03:36,917 INFO L226 Difference]: Without dead ends: 13975 [2023-11-19 05:03:36,947 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 145 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-19 05:03:36,948 INFO L413 NwaCegarLoop]: 3326 mSDtfsCounter, 3553 mSDsluCounter, 262 mSDsCounter, 0 mSdLazyCounter, 319 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3553 SdHoareTripleChecker+Valid, 3588 SdHoareTripleChecker+Invalid, 321 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 319 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-19 05:03:36,948 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3553 Valid, 3588 Invalid, 321 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 319 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-19 05:03:36,968 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 13975 states. [2023-11-19 05:03:37,487 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 13975 to 13939. [2023-11-19 05:03:37,512 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 13939 states, 12235 states have (on average 1.5358398038414385) internal successors, (18791), 12270 states have internal predecessors, (18791), 1318 states have call successors, (1318), 385 states have call predecessors, (1318), 384 states have return successors, (1316), 1284 states have call predecessors, (1316), 1316 states have call successors, (1316) [2023-11-19 05:03:37,606 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13939 states to 13939 states and 21425 transitions. [2023-11-19 05:03:37,607 INFO L78 Accepts]: Start accepts. Automaton has 13939 states and 21425 transitions. Word has length 145 [2023-11-19 05:03:37,608 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:03:37,609 INFO L495 AbstractCegarLoop]: Abstraction has 13939 states and 21425 transitions. [2023-11-19 05:03:37,609 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 34.0) internal successors, (102), 2 states have internal predecessors, (102), 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-19 05:03:37,609 INFO L276 IsEmpty]: Start isEmpty. Operand 13939 states and 21425 transitions. [2023-11-19 05:03:37,646 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 146 [2023-11-19 05:03:37,646 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:03:37,647 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, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:03:37,670 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-19 05:03:37,861 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2023-11-19 05:03:37,862 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:03:37,862 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:03:37,862 INFO L85 PathProgramCache]: Analyzing trace with hash 1655416105, now seen corresponding path program 1 times [2023-11-19 05:03:37,863 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:03:37,863 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1845470382] [2023-11-19 05:03:37,863 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:03:37,863 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:03:37,909 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:03:38,131 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2023-11-19 05:03:38,132 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:03:38,132 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1845470382] [2023-11-19 05:03:38,132 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1845470382] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-19 05:03:38,132 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [652554015] [2023-11-19 05:03:38,133 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:03:38,133 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:03:38,133 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:03:38,135 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:03:38,162 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-19 05:03:38,572 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:03:38,578 INFO L262 TraceCheckSpWp]: Trace formula consists of 1084 conjuncts, 2 conjunts are in the unsatisfiable core [2023-11-19 05:03:38,582 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:03:38,621 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2023-11-19 05:03:38,621 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-19 05:03:38,621 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [652554015] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 05:03:38,622 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-19 05:03:38,622 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [5] total 6 [2023-11-19 05:03:38,623 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [77558673] [2023-11-19 05:03:38,623 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 05:03:38,623 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-19 05:03:38,624 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:03:38,625 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-19 05:03:38,625 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-11-19 05:03:38,626 INFO L87 Difference]: Start difference. First operand 13939 states and 21425 transitions. Second operand has 3 states, 3 states have (on average 29.0) internal successors, (87), 2 states have internal predecessors, (87), 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-19 05:03:39,919 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:03:39,920 INFO L93 Difference]: Finished difference Result 38332 states and 58266 transitions. [2023-11-19 05:03:39,920 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-19 05:03:39,921 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 29.0) internal successors, (87), 2 states have internal predecessors, (87), 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 145 [2023-11-19 05:03:39,921 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:03:40,041 INFO L225 Difference]: With dead ends: 38332 [2023-11-19 05:03:40,042 INFO L226 Difference]: Without dead ends: 26039 [2023-11-19 05:03:40,103 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 145 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-19 05:03:40,104 INFO L413 NwaCegarLoop]: 3379 mSDtfsCounter, 3568 mSDsluCounter, 262 mSDsCounter, 0 mSdLazyCounter, 322 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3568 SdHoareTripleChecker+Valid, 3641 SdHoareTripleChecker+Invalid, 324 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 322 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2023-11-19 05:03:40,104 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3568 Valid, 3641 Invalid, 324 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 322 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2023-11-19 05:03:40,140 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26039 states. [2023-11-19 05:03:41,309 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26039 to 25971. [2023-11-19 05:03:41,343 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25971 states, 22635 states have (on average 1.4988734261100067) internal successors, (33927), 22702 states have internal predecessors, (33927), 2566 states have call successors, (2566), 769 states have call predecessors, (2566), 768 states have return successors, (2564), 2500 states have call predecessors, (2564), 2564 states have call successors, (2564) [2023-11-19 05:03:41,467 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25971 states to 25971 states and 39057 transitions. [2023-11-19 05:03:41,469 INFO L78 Accepts]: Start accepts. Automaton has 25971 states and 39057 transitions. Word has length 145 [2023-11-19 05:03:41,470 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:03:41,470 INFO L495 AbstractCegarLoop]: Abstraction has 25971 states and 39057 transitions. [2023-11-19 05:03:41,470 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 29.0) internal successors, (87), 2 states have internal predecessors, (87), 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-19 05:03:41,470 INFO L276 IsEmpty]: Start isEmpty. Operand 25971 states and 39057 transitions. [2023-11-19 05:03:41,715 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 146 [2023-11-19 05:03:41,715 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:03:41,715 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, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:03:41,743 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-19 05:03:41,928 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2bf4a7d8-ff7e-46aa-bafa-9218eed77d77/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2023-11-19 05:03:41,929 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:03:41,929 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:03:41,929 INFO L85 PathProgramCache]: Analyzing trace with hash 143011559, now seen corresponding path program 1 times [2023-11-19 05:03:41,930 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:03:41,930 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [704390124] [2023-11-19 05:03:41,930 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:03:41,930 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:03:41,984 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat