./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/combinations/Problem05_label45+token_ring.03.cil-1.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 4fc63b2a Calling Ultimate with: /usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/config/TaipanReach.xml -i ../../sv-benchmarks/c/combinations/Problem05_label45+token_ring.03.cil-1.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2 --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 7ec37a095871269c822e7d35e6d840f2de134a68f657807281a5c0e96980df26 --- Real Ultimate output --- This is Ultimate 0.2.5-dev-4fc63b2 [2024-11-02 11:24:40,525 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-02 11:24:40,623 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/config/svcomp-Reach-32bit-Taipan_Default.epf [2024-11-02 11:24:40,633 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-02 11:24:40,634 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-02 11:24:40,674 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-02 11:24:40,675 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-02 11:24:40,675 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-02 11:24:40,676 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-02 11:24:40,677 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-02 11:24:40,678 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-02 11:24:40,678 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-02 11:24:40,679 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-02 11:24:40,679 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-02 11:24:40,681 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-02 11:24:40,682 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-02 11:24:40,682 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-02 11:24:40,682 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-02 11:24:40,683 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-02 11:24:40,683 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-02 11:24:40,683 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-02 11:24:40,688 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-02 11:24:40,688 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-02 11:24:40,689 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-02 11:24:40,689 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-02 11:24:40,689 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-02 11:24:40,690 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-02 11:24:40,690 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-02 11:24:40,690 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-02 11:24:40,690 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-02 11:24:40,691 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-02 11:24:40,691 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-02 11:24:40,691 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-02 11:24:40,692 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-02 11:24:40,693 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-02 11:24:40,693 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-02 11:24:40,694 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-02 11:24:40,694 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-02 11:24:40,695 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-02 11:24:40,695 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-02 11:24:40,695 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-02 11:24:40,696 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-02 11:24:40,696 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-02 11:24:40,696 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-02 11:24:40,697 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-02 11:24:40,697 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-02 11:24:40,697 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-02 11:24:40,698 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_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/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_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2 Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Taipan Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 7ec37a095871269c822e7d35e6d840f2de134a68f657807281a5c0e96980df26 [2024-11-02 11:24:41,000 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-02 11:24:41,031 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-02 11:24:41,035 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-02 11:24:41,038 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-02 11:24:41,038 INFO L274 PluginConnector]: CDTParser initialized [2024-11-02 11:24:41,039 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/../../sv-benchmarks/c/combinations/Problem05_label45+token_ring.03.cil-1.c Unable to find full path for "g++" [2024-11-02 11:24:43,066 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-02 11:24:43,731 INFO L384 CDTParser]: Found 1 translation units. [2024-11-02 11:24:43,732 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/sv-benchmarks/c/combinations/Problem05_label45+token_ring.03.cil-1.c [2024-11-02 11:24:43,785 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/data/3c34b4316/51fae5fd0e324c0eb0c0deade3fd88ed/FLAG2166a7b56 [2024-11-02 11:24:43,803 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/data/3c34b4316/51fae5fd0e324c0eb0c0deade3fd88ed [2024-11-02 11:24:43,806 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-02 11:24:43,809 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-02 11:24:43,810 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-02 11:24:43,810 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-02 11:24:43,816 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-02 11:24:43,817 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.11 11:24:43" (1/1) ... [2024-11-02 11:24:43,818 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2878b377 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 11:24:43, skipping insertion in model container [2024-11-02 11:24:43,820 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.11 11:24:43" (1/1) ... [2024-11-02 11:24:44,039 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-02 11:24:46,545 WARN L251 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_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/sv-benchmarks/c/combinations/Problem05_label45+token_ring.03.cil-1.c[380323,380336] [2024-11-02 11:24:46,577 WARN L251 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_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/sv-benchmarks/c/combinations/Problem05_label45+token_ring.03.cil-1.c[383339,383352] [2024-11-02 11:24:46,758 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-02 11:24:46,766 INFO L200 MainTranslator]: Completed pre-run [2024-11-02 11:24:47,872 WARN L251 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_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/sv-benchmarks/c/combinations/Problem05_label45+token_ring.03.cil-1.c[380323,380336] [2024-11-02 11:24:47,877 WARN L251 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_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/sv-benchmarks/c/combinations/Problem05_label45+token_ring.03.cil-1.c[383339,383352] [2024-11-02 11:24:47,889 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-02 11:24:47,960 INFO L204 MainTranslator]: Completed translation [2024-11-02 11:24:47,961 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 11:24:47 WrapperNode [2024-11-02 11:24:47,961 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-02 11:24:47,962 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-02 11:24:47,962 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-02 11:24:47,962 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-02 11:24:47,970 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 11:24:47" (1/1) ... [2024-11-02 11:24:48,052 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 11:24:47" (1/1) ... [2024-11-02 11:24:48,442 INFO L138 Inliner]: procedures = 50, calls = 51, calls flagged for inlining = 27, calls inlined = 27, statements flattened = 12699 [2024-11-02 11:24:48,443 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-02 11:24:48,443 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-02 11:24:48,443 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-02 11:24:48,444 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-02 11:24:48,453 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 11:24:47" (1/1) ... [2024-11-02 11:24:48,453 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 11:24:47" (1/1) ... [2024-11-02 11:24:48,515 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 11:24:47" (1/1) ... [2024-11-02 11:24:48,518 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 11:24:47" (1/1) ... [2024-11-02 11:24:48,774 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 11:24:47" (1/1) ... [2024-11-02 11:24:48,840 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 11:24:47" (1/1) ... [2024-11-02 11:24:48,863 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 11:24:47" (1/1) ... [2024-11-02 11:24:48,885 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 11:24:47" (1/1) ... [2024-11-02 11:24:49,016 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-02 11:24:49,020 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-02 11:24:49,020 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-02 11:24:49,020 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-02 11:24:49,021 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 11:24:47" (1/1) ... [2024-11-02 11:24:49,030 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-02 11:24:49,041 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/z3 [2024-11-02 11:24:49,055 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-02 11:24:49,058 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-02 11:24:49,092 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-02 11:24:49,093 INFO L130 BoogieDeclarations]: Found specification of procedure activate_threads [2024-11-02 11:24:49,093 INFO L138 BoogieDeclarations]: Found implementation of procedure activate_threads [2024-11-02 11:24:49,094 INFO L130 BoogieDeclarations]: Found specification of procedure immediate_notify [2024-11-02 11:24:49,094 INFO L138 BoogieDeclarations]: Found implementation of procedure immediate_notify [2024-11-02 11:24:49,094 INFO L130 BoogieDeclarations]: Found specification of procedure update_channels [2024-11-02 11:24:49,094 INFO L138 BoogieDeclarations]: Found implementation of procedure update_channels [2024-11-02 11:24:49,094 INFO L130 BoogieDeclarations]: Found specification of procedure error [2024-11-02 11:24:49,094 INFO L138 BoogieDeclarations]: Found implementation of procedure error [2024-11-02 11:24:49,094 INFO L130 BoogieDeclarations]: Found specification of procedure fire_delta_events [2024-11-02 11:24:49,095 INFO L138 BoogieDeclarations]: Found implementation of procedure fire_delta_events [2024-11-02 11:24:49,095 INFO L130 BoogieDeclarations]: Found specification of procedure exists_runnable_thread [2024-11-02 11:24:49,095 INFO L138 BoogieDeclarations]: Found implementation of procedure exists_runnable_thread [2024-11-02 11:24:49,095 INFO L130 BoogieDeclarations]: Found specification of procedure reset_delta_events [2024-11-02 11:24:49,095 INFO L138 BoogieDeclarations]: Found implementation of procedure reset_delta_events [2024-11-02 11:24:49,096 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-02 11:24:49,096 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-02 11:24:49,096 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-02 11:24:49,219 INFO L238 CfgBuilder]: Building ICFG [2024-11-02 11:24:49,221 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-02 11:24:59,116 INFO L? ?]: Removed 1705 outVars from TransFormulas that were not future-live. [2024-11-02 11:24:59,116 INFO L287 CfgBuilder]: Performing block encoding [2024-11-02 11:25:01,494 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-02 11:25:01,494 INFO L316 CfgBuilder]: Removed 7 assume(true) statements. [2024-11-02 11:25:01,494 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.11 11:25:01 BoogieIcfgContainer [2024-11-02 11:25:01,495 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-02 11:25:01,501 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-02 11:25:01,501 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-02 11:25:01,504 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-02 11:25:01,505 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 02.11 11:24:43" (1/3) ... [2024-11-02 11:25:01,505 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@249457a2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.11 11:25:01, skipping insertion in model container [2024-11-02 11:25:01,507 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.11 11:24:47" (2/3) ... [2024-11-02 11:25:01,507 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@249457a2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.11 11:25:01, skipping insertion in model container [2024-11-02 11:25:01,507 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.11 11:25:01" (3/3) ... [2024-11-02 11:25:01,509 INFO L112 eAbstractionObserver]: Analyzing ICFG Problem05_label45+token_ring.03.cil-1.c [2024-11-02 11:25:01,527 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-02 11:25:01,528 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 2 error locations. [2024-11-02 11:25:01,651 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-02 11:25:01,657 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=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;@3a8ee4d7, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-02 11:25:01,657 INFO L334 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2024-11-02 11:25:01,668 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) [2024-11-02 11:25:01,678 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2024-11-02 11:25:01,678 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 11:25:01,679 INFO L215 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] [2024-11-02 11:25:01,679 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 11:25:01,684 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 11:25:01,685 INFO L85 PathProgramCache]: Analyzing trace with hash -1412005592, now seen corresponding path program 1 times [2024-11-02 11:25:01,694 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 11:25:01,695 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1524719589] [2024-11-02 11:25:01,695 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 11:25:01,695 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 11:25:01,853 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 11:25:02,179 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-02 11:25:02,180 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-02 11:25:02,180 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1524719589] [2024-11-02 11:25:02,181 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1524719589] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-02 11:25:02,181 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-02 11:25:02,184 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-02 11:25:02,186 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [239751635] [2024-11-02 11:25:02,187 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-02 11:25:02,192 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-02 11:25:02,192 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-02 11:25:02,212 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-02 11:25:02,212 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-02 11:25:02,218 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) [2024-11-02 11:25:03,212 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-02 11:25:03,213 INFO L93 Difference]: Finished difference Result 3559 states and 6955 transitions. [2024-11-02 11:25:03,214 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-02 11:25:03,215 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 [2024-11-02 11:25:03,216 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-02 11:25:03,239 INFO L225 Difference]: With dead ends: 3559 [2024-11-02 11:25:03,239 INFO L226 Difference]: Without dead ends: 1816 [2024-11-02 11:25:03,247 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-02 11:25:03,250 INFO L432 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.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 586 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-11-02 11:25:03,251 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [3498 Valid, 6448 Invalid, 600 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 586 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-11-02 11:25:03,274 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1816 states. [2024-11-02 11:25:03,383 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1816 to 1815. [2024-11-02 11:25:03,390 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) [2024-11-02 11:25:03,399 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1815 states to 1815 states and 3508 transitions. [2024-11-02 11:25:03,402 INFO L78 Accepts]: Start accepts. Automaton has 1815 states and 3508 transitions. Word has length 41 [2024-11-02 11:25:03,403 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-02 11:25:03,404 INFO L471 AbstractCegarLoop]: Abstraction has 1815 states and 3508 transitions. [2024-11-02 11:25:03,404 INFO L472 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) [2024-11-02 11:25:03,404 INFO L276 IsEmpty]: Start isEmpty. Operand 1815 states and 3508 transitions. [2024-11-02 11:25:03,409 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2024-11-02 11:25:03,411 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 11:25:03,411 INFO L215 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] [2024-11-02 11:25:03,412 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-02 11:25:03,412 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 11:25:03,412 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 11:25:03,414 INFO L85 PathProgramCache]: Analyzing trace with hash -1902654840, now seen corresponding path program 1 times [2024-11-02 11:25:03,414 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 11:25:03,414 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1799463490] [2024-11-02 11:25:03,415 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 11:25:03,415 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 11:25:03,452 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 11:25:03,650 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2024-11-02 11:25:03,651 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-02 11:25:03,651 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1799463490] [2024-11-02 11:25:03,651 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1799463490] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-02 11:25:03,652 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1053078644] [2024-11-02 11:25:03,652 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 11:25:03,652 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 11:25:03,652 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/z3 [2024-11-02 11:25:03,655 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-02 11:25:03,657 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-02 11:25:03,810 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 11:25:03,814 INFO L255 TraceCheckSpWp]: Trace formula consists of 385 conjuncts, 2 conjuncts are in the unsatisfiable core [2024-11-02 11:25:03,822 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-02 11:25:03,893 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 11 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-02 11:25:03,896 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-02 11:25:03,896 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1053078644] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-02 11:25:03,897 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-02 11:25:03,897 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [5] total 6 [2024-11-02 11:25:03,898 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1758086961] [2024-11-02 11:25:03,899 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-02 11:25:03,900 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-02 11:25:03,901 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-02 11:25:03,902 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-02 11:25:03,902 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-02 11:25:03,903 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) [2024-11-02 11:25:04,532 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-02 11:25:04,532 INFO L93 Difference]: Finished difference Result 2146 states and 3973 transitions. [2024-11-02 11:25:04,533 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-02 11:25:04,533 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 [2024-11-02 11:25:04,533 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-02 11:25:04,543 INFO L225 Difference]: With dead ends: 2146 [2024-11-02 11:25:04,544 INFO L226 Difference]: Without dead ends: 1977 [2024-11-02 11:25:04,545 INFO L431 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 [2024-11-02 11:25:04,546 INFO L432 NwaCegarLoop]: 3207 mSDtfsCounter, 3375 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 265 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s 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.5s IncrementalHoareTripleChecker+Time [2024-11-02 11:25:04,547 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [3375 Valid, 3308 Invalid, 267 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 265 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-02 11:25:04,550 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1977 states. [2024-11-02 11:25:04,592 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1977 to 1971. [2024-11-02 11:25:04,596 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) [2024-11-02 11:25:04,605 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1971 states to 1971 states and 3719 transitions. [2024-11-02 11:25:04,606 INFO L78 Accepts]: Start accepts. Automaton has 1971 states and 3719 transitions. Word has length 75 [2024-11-02 11:25:04,606 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-02 11:25:04,607 INFO L471 AbstractCegarLoop]: Abstraction has 1971 states and 3719 transitions. [2024-11-02 11:25:04,607 INFO L472 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) [2024-11-02 11:25:04,607 INFO L276 IsEmpty]: Start isEmpty. Operand 1971 states and 3719 transitions. [2024-11-02 11:25:04,610 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2024-11-02 11:25:04,610 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 11:25:04,610 INFO L215 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] [2024-11-02 11:25:04,632 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-11-02 11:25:04,815 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 11:25:04,815 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 11:25:04,815 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 11:25:04,816 INFO L85 PathProgramCache]: Analyzing trace with hash -773420214, now seen corresponding path program 1 times [2024-11-02 11:25:04,816 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 11:25:04,816 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1269423267] [2024-11-02 11:25:04,816 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 11:25:04,817 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 11:25:04,839 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 11:25:04,976 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2024-11-02 11:25:04,977 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-02 11:25:04,977 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1269423267] [2024-11-02 11:25:04,977 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1269423267] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-02 11:25:04,977 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1667048468] [2024-11-02 11:25:04,977 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 11:25:04,978 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 11:25:04,978 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/z3 [2024-11-02 11:25:04,981 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-02 11:25:04,982 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-02 11:25:05,111 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 11:25:05,113 INFO L255 TraceCheckSpWp]: Trace formula consists of 379 conjuncts, 2 conjuncts are in the unsatisfiable core [2024-11-02 11:25:05,115 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-02 11:25:05,174 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-02 11:25:05,178 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-02 11:25:05,179 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1667048468] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-02 11:25:05,179 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-02 11:25:05,179 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [5] total 6 [2024-11-02 11:25:05,179 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1623546852] [2024-11-02 11:25:05,179 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-02 11:25:05,180 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-02 11:25:05,180 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-02 11:25:05,181 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-02 11:25:05,181 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-02 11:25:05,182 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) [2024-11-02 11:25:05,734 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-02 11:25:05,734 INFO L93 Difference]: Finished difference Result 2608 states and 4606 transitions. [2024-11-02 11:25:05,735 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-02 11:25:05,735 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 [2024-11-02 11:25:05,735 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-02 11:25:05,746 INFO L225 Difference]: With dead ends: 2608 [2024-11-02 11:25:05,747 INFO L226 Difference]: Without dead ends: 2283 [2024-11-02 11:25:05,749 INFO L431 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 [2024-11-02 11:25:05,750 INFO L432 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 [2024-11-02 11:25:05,751 INFO L433 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] [2024-11-02 11:25:05,755 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2283 states. [2024-11-02 11:25:05,816 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2283 to 2275. [2024-11-02 11:25:05,822 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) [2024-11-02 11:25:05,833 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2275 states to 2275 states and 4125 transitions. [2024-11-02 11:25:05,834 INFO L78 Accepts]: Start accepts. Automaton has 2275 states and 4125 transitions. Word has length 75 [2024-11-02 11:25:05,834 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-02 11:25:05,835 INFO L471 AbstractCegarLoop]: Abstraction has 2275 states and 4125 transitions. [2024-11-02 11:25:05,835 INFO L472 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) [2024-11-02 11:25:05,835 INFO L276 IsEmpty]: Start isEmpty. Operand 2275 states and 4125 transitions. [2024-11-02 11:25:05,838 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2024-11-02 11:25:05,838 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 11:25:05,838 INFO L215 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] [2024-11-02 11:25:05,859 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-02 11:25:06,039 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 11:25:06,039 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 11:25:06,040 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 11:25:06,040 INFO L85 PathProgramCache]: Analyzing trace with hash 2071460680, now seen corresponding path program 1 times [2024-11-02 11:25:06,040 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 11:25:06,040 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [393362163] [2024-11-02 11:25:06,040 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 11:25:06,041 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 11:25:06,060 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 11:25:06,337 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-11-02 11:25:06,337 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-02 11:25:06,337 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [393362163] [2024-11-02 11:25:06,338 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [393362163] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-02 11:25:06,338 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-02 11:25:06,338 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-02 11:25:06,338 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1846653342] [2024-11-02 11:25:06,338 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-02 11:25:06,339 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-02 11:25:06,339 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-02 11:25:06,339 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-02 11:25:06,340 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-02 11:25:06,340 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) [2024-11-02 11:25:07,429 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-02 11:25:07,429 INFO L93 Difference]: Finished difference Result 3579 states and 5883 transitions. [2024-11-02 11:25:07,430 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-02 11:25:07,430 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 [2024-11-02 11:25:07,430 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-02 11:25:07,445 INFO L225 Difference]: With dead ends: 3579 [2024-11-02 11:25:07,445 INFO L226 Difference]: Without dead ends: 2951 [2024-11-02 11:25:07,448 INFO L431 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 [2024-11-02 11:25:07,449 INFO L432 NwaCegarLoop]: 3175 mSDtfsCounter, 3577 mSDsluCounter, 6294 mSDsCounter, 0 mSdLazyCounter, 802 mSolverCounterSat, 82 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3589 SdHoareTripleChecker+Valid, 9469 SdHoareTripleChecker+Invalid, 884 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 82 IncrementalHoareTripleChecker+Valid, 802 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2024-11-02 11:25:07,449 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [3589 Valid, 9469 Invalid, 884 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [82 Valid, 802 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2024-11-02 11:25:07,453 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2951 states. [2024-11-02 11:25:07,544 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2951 to 2851. [2024-11-02 11:25:07,550 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) [2024-11-02 11:25:07,563 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2851 states to 2851 states and 4881 transitions. [2024-11-02 11:25:07,564 INFO L78 Accepts]: Start accepts. Automaton has 2851 states and 4881 transitions. Word has length 75 [2024-11-02 11:25:07,565 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-02 11:25:07,565 INFO L471 AbstractCegarLoop]: Abstraction has 2851 states and 4881 transitions. [2024-11-02 11:25:07,565 INFO L472 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) [2024-11-02 11:25:07,565 INFO L276 IsEmpty]: Start isEmpty. Operand 2851 states and 4881 transitions. [2024-11-02 11:25:07,568 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2024-11-02 11:25:07,569 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 11:25:07,569 INFO L215 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] [2024-11-02 11:25:07,569 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-02 11:25:07,569 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 11:25:07,570 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 11:25:07,570 INFO L85 PathProgramCache]: Analyzing trace with hash -1262074616, now seen corresponding path program 1 times [2024-11-02 11:25:07,570 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 11:25:07,570 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1661149258] [2024-11-02 11:25:07,571 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 11:25:07,571 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 11:25:07,589 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 11:25:07,840 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 10 proven. 14 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-11-02 11:25:07,841 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-02 11:25:07,841 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1661149258] [2024-11-02 11:25:07,841 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1661149258] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-02 11:25:07,841 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2123247279] [2024-11-02 11:25:07,841 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 11:25:07,842 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 11:25:07,842 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/z3 [2024-11-02 11:25:07,845 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-02 11:25:07,846 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-02 11:25:07,979 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 11:25:07,981 INFO L255 TraceCheckSpWp]: Trace formula consists of 402 conjuncts, 2 conjuncts are in the unsatisfiable core [2024-11-02 11:25:07,984 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-02 11:25:08,028 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 19 proven. 0 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2024-11-02 11:25:08,029 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-02 11:25:08,029 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2123247279] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-02 11:25:08,029 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-02 11:25:08,029 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [6] total 7 [2024-11-02 11:25:08,029 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1863060996] [2024-11-02 11:25:08,030 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-02 11:25:08,030 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-02 11:25:08,030 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-02 11:25:08,031 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-02 11:25:08,031 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2024-11-02 11:25:08,031 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) [2024-11-02 11:25:08,654 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-02 11:25:08,655 INFO L93 Difference]: Finished difference Result 3802 states and 6174 transitions. [2024-11-02 11:25:08,661 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-02 11:25:08,661 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 [2024-11-02 11:25:08,661 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-02 11:25:08,678 INFO L225 Difference]: With dead ends: 3802 [2024-11-02 11:25:08,678 INFO L226 Difference]: Without dead ends: 3166 [2024-11-02 11:25:08,683 INFO L431 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 [2024-11-02 11:25:08,684 INFO L432 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 [2024-11-02 11:25:08,685 INFO L433 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] [2024-11-02 11:25:08,690 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3166 states. [2024-11-02 11:25:08,807 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3166 to 3035. [2024-11-02 11:25:08,813 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) [2024-11-02 11:25:08,830 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3035 states to 3035 states and 5145 transitions. [2024-11-02 11:25:08,835 INFO L78 Accepts]: Start accepts. Automaton has 3035 states and 5145 transitions. Word has length 89 [2024-11-02 11:25:08,836 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-02 11:25:08,836 INFO L471 AbstractCegarLoop]: Abstraction has 3035 states and 5145 transitions. [2024-11-02 11:25:08,836 INFO L472 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) [2024-11-02 11:25:08,836 INFO L276 IsEmpty]: Start isEmpty. Operand 3035 states and 5145 transitions. [2024-11-02 11:25:08,844 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2024-11-02 11:25:08,847 INFO L207 NwaCegarLoop]: Found error trace [2024-11-02 11:25:08,847 INFO L215 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] [2024-11-02 11:25:08,867 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-02 11:25:09,051 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2c191a89-3b0e-4432-a78b-9b24d2c0ba74/bin/utaipan-verify-DbMuA5NWw2/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-02 11:25:09,052 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-02 11:25:09,053 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-02 11:25:09,053 INFO L85 PathProgramCache]: Analyzing trace with hash 1306086039, now seen corresponding path program 1 times [2024-11-02 11:25:09,053 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-02 11:25:09,053 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [942269509] [2024-11-02 11:25:09,054 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-02 11:25:09,054 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-02 11:25:09,073 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-02 11:25:09,119 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-02 11:25:09,120 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-02 11:25:09,120 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [942269509] [2024-11-02 11:25:09,120 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [942269509] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-02 11:25:09,120 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-02 11:25:09,120 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-02 11:25:09,121 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [739362188] [2024-11-02 11:25:09,121 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-02 11:25:09,121 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-02 11:25:09,121 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-02 11:25:09,122 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-02 11:25:09,122 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-02 11:25:09,122 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) [2024-11-02 11:25:09,800 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-02 11:25:09,801 INFO L93 Difference]: Finished difference Result 5116 states and 7974 transitions. [2024-11-02 11:25:09,801 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-02 11:25:09,801 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 [2024-11-02 11:25:09,803 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-02 11:25:09,819 INFO L225 Difference]: With dead ends: 5116 [2024-11-02 11:25:09,819 INFO L226 Difference]: Without dead ends: 3727 [2024-11-02 11:25:09,824 INFO L431 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 [2024-11-02 11:25:09,826 INFO L432 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 [2024-11-02 11:25:09,826 INFO L433 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] [2024-11-02 11:25:09,832 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3727 states.