./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/combinations/Problem05_label43+token_ring.03.cil-1.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version cf1a7837 Calling Ultimate with: /usr/lib/jvm/java-11-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/config/TaipanReach.xml -i ../../sv-benchmarks/c/combinations/Problem05_label43+token_ring.03.cil-1.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash d5e8784cabcb38b73600d610d5b7e0bbbbf790f527b046ae80f9a34c4ea82403 --- Real Ultimate output --- This is Ultimate 0.2.3-dev-cf1a783 [2023-11-12 01:03:36,317 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-12 01:03:36,439 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-12 01:03:36,453 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-12 01:03:36,454 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-12 01:03:36,504 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-12 01:03:36,506 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-12 01:03:36,506 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-12 01:03:36,510 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-12 01:03:36,517 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-12 01:03:36,518 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-12 01:03:36,519 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-12 01:03:36,520 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-12 01:03:36,521 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-12 01:03:36,522 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-12 01:03:36,522 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-12 01:03:36,522 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-12 01:03:36,523 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-12 01:03:36,523 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-12 01:03:36,524 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-12 01:03:36,524 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-12 01:03:36,525 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-12 01:03:36,527 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-12 01:03:36,527 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-12 01:03:36,527 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-12 01:03:36,528 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-12 01:03:36,528 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-12 01:03:36,529 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-12 01:03:36,529 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-12 01:03:36,529 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-12 01:03:36,531 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-12 01:03:36,531 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-12 01:03:36,531 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-12 01:03:36,532 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-12 01:03:36,532 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-12 01:03:36,532 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-12 01:03:36,532 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 01:03:36,533 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-12 01:03:36,533 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-12 01:03:36,533 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-12 01:03:36,533 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-12 01:03:36,534 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-12 01:03:36,534 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-12 01:03:36,534 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-12 01:03:36,535 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-12 01:03:36,535 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_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Taipan Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> d5e8784cabcb38b73600d610d5b7e0bbbbf790f527b046ae80f9a34c4ea82403 [2023-11-12 01:03:36,812 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-12 01:03:36,850 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-12 01:03:36,853 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-12 01:03:36,854 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-12 01:03:36,855 INFO L274 PluginConnector]: CDTParser initialized [2023-11-12 01:03:36,857 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/../../sv-benchmarks/c/combinations/Problem05_label43+token_ring.03.cil-1.c [2023-11-12 01:03:39,959 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-12 01:03:40,816 INFO L384 CDTParser]: Found 1 translation units. [2023-11-12 01:03:40,816 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/sv-benchmarks/c/combinations/Problem05_label43+token_ring.03.cil-1.c [2023-11-12 01:03:40,872 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/data/91c1d8aa1/3911e7acb45c40448cd48758361830d7/FLAGc52fc56ee [2023-11-12 01:03:40,888 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/data/91c1d8aa1/3911e7acb45c40448cd48758361830d7 [2023-11-12 01:03:40,897 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-12 01:03:40,899 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-12 01:03:40,900 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-12 01:03:40,900 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-12 01:03:40,906 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-12 01:03:40,907 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 01:03:40" (1/1) ... [2023-11-12 01:03:40,908 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@230b0251 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:40, skipping insertion in model container [2023-11-12 01:03:40,908 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 01:03:40" (1/1) ... [2023-11-12 01:03:41,208 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-12 01:03:43,668 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_362a8e16-b7a1-4631-b11c-53cce55cb58c/sv-benchmarks/c/combinations/Problem05_label43+token_ring.03.cil-1.c[381679,381692] [2023-11-12 01:03:43,700 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_362a8e16-b7a1-4631-b11c-53cce55cb58c/sv-benchmarks/c/combinations/Problem05_label43+token_ring.03.cil-1.c[383339,383352] [2023-11-12 01:03:43,936 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 01:03:43,948 INFO L202 MainTranslator]: Completed pre-run [2023-11-12 01:03:45,240 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_362a8e16-b7a1-4631-b11c-53cce55cb58c/sv-benchmarks/c/combinations/Problem05_label43+token_ring.03.cil-1.c[381679,381692] [2023-11-12 01:03:45,244 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_362a8e16-b7a1-4631-b11c-53cce55cb58c/sv-benchmarks/c/combinations/Problem05_label43+token_ring.03.cil-1.c[383339,383352] [2023-11-12 01:03:45,270 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 01:03:45,353 INFO L206 MainTranslator]: Completed translation [2023-11-12 01:03:45,354 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:45 WrapperNode [2023-11-12 01:03:45,354 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-12 01:03:45,355 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-12 01:03:45,356 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-12 01:03:45,356 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-12 01:03:45,363 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:45" (1/1) ... [2023-11-12 01:03:45,461 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:45" (1/1) ... [2023-11-12 01:03:45,878 INFO L138 Inliner]: procedures = 50, calls = 51, calls flagged for inlining = 27, calls inlined = 27, statements flattened = 12694 [2023-11-12 01:03:45,879 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-12 01:03:45,880 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-12 01:03:45,880 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-12 01:03:45,880 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-12 01:03:45,890 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:45" (1/1) ... [2023-11-12 01:03:45,890 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:45" (1/1) ... [2023-11-12 01:03:46,078 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:45" (1/1) ... [2023-11-12 01:03:46,079 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:45" (1/1) ... [2023-11-12 01:03:46,402 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:45" (1/1) ... [2023-11-12 01:03:46,482 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:45" (1/1) ... [2023-11-12 01:03:46,518 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:45" (1/1) ... [2023-11-12 01:03:46,570 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:45" (1/1) ... [2023-11-12 01:03:46,634 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-12 01:03:46,636 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-12 01:03:46,636 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-12 01:03:46,636 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-12 01:03:46,637 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:45" (1/1) ... [2023-11-12 01:03:46,644 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 01:03:46,673 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:03:46,700 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-12 01:03:46,779 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-12 01:03:46,837 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-12 01:03:46,837 INFO L130 BoogieDeclarations]: Found specification of procedure activate_threads [2023-11-12 01:03:46,838 INFO L138 BoogieDeclarations]: Found implementation of procedure activate_threads [2023-11-12 01:03:46,838 INFO L130 BoogieDeclarations]: Found specification of procedure immediate_notify [2023-11-12 01:03:46,838 INFO L138 BoogieDeclarations]: Found implementation of procedure immediate_notify [2023-11-12 01:03:46,838 INFO L130 BoogieDeclarations]: Found specification of procedure update_channels [2023-11-12 01:03:46,838 INFO L138 BoogieDeclarations]: Found implementation of procedure update_channels [2023-11-12 01:03:46,838 INFO L130 BoogieDeclarations]: Found specification of procedure error [2023-11-12 01:03:46,839 INFO L138 BoogieDeclarations]: Found implementation of procedure error [2023-11-12 01:03:46,839 INFO L130 BoogieDeclarations]: Found specification of procedure fire_delta_events [2023-11-12 01:03:46,839 INFO L138 BoogieDeclarations]: Found implementation of procedure fire_delta_events [2023-11-12 01:03:46,839 INFO L130 BoogieDeclarations]: Found specification of procedure exists_runnable_thread [2023-11-12 01:03:46,839 INFO L138 BoogieDeclarations]: Found implementation of procedure exists_runnable_thread [2023-11-12 01:03:46,840 INFO L130 BoogieDeclarations]: Found specification of procedure reset_delta_events [2023-11-12 01:03:46,840 INFO L138 BoogieDeclarations]: Found implementation of procedure reset_delta_events [2023-11-12 01:03:46,840 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-12 01:03:46,840 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-12 01:03:46,840 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-12 01:03:47,006 INFO L236 CfgBuilder]: Building ICFG [2023-11-12 01:03:47,008 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-12 01:03:56,544 INFO L277 CfgBuilder]: Performing block encoding [2023-11-12 01:03:58,832 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-12 01:03:58,832 INFO L302 CfgBuilder]: Removed 7 assume(true) statements. [2023-11-12 01:03:58,839 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 01:03:58 BoogieIcfgContainer [2023-11-12 01:03:58,839 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-12 01:03:58,842 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-12 01:03:58,842 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-12 01:03:58,846 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-12 01:03:58,847 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.11 01:03:40" (1/3) ... [2023-11-12 01:03:58,847 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4a6a5fdf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 01:03:58, skipping insertion in model container [2023-11-12 01:03:58,848 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:45" (2/3) ... [2023-11-12 01:03:58,848 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4a6a5fdf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 01:03:58, skipping insertion in model container [2023-11-12 01:03:58,848 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 01:03:58" (3/3) ... [2023-11-12 01:03:58,850 INFO L112 eAbstractionObserver]: Analyzing ICFG Problem05_label43+token_ring.03.cil-1.c [2023-11-12 01:03:58,871 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-12 01:03:58,872 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 2 error locations. [2023-11-12 01:03:58,967 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-12 01:03:58,975 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;@3566df70, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-12 01:03:58,975 INFO L358 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2023-11-12 01:03:58,988 INFO L276 IsEmpty]: Start isEmpty. Operand has 1742 states, 1713 states have (on average 1.9725627553998832) internal successors, (3379), 1718 states have internal predecessors, (3379), 19 states have call successors, (19), 7 states have call predecessors, (19), 7 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2023-11-12 01:03:59,001 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2023-11-12 01:03:59,001 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:03:59,002 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:03:59,003 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:03:59,008 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:03:59,009 INFO L85 PathProgramCache]: Analyzing trace with hash 838533184, now seen corresponding path program 1 times [2023-11-12 01:03:59,020 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:03:59,020 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [956811109] [2023-11-12 01:03:59,021 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:03:59,021 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:03:59,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:03:59,507 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-12 01:03:59,507 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:03:59,508 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [956811109] [2023-11-12 01:03:59,508 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [956811109] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 01:03:59,509 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 01:03:59,509 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-11-12 01:03:59,511 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2023776733] [2023-11-12 01:03:59,512 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 01:03:59,518 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-12 01:03:59,518 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:03:59,566 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-12 01:03:59,567 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-12 01:03:59,574 INFO L87 Difference]: Start difference. First operand has 1742 states, 1713 states have (on average 1.9725627553998832) internal successors, (3379), 1718 states have internal predecessors, (3379), 19 states have call successors, (19), 7 states have call predecessors, (19), 7 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) Second operand has 4 states, 4 states have (on average 7.5) internal successors, (30), 4 states have internal predecessors, (30), 2 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-11-12 01:04:00,545 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:04:00,545 INFO L93 Difference]: Finished difference Result 3559 states and 6955 transitions. [2023-11-12 01:04:00,546 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-12 01:04:00,548 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 7.5) internal successors, (30), 4 states have internal predecessors, (30), 2 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 41 [2023-11-12 01:04:00,549 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:04:00,581 INFO L225 Difference]: With dead ends: 3559 [2023-11-12 01:04:00,582 INFO L226 Difference]: Without dead ends: 1816 [2023-11-12 01:04:00,594 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-12 01:04:00,601 INFO L413 NwaCegarLoop]: 3256 mSDtfsCounter, 3498 mSDsluCounter, 3192 mSDsCounter, 0 mSdLazyCounter, 586 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3498 SdHoareTripleChecker+Valid, 6448 SdHoareTripleChecker+Invalid, 600 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.1s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 586 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2023-11-12 01:04:00,603 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3498 Valid, 6448 Invalid, 600 Unknown, 0 Unchecked, 0.1s Time], IncrementalHoareTripleChecker [14 Valid, 586 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2023-11-12 01:04:00,628 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1816 states. [2023-11-12 01:04:00,773 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1816 to 1815. [2023-11-12 01:04:00,780 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1815 states, 1769 states have (on average 1.9479932165065008) internal successors, (3446), 1773 states have internal predecessors, (3446), 32 states have call successors, (32), 13 states have call predecessors, (32), 12 states have return successors, (30), 29 states have call predecessors, (30), 30 states have call successors, (30) [2023-11-12 01:04:00,794 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1815 states to 1815 states and 3508 transitions. [2023-11-12 01:04:00,796 INFO L78 Accepts]: Start accepts. Automaton has 1815 states and 3508 transitions. Word has length 41 [2023-11-12 01:04:00,796 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:04:00,797 INFO L495 AbstractCegarLoop]: Abstraction has 1815 states and 3508 transitions. [2023-11-12 01:04:00,797 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 7.5) internal successors, (30), 4 states have internal predecessors, (30), 2 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-11-12 01:04:00,797 INFO L276 IsEmpty]: Start isEmpty. Operand 1815 states and 3508 transitions. [2023-11-12 01:04:00,813 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2023-11-12 01:04:00,813 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:04:00,813 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:04:00,814 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-12 01:04:00,814 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:04:00,815 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:04:00,816 INFO L85 PathProgramCache]: Analyzing trace with hash 766175791, now seen corresponding path program 1 times [2023-11-12 01:04:00,816 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:04:00,817 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [365041035] [2023-11-12 01:04:00,817 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:00,818 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:04:00,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:01,064 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2023-11-12 01:04:01,064 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:04:01,065 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [365041035] [2023-11-12 01:04:01,065 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [365041035] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 01:04:01,065 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1977638618] [2023-11-12 01:04:01,066 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:01,066 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:01,066 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:04:01,070 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:04:01,084 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-12 01:04:01,232 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:01,236 INFO L262 TraceCheckSpWp]: Trace formula consists of 424 conjuncts, 2 conjunts are in the unsatisfiable core [2023-11-12 01:04:01,246 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:04:01,318 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 11 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-11-12 01:04:01,318 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 01:04:01,319 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1977638618] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 01:04:01,319 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 01:04:01,319 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [5] total 6 [2023-11-12 01:04:01,320 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [835275203] [2023-11-12 01:04:01,321 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 01:04:01,322 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-12 01:04:01,322 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:04:01,323 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-12 01:04:01,323 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-11-12 01:04:01,324 INFO L87 Difference]: Start difference. First operand 1815 states and 3508 transitions. Second operand has 3 states, 3 states have (on average 16.666666666666668) internal successors, (50), 2 states have internal predecessors, (50), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2023-11-12 01:04:01,887 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:04:01,888 INFO L93 Difference]: Finished difference Result 2146 states and 3973 transitions. [2023-11-12 01:04:01,888 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-12 01:04:01,889 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 16.666666666666668) internal successors, (50), 2 states have internal predecessors, (50), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 75 [2023-11-12 01:04:01,889 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:04:01,916 INFO L225 Difference]: With dead ends: 2146 [2023-11-12 01:04:01,916 INFO L226 Difference]: Without dead ends: 1977 [2023-11-12 01:04:01,920 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 75 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-11-12 01:04:01,922 INFO L413 NwaCegarLoop]: 3207 mSDtfsCounter, 3375 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 265 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3375 SdHoareTripleChecker+Valid, 3308 SdHoareTripleChecker+Invalid, 267 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 265 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-12 01:04:01,923 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3375 Valid, 3308 Invalid, 267 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 265 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-12 01:04:01,932 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1977 states. [2023-11-12 01:04:02,011 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1977 to 1971. [2023-11-12 01:04:02,018 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1971 states, 1889 states have (on average 1.9105346744309157) internal successors, (3609), 1894 states have internal predecessors, (3609), 56 states have call successors, (56), 25 states have call predecessors, (56), 24 states have return successors, (54), 52 states have call predecessors, (54), 54 states have call successors, (54) [2023-11-12 01:04:02,036 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1971 states to 1971 states and 3719 transitions. [2023-11-12 01:04:02,037 INFO L78 Accepts]: Start accepts. Automaton has 1971 states and 3719 transitions. Word has length 75 [2023-11-12 01:04:02,037 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:04:02,038 INFO L495 AbstractCegarLoop]: Abstraction has 1971 states and 3719 transitions. [2023-11-12 01:04:02,038 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 16.666666666666668) internal successors, (50), 2 states have internal predecessors, (50), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2023-11-12 01:04:02,038 INFO L276 IsEmpty]: Start isEmpty. Operand 1971 states and 3719 transitions. [2023-11-12 01:04:02,042 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2023-11-12 01:04:02,043 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:04:02,043 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:04:02,064 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-12 01:04:02,264 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:02,264 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:04:02,265 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:04:02,265 INFO L85 PathProgramCache]: Analyzing trace with hash 1895410417, now seen corresponding path program 1 times [2023-11-12 01:04:02,265 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:04:02,266 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [941967398] [2023-11-12 01:04:02,266 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:02,266 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:04:02,292 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:02,443 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2023-11-12 01:04:02,444 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:04:02,444 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [941967398] [2023-11-12 01:04:02,445 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [941967398] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 01:04:02,445 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1373628036] [2023-11-12 01:04:02,445 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:02,446 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:02,446 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:04:02,447 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:04:02,469 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-12 01:04:02,616 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:02,620 INFO L262 TraceCheckSpWp]: Trace formula consists of 418 conjuncts, 2 conjunts are in the unsatisfiable core [2023-11-12 01:04:02,627 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:04:02,698 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-11-12 01:04:02,699 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 01:04:02,700 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1373628036] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 01:04:02,700 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 01:04:02,701 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [5] total 6 [2023-11-12 01:04:02,701 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [512433477] [2023-11-12 01:04:02,701 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 01:04:02,703 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-12 01:04:02,703 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:04:02,705 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-12 01:04:02,705 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-11-12 01:04:02,705 INFO L87 Difference]: Start difference. First operand 1971 states and 3719 transitions. Second operand has 3 states, 3 states have (on average 15.666666666666666) internal successors, (47), 2 states have internal predecessors, (47), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2023-11-12 01:04:03,354 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:04:03,354 INFO L93 Difference]: Finished difference Result 2608 states and 4606 transitions. [2023-11-12 01:04:03,355 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-12 01:04:03,356 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 15.666666666666666) internal successors, (47), 2 states have internal predecessors, (47), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 75 [2023-11-12 01:04:03,356 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:04:03,374 INFO L225 Difference]: With dead ends: 2608 [2023-11-12 01:04:03,375 INFO L226 Difference]: Without dead ends: 2283 [2023-11-12 01:04:03,377 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 75 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-11-12 01:04:03,379 INFO L413 NwaCegarLoop]: 3205 mSDtfsCounter, 3378 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 265 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3378 SdHoareTripleChecker+Valid, 3306 SdHoareTripleChecker+Invalid, 267 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 265 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-12 01:04:03,380 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3378 Valid, 3306 Invalid, 267 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 265 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-12 01:04:03,386 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2283 states. [2023-11-12 01:04:03,603 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2283 to 2275. [2023-11-12 01:04:03,622 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2275 states, 2123 states have (on average 1.8478568064060292) internal successors, (3923), 2130 states have internal predecessors, (3923), 102 states have call successors, (102), 49 states have call predecessors, (102), 48 states have return successors, (100), 96 states have call predecessors, (100), 100 states have call successors, (100) [2023-11-12 01:04:03,660 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2275 states to 2275 states and 4125 transitions. [2023-11-12 01:04:03,660 INFO L78 Accepts]: Start accepts. Automaton has 2275 states and 4125 transitions. Word has length 75 [2023-11-12 01:04:03,661 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:04:03,661 INFO L495 AbstractCegarLoop]: Abstraction has 2275 states and 4125 transitions. [2023-11-12 01:04:03,661 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 15.666666666666666) internal successors, (47), 2 states have internal predecessors, (47), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2023-11-12 01:04:03,661 INFO L276 IsEmpty]: Start isEmpty. Operand 2275 states and 4125 transitions. [2023-11-12 01:04:03,664 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2023-11-12 01:04:03,664 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:04:03,664 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:04:03,689 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-12 01:04:03,865 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:03,865 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:04:03,865 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:04:03,865 INFO L85 PathProgramCache]: Analyzing trace with hash 445324015, now seen corresponding path program 1 times [2023-11-12 01:04:03,866 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:04:03,866 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [660552230] [2023-11-12 01:04:03,866 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:03,866 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:04:03,910 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:04,437 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2023-11-12 01:04:04,438 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:04:04,439 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [660552230] [2023-11-12 01:04:04,441 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [660552230] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 01:04:04,442 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 01:04:04,442 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2023-11-12 01:04:04,444 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1481511394] [2023-11-12 01:04:04,445 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 01:04:04,446 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-11-12 01:04:04,448 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:04:04,449 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-11-12 01:04:04,449 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2023-11-12 01:04:04,450 INFO L87 Difference]: Start difference. First operand 2275 states and 4125 transitions. Second operand has 6 states, 6 states have (on average 7.333333333333333) internal successors, (44), 6 states have internal predecessors, (44), 4 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2023-11-12 01:04:05,725 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:04:05,725 INFO L93 Difference]: Finished difference Result 3579 states and 5883 transitions. [2023-11-12 01:04:05,725 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-12 01:04:05,726 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 7.333333333333333) internal successors, (44), 6 states have internal predecessors, (44), 4 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) Word has length 75 [2023-11-12 01:04:05,728 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:04:05,753 INFO L225 Difference]: With dead ends: 3579 [2023-11-12 01:04:05,753 INFO L226 Difference]: Without dead ends: 2951 [2023-11-12 01:04:05,759 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=41, Invalid=69, Unknown=0, NotChecked=0, Total=110 [2023-11-12 01:04:05,761 INFO L413 NwaCegarLoop]: 3175 mSDtfsCounter, 3577 mSDsluCounter, 9412 mSDsCounter, 0 mSdLazyCounter, 1054 mSolverCounterSat, 82 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3589 SdHoareTripleChecker+Valid, 12587 SdHoareTripleChecker+Invalid, 1136 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.1s SdHoareTripleChecker+Time, 82 IncrementalHoareTripleChecker+Valid, 1054 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2023-11-12 01:04:05,763 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3589 Valid, 12587 Invalid, 1136 Unknown, 0 Unchecked, 0.1s Time], IncrementalHoareTripleChecker [82 Valid, 1054 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2023-11-12 01:04:05,771 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2951 states. [2023-11-12 01:04:05,897 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2951 to 2851. [2023-11-12 01:04:05,904 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2851 states, 2563 states have (on average 1.7569254779555208) internal successors, (4503), 2574 states have internal predecessors, (4503), 190 states have call successors, (190), 97 states have call predecessors, (190), 96 states have return successors, (188), 180 states have call predecessors, (188), 188 states have call successors, (188) [2023-11-12 01:04:05,924 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2851 states to 2851 states and 4881 transitions. [2023-11-12 01:04:05,925 INFO L78 Accepts]: Start accepts. Automaton has 2851 states and 4881 transitions. Word has length 75 [2023-11-12 01:04:05,925 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:04:05,925 INFO L495 AbstractCegarLoop]: Abstraction has 2851 states and 4881 transitions. [2023-11-12 01:04:05,926 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 7.333333333333333) internal successors, (44), 6 states have internal predecessors, (44), 4 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2023-11-12 01:04:05,926 INFO L276 IsEmpty]: Start isEmpty. Operand 2851 states and 4881 transitions. [2023-11-12 01:04:05,929 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2023-11-12 01:04:05,930 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:04:05,930 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:04:05,930 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2023-11-12 01:04:05,931 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:04:05,931 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:04:05,931 INFO L85 PathProgramCache]: Analyzing trace with hash 1549071346, now seen corresponding path program 1 times [2023-11-12 01:04:05,932 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:04:05,932 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2067884491] [2023-11-12 01:04:05,932 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:05,932 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:04:05,952 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:06,160 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 10 proven. 14 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2023-11-12 01:04:06,160 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:04:06,160 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2067884491] [2023-11-12 01:04:06,161 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2067884491] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 01:04:06,161 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2017088807] [2023-11-12 01:04:06,161 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:06,161 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:06,162 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:04:06,163 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:04:06,189 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-12 01:04:06,310 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:06,312 INFO L262 TraceCheckSpWp]: Trace formula consists of 443 conjuncts, 2 conjunts are in the unsatisfiable core [2023-11-12 01:04:06,323 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:04:06,374 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 19 proven. 0 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2023-11-12 01:04:06,374 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 01:04:06,374 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2017088807] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 01:04:06,374 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 01:04:06,375 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [6] total 7 [2023-11-12 01:04:06,375 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1138519553] [2023-11-12 01:04:06,375 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 01:04:06,376 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-12 01:04:06,376 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:04:06,376 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-12 01:04:06,377 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2023-11-12 01:04:06,377 INFO L87 Difference]: Start difference. First operand 2851 states and 4881 transitions. Second operand has 3 states, 3 states have (on average 17.666666666666668) internal successors, (53), 3 states have internal predecessors, (53), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2023-11-12 01:04:07,048 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:04:07,048 INFO L93 Difference]: Finished difference Result 3802 states and 6174 transitions. [2023-11-12 01:04:07,049 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-12 01:04:07,049 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 17.666666666666668) internal successors, (53), 3 states have internal predecessors, (53), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 89 [2023-11-12 01:04:07,050 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:04:07,072 INFO L225 Difference]: With dead ends: 3802 [2023-11-12 01:04:07,073 INFO L226 Difference]: Without dead ends: 3166 [2023-11-12 01:04:07,076 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 91 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2023-11-12 01:04:07,077 INFO L413 NwaCegarLoop]: 3218 mSDtfsCounter, 47 mSDsluCounter, 3168 mSDsCounter, 0 mSdLazyCounter, 482 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 6386 SdHoareTripleChecker+Invalid, 482 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 482 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-12 01:04:07,078 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 6386 Invalid, 482 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 482 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-12 01:04:07,084 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3166 states. [2023-11-12 01:04:07,218 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3166 to 3035. [2023-11-12 01:04:07,226 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3035 states, 2731 states have (on average 1.7396558037348957) internal successors, (4751), 2742 states have internal predecessors, (4751), 198 states have call successors, (198), 105 states have call predecessors, (198), 104 states have return successors, (196), 188 states have call predecessors, (196), 196 states have call successors, (196) [2023-11-12 01:04:07,256 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3035 states to 3035 states and 5145 transitions. [2023-11-12 01:04:07,258 INFO L78 Accepts]: Start accepts. Automaton has 3035 states and 5145 transitions. Word has length 89 [2023-11-12 01:04:07,260 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:04:07,260 INFO L495 AbstractCegarLoop]: Abstraction has 3035 states and 5145 transitions. [2023-11-12 01:04:07,260 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 17.666666666666668) internal successors, (53), 3 states have internal predecessors, (53), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2023-11-12 01:04:07,261 INFO L276 IsEmpty]: Start isEmpty. Operand 3035 states and 5145 transitions. [2023-11-12 01:04:07,271 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2023-11-12 01:04:07,271 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:04:07,272 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:04:07,284 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-12 01:04:07,478 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:07,479 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:04:07,479 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:04:07,479 INFO L85 PathProgramCache]: Analyzing trace with hash 894078126, now seen corresponding path program 1 times [2023-11-12 01:04:07,479 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:04:07,479 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [220395708] [2023-11-12 01:04:07,480 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:07,480 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:04:07,506 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:07,647 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2023-11-12 01:04:07,647 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:04:07,647 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [220395708] [2023-11-12 01:04:07,648 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [220395708] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 01:04:07,648 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 01:04:07,648 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-12 01:04:07,648 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [780206141] [2023-11-12 01:04:07,649 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 01:04:07,649 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-12 01:04:07,650 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:04:07,650 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-12 01:04:07,651 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-12 01:04:07,651 INFO L87 Difference]: Start difference. First operand 3035 states and 5145 transitions. Second operand has 3 states, 3 states have (on average 17.333333333333332) internal successors, (52), 3 states have internal predecessors, (52), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2023-11-12 01:04:08,338 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:04:08,339 INFO L93 Difference]: Finished difference Result 5116 states and 7974 transitions. [2023-11-12 01:04:08,340 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-12 01:04:08,340 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 17.333333333333332) internal successors, (52), 3 states have internal predecessors, (52), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 99 [2023-11-12 01:04:08,341 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:04:08,373 INFO L225 Difference]: With dead ends: 5116 [2023-11-12 01:04:08,373 INFO L226 Difference]: Without dead ends: 3727 [2023-11-12 01:04:08,381 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-12 01:04:08,382 INFO L413 NwaCegarLoop]: 3207 mSDtfsCounter, 3370 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 265 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3370 SdHoareTripleChecker+Valid, 3308 SdHoareTripleChecker+Invalid, 267 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 265 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-12 01:04:08,383 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3370 Valid, 3308 Invalid, 267 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 265 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-12 01:04:08,392 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3727 states. [2023-11-12 01:04:08,635 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3727 to 3711. [2023-11-12 01:04:08,646 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3711 states, 3263 states have (on average 1.6705485749310451) internal successors, (5451), 3278 states have internal predecessors, (5451), 290 states have call successors, (290), 157 states have call predecessors, (290), 156 states have return successors, (288), 276 states have call predecessors, (288), 288 states have call successors, (288) [2023-11-12 01:04:08,672 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3711 states to 3711 states and 6029 transitions. [2023-11-12 01:04:08,673 INFO L78 Accepts]: Start accepts. Automaton has 3711 states and 6029 transitions. Word has length 99 [2023-11-12 01:04:08,673 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:04:08,673 INFO L495 AbstractCegarLoop]: Abstraction has 3711 states and 6029 transitions. [2023-11-12 01:04:08,674 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 17.333333333333332) internal successors, (52), 3 states have internal predecessors, (52), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2023-11-12 01:04:08,674 INFO L276 IsEmpty]: Start isEmpty. Operand 3711 states and 6029 transitions. [2023-11-12 01:04:08,686 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 114 [2023-11-12 01:04:08,687 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:04:08,687 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:04:08,687 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2023-11-12 01:04:08,688 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:04:08,688 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:04:08,689 INFO L85 PathProgramCache]: Analyzing trace with hash 1776962737, now seen corresponding path program 1 times [2023-11-12 01:04:08,689 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:04:08,689 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [46757408] [2023-11-12 01:04:08,690 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:08,690 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:04:08,717 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:09,146 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 10 proven. 27 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2023-11-12 01:04:09,147 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:04:09,147 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [46757408] [2023-11-12 01:04:09,148 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [46757408] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 01:04:09,148 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [656423948] [2023-11-12 01:04:09,148 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:09,148 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:09,149 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:04:09,151 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:04:09,164 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-12 01:04:09,347 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:09,350 INFO L262 TraceCheckSpWp]: Trace formula consists of 544 conjuncts, 3 conjunts are in the unsatisfiable core [2023-11-12 01:04:09,362 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:04:09,424 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 62 proven. 0 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2023-11-12 01:04:09,424 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 01:04:09,424 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [656423948] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 01:04:09,425 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 01:04:09,425 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [6] total 7 [2023-11-12 01:04:09,425 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1608868863] [2023-11-12 01:04:09,426 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 01:04:09,427 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-12 01:04:09,427 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:04:09,428 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-12 01:04:09,428 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2023-11-12 01:04:09,428 INFO L87 Difference]: Start difference. First operand 3711 states and 6029 transitions. Second operand has 3 states, 3 states have (on average 27.0) internal successors, (81), 3 states have internal predecessors, (81), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2023-11-12 01:04:10,171 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:04:10,171 INFO L93 Difference]: Finished difference Result 5111 states and 7995 transitions. [2023-11-12 01:04:10,172 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-12 01:04:10,172 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 27.0) internal successors, (81), 3 states have internal predecessors, (81), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 113 [2023-11-12 01:04:10,173 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:04:10,199 INFO L225 Difference]: With dead ends: 5111 [2023-11-12 01:04:10,200 INFO L226 Difference]: Without dead ends: 3723 [2023-11-12 01:04:10,206 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 115 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2023-11-12 01:04:10,208 INFO L413 NwaCegarLoop]: 3221 mSDtfsCounter, 102 mSDsluCounter, 3158 mSDsCounter, 0 mSdLazyCounter, 482 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 102 SdHoareTripleChecker+Valid, 6379 SdHoareTripleChecker+Invalid, 484 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 482 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-12 01:04:10,208 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [102 Valid, 6379 Invalid, 484 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 482 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-12 01:04:10,217 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3723 states. [2023-11-12 01:04:10,425 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3723 to 3703. [2023-11-12 01:04:10,442 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3703 states, 3255 states have (on average 1.6599078341013824) internal successors, (5403), 3270 states have internal predecessors, (5403), 290 states have call successors, (290), 157 states have call predecessors, (290), 156 states have return successors, (288), 276 states have call predecessors, (288), 288 states have call successors, (288) [2023-11-12 01:04:10,474 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3703 states to 3703 states and 5981 transitions. [2023-11-12 01:04:10,474 INFO L78 Accepts]: Start accepts. Automaton has 3703 states and 5981 transitions. Word has length 113 [2023-11-12 01:04:10,475 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:04:10,475 INFO L495 AbstractCegarLoop]: Abstraction has 3703 states and 5981 transitions. [2023-11-12 01:04:10,476 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 27.0) internal successors, (81), 3 states have internal predecessors, (81), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2023-11-12 01:04:10,476 INFO L276 IsEmpty]: Start isEmpty. Operand 3703 states and 5981 transitions. [2023-11-12 01:04:10,490 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 114 [2023-11-12 01:04:10,491 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:04:10,491 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:04:10,500 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-12 01:04:10,700 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:10,701 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:04:10,702 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:04:10,702 INFO L85 PathProgramCache]: Analyzing trace with hash -1352731695, now seen corresponding path program 1 times [2023-11-12 01:04:10,704 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:04:10,704 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1945279734] [2023-11-12 01:04:10,705 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:10,705 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:04:10,738 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:11,069 INFO L134 CoverageAnalysis]: Checked inductivity of 71 backedges. 10 proven. 25 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2023-11-12 01:04:11,069 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:04:11,069 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1945279734] [2023-11-12 01:04:11,070 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1945279734] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 01:04:11,072 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [575438589] [2023-11-12 01:04:11,073 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:11,073 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:11,073 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:04:11,075 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:04:11,099 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-12 01:04:11,264 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:11,268 INFO L262 TraceCheckSpWp]: Trace formula consists of 550 conjuncts, 2 conjunts are in the unsatisfiable core [2023-11-12 01:04:11,276 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:04:11,314 INFO L134 CoverageAnalysis]: Checked inductivity of 71 backedges. 51 proven. 0 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2023-11-12 01:04:11,315 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 01:04:11,315 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [575438589] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 01:04:11,315 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 01:04:11,316 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [6] total 7 [2023-11-12 01:04:11,316 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1589768135] [2023-11-12 01:04:11,316 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 01:04:11,317 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-12 01:04:11,317 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:04:11,317 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-12 01:04:11,318 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2023-11-12 01:04:11,318 INFO L87 Difference]: Start difference. First operand 3703 states and 5981 transitions. Second operand has 3 states, 3 states have (on average 25.0) internal successors, (75), 3 states have internal predecessors, (75), 3 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (10), 2 states have call predecessors, (10), 3 states have call successors, (10) [2023-11-12 01:04:11,905 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:04:11,906 INFO L93 Difference]: Finished difference Result 5523 states and 8362 transitions. [2023-11-12 01:04:11,906 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-12 01:04:11,906 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 25.0) internal successors, (75), 3 states have internal predecessors, (75), 3 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (10), 2 states have call predecessors, (10), 3 states have call successors, (10) Word has length 113 [2023-11-12 01:04:11,907 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:04:11,933 INFO L225 Difference]: With dead ends: 5523 [2023-11-12 01:04:11,933 INFO L226 Difference]: Without dead ends: 4151 [2023-11-12 01:04:11,939 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 115 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2023-11-12 01:04:11,940 INFO L413 NwaCegarLoop]: 3178 mSDtfsCounter, 3380 mSDsluCounter, 24 mSDsCounter, 0 mSdLazyCounter, 242 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3380 SdHoareTripleChecker+Valid, 3202 SdHoareTripleChecker+Invalid, 246 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 242 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-12 01:04:11,940 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3380 Valid, 3202 Invalid, 246 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 242 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-12 01:04:11,947 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4151 states. [2023-11-12 01:04:12,129 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4151 to 4151. [2023-11-12 01:04:12,136 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4151 states, 3639 states have (on average 1.606760098928277) internal successors, (5847), 3654 states have internal predecessors, (5847), 310 states have call successors, (310), 201 states have call predecessors, (310), 200 states have return successors, (308), 296 states have call predecessors, (308), 308 states have call successors, (308) [2023-11-12 01:04:12,154 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4151 states to 4151 states and 6465 transitions. [2023-11-12 01:04:12,154 INFO L78 Accepts]: Start accepts. Automaton has 4151 states and 6465 transitions. Word has length 113 [2023-11-12 01:04:12,155 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:04:12,155 INFO L495 AbstractCegarLoop]: Abstraction has 4151 states and 6465 transitions. [2023-11-12 01:04:12,155 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 25.0) internal successors, (75), 3 states have internal predecessors, (75), 3 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (10), 2 states have call predecessors, (10), 3 states have call successors, (10) [2023-11-12 01:04:12,155 INFO L276 IsEmpty]: Start isEmpty. Operand 4151 states and 6465 transitions. [2023-11-12 01:04:12,164 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2023-11-12 01:04:12,165 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:04:12,165 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:04:12,176 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-12 01:04:12,371 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:12,371 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:04:12,371 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:04:12,371 INFO L85 PathProgramCache]: Analyzing trace with hash 724085554, now seen corresponding path program 1 times [2023-11-12 01:04:12,371 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:04:12,372 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1739763408] [2023-11-12 01:04:12,372 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:12,372 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:04:12,394 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:12,637 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 10 proven. 26 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2023-11-12 01:04:12,638 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:04:12,638 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1739763408] [2023-11-12 01:04:12,638 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1739763408] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 01:04:12,638 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1362275935] [2023-11-12 01:04:12,639 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:12,639 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:12,639 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:04:12,640 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:04:12,675 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-12 01:04:12,821 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:12,824 INFO L262 TraceCheckSpWp]: Trace formula consists of 549 conjuncts, 3 conjunts are in the unsatisfiable core [2023-11-12 01:04:12,828 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:04:12,988 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 54 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2023-11-12 01:04:12,988 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 01:04:12,988 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1362275935] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 01:04:12,988 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 01:04:12,989 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [6] total 7 [2023-11-12 01:04:12,989 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1479983630] [2023-11-12 01:04:12,989 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 01:04:12,989 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-12 01:04:12,990 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:04:12,990 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-12 01:04:12,990 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2023-11-12 01:04:12,991 INFO L87 Difference]: Start difference. First operand 4151 states and 6465 transitions. Second operand has 3 states, 3 states have (on average 26.333333333333332) internal successors, (79), 3 states have internal predecessors, (79), 3 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2023-11-12 01:04:13,756 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:04:13,757 INFO L93 Difference]: Finished difference Result 7559 states and 10884 transitions. [2023-11-12 01:04:13,757 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-12 01:04:13,757 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 26.333333333333332) internal successors, (79), 3 states have internal predecessors, (79), 3 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 114 [2023-11-12 01:04:13,758 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:04:13,782 INFO L225 Difference]: With dead ends: 7559 [2023-11-12 01:04:13,782 INFO L226 Difference]: Without dead ends: 5055 [2023-11-12 01:04:13,790 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 116 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2023-11-12 01:04:13,791 INFO L413 NwaCegarLoop]: 3181 mSDtfsCounter, 60 mSDsluCounter, 3149 mSDsCounter, 0 mSdLazyCounter, 472 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 60 SdHoareTripleChecker+Valid, 6330 SdHoareTripleChecker+Invalid, 474 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 472 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-12 01:04:13,791 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [60 Valid, 6330 Invalid, 474 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 472 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-12 01:04:13,800 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 5055 states. [2023-11-12 01:04:14,009 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 5055 to 4415. [2023-11-12 01:04:14,017 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4415 states, 3875 states have (on average 1.5976774193548386) internal successors, (6191), 3891 states have internal predecessors, (6191), 324 states have call successors, (324), 215 states have call predecessors, (324), 214 states have return successors, (322), 309 states have call predecessors, (322), 322 states have call successors, (322) [2023-11-12 01:04:14,032 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4415 states to 4415 states and 6837 transitions. [2023-11-12 01:04:14,033 INFO L78 Accepts]: Start accepts. Automaton has 4415 states and 6837 transitions. Word has length 114 [2023-11-12 01:04:14,033 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:04:14,034 INFO L495 AbstractCegarLoop]: Abstraction has 4415 states and 6837 transitions. [2023-11-12 01:04:14,034 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 26.333333333333332) internal successors, (79), 3 states have internal predecessors, (79), 3 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2023-11-12 01:04:14,034 INFO L276 IsEmpty]: Start isEmpty. Operand 4415 states and 6837 transitions. [2023-11-12 01:04:14,043 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2023-11-12 01:04:14,044 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:04:14,044 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:04:14,055 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2023-11-12 01:04:14,255 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:14,255 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:04:14,256 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:04:14,256 INFO L85 PathProgramCache]: Analyzing trace with hash 78868689, now seen corresponding path program 1 times [2023-11-12 01:04:14,256 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:04:14,256 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1614873908] [2023-11-12 01:04:14,256 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:14,256 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:04:14,280 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:14,365 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 23 proven. 1 refuted. 0 times theorem prover too weak. 49 trivial. 0 not checked. [2023-11-12 01:04:14,366 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:04:14,366 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1614873908] [2023-11-12 01:04:14,366 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1614873908] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 01:04:14,366 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [627396855] [2023-11-12 01:04:14,366 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:14,367 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:14,367 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:04:14,368 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:04:14,387 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-12 01:04:14,557 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:14,560 INFO L262 TraceCheckSpWp]: Trace formula consists of 546 conjuncts, 2 conjunts are in the unsatisfiable core [2023-11-12 01:04:14,563 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:04:14,590 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 59 proven. 0 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2023-11-12 01:04:14,591 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 01:04:14,591 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [627396855] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 01:04:14,591 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 01:04:14,592 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [5] total 6 [2023-11-12 01:04:14,592 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1707364723] [2023-11-12 01:04:14,592 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 01:04:14,593 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-12 01:04:14,593 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:04:14,594 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-12 01:04:14,594 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2023-11-12 01:04:14,594 INFO L87 Difference]: Start difference. First operand 4415 states and 6837 transitions. Second operand has 3 states, 3 states have (on average 26.0) internal successors, (78), 3 states have internal predecessors, (78), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2023-11-12 01:04:15,313 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:04:15,313 INFO L93 Difference]: Finished difference Result 6851 states and 10037 transitions. [2023-11-12 01:04:15,314 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-12 01:04:15,314 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 26.0) internal successors, (78), 3 states have internal predecessors, (78), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 114 [2023-11-12 01:04:15,314 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:04:15,331 INFO L225 Difference]: With dead ends: 6851 [2023-11-12 01:04:15,331 INFO L226 Difference]: Without dead ends: 5013 [2023-11-12 01:04:15,338 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 118 GetRequests, 114 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2023-11-12 01:04:15,339 INFO L413 NwaCegarLoop]: 3216 mSDtfsCounter, 63 mSDsluCounter, 3168 mSDsCounter, 0 mSdLazyCounter, 479 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 63 SdHoareTripleChecker+Valid, 6384 SdHoareTripleChecker+Invalid, 479 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 479 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-12 01:04:15,339 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [63 Valid, 6384 Invalid, 479 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 479 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-12 01:04:15,348 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 5013 states. [2023-11-12 01:04:15,553 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 5013 to 4735. [2023-11-12 01:04:15,562 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4735 states, 4163 states have (on average 1.5909200096084555) internal successors, (6623), 4179 states have internal predecessors, (6623), 340 states have call successors, (340), 231 states have call predecessors, (340), 230 states have return successors, (338), 325 states have call predecessors, (338), 338 states have call successors, (338) [2023-11-12 01:04:15,576 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4735 states to 4735 states and 7301 transitions. [2023-11-12 01:04:15,577 INFO L78 Accepts]: Start accepts. Automaton has 4735 states and 7301 transitions. Word has length 114 [2023-11-12 01:04:15,577 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:04:15,578 INFO L495 AbstractCegarLoop]: Abstraction has 4735 states and 7301 transitions. [2023-11-12 01:04:15,578 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 26.0) internal successors, (78), 3 states have internal predecessors, (78), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2023-11-12 01:04:15,578 INFO L276 IsEmpty]: Start isEmpty. Operand 4735 states and 7301 transitions. [2023-11-12 01:04:15,588 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2023-11-12 01:04:15,588 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:04:15,588 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:04:15,600 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-12 01:04:15,794 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-11-12 01:04:15,795 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:04:15,795 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:04:15,795 INFO L85 PathProgramCache]: Analyzing trace with hash 548145659, now seen corresponding path program 1 times [2023-11-12 01:04:15,795 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:04:15,795 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1563827932] [2023-11-12 01:04:15,796 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:15,796 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:04:15,814 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:16,042 INFO L134 CoverageAnalysis]: Checked inductivity of 75 backedges. 19 proven. 26 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-11-12 01:04:16,043 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:04:16,043 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1563827932] [2023-11-12 01:04:16,043 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1563827932] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 01:04:16,043 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1953301621] [2023-11-12 01:04:16,043 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:16,044 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:16,044 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:04:16,045 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:04:16,053 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-12 01:04:16,215 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:16,218 INFO L262 TraceCheckSpWp]: Trace formula consists of 555 conjuncts, 9 conjunts are in the unsatisfiable core [2023-11-12 01:04:16,221 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:04:16,356 INFO L134 CoverageAnalysis]: Checked inductivity of 75 backedges. 49 proven. 0 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2023-11-12 01:04:16,356 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 01:04:16,356 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1953301621] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 01:04:16,356 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 01:04:16,357 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 7 [2023-11-12 01:04:16,358 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1083473103] [2023-11-12 01:04:16,358 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 01:04:16,359 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-11-12 01:04:16,359 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:04:16,360 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-11-12 01:04:16,360 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2023-11-12 01:04:16,360 INFO L87 Difference]: Start difference. First operand 4735 states and 7301 transitions. Second operand has 6 states, 6 states have (on average 12.5) internal successors, (75), 6 states have internal predecessors, (75), 3 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2023-11-12 01:04:17,757 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:04:17,757 INFO L93 Difference]: Finished difference Result 9247 states and 13153 transitions. [2023-11-12 01:04:17,757 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-11-12 01:04:17,758 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 12.5) internal successors, (75), 6 states have internal predecessors, (75), 3 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 116 [2023-11-12 01:04:17,758 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:04:17,776 INFO L225 Difference]: With dead ends: 9247 [2023-11-12 01:04:17,776 INFO L226 Difference]: Without dead ends: 6159 [2023-11-12 01:04:17,783 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 118 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2023-11-12 01:04:17,784 INFO L413 NwaCegarLoop]: 3171 mSDtfsCounter, 3554 mSDsluCounter, 6310 mSDsCounter, 0 mSdLazyCounter, 789 mSolverCounterSat, 85 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3566 SdHoareTripleChecker+Valid, 9481 SdHoareTripleChecker+Invalid, 874 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.1s SdHoareTripleChecker+Time, 85 IncrementalHoareTripleChecker+Valid, 789 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2023-11-12 01:04:17,785 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3566 Valid, 9481 Invalid, 874 Unknown, 0 Unchecked, 0.1s Time], IncrementalHoareTripleChecker [85 Valid, 789 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2023-11-12 01:04:17,794 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 6159 states. [2023-11-12 01:04:18,106 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 6159 to 6155. [2023-11-12 01:04:18,116 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6155 states, 5313 states have (on average 1.5187276491624317) internal successors, (8069), 5335 states have internal predecessors, (8069), 498 states have call successors, (498), 343 states have call predecessors, (498), 342 states have return successors, (496), 477 states have call predecessors, (496), 496 states have call successors, (496) [2023-11-12 01:04:18,136 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6155 states to 6155 states and 9063 transitions. [2023-11-12 01:04:18,136 INFO L78 Accepts]: Start accepts. Automaton has 6155 states and 9063 transitions. Word has length 116 [2023-11-12 01:04:18,137 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:04:18,137 INFO L495 AbstractCegarLoop]: Abstraction has 6155 states and 9063 transitions. [2023-11-12 01:04:18,137 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 12.5) internal successors, (75), 6 states have internal predecessors, (75), 3 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2023-11-12 01:04:18,137 INFO L276 IsEmpty]: Start isEmpty. Operand 6155 states and 9063 transitions. [2023-11-12 01:04:18,151 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 118 [2023-11-12 01:04:18,151 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:04:18,151 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:04:18,162 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-11-12 01:04:18,357 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:18,358 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:04:18,358 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:04:18,358 INFO L85 PathProgramCache]: Analyzing trace with hash 1586316469, now seen corresponding path program 1 times [2023-11-12 01:04:18,358 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:04:18,359 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [12871573] [2023-11-12 01:04:18,359 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:18,359 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:04:18,388 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:18,476 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 22 proven. 4 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2023-11-12 01:04:18,477 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:04:18,477 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [12871573] [2023-11-12 01:04:18,477 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [12871573] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 01:04:18,477 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [925025987] [2023-11-12 01:04:18,477 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:18,478 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:18,478 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:04:18,481 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:04:18,488 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-11-12 01:04:18,644 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:18,647 INFO L262 TraceCheckSpWp]: Trace formula consists of 559 conjuncts, 2 conjunts are in the unsatisfiable core [2023-11-12 01:04:18,651 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:04:18,676 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 59 proven. 0 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2023-11-12 01:04:18,676 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 01:04:18,676 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [925025987] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 01:04:18,676 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 01:04:18,676 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [5] total 6 [2023-11-12 01:04:18,677 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [493550304] [2023-11-12 01:04:18,677 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 01:04:18,677 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-12 01:04:18,678 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:04:18,678 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-12 01:04:18,678 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2023-11-12 01:04:18,678 INFO L87 Difference]: Start difference. First operand 6155 states and 9063 transitions. Second operand has 3 states, 3 states have (on average 27.0) internal successors, (81), 3 states have internal predecessors, (81), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2023-11-12 01:04:19,509 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:04:19,510 INFO L93 Difference]: Finished difference Result 10223 states and 14395 transitions. [2023-11-12 01:04:19,510 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-12 01:04:19,510 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 27.0) internal successors, (81), 3 states have internal predecessors, (81), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 117 [2023-11-12 01:04:19,511 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:04:19,536 INFO L225 Difference]: With dead ends: 10223 [2023-11-12 01:04:19,536 INFO L226 Difference]: Without dead ends: 7215 [2023-11-12 01:04:19,546 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 117 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2023-11-12 01:04:19,547 INFO L413 NwaCegarLoop]: 3222 mSDtfsCounter, 67 mSDsluCounter, 3168 mSDsCounter, 0 mSdLazyCounter, 481 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 67 SdHoareTripleChecker+Valid, 6390 SdHoareTripleChecker+Invalid, 481 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 481 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-12 01:04:19,547 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [67 Valid, 6390 Invalid, 481 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 481 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-12 01:04:19,560 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7215 states. [2023-11-12 01:04:19,912 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7215 to 6707. [2023-11-12 01:04:19,923 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6707 states, 5801 states have (on average 1.5095673159800034) internal successors, (8757), 5823 states have internal predecessors, (8757), 530 states have call successors, (530), 375 states have call predecessors, (530), 374 states have return successors, (528), 509 states have call predecessors, (528), 528 states have call successors, (528) [2023-11-12 01:04:19,944 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6707 states to 6707 states and 9815 transitions. [2023-11-12 01:04:19,945 INFO L78 Accepts]: Start accepts. Automaton has 6707 states and 9815 transitions. Word has length 117 [2023-11-12 01:04:19,945 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:04:19,945 INFO L495 AbstractCegarLoop]: Abstraction has 6707 states and 9815 transitions. [2023-11-12 01:04:19,945 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 27.0) internal successors, (81), 3 states have internal predecessors, (81), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2023-11-12 01:04:19,946 INFO L276 IsEmpty]: Start isEmpty. Operand 6707 states and 9815 transitions. [2023-11-12 01:04:19,961 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 124 [2023-11-12 01:04:19,962 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:04:19,962 INFO L195 NwaCegarLoop]: trace histogram [5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:04:19,973 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-11-12 01:04:20,173 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:20,174 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:04:20,174 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:04:20,174 INFO L85 PathProgramCache]: Analyzing trace with hash -677666488, now seen corresponding path program 1 times [2023-11-12 01:04:20,175 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:04:20,175 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [283762115] [2023-11-12 01:04:20,175 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:20,175 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:04:20,201 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:20,684 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 12 proven. 26 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2023-11-12 01:04:20,685 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:04:20,685 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [283762115] [2023-11-12 01:04:20,685 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [283762115] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 01:04:20,685 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [600838132] [2023-11-12 01:04:20,685 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:20,686 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:20,686 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:04:20,687 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:04:20,693 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_362a8e16-b7a1-4631-b11c-53cce55cb58c/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-11-12 01:04:20,868 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:04:20,871 INFO L262 TraceCheckSpWp]: Trace formula consists of 627 conjuncts, 15 conjunts are in the unsatisfiable core [2023-11-12 01:04:20,876 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:04:21,034 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 62 proven. 14 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-11-12 01:04:21,034 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 01:04:21,464 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 17 proven. 3 refuted. 0 times theorem prover too weak. 62 trivial. 0 not checked. [2023-11-12 01:04:21,465 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [600838132] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 01:04:21,465 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2015521280] [2023-11-12 01:04:21,488 INFO L159 IcfgInterpreter]: Started Sifa with 71 locations of interest [2023-11-12 01:04:21,489 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 01:04:21,492 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 01:04:21,497 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 01:04:21,498 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs