./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_unwindbound100.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version a0165632 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_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_unwindbound100.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje --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 f5161832faa85efa7698287d22f9a23de4fa8b958c1b2d2c225d3d8c999a24ce --- Real Ultimate output --- This is Ultimate 0.2.5-dev-a016563 [2024-11-09 05:53:05,702 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 05:53:05,782 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/config/svcomp-Reach-32bit-Taipan_Default.epf [2024-11-09 05:53:05,787 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 05:53:05,788 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 05:53:05,815 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 05:53:05,816 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 05:53:05,816 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 05:53:05,817 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-09 05:53:05,818 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-09 05:53:05,818 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-09 05:53:05,819 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-09 05:53:05,819 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-09 05:53:05,820 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-09 05:53:05,820 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-09 05:53:05,821 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-09 05:53:05,821 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-09 05:53:05,825 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-09 05:53:05,825 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-09 05:53:05,826 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-09 05:53:05,826 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-09 05:53:05,831 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-09 05:53:05,832 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 05:53:05,832 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-09 05:53:05,832 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 05:53:05,833 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 05:53:05,833 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 05:53:05,833 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 05:53:05,834 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-09 05:53:05,834 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-09 05:53:05,835 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-09 05:53:05,835 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 05:53:05,836 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 05:53:05,836 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 05:53:05,837 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 05:53:05,837 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-09 05:53:05,838 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-09 05:53:05,838 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-09 05:53:05,838 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-09 05:53:05,839 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 05:53:05,839 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-09 05:53:05,841 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-09 05:53:05,842 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-09 05:53:05,842 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-09 05:53:05,842 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-09 05:53:05,843 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-09 05:53:05,844 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-09 05:53:05,844 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_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/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_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje 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 -> f5161832faa85efa7698287d22f9a23de4fa8b958c1b2d2c225d3d8c999a24ce [2024-11-09 05:53:06,204 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 05:53:06,233 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 05:53:06,237 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 05:53:06,238 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 05:53:06,239 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 05:53:06,241 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/../../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_unwindbound100.c Unable to find full path for "g++" [2024-11-09 05:53:08,482 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 05:53:08,722 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 05:53:08,725 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_unwindbound100.c [2024-11-09 05:53:08,737 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/data/3ef57bff0/55138069313f4fbfbc8c017a42a2aa81/FLAG4cdb0e29e [2024-11-09 05:53:08,763 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/data/3ef57bff0/55138069313f4fbfbc8c017a42a2aa81 [2024-11-09 05:53:08,766 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 05:53:08,768 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 05:53:08,771 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 05:53:08,773 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 05:53:08,779 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 05:53:08,780 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 05:53:08" (1/1) ... [2024-11-09 05:53:08,781 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@51ab2555 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:53:08, skipping insertion in model container [2024-11-09 05:53:08,784 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 05:53:08" (1/1) ... [2024-11-09 05:53:08,813 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 05:53:09,061 WARN L250 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_b2c9c06b-7042-4c4f-89ba-d46ab246284e/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_unwindbound100.c[489,502] [2024-11-09 05:53:09,108 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 05:53:09,125 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 05:53:09,162 WARN L250 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_b2c9c06b-7042-4c4f-89ba-d46ab246284e/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_unwindbound100.c[489,502] [2024-11-09 05:53:09,187 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 05:53:09,223 INFO L204 MainTranslator]: Completed translation [2024-11-09 05:53:09,224 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:53:09 WrapperNode [2024-11-09 05:53:09,224 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 05:53:09,226 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 05:53:09,226 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 05:53:09,226 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 05:53:09,235 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:53:09" (1/1) ... [2024-11-09 05:53:09,245 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:53:09" (1/1) ... [2024-11-09 05:53:09,270 INFO L138 Inliner]: procedures = 14, calls = 16, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 59 [2024-11-09 05:53:09,271 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 05:53:09,271 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 05:53:09,272 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 05:53:09,272 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 05:53:09,280 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:53:09" (1/1) ... [2024-11-09 05:53:09,280 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:53:09" (1/1) ... [2024-11-09 05:53:09,282 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:53:09" (1/1) ... [2024-11-09 05:53:09,282 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:53:09" (1/1) ... [2024-11-09 05:53:09,286 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:53:09" (1/1) ... [2024-11-09 05:53:09,290 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:53:09" (1/1) ... [2024-11-09 05:53:09,291 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:53:09" (1/1) ... [2024-11-09 05:53:09,292 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:53:09" (1/1) ... [2024-11-09 05:53:09,294 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 05:53:09,295 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-09 05:53:09,296 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-09 05:53:09,296 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-09 05:53:09,297 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:53:09" (1/1) ... [2024-11-09 05:53:09,306 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-09 05:53:09,322 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:53:09,341 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-09 05:53:09,345 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-09 05:53:09,376 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 05:53:09,377 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-09 05:53:09,377 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-09 05:53:09,379 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-09 05:53:09,380 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 05:53:09,380 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 05:53:09,380 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-09 05:53:09,380 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-09 05:53:09,454 INFO L238 CfgBuilder]: Building ICFG [2024-11-09 05:53:09,457 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 05:53:09,789 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2024-11-09 05:53:09,790 INFO L287 CfgBuilder]: Performing block encoding [2024-11-09 05:53:09,858 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 05:53:09,858 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-09 05:53:09,859 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 05:53:09 BoogieIcfgContainer [2024-11-09 05:53:09,859 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-09 05:53:09,862 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-09 05:53:09,863 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-09 05:53:09,867 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-09 05:53:09,867 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.11 05:53:08" (1/3) ... [2024-11-09 05:53:09,868 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6cde114f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 05:53:09, skipping insertion in model container [2024-11-09 05:53:09,869 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:53:09" (2/3) ... [2024-11-09 05:53:09,869 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6cde114f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 05:53:09, skipping insertion in model container [2024-11-09 05:53:09,869 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 05:53:09" (3/3) ... [2024-11-09 05:53:09,871 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd-ll_unwindbound100.c [2024-11-09 05:53:09,894 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-09 05:53:09,894 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-09 05:53:09,963 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-09 05:53:09,970 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;@76fd167f, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-09 05:53:09,971 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-09 05:53:09,978 INFO L276 IsEmpty]: Start isEmpty. Operand has 24 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 12 states have internal predecessors, (16), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-09 05:53:09,989 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2024-11-09 05:53:09,990 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:53:09,991 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:53:09,992 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:53:10,002 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:53:10,005 INFO L85 PathProgramCache]: Analyzing trace with hash -1162680393, now seen corresponding path program 1 times [2024-11-09 05:53:10,018 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:53:10,018 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [94843899] [2024-11-09 05:53:10,019 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:53:10,019 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:53:10,302 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:53:10,385 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-09 05:53:10,386 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:53:10,386 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [94843899] [2024-11-09 05:53:10,387 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [94843899] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 05:53:10,388 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 05:53:10,388 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-09 05:53:10,390 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1644106786] [2024-11-09 05:53:10,391 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 05:53:10,396 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-09 05:53:10,398 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:53:10,430 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-09 05:53:10,432 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-09 05:53:10,435 INFO L87 Difference]: Start difference. First operand has 24 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 12 states have internal predecessors, (16), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 05:53:10,494 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:53:10,496 INFO L93 Difference]: Finished difference Result 42 states and 68 transitions. [2024-11-09 05:53:10,497 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-09 05:53:10,499 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 13 [2024-11-09 05:53:10,499 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:53:10,509 INFO L225 Difference]: With dead ends: 42 [2024-11-09 05:53:10,510 INFO L226 Difference]: Without dead ends: 22 [2024-11-09 05:53:10,514 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-09 05:53:10,518 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 4 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 28 SdHoareTripleChecker+Invalid, 4 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 4 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 05:53:10,520 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 28 Invalid, 4 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 4 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 05:53:10,541 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2024-11-09 05:53:10,569 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2024-11-09 05:53:10,571 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-09 05:53:10,572 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 30 transitions. [2024-11-09 05:53:10,574 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 30 transitions. Word has length 13 [2024-11-09 05:53:10,578 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:53:10,579 INFO L471 AbstractCegarLoop]: Abstraction has 22 states and 30 transitions. [2024-11-09 05:53:10,579 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 05:53:10,579 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 30 transitions. [2024-11-09 05:53:10,581 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2024-11-09 05:53:10,582 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:53:10,582 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:53:10,582 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-09 05:53:10,583 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:53:10,584 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:53:10,584 INFO L85 PathProgramCache]: Analyzing trace with hash 1958383332, now seen corresponding path program 1 times [2024-11-09 05:53:10,585 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:53:10,585 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [582670323] [2024-11-09 05:53:10,586 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:53:10,586 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:53:10,626 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:53:10,818 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-09 05:53:10,818 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:53:10,819 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [582670323] [2024-11-09 05:53:10,819 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [582670323] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 05:53:10,819 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 05:53:10,819 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-09 05:53:10,820 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2070146681] [2024-11-09 05:53:10,820 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 05:53:10,822 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-09 05:53:10,823 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:53:10,824 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-09 05:53:10,824 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-09 05:53:10,825 INFO L87 Difference]: Start difference. First operand 22 states and 30 transitions. Second operand has 4 states, 4 states have (on average 2.0) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 05:53:10,878 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:53:10,878 INFO L93 Difference]: Finished difference Result 34 states and 45 transitions. [2024-11-09 05:53:10,879 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-09 05:53:10,879 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 14 [2024-11-09 05:53:10,880 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:53:10,881 INFO L225 Difference]: With dead ends: 34 [2024-11-09 05:53:10,881 INFO L226 Difference]: Without dead ends: 24 [2024-11-09 05:53:10,881 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-09 05:53:10,883 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 3 mSDsluCounter, 44 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 69 SdHoareTripleChecker+Invalid, 14 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 05:53:10,884 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 69 Invalid, 14 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 05:53:10,885 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2024-11-09 05:53:10,891 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-09 05:53:10,892 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-09 05:53:10,893 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 32 transitions. [2024-11-09 05:53:10,894 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 32 transitions. Word has length 14 [2024-11-09 05:53:10,894 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:53:10,895 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 32 transitions. [2024-11-09 05:53:10,895 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 05:53:10,895 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 32 transitions. [2024-11-09 05:53:10,896 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2024-11-09 05:53:10,896 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:53:10,896 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:53:10,900 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-09 05:53:10,901 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:53:10,902 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:53:10,902 INFO L85 PathProgramCache]: Analyzing trace with hash 1960051628, now seen corresponding path program 1 times [2024-11-09 05:53:10,902 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:53:10,903 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [35370939] [2024-11-09 05:53:10,903 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:53:10,903 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:53:10,951 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:53:10,956 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1051253046] [2024-11-09 05:53:10,957 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:53:10,957 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:53:10,958 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:53:10,960 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:53:10,963 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-09 05:53:11,024 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:53:11,027 INFO L255 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-09 05:53:11,033 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:53:11,173 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-09 05:53:11,174 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 05:53:11,174 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:53:11,174 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [35370939] [2024-11-09 05:53:11,175 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:53:11,178 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1051253046] [2024-11-09 05:53:11,180 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1051253046] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 05:53:11,180 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 05:53:11,181 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 05:53:11,181 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [842571311] [2024-11-09 05:53:11,181 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 05:53:11,182 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 05:53:11,182 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:53:11,183 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 05:53:11,183 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 05:53:11,183 INFO L87 Difference]: Start difference. First operand 24 states and 32 transitions. Second operand has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 05:53:11,289 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:53:11,290 INFO L93 Difference]: Finished difference Result 38 states and 52 transitions. [2024-11-09 05:53:11,291 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 05:53:11,292 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 14 [2024-11-09 05:53:11,292 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:53:11,293 INFO L225 Difference]: With dead ends: 38 [2024-11-09 05:53:11,294 INFO L226 Difference]: Without dead ends: 36 [2024-11-09 05:53:11,294 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 05:53:11,296 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 4 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 05:53:11,297 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 104 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 05:53:11,298 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2024-11-09 05:53:11,309 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 35. [2024-11-09 05:53:11,309 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 16 states have (on average 1.25) internal successors, (20), 18 states have internal predecessors, (20), 15 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-09 05:53:11,310 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 49 transitions. [2024-11-09 05:53:11,311 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 49 transitions. Word has length 14 [2024-11-09 05:53:11,311 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:53:11,312 INFO L471 AbstractCegarLoop]: Abstraction has 35 states and 49 transitions. [2024-11-09 05:53:11,312 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 05:53:11,312 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 49 transitions. [2024-11-09 05:53:11,313 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-09 05:53:11,313 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:53:11,313 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:53:11,335 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-09 05:53:11,514 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:53:11,515 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:53:11,515 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:53:11,515 INFO L85 PathProgramCache]: Analyzing trace with hash -933039579, now seen corresponding path program 1 times [2024-11-09 05:53:11,516 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:53:11,516 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1013176694] [2024-11-09 05:53:11,516 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:53:11,517 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:53:11,544 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:53:11,546 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1562112078] [2024-11-09 05:53:11,546 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:53:11,546 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:53:11,547 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:53:11,549 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:53:11,553 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-09 05:53:11,617 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:53:11,621 INFO L255 TraceCheckSpWp]: Trace formula consists of 74 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-09 05:53:11,623 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:53:11,731 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-09 05:53:11,731 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 05:53:11,732 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:53:11,732 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1013176694] [2024-11-09 05:53:11,732 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:53:11,732 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1562112078] [2024-11-09 05:53:11,733 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1562112078] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 05:53:11,733 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 05:53:11,733 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 05:53:11,733 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [171059371] [2024-11-09 05:53:11,733 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 05:53:11,737 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 05:53:11,737 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:53:11,738 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 05:53:11,738 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 05:53:11,739 INFO L87 Difference]: Start difference. First operand 35 states and 49 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-09 05:53:11,826 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:53:11,826 INFO L93 Difference]: Finished difference Result 42 states and 55 transitions. [2024-11-09 05:53:11,828 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 05:53:11,828 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 19 [2024-11-09 05:53:11,829 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:53:11,830 INFO L225 Difference]: With dead ends: 42 [2024-11-09 05:53:11,830 INFO L226 Difference]: Without dead ends: 40 [2024-11-09 05:53:11,830 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 05:53:11,834 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 4 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 92 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 05:53:11,835 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 92 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 05:53:11,836 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2024-11-09 05:53:11,854 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 39. [2024-11-09 05:53:11,854 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 19 states have (on average 1.2105263157894737) internal successors, (23), 21 states have internal predecessors, (23), 15 states have call successors, (15), 4 states have call predecessors, (15), 4 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-09 05:53:11,855 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 52 transitions. [2024-11-09 05:53:11,856 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 52 transitions. Word has length 19 [2024-11-09 05:53:11,856 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:53:11,856 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 52 transitions. [2024-11-09 05:53:11,856 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-09 05:53:11,857 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 52 transitions. [2024-11-09 05:53:11,857 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-11-09 05:53:11,858 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:53:11,858 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:53:11,880 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-09 05:53:12,062 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:53:12,064 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:53:12,064 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:53:12,064 INFO L85 PathProgramCache]: Analyzing trace with hash 1838169868, now seen corresponding path program 1 times [2024-11-09 05:53:12,065 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:53:12,065 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [762942240] [2024-11-09 05:53:12,065 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:53:12,065 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:53:12,093 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:53:12,094 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1622376742] [2024-11-09 05:53:12,095 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:53:12,095 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:53:12,095 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:53:12,097 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:53:12,106 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-09 05:53:12,182 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:53:12,184 INFO L255 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-09 05:53:12,186 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:53:12,284 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-09 05:53:12,284 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 05:53:12,284 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:53:12,285 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [762942240] [2024-11-09 05:53:12,285 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:53:12,285 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1622376742] [2024-11-09 05:53:12,285 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1622376742] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 05:53:12,286 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 05:53:12,286 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 05:53:12,286 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2747058] [2024-11-09 05:53:12,286 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 05:53:12,287 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 05:53:12,287 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:53:12,288 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 05:53:12,288 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 05:53:12,288 INFO L87 Difference]: Start difference. First operand 39 states and 52 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-09 05:53:12,369 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:53:12,369 INFO L93 Difference]: Finished difference Result 46 states and 58 transitions. [2024-11-09 05:53:12,370 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 05:53:12,370 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 24 [2024-11-09 05:53:12,370 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:53:12,371 INFO L225 Difference]: With dead ends: 46 [2024-11-09 05:53:12,372 INFO L226 Difference]: Without dead ends: 42 [2024-11-09 05:53:12,372 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 05:53:12,373 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 4 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 92 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 05:53:12,374 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 92 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 05:53:12,375 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2024-11-09 05:53:12,384 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 42. [2024-11-09 05:53:12,385 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 24 states have internal predecessors, (26), 14 states have call successors, (14), 5 states have call predecessors, (14), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-09 05:53:12,386 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 52 transitions. [2024-11-09 05:53:12,386 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 52 transitions. Word has length 24 [2024-11-09 05:53:12,386 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:53:12,387 INFO L471 AbstractCegarLoop]: Abstraction has 42 states and 52 transitions. [2024-11-09 05:53:12,387 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-09 05:53:12,387 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 52 transitions. [2024-11-09 05:53:12,388 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2024-11-09 05:53:12,388 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:53:12,388 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:53:12,411 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-09 05:53:12,592 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:53:12,596 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:53:12,600 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:53:12,600 INFO L85 PathProgramCache]: Analyzing trace with hash -1441249495, now seen corresponding path program 1 times [2024-11-09 05:53:12,600 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:53:12,601 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1176584991] [2024-11-09 05:53:12,605 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:53:12,606 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:53:12,647 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:53:12,892 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-09 05:53:12,892 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:53:12,892 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1176584991] [2024-11-09 05:53:12,893 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1176584991] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 05:53:12,893 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 05:53:12,893 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 05:53:12,893 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1209402761] [2024-11-09 05:53:12,893 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 05:53:12,894 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 05:53:12,894 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:53:12,894 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 05:53:12,895 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 05:53:12,895 INFO L87 Difference]: Start difference. First operand 42 states and 52 transitions. Second operand has 5 states, 4 states have (on average 3.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2024-11-09 05:53:13,005 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:53:13,005 INFO L93 Difference]: Finished difference Result 52 states and 64 transitions. [2024-11-09 05:53:13,006 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 05:53:13,007 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) Word has length 30 [2024-11-09 05:53:13,007 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:53:13,008 INFO L225 Difference]: With dead ends: 52 [2024-11-09 05:53:13,008 INFO L226 Difference]: Without dead ends: 50 [2024-11-09 05:53:13,009 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 05:53:13,012 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 3 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 107 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 05:53:13,012 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 107 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 05:53:13,013 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2024-11-09 05:53:13,032 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 47. [2024-11-09 05:53:13,033 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 25 states have (on average 1.16) internal successors, (29), 28 states have internal predecessors, (29), 15 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2024-11-09 05:53:13,035 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 57 transitions. [2024-11-09 05:53:13,035 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 57 transitions. Word has length 30 [2024-11-09 05:53:13,035 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:53:13,036 INFO L471 AbstractCegarLoop]: Abstraction has 47 states and 57 transitions. [2024-11-09 05:53:13,036 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2024-11-09 05:53:13,036 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 57 transitions. [2024-11-09 05:53:13,042 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2024-11-09 05:53:13,042 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:53:13,042 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:53:13,042 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-09 05:53:13,043 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:53:13,043 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:53:13,043 INFO L85 PathProgramCache]: Analyzing trace with hash 1448869900, now seen corresponding path program 1 times [2024-11-09 05:53:13,043 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:53:13,044 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1098393709] [2024-11-09 05:53:13,044 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:53:13,044 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:53:13,077 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:53:13,226 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-09 05:53:13,227 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:53:13,227 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1098393709] [2024-11-09 05:53:13,227 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1098393709] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 05:53:13,228 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2025976519] [2024-11-09 05:53:13,228 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:53:13,228 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:53:13,228 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:53:13,230 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:53:13,232 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-09 05:53:13,304 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:53:13,305 INFO L255 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-09 05:53:13,307 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:53:13,397 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-09 05:53:13,397 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:53:13,508 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-09 05:53:13,509 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2025976519] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:53:13,509 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1004412579] [2024-11-09 05:53:13,534 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2024-11-09 05:53:13,534 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:53:13,539 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:53:13,545 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:53:13,546 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:53:16,276 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2024-11-09 05:53:16,284 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 64 for LOIs [2024-11-09 05:53:16,324 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:53:29,479 WARN L286 SmtUtils]: Spent 12.41s on a formula simplification. DAG size of input: 106 DAG size of output: 104 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 05:53:40,299 WARN L286 SmtUtils]: Spent 8.48s on a formula simplification. DAG size of input: 109 DAG size of output: 106 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 05:53:48,060 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1171#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 05:53:48,061 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:53:48,061 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 05:53:48,061 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 4, 5] total 10 [2024-11-09 05:53:48,061 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1591222227] [2024-11-09 05:53:48,061 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 05:53:48,062 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-09 05:53:48,062 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:53:48,063 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-09 05:53:48,063 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=110, Invalid=488, Unknown=2, NotChecked=0, Total=600 [2024-11-09 05:53:48,063 INFO L87 Difference]: Start difference. First operand 47 states and 57 transitions. Second operand has 10 states, 10 states have (on average 2.9) internal successors, (29), 10 states have internal predecessors, (29), 6 states have call successors, (16), 4 states have call predecessors, (16), 3 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2024-11-09 05:53:48,316 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:53:48,316 INFO L93 Difference]: Finished difference Result 109 states and 132 transitions. [2024-11-09 05:53:48,316 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-09 05:53:48,317 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.9) internal successors, (29), 10 states have internal predecessors, (29), 6 states have call successors, (16), 4 states have call predecessors, (16), 3 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) Word has length 32 [2024-11-09 05:53:48,317 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:53:48,320 INFO L225 Difference]: With dead ends: 109 [2024-11-09 05:53:48,320 INFO L226 Difference]: Without dead ends: 97 [2024-11-09 05:53:48,321 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 102 GetRequests, 77 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 222 ImplicationChecksByTransitivity, 31.8s TimeCoverageRelationStatistics Valid=123, Invalid=577, Unknown=2, NotChecked=0, Total=702 [2024-11-09 05:53:48,322 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 46 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 76 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 125 SdHoareTripleChecker+Invalid, 77 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 76 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 05:53:48,322 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [46 Valid, 125 Invalid, 77 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 76 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 05:53:48,323 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states. [2024-11-09 05:53:48,338 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 91. [2024-11-09 05:53:48,339 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 50 states have (on average 1.16) internal successors, (58), 54 states have internal predecessors, (58), 29 states have call successors, (29), 12 states have call predecessors, (29), 11 states have return successors, (25), 24 states have call predecessors, (25), 25 states have call successors, (25) [2024-11-09 05:53:48,340 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 112 transitions. [2024-11-09 05:53:48,341 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 112 transitions. Word has length 32 [2024-11-09 05:53:48,341 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:53:48,341 INFO L471 AbstractCegarLoop]: Abstraction has 91 states and 112 transitions. [2024-11-09 05:53:48,341 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.9) internal successors, (29), 10 states have internal predecessors, (29), 6 states have call successors, (16), 4 states have call predecessors, (16), 3 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2024-11-09 05:53:48,342 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 112 transitions. [2024-11-09 05:53:48,342 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2024-11-09 05:53:48,343 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:53:48,343 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:53:48,367 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-09 05:53:48,546 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:53:48,547 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:53:48,547 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:53:48,547 INFO L85 PathProgramCache]: Analyzing trace with hash 1450538196, now seen corresponding path program 1 times [2024-11-09 05:53:48,548 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:53:48,548 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [982049365] [2024-11-09 05:53:48,548 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:53:48,548 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:53:48,589 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:53:48,591 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1376793453] [2024-11-09 05:53:48,594 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:53:48,595 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:53:48,595 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:53:48,597 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:53:48,601 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-09 05:53:48,671 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:53:48,672 INFO L255 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-11-09 05:53:48,675 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:53:49,100 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 8 proven. 7 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-09 05:53:49,100 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:53:49,842 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:53:49,842 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [982049365] [2024-11-09 05:53:49,842 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:53:49,842 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1376793453] [2024-11-09 05:53:49,842 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1376793453] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 05:53:49,842 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [269311253] [2024-11-09 05:53:49,845 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2024-11-09 05:53:49,846 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:53:49,846 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:53:49,846 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:53:49,846 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:53:51,108 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2024-11-09 05:53:51,124 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 64 for LOIs [2024-11-09 05:53:51,140 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:54:12,487 WARN L286 SmtUtils]: Spent 12.08s on a formula simplification. DAG size of input: 109 DAG size of output: 106 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 05:54:23,326 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1655#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 05:54:23,326 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:54:23,326 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-09 05:54:23,326 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2024-11-09 05:54:23,326 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1113315398] [2024-11-09 05:54:23,326 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-09 05:54:23,327 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-09 05:54:23,327 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:54:23,328 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-09 05:54:23,328 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=605, Unknown=3, NotChecked=0, Total=702 [2024-11-09 05:54:23,328 INFO L87 Difference]: Start difference. First operand 91 states and 112 transitions. Second operand has 9 states, 9 states have (on average 1.8888888888888888) internal successors, (17), 7 states have internal predecessors, (17), 4 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-11-09 05:54:23,675 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:54:23,675 INFO L93 Difference]: Finished difference Result 97 states and 117 transitions. [2024-11-09 05:54:23,676 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-09 05:54:23,676 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 1.8888888888888888) internal successors, (17), 7 states have internal predecessors, (17), 4 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Word has length 32 [2024-11-09 05:54:23,676 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:54:23,678 INFO L225 Difference]: With dead ends: 97 [2024-11-09 05:54:23,678 INFO L226 Difference]: Without dead ends: 95 [2024-11-09 05:54:23,679 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 51 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 153 ImplicationChecksByTransitivity, 32.8s TimeCoverageRelationStatistics Valid=101, Invalid=652, Unknown=3, NotChecked=0, Total=756 [2024-11-09 05:54:23,680 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 6 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 147 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 151 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 147 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-09 05:54:23,681 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 131 Invalid, 151 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 147 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-09 05:54:23,681 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2024-11-09 05:54:23,709 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 95. [2024-11-09 05:54:23,709 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 95 states, 53 states have (on average 1.150943396226415) internal successors, (61), 57 states have internal predecessors, (61), 29 states have call successors, (29), 13 states have call predecessors, (29), 12 states have return successors, (25), 24 states have call predecessors, (25), 25 states have call successors, (25) [2024-11-09 05:54:23,713 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 115 transitions. [2024-11-09 05:54:23,716 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 115 transitions. Word has length 32 [2024-11-09 05:54:23,717 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:54:23,717 INFO L471 AbstractCegarLoop]: Abstraction has 95 states and 115 transitions. [2024-11-09 05:54:23,717 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 1.8888888888888888) internal successors, (17), 7 states have internal predecessors, (17), 4 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-11-09 05:54:23,718 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 115 transitions. [2024-11-09 05:54:23,720 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-09 05:54:23,721 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:54:23,721 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:54:23,741 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-09 05:54:23,921 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:54:23,922 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:54:23,922 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:54:23,922 INFO L85 PathProgramCache]: Analyzing trace with hash 1744149512, now seen corresponding path program 1 times [2024-11-09 05:54:23,922 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:54:23,922 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [203647334] [2024-11-09 05:54:23,922 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:54:23,923 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:54:23,937 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:54:24,226 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2024-11-09 05:54:24,227 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:54:24,227 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [203647334] [2024-11-09 05:54:24,227 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [203647334] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 05:54:24,228 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1633047631] [2024-11-09 05:54:24,228 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:54:24,228 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:54:24,228 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:54:24,230 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:54:24,233 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-09 05:54:24,287 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:54:24,288 INFO L255 TraceCheckSpWp]: Trace formula consists of 103 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 05:54:24,290 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:54:24,537 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-09 05:54:24,537 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 05:54:24,537 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1633047631] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 05:54:24,537 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-09 05:54:24,538 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [8] total 12 [2024-11-09 05:54:24,538 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1999090992] [2024-11-09 05:54:24,538 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 05:54:24,538 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-09 05:54:24,539 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:54:24,539 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-09 05:54:24,540 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2024-11-09 05:54:24,540 INFO L87 Difference]: Start difference. First operand 95 states and 115 transitions. Second operand has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-11-09 05:54:24,715 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:54:24,715 INFO L93 Difference]: Finished difference Result 97 states and 116 transitions. [2024-11-09 05:54:24,716 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-09 05:54:24,716 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 35 [2024-11-09 05:54:24,716 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:54:24,717 INFO L225 Difference]: With dead ends: 97 [2024-11-09 05:54:24,717 INFO L226 Difference]: Without dead ends: 87 [2024-11-09 05:54:24,718 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2024-11-09 05:54:24,719 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 4 mSDsluCounter, 87 mSDsCounter, 0 mSdLazyCounter, 48 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 51 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 48 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 05:54:24,719 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 112 Invalid, 51 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 48 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 05:54:24,720 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2024-11-09 05:54:24,733 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 87. [2024-11-09 05:54:24,734 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 87 states, 48 states have (on average 1.1458333333333333) internal successors, (55), 52 states have internal predecessors, (55), 27 states have call successors, (27), 11 states have call predecessors, (27), 11 states have return successors, (24), 23 states have call predecessors, (24), 24 states have call successors, (24) [2024-11-09 05:54:24,735 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 106 transitions. [2024-11-09 05:54:24,736 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 106 transitions. Word has length 35 [2024-11-09 05:54:24,736 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:54:24,736 INFO L471 AbstractCegarLoop]: Abstraction has 87 states and 106 transitions. [2024-11-09 05:54:24,736 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-11-09 05:54:24,737 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 106 transitions. [2024-11-09 05:54:24,737 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2024-11-09 05:54:24,738 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:54:24,738 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:54:24,764 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-09 05:54:24,941 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:54:24,942 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:54:24,943 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:54:24,943 INFO L85 PathProgramCache]: Analyzing trace with hash -616433155, now seen corresponding path program 2 times [2024-11-09 05:54:24,943 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:54:24,943 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [542333074] [2024-11-09 05:54:24,943 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:54:24,943 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:54:24,967 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:54:24,969 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1835826613] [2024-11-09 05:54:24,969 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 05:54:24,969 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:54:24,969 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:54:24,987 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:54:24,989 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-09 05:54:25,060 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2024-11-09 05:54:25,060 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 05:54:25,061 INFO L255 TraceCheckSpWp]: Trace formula consists of 90 conjuncts, 23 conjuncts are in the unsatisfiable core [2024-11-09 05:54:25,064 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:54:25,686 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-11-09 05:54:25,686 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:54:26,418 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 8 proven. 4 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-09 05:54:26,418 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:54:26,419 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [542333074] [2024-11-09 05:54:26,419 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:54:26,419 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1835826613] [2024-11-09 05:54:26,419 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1835826613] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:54:26,419 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2054229253] [2024-11-09 05:54:26,422 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2024-11-09 05:54:26,423 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:54:26,423 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:54:26,423 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:54:26,423 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:54:27,553 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2024-11-09 05:54:27,562 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 64 for LOIs [2024-11-09 05:54:27,574 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:54:34,422 WARN L286 SmtUtils]: Spent 5.70s on a formula simplification. DAG size of input: 106 DAG size of output: 102 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 05:54:52,415 WARN L286 SmtUtils]: Spent 13.98s on a formula simplification. DAG size of input: 109 DAG size of output: 107 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 05:54:59,439 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2625#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 05:54:59,439 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:54:59,439 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 05:54:59,439 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6] total 12 [2024-11-09 05:54:59,440 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [181790840] [2024-11-09 05:54:59,440 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 05:54:59,440 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-09 05:54:59,441 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:54:59,441 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-09 05:54:59,442 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=603, Unknown=3, NotChecked=0, Total=702 [2024-11-09 05:54:59,442 INFO L87 Difference]: Start difference. First operand 87 states and 106 transitions. Second operand has 12 states, 11 states have (on average 2.090909090909091) internal successors, (23), 9 states have internal predecessors, (23), 6 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (12), 6 states have call predecessors, (12), 6 states have call successors, (12) [2024-11-09 05:55:03,199 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:55:03,200 INFO L93 Difference]: Finished difference Result 100 states and 120 transitions. [2024-11-09 05:55:03,201 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-09 05:55:03,201 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.090909090909091) internal successors, (23), 9 states have internal predecessors, (23), 6 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (12), 6 states have call predecessors, (12), 6 states have call successors, (12) Word has length 37 [2024-11-09 05:55:03,201 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:55:03,203 INFO L225 Difference]: With dead ends: 100 [2024-11-09 05:55:03,203 INFO L226 Difference]: Without dead ends: 98 [2024-11-09 05:55:03,204 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 114 GetRequests, 84 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 210 ImplicationChecksByTransitivity, 35.3s TimeCoverageRelationStatistics Valid=140, Invalid=849, Unknown=3, NotChecked=0, Total=992 [2024-11-09 05:55:03,205 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 16 mSDsluCounter, 151 mSDsCounter, 0 mSdLazyCounter, 141 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 176 SdHoareTripleChecker+Invalid, 176 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 141 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-09 05:55:03,205 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 176 Invalid, 176 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 141 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-09 05:55:03,206 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2024-11-09 05:55:03,229 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 95. [2024-11-09 05:55:03,229 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 95 states, 54 states have (on average 1.1296296296296295) internal successors, (61), 58 states have internal predecessors, (61), 27 states have call successors, (27), 13 states have call predecessors, (27), 13 states have return successors, (24), 23 states have call predecessors, (24), 24 states have call successors, (24) [2024-11-09 05:55:03,231 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 112 transitions. [2024-11-09 05:55:03,231 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 112 transitions. Word has length 37 [2024-11-09 05:55:03,232 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:55:03,232 INFO L471 AbstractCegarLoop]: Abstraction has 95 states and 112 transitions. [2024-11-09 05:55:03,232 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.090909090909091) internal successors, (23), 9 states have internal predecessors, (23), 6 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (12), 6 states have call predecessors, (12), 6 states have call successors, (12) [2024-11-09 05:55:03,232 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 112 transitions. [2024-11-09 05:55:03,233 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-11-09 05:55:03,233 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:55:03,233 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:55:03,254 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-11-09 05:55:03,434 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-09 05:55:03,434 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:55:03,435 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:55:03,435 INFO L85 PathProgramCache]: Analyzing trace with hash -1332453836, now seen corresponding path program 3 times [2024-11-09 05:55:03,435 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:55:03,435 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [612967899] [2024-11-09 05:55:03,435 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:55:03,435 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:55:03,476 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:55:03,478 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2014752000] [2024-11-09 05:55:03,478 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-09 05:55:03,479 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:55:03,479 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:55:03,481 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:55:03,482 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-09 05:55:03,549 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-09 05:55:03,549 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 05:55:03,551 INFO L255 TraceCheckSpWp]: Trace formula consists of 90 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-09 05:55:03,553 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:55:04,590 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 21 proven. 7 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2024-11-09 05:55:04,590 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:55:05,551 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 22 proven. 5 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2024-11-09 05:55:05,551 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:55:05,551 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [612967899] [2024-11-09 05:55:05,551 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:55:05,551 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2014752000] [2024-11-09 05:55:05,552 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2014752000] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:55:05,552 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [602117998] [2024-11-09 05:55:05,554 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2024-11-09 05:55:05,554 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:55:05,555 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:55:05,555 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:55:05,555 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:55:06,481 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2024-11-09 05:55:06,491 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 64 for LOIs [2024-11-09 05:55:06,512 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:55:25,019 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3225#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 05:55:25,019 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:55:25,019 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 05:55:25,020 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 15 [2024-11-09 05:55:25,020 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [740547336] [2024-11-09 05:55:25,020 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 05:55:25,020 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-09 05:55:25,021 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:55:25,021 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-09 05:55:25,022 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=119, Invalid=748, Unknown=3, NotChecked=0, Total=870 [2024-11-09 05:55:25,022 INFO L87 Difference]: Start difference. First operand 95 states and 112 transitions. Second operand has 15 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 11 states have internal predecessors, (26), 8 states have call successors, (15), 2 states have call predecessors, (15), 3 states have return successors, (14), 8 states have call predecessors, (14), 6 states have call successors, (14) [2024-11-09 05:55:27,386 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:55:27,386 INFO L93 Difference]: Finished difference Result 112 states and 130 transitions. [2024-11-09 05:55:27,387 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-09 05:55:27,387 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 11 states have internal predecessors, (26), 8 states have call successors, (15), 2 states have call predecessors, (15), 3 states have return successors, (14), 8 states have call predecessors, (14), 6 states have call successors, (14) Word has length 42 [2024-11-09 05:55:27,387 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:55:27,389 INFO L225 Difference]: With dead ends: 112 [2024-11-09 05:55:27,389 INFO L226 Difference]: Without dead ends: 104 [2024-11-09 05:55:27,390 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 94 SyntacticMatches, 2 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 259 ImplicationChecksByTransitivity, 20.5s TimeCoverageRelationStatistics Valid=150, Invalid=903, Unknown=3, NotChecked=0, Total=1056 [2024-11-09 05:55:27,392 INFO L432 NwaCegarLoop]: 19 mSDtfsCounter, 19 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 146 mSolverCounterSat, 46 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 192 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 46 IncrementalHoareTripleChecker+Valid, 146 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2024-11-09 05:55:27,392 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [24 Valid, 129 Invalid, 192 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [46 Valid, 146 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2024-11-09 05:55:27,393 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2024-11-09 05:55:27,417 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 104. [2024-11-09 05:55:27,417 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 104 states, 62 states have (on average 1.096774193548387) internal successors, (68), 65 states have internal predecessors, (68), 26 states have call successors, (26), 16 states have call predecessors, (26), 15 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-11-09 05:55:27,418 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 104 states to 104 states and 116 transitions. [2024-11-09 05:55:27,419 INFO L78 Accepts]: Start accepts. Automaton has 104 states and 116 transitions. Word has length 42 [2024-11-09 05:55:27,419 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:55:27,419 INFO L471 AbstractCegarLoop]: Abstraction has 104 states and 116 transitions. [2024-11-09 05:55:27,419 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 11 states have internal predecessors, (26), 8 states have call successors, (15), 2 states have call predecessors, (15), 3 states have return successors, (14), 8 states have call predecessors, (14), 6 states have call successors, (14) [2024-11-09 05:55:27,419 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 116 transitions. [2024-11-09 05:55:27,420 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2024-11-09 05:55:27,420 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:55:27,421 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:55:27,438 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-09 05:55:27,621 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-09 05:55:27,621 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:55:27,622 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:55:27,622 INFO L85 PathProgramCache]: Analyzing trace with hash -912528388, now seen corresponding path program 4 times [2024-11-09 05:55:27,622 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:55:27,622 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [457108021] [2024-11-09 05:55:27,622 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:55:27,622 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:55:27,659 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:55:27,660 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1790241713] [2024-11-09 05:55:27,663 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-09 05:55:27,664 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:55:27,664 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:55:27,666 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:55:27,668 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-09 05:55:27,748 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:55:27,749 INFO L255 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-09 05:55:27,752 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:55:28,771 INFO L134 CoverageAnalysis]: Checked inductivity of 86 backedges. 12 proven. 12 refuted. 0 times theorem prover too weak. 62 trivial. 0 not checked. [2024-11-09 05:55:28,771 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:55:29,338 INFO L134 CoverageAnalysis]: Checked inductivity of 86 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 74 trivial. 0 not checked. [2024-11-09 05:55:29,339 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:55:29,339 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [457108021] [2024-11-09 05:55:29,339 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:55:29,339 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1790241713] [2024-11-09 05:55:29,339 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1790241713] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-09 05:55:29,339 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-09 05:55:29,339 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [7] total 8 [2024-11-09 05:55:29,340 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1487288939] [2024-11-09 05:55:29,340 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 05:55:29,340 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 05:55:29,340 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:55:29,341 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 05:55:29,341 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2024-11-09 05:55:29,341 INFO L87 Difference]: Start difference. First operand 104 states and 116 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-09 05:55:29,498 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:55:29,498 INFO L93 Difference]: Finished difference Result 114 states and 125 transitions. [2024-11-09 05:55:29,499 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 05:55:29,499 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 50 [2024-11-09 05:55:29,499 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:55:29,500 INFO L225 Difference]: With dead ends: 114 [2024-11-09 05:55:29,500 INFO L226 Difference]: Without dead ends: 108 [2024-11-09 05:55:29,500 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 89 SyntacticMatches, 3 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2024-11-09 05:55:29,501 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 5 mSDsluCounter, 53 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 76 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 05:55:29,501 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 76 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 05:55:29,502 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states. [2024-11-09 05:55:29,533 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 100. [2024-11-09 05:55:29,534 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 100 states, 62 states have (on average 1.0806451612903225) internal successors, (67), 64 states have internal predecessors, (67), 22 states have call successors, (22), 16 states have call predecessors, (22), 15 states have return successors, (19), 19 states have call predecessors, (19), 19 states have call successors, (19) [2024-11-09 05:55:29,536 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 108 transitions. [2024-11-09 05:55:29,536 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 108 transitions. Word has length 50 [2024-11-09 05:55:29,537 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:55:29,537 INFO L471 AbstractCegarLoop]: Abstraction has 100 states and 108 transitions. [2024-11-09 05:55:29,537 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-09 05:55:29,537 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 108 transitions. [2024-11-09 05:55:29,538 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2024-11-09 05:55:29,538 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:55:29,538 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:55:29,562 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-11-09 05:55:29,740 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:55:29,741 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:55:29,741 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:55:29,741 INFO L85 PathProgramCache]: Analyzing trace with hash -1858472992, now seen corresponding path program 1 times [2024-11-09 05:55:29,741 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:55:29,742 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [65831154] [2024-11-09 05:55:29,742 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:55:29,742 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:55:29,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:55:30,165 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2024-11-09 05:55:30,166 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:55:30,166 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [65831154] [2024-11-09 05:55:30,166 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [65831154] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 05:55:30,166 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2027964190] [2024-11-09 05:55:30,166 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:55:30,166 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:55:30,167 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:55:30,169 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:55:30,172 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-09 05:55:30,240 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:55:30,242 INFO L255 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-09 05:55:30,245 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:55:30,392 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 41 proven. 5 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-09 05:55:30,393 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:55:30,604 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 41 proven. 5 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-09 05:55:30,604 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2027964190] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:55:30,604 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1891040292] [2024-11-09 05:55:30,608 INFO L159 IcfgInterpreter]: Started Sifa with 20 locations of interest [2024-11-09 05:55:30,608 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:55:30,608 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:55:30,609 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:55:30,609 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:55:31,953 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2024-11-09 05:55:31,963 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 64 for LOIs [2024-11-09 05:55:31,979 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:55:46,004 WARN L286 SmtUtils]: Spent 13.03s on a formula simplification. DAG size of input: 106 DAG size of output: 104 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 05:55:53,369 WARN L286 SmtUtils]: Spent 6.95s on a formula simplification. DAG size of input: 109 DAG size of output: 107 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 05:56:04,725 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4558#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 05:56:04,726 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:56:04,726 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 05:56:04,726 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 9, 8] total 13 [2024-11-09 05:56:04,726 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1619469450] [2024-11-09 05:56:04,726 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 05:56:04,727 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-09 05:56:04,727 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:56:04,727 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-09 05:56:04,728 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=117, Invalid=692, Unknown=3, NotChecked=0, Total=812 [2024-11-09 05:56:04,728 INFO L87 Difference]: Start difference. First operand 100 states and 108 transitions. Second operand has 13 states, 10 states have (on average 2.2) internal successors, (22), 10 states have internal predecessors, (22), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (12), 4 states have call predecessors, (12), 6 states have call successors, (12) [2024-11-09 05:56:05,000 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:56:05,000 INFO L93 Difference]: Finished difference Result 106 states and 113 transitions. [2024-11-09 05:56:05,001 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 05:56:05,001 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 10 states have (on average 2.2) internal successors, (22), 10 states have internal predecessors, (22), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (12), 4 states have call predecessors, (12), 6 states have call successors, (12) Word has length 53 [2024-11-09 05:56:05,001 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:56:05,002 INFO L225 Difference]: With dead ends: 106 [2024-11-09 05:56:05,002 INFO L226 Difference]: Without dead ends: 86 [2024-11-09 05:56:05,003 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 167 GetRequests, 139 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 211 ImplicationChecksByTransitivity, 33.0s TimeCoverageRelationStatistics Valid=125, Invalid=742, Unknown=3, NotChecked=0, Total=870 [2024-11-09 05:56:05,003 INFO L432 NwaCegarLoop]: 19 mSDtfsCounter, 7 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 129 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 114 SdHoareTripleChecker+Invalid, 138 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 129 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 05:56:05,004 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 114 Invalid, 138 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 129 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 05:56:05,004 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2024-11-09 05:56:05,023 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 86. [2024-11-09 05:56:05,024 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 86 states, 54 states have (on average 1.037037037037037) internal successors, (56), 55 states have internal predecessors, (56), 18 states have call successors, (18), 13 states have call predecessors, (18), 13 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2024-11-09 05:56:05,024 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 91 transitions. [2024-11-09 05:56:05,025 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 91 transitions. Word has length 53 [2024-11-09 05:56:05,025 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:56:05,025 INFO L471 AbstractCegarLoop]: Abstraction has 86 states and 91 transitions. [2024-11-09 05:56:05,026 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 10 states have (on average 2.2) internal successors, (22), 10 states have internal predecessors, (22), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (12), 4 states have call predecessors, (12), 6 states have call successors, (12) [2024-11-09 05:56:05,026 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 91 transitions. [2024-11-09 05:56:05,027 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2024-11-09 05:56:05,027 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:56:05,027 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:56:05,048 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-09 05:56:05,231 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-09 05:56:05,232 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:56:05,232 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:56:05,232 INFO L85 PathProgramCache]: Analyzing trace with hash 1083291565, now seen corresponding path program 5 times [2024-11-09 05:56:05,232 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:56:05,233 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1715271287] [2024-11-09 05:56:05,233 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:56:05,233 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:56:05,292 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:56:05,294 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [861734034] [2024-11-09 05:56:05,294 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 05:56:05,295 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:56:05,295 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:56:05,296 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:56:05,299 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-09 05:56:05,436 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-09 05:56:05,436 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 05:56:05,438 INFO L255 TraceCheckSpWp]: Trace formula consists of 149 conjuncts, 30 conjuncts are in the unsatisfiable core [2024-11-09 05:56:05,442 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:56:10,184 INFO L134 CoverageAnalysis]: Checked inductivity of 232 backedges. 43 proven. 35 refuted. 0 times theorem prover too weak. 154 trivial. 0 not checked. [2024-11-09 05:56:10,184 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:56:13,486 INFO L134 CoverageAnalysis]: Checked inductivity of 232 backedges. 57 proven. 20 refuted. 0 times theorem prover too weak. 155 trivial. 0 not checked. [2024-11-09 05:56:13,486 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:56:13,487 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1715271287] [2024-11-09 05:56:13,487 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:56:13,487 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [861734034] [2024-11-09 05:56:13,487 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [861734034] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:56:13,487 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [177857466] [2024-11-09 05:56:13,489 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2024-11-09 05:56:13,489 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:56:13,490 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:56:13,490 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:56:13,490 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:56:14,310 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2024-11-09 05:56:14,319 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 64 for LOIs [2024-11-09 05:56:14,336 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:56:28,896 WARN L286 SmtUtils]: Spent 12.96s on a formula simplification. DAG size of input: 106 DAG size of output: 106 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 05:56:40,981 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5328#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 05:56:40,981 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:56:40,982 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 05:56:40,982 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10] total 19 [2024-11-09 05:56:40,982 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1451522611] [2024-11-09 05:56:40,982 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 05:56:40,982 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-09 05:56:40,982 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:56:40,983 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-09 05:56:40,984 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=153, Invalid=967, Unknown=2, NotChecked=0, Total=1122 [2024-11-09 05:56:40,984 INFO L87 Difference]: Start difference. First operand 86 states and 91 transitions. Second operand has 19 states, 18 states have (on average 2.2222222222222223) internal successors, (40), 16 states have internal predecessors, (40), 10 states have call successors, (25), 3 states have call predecessors, (25), 3 states have return successors, (24), 11 states have call predecessors, (24), 10 states have call successors, (24) [2024-11-09 05:56:42,780 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:56:42,780 INFO L93 Difference]: Finished difference Result 96 states and 103 transitions. [2024-11-09 05:56:42,781 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-09 05:56:42,781 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 2.2222222222222223) internal successors, (40), 16 states have internal predecessors, (40), 10 states have call successors, (25), 3 states have call predecessors, (25), 3 states have return successors, (24), 11 states have call predecessors, (24), 10 states have call successors, (24) Word has length 73 [2024-11-09 05:56:42,781 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:56:42,785 INFO L225 Difference]: With dead ends: 96 [2024-11-09 05:56:42,786 INFO L226 Difference]: Without dead ends: 94 [2024-11-09 05:56:42,786 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 221 GetRequests, 185 SyntacticMatches, 0 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 336 ImplicationChecksByTransitivity, 28.8s TimeCoverageRelationStatistics Valid=202, Invalid=1202, Unknown=2, NotChecked=0, Total=1406 [2024-11-09 05:56:42,787 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 15 mSDsluCounter, 205 mSDsCounter, 0 mSdLazyCounter, 281 mSolverCounterSat, 44 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 234 SdHoareTripleChecker+Invalid, 325 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 281 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2024-11-09 05:56:42,788 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 234 Invalid, 325 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 281 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2024-11-09 05:56:42,788 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 94 states. [2024-11-09 05:56:42,823 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 94 to 90. [2024-11-09 05:56:42,823 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 90 states, 57 states have (on average 1.0350877192982457) internal successors, (59), 58 states have internal predecessors, (59), 18 states have call successors, (18), 14 states have call predecessors, (18), 14 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2024-11-09 05:56:42,824 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 94 transitions. [2024-11-09 05:56:42,824 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 94 transitions. Word has length 73 [2024-11-09 05:56:42,826 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:56:42,826 INFO L471 AbstractCegarLoop]: Abstraction has 90 states and 94 transitions. [2024-11-09 05:56:42,826 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 2.2222222222222223) internal successors, (40), 16 states have internal predecessors, (40), 10 states have call successors, (25), 3 states have call predecessors, (25), 3 states have return successors, (24), 11 states have call predecessors, (24), 10 states have call successors, (24) [2024-11-09 05:56:42,827 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 94 transitions. [2024-11-09 05:56:42,829 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2024-11-09 05:56:42,829 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:56:42,830 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 5, 4, 4, 4, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:56:42,852 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-09 05:56:43,034 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-11-09 05:56:43,035 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:56:43,035 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:56:43,035 INFO L85 PathProgramCache]: Analyzing trace with hash -1024952444, now seen corresponding path program 2 times [2024-11-09 05:56:43,035 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:56:43,036 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1132587565] [2024-11-09 05:56:43,036 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:56:43,036 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:56:43,051 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:56:43,344 INFO L134 CoverageAnalysis]: Checked inductivity of 334 backedges. 24 proven. 44 refuted. 0 times theorem prover too weak. 266 trivial. 0 not checked. [2024-11-09 05:56:43,344 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:56:43,344 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1132587565] [2024-11-09 05:56:43,345 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1132587565] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 05:56:43,345 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [873320757] [2024-11-09 05:56:43,345 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 05:56:43,345 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:56:43,346 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:56:43,347 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:56:43,353 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-09 05:56:43,699 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2024-11-09 05:56:43,699 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 05:56:43,701 INFO L255 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 05:56:43,703 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:56:43,993 INFO L134 CoverageAnalysis]: Checked inductivity of 334 backedges. 24 proven. 260 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2024-11-09 05:56:43,994 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:56:44,393 INFO L134 CoverageAnalysis]: Checked inductivity of 334 backedges. 24 proven. 44 refuted. 0 times theorem prover too weak. 266 trivial. 0 not checked. [2024-11-09 05:56:44,393 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [873320757] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:56:44,393 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [102379001] [2024-11-09 05:56:44,395 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2024-11-09 05:56:44,396 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:56:44,396 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:56:44,396 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:56:44,397 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:56:45,242 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2024-11-09 05:56:45,249 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 64 for LOIs [2024-11-09 05:56:45,260 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:56:58,488 WARN L286 SmtUtils]: Spent 7.77s on a formula simplification. DAG size of input: 109 DAG size of output: 107 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 05:57:06,254 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '6168#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 05:57:06,254 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:57:06,254 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 05:57:06,255 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 8] total 16 [2024-11-09 05:57:06,255 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [157354708] [2024-11-09 05:57:06,255 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 05:57:06,255 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-09 05:57:06,256 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:57:06,256 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-09 05:57:06,257 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=202, Invalid=725, Unknown=3, NotChecked=0, Total=930 [2024-11-09 05:57:06,257 INFO L87 Difference]: Start difference. First operand 90 states and 94 transitions. Second operand has 16 states, 16 states have (on average 3.5) internal successors, (56), 16 states have internal predecessors, (56), 12 states have call successors, (43), 7 states have call predecessors, (43), 6 states have return successors, (42), 11 states have call predecessors, (42), 11 states have call successors, (42) [2024-11-09 05:57:06,977 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:57:06,978 INFO L93 Difference]: Finished difference Result 212 states and 223 transitions. [2024-11-09 05:57:06,978 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-09 05:57:06,978 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.5) internal successors, (56), 16 states have internal predecessors, (56), 12 states have call successors, (43), 7 states have call predecessors, (43), 6 states have return successors, (42), 11 states have call predecessors, (42), 11 states have call successors, (42) Word has length 86 [2024-11-09 05:57:06,979 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:57:06,980 INFO L225 Difference]: With dead ends: 212 [2024-11-09 05:57:06,980 INFO L226 Difference]: Without dead ends: 198 [2024-11-09 05:57:06,981 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 273 GetRequests, 236 SyntacticMatches, 0 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 506 ImplicationChecksByTransitivity, 21.6s TimeCoverageRelationStatistics Valid=302, Invalid=1177, Unknown=3, NotChecked=0, Total=1482 [2024-11-09 05:57:06,981 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 47 mSDsluCounter, 128 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 152 SdHoareTripleChecker+Invalid, 136 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-09 05:57:06,983 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 152 Invalid, 136 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-09 05:57:06,983 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 198 states. [2024-11-09 05:57:07,037 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 198 to 198. [2024-11-09 05:57:07,037 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 198 states, 129 states have (on average 1.0155038759689923) internal successors, (131), 130 states have internal predecessors, (131), 36 states have call successors, (36), 32 states have call predecessors, (36), 32 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2024-11-09 05:57:07,038 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 198 states to 198 states and 202 transitions. [2024-11-09 05:57:07,038 INFO L78 Accepts]: Start accepts. Automaton has 198 states and 202 transitions. Word has length 86 [2024-11-09 05:57:07,039 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:57:07,039 INFO L471 AbstractCegarLoop]: Abstraction has 198 states and 202 transitions. [2024-11-09 05:57:07,039 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.5) internal successors, (56), 16 states have internal predecessors, (56), 12 states have call successors, (43), 7 states have call predecessors, (43), 6 states have return successors, (42), 11 states have call predecessors, (42), 11 states have call successors, (42) [2024-11-09 05:57:07,039 INFO L276 IsEmpty]: Start isEmpty. Operand 198 states and 202 transitions. [2024-11-09 05:57:07,042 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 195 [2024-11-09 05:57:07,042 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:57:07,042 INFO L215 NwaCegarLoop]: trace histogram [31, 30, 30, 11, 10, 10, 10, 10, 10, 10, 10, 10, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:57:07,050 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-09 05:57:07,246 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-11-09 05:57:07,247 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:57:07,247 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:57:07,247 INFO L85 PathProgramCache]: Analyzing trace with hash -115931020, now seen corresponding path program 3 times [2024-11-09 05:57:07,247 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:57:07,248 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1241948784] [2024-11-09 05:57:07,248 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:57:07,248 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:57:07,281 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:57:08,403 INFO L134 CoverageAnalysis]: Checked inductivity of 2092 backedges. 60 proven. 290 refuted. 0 times theorem prover too weak. 1742 trivial. 0 not checked. [2024-11-09 05:57:08,403 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:57:08,404 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1241948784] [2024-11-09 05:57:08,404 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1241948784] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 05:57:08,404 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [598726206] [2024-11-09 05:57:08,404 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-09 05:57:08,404 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:57:08,404 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:57:08,407 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:57:08,409 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-09 05:57:08,556 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-09 05:57:08,557 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 05:57:08,560 INFO L255 TraceCheckSpWp]: Trace formula consists of 405 conjuncts, 23 conjuncts are in the unsatisfiable core [2024-11-09 05:57:08,565 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:57:09,283 INFO L134 CoverageAnalysis]: Checked inductivity of 2092 backedges. 60 proven. 1910 refuted. 0 times theorem prover too weak. 122 trivial. 0 not checked. [2024-11-09 05:57:09,284 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:57:10,214 INFO L134 CoverageAnalysis]: Checked inductivity of 2092 backedges. 60 proven. 290 refuted. 0 times theorem prover too weak. 1742 trivial. 0 not checked. [2024-11-09 05:57:10,214 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [598726206] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:57:10,215 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1390659046] [2024-11-09 05:57:10,217 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2024-11-09 05:57:10,217 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:57:10,218 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:57:10,218 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:57:10,218 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:57:11,167 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2024-11-09 05:57:11,177 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 64 for LOIs [2024-11-09 05:57:11,195 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:57:27,339 WARN L286 SmtUtils]: Spent 8.77s on a formula simplification. DAG size of input: 109 DAG size of output: 108 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 05:57:36,544 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '8025#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 05:57:36,544 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:57:36,545 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 05:57:36,545 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13, 14] total 28 [2024-11-09 05:57:36,545 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1231680551] [2024-11-09 05:57:36,545 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 05:57:36,546 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2024-11-09 05:57:36,546 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:57:36,547 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2024-11-09 05:57:36,547 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=496, Invalid=1307, Unknown=3, NotChecked=0, Total=1806 [2024-11-09 05:57:36,548 INFO L87 Difference]: Start difference. First operand 198 states and 202 transitions. Second operand has 28 states, 28 states have (on average 3.9285714285714284) internal successors, (110), 28 states have internal predecessors, (110), 24 states have call successors, (97), 13 states have call predecessors, (97), 12 states have return successors, (96), 23 states have call predecessors, (96), 23 states have call successors, (96) [2024-11-09 05:57:38,659 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:57:38,659 INFO L93 Difference]: Finished difference Result 428 states and 445 transitions. [2024-11-09 05:57:38,660 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2024-11-09 05:57:38,660 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 28 states have (on average 3.9285714285714284) internal successors, (110), 28 states have internal predecessors, (110), 24 states have call successors, (97), 13 states have call predecessors, (97), 12 states have return successors, (96), 23 states have call predecessors, (96), 23 states have call successors, (96) Word has length 194 [2024-11-09 05:57:38,661 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:57:38,663 INFO L225 Difference]: With dead ends: 428 [2024-11-09 05:57:38,663 INFO L226 Difference]: Without dead ends: 414 [2024-11-09 05:57:38,665 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 615 GetRequests, 554 SyntacticMatches, 0 SemanticMatches, 61 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1167 ImplicationChecksByTransitivity, 27.3s TimeCoverageRelationStatistics Valid=986, Invalid=2917, Unknown=3, NotChecked=0, Total=3906 [2024-11-09 05:57:38,666 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 131 mSDsluCounter, 122 mSDsCounter, 0 mSdLazyCounter, 228 mSolverCounterSat, 58 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 131 SdHoareTripleChecker+Valid, 146 SdHoareTripleChecker+Invalid, 286 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 58 IncrementalHoareTripleChecker+Valid, 228 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-11-09 05:57:38,666 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [131 Valid, 146 Invalid, 286 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [58 Valid, 228 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-11-09 05:57:38,667 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 414 states. [2024-11-09 05:57:38,797 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 414 to 414. [2024-11-09 05:57:38,798 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 414 states, 273 states have (on average 1.0073260073260073) internal successors, (275), 274 states have internal predecessors, (275), 72 states have call successors, (72), 68 states have call predecessors, (72), 68 states have return successors, (71), 71 states have call predecessors, (71), 71 states have call successors, (71) [2024-11-09 05:57:38,800 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 414 states to 414 states and 418 transitions. [2024-11-09 05:57:38,800 INFO L78 Accepts]: Start accepts. Automaton has 414 states and 418 transitions. Word has length 194 [2024-11-09 05:57:38,801 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:57:38,801 INFO L471 AbstractCegarLoop]: Abstraction has 414 states and 418 transitions. [2024-11-09 05:57:38,801 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 28 states have (on average 3.9285714285714284) internal successors, (110), 28 states have internal predecessors, (110), 24 states have call successors, (97), 13 states have call predecessors, (97), 12 states have return successors, (96), 23 states have call predecessors, (96), 23 states have call successors, (96) [2024-11-09 05:57:38,802 INFO L276 IsEmpty]: Start isEmpty. Operand 414 states and 418 transitions. [2024-11-09 05:57:38,809 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 411 [2024-11-09 05:57:38,809 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:57:38,810 INFO L215 NwaCegarLoop]: trace histogram [67, 66, 66, 23, 22, 22, 22, 22, 22, 22, 22, 22, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:57:38,832 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-11-09 05:57:39,010 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2024-11-09 05:57:39,011 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:57:39,011 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:57:39,011 INFO L85 PathProgramCache]: Analyzing trace with hash -806571436, now seen corresponding path program 4 times [2024-11-09 05:57:39,011 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:57:39,011 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [873110569] [2024-11-09 05:57:39,011 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:57:39,012 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:57:39,093 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:57:42,639 INFO L134 CoverageAnalysis]: Checked inductivity of 10144 backedges. 132 proven. 1430 refuted. 0 times theorem prover too weak. 8582 trivial. 0 not checked. [2024-11-09 05:57:42,639 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:57:42,639 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [873110569] [2024-11-09 05:57:42,639 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [873110569] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 05:57:42,640 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1122736944] [2024-11-09 05:57:42,640 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-09 05:57:42,640 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:57:42,640 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:57:42,642 INFO L229 MonitoredProcess]: Starting monitored process 15 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:57:42,645 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-09 05:57:42,855 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:57:42,859 INFO L255 TraceCheckSpWp]: Trace formula consists of 813 conjuncts, 47 conjuncts are in the unsatisfiable core [2024-11-09 05:57:42,864 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:57:44,253 INFO L134 CoverageAnalysis]: Checked inductivity of 10144 backedges. 132 proven. 9746 refuted. 0 times theorem prover too weak. 266 trivial. 0 not checked. [2024-11-09 05:57:44,254 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:57:47,758 INFO L134 CoverageAnalysis]: Checked inductivity of 10144 backedges. 132 proven. 1430 refuted. 0 times theorem prover too weak. 8582 trivial. 0 not checked. [2024-11-09 05:57:47,758 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1122736944] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:57:47,758 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1790018416] [2024-11-09 05:57:47,764 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2024-11-09 05:57:47,764 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:57:47,764 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:57:47,765 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:57:47,765 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:57:48,668 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2024-11-09 05:57:48,675 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 64 for LOIs [2024-11-09 05:57:48,686 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:58:07,219 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '11898#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 05:58:07,220 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:58:07,220 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 05:58:07,220 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 25, 26] total 52 [2024-11-09 05:58:07,220 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [777355149] [2024-11-09 05:58:07,220 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 05:58:07,222 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 52 states [2024-11-09 05:58:07,222 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:58:07,223 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 52 interpolants. [2024-11-09 05:58:07,225 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1516, Invalid=2903, Unknown=3, NotChecked=0, Total=4422 [2024-11-09 05:58:07,225 INFO L87 Difference]: Start difference. First operand 414 states and 418 transitions. Second operand has 52 states, 52 states have (on average 4.1923076923076925) internal successors, (218), 52 states have internal predecessors, (218), 48 states have call successors, (205), 25 states have call predecessors, (205), 24 states have return successors, (204), 47 states have call predecessors, (204), 47 states have call successors, (204) [2024-11-09 05:58:12,689 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:58:12,689 INFO L93 Difference]: Finished difference Result 860 states and 889 transitions. [2024-11-09 05:58:12,690 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 94 states. [2024-11-09 05:58:12,690 INFO L78 Accepts]: Start accepts. Automaton has has 52 states, 52 states have (on average 4.1923076923076925) internal successors, (218), 52 states have internal predecessors, (218), 48 states have call successors, (205), 25 states have call predecessors, (205), 24 states have return successors, (204), 47 states have call predecessors, (204), 47 states have call successors, (204) Word has length 410 [2024-11-09 05:58:12,691 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:58:12,696 INFO L225 Difference]: With dead ends: 860 [2024-11-09 05:58:12,696 INFO L226 Difference]: Without dead ends: 846 [2024-11-09 05:58:12,700 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 1299 GetRequests, 1190 SyntacticMatches, 0 SemanticMatches, 109 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3057 ImplicationChecksByTransitivity, 25.5s TimeCoverageRelationStatistics Valid=3650, Invalid=8557, Unknown=3, NotChecked=0, Total=12210 [2024-11-09 05:58:12,701 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 257 mSDsluCounter, 240 mSDsCounter, 0 mSdLazyCounter, 425 mSolverCounterSat, 112 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 257 SdHoareTripleChecker+Valid, 264 SdHoareTripleChecker+Invalid, 537 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 112 IncrementalHoareTripleChecker+Valid, 425 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2024-11-09 05:58:12,701 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [257 Valid, 264 Invalid, 537 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [112 Valid, 425 Invalid, 0 Unknown, 0 Unchecked, 1.4s Time] [2024-11-09 05:58:12,702 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 846 states. [2024-11-09 05:58:12,904 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 846 to 846. [2024-11-09 05:58:12,905 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 846 states, 561 states have (on average 1.0035650623885919) internal successors, (563), 562 states have internal predecessors, (563), 144 states have call successors, (144), 140 states have call predecessors, (144), 140 states have return successors, (143), 143 states have call predecessors, (143), 143 states have call successors, (143) [2024-11-09 05:58:12,908 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 846 states to 846 states and 850 transitions. [2024-11-09 05:58:12,909 INFO L78 Accepts]: Start accepts. Automaton has 846 states and 850 transitions. Word has length 410 [2024-11-09 05:58:12,910 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:58:12,910 INFO L471 AbstractCegarLoop]: Abstraction has 846 states and 850 transitions. [2024-11-09 05:58:12,911 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 52 states, 52 states have (on average 4.1923076923076925) internal successors, (218), 52 states have internal predecessors, (218), 48 states have call successors, (205), 25 states have call predecessors, (205), 24 states have return successors, (204), 47 states have call predecessors, (204), 47 states have call successors, (204) [2024-11-09 05:58:12,911 INFO L276 IsEmpty]: Start isEmpty. Operand 846 states and 850 transitions. [2024-11-09 05:58:12,940 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 843 [2024-11-09 05:58:12,940 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:58:12,941 INFO L215 NwaCegarLoop]: trace histogram [139, 138, 138, 47, 46, 46, 46, 46, 46, 46, 46, 46, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:58:12,963 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2024-11-09 05:58:13,141 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable16,15 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:58:13,141 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:58:13,142 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:58:13,142 INFO L85 PathProgramCache]: Analyzing trace with hash 1401562644, now seen corresponding path program 5 times [2024-11-09 05:58:13,142 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:58:13,142 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [168962771] [2024-11-09 05:58:13,142 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:58:13,142 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:58:13,293 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:58:25,556 INFO L134 CoverageAnalysis]: Checked inductivity of 44392 backedges. 276 proven. 6302 refuted. 0 times theorem prover too weak. 37814 trivial. 0 not checked. [2024-11-09 05:58:25,557 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:58:25,557 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [168962771] [2024-11-09 05:58:25,557 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [168962771] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 05:58:25,557 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [582682280] [2024-11-09 05:58:25,557 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 05:58:25,557 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:58:25,558 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:58:25,559 INFO L229 MonitoredProcess]: Starting monitored process 16 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:58:25,560 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-09 06:03:50,775 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 92 check-sat command(s) [2024-11-09 06:03:50,776 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 06:03:50,810 INFO L255 TraceCheckSpWp]: Trace formula consists of 1602 conjuncts, 95 conjuncts are in the unsatisfiable core [2024-11-09 06:03:50,830 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 06:03:54,163 INFO L134 CoverageAnalysis]: Checked inductivity of 44392 backedges. 276 proven. 43562 refuted. 0 times theorem prover too weak. 554 trivial. 0 not checked. [2024-11-09 06:03:54,163 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 06:04:05,921 INFO L134 CoverageAnalysis]: Checked inductivity of 44392 backedges. 276 proven. 6302 refuted. 0 times theorem prover too weak. 37814 trivial. 0 not checked. [2024-11-09 06:04:05,922 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [582682280] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 06:04:05,922 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1205252087] [2024-11-09 06:04:05,925 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2024-11-09 06:04:05,925 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 06:04:05,926 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 06:04:05,926 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 06:04:05,926 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 06:04:06,686 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2024-11-09 06:04:06,693 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 64 for LOIs [2024-11-09 06:04:06,704 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 06:04:14,429 WARN L286 SmtUtils]: Spent 6.40s on a formula simplification. DAG size of input: 106 DAG size of output: 104 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 06:04:31,200 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '19803#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 06:04:31,200 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 06:04:31,201 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 06:04:31,201 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [51, 49, 50] total 100 [2024-11-09 06:04:31,201 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [437472307] [2024-11-09 06:04:31,201 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 06:04:31,203 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 100 states [2024-11-09 06:04:31,203 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 06:04:31,206 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 100 interpolants. [2024-11-09 06:04:31,208 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5285, Invalid=7823, Unknown=2, NotChecked=0, Total=13110 [2024-11-09 06:04:31,209 INFO L87 Difference]: Start difference. First operand 846 states and 850 transitions. Second operand has 100 states, 100 states have (on average 4.34) internal successors, (434), 100 states have internal predecessors, (434), 96 states have call successors, (421), 49 states have call predecessors, (421), 48 states have return successors, (420), 95 states have call predecessors, (420), 95 states have call successors, (420) [2024-11-09 06:04:48,886 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 06:04:48,886 INFO L93 Difference]: Finished difference Result 1724 states and 1777 transitions. [2024-11-09 06:04:48,887 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 190 states. [2024-11-09 06:04:48,888 INFO L78 Accepts]: Start accepts. Automaton has has 100 states, 100 states have (on average 4.34) internal successors, (434), 100 states have internal predecessors, (434), 96 states have call successors, (421), 49 states have call predecessors, (421), 48 states have return successors, (420), 95 states have call predecessors, (420), 95 states have call successors, (420) Word has length 842 [2024-11-09 06:04:48,889 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 06:04:48,896 INFO L225 Difference]: With dead ends: 1724 [2024-11-09 06:04:48,896 INFO L226 Difference]: Without dead ends: 1710 [2024-11-09 06:04:48,905 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2667 GetRequests, 2462 SyntacticMatches, 0 SemanticMatches, 205 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8997 ImplicationChecksByTransitivity, 50.0s TimeCoverageRelationStatistics Valid=14163, Invalid=28477, Unknown=2, NotChecked=0, Total=42642 [2024-11-09 06:04:48,906 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 560 mSDsluCounter, 401 mSDsCounter, 0 mSdLazyCounter, 881 mSolverCounterSat, 271 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 560 SdHoareTripleChecker+Valid, 425 SdHoareTripleChecker+Invalid, 1152 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 271 IncrementalHoareTripleChecker+Valid, 881 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.9s IncrementalHoareTripleChecker+Time [2024-11-09 06:04:48,906 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [560 Valid, 425 Invalid, 1152 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [271 Valid, 881 Invalid, 0 Unknown, 0 Unchecked, 2.9s Time] [2024-11-09 06:04:48,908 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1710 states. [2024-11-09 06:04:49,347 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1710 to 1710. [2024-11-09 06:04:49,350 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1710 states, 1137 states have (on average 1.0017590149516271) internal successors, (1139), 1138 states have internal predecessors, (1139), 288 states have call successors, (288), 284 states have call predecessors, (288), 284 states have return successors, (287), 287 states have call predecessors, (287), 287 states have call successors, (287) [2024-11-09 06:04:49,355 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1710 states to 1710 states and 1714 transitions. [2024-11-09 06:04:49,357 INFO L78 Accepts]: Start accepts. Automaton has 1710 states and 1714 transitions. Word has length 842 [2024-11-09 06:04:49,359 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 06:04:49,359 INFO L471 AbstractCegarLoop]: Abstraction has 1710 states and 1714 transitions. [2024-11-09 06:04:49,360 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 100 states, 100 states have (on average 4.34) internal successors, (434), 100 states have internal predecessors, (434), 96 states have call successors, (421), 49 states have call predecessors, (421), 48 states have return successors, (420), 95 states have call predecessors, (420), 95 states have call successors, (420) [2024-11-09 06:04:49,360 INFO L276 IsEmpty]: Start isEmpty. Operand 1710 states and 1714 transitions. [2024-11-09 06:04:49,405 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1707 [2024-11-09 06:04:49,405 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 06:04:49,405 INFO L215 NwaCegarLoop]: trace histogram [283, 282, 282, 95, 94, 94, 94, 94, 94, 94, 94, 94, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 06:04:49,437 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2024-11-09 06:04:49,605 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2024-11-09 06:04:49,606 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 06:04:49,606 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 06:04:49,606 INFO L85 PathProgramCache]: Analyzing trace with hash -1022521964, now seen corresponding path program 6 times [2024-11-09 06:04:49,606 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 06:04:49,607 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1840975926] [2024-11-09 06:04:49,607 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 06:04:49,607 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 06:04:50,122 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 06:05:43,514 INFO L134 CoverageAnalysis]: Checked inductivity of 185464 backedges. 564 proven. 26414 refuted. 0 times theorem prover too weak. 158486 trivial. 0 not checked. [2024-11-09 06:05:43,514 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 06:05:43,514 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1840975926] [2024-11-09 06:05:43,515 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1840975926] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 06:05:43,515 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [268085499] [2024-11-09 06:05:43,515 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-09 06:05:43,515 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 06:05:43,515 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 06:05:43,517 INFO L229 MonitoredProcess]: Starting monitored process 17 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 06:05:43,518 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-11-09 06:05:50,160 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-09 06:05:50,160 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 06:05:50,184 INFO L255 TraceCheckSpWp]: Trace formula consists of 3261 conjuncts, 191 conjuncts are in the unsatisfiable core [2024-11-09 06:05:50,215 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 06:05:56,072 INFO L134 CoverageAnalysis]: Checked inductivity of 185464 backedges. 564 proven. 183770 refuted. 0 times theorem prover too weak. 1130 trivial. 0 not checked. [2024-11-09 06:05:56,072 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 06:06:13,176 INFO L134 CoverageAnalysis]: Checked inductivity of 185464 backedges. 564 proven. 26414 refuted. 0 times theorem prover too weak. 158486 trivial. 0 not checked. [2024-11-09 06:06:13,176 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [268085499] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 06:06:13,176 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [432185097] [2024-11-09 06:06:13,178 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2024-11-09 06:06:13,179 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 06:06:13,179 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 06:06:13,179 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 06:06:13,179 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 06:06:13,850 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2024-11-09 06:06:13,858 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 64 for LOIs [2024-11-09 06:06:13,868 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 06:06:23,829 WARN L286 SmtUtils]: Spent 7.50s on a formula simplification. DAG size of input: 106 DAG size of output: 104 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 06:06:40,765 WARN L286 SmtUtils]: Spent 9.27s on a formula simplification. DAG size of input: 109 DAG size of output: 107 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 06:06:51,981 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '35682#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 06:06:51,982 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 06:06:51,982 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 06:06:51,982 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [99, 97, 98] total 106 [2024-11-09 06:06:51,982 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [600241072] [2024-11-09 06:06:51,982 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 06:06:51,986 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 106 states [2024-11-09 06:06:51,986 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 06:06:51,990 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 106 interpolants. [2024-11-09 06:06:51,992 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5918, Invalid=8600, Unknown=2, NotChecked=0, Total=14520 [2024-11-09 06:06:51,994 INFO L87 Difference]: Start difference. First operand 1710 states and 1714 transitions. Second operand has 106 states, 106 states have (on average 5.650943396226415) internal successors, (599), 106 states have internal predecessors, (599), 102 states have call successors, (586), 97 states have call predecessors, (586), 96 states have return successors, (585), 101 states have call predecessors, (585), 101 states have call successors, (585) [2024-11-09 06:07:11,596 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 06:07:11,596 INFO L93 Difference]: Finished difference Result 1832 states and 1843 transitions. [2024-11-09 06:07:11,596 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 202 states. [2024-11-09 06:07:11,598 INFO L78 Accepts]: Start accepts. Automaton has has 106 states, 106 states have (on average 5.650943396226415) internal successors, (599), 106 states have internal predecessors, (599), 102 states have call successors, (586), 97 states have call predecessors, (586), 96 states have return successors, (585), 101 states have call predecessors, (585), 101 states have call successors, (585) Word has length 1706 [2024-11-09 06:07:11,602 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 06:07:11,611 INFO L225 Difference]: With dead ends: 1832 [2024-11-09 06:07:11,612 INFO L226 Difference]: Without dead ends: 1818 [2024-11-09 06:07:11,620 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 5313 GetRequests, 5006 SyntacticMatches, 90 SemanticMatches, 217 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13107 ImplicationChecksByTransitivity, 78.5s TimeCoverageRelationStatistics Valid=16008, Invalid=31732, Unknown=2, NotChecked=0, Total=47742 [2024-11-09 06:07:11,621 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 39 mSDsluCounter, 379 mSDsCounter, 0 mSdLazyCounter, 907 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 403 SdHoareTripleChecker+Invalid, 913 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 907 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.8s IncrementalHoareTripleChecker+Time [2024-11-09 06:07:11,621 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 403 Invalid, 913 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 907 Invalid, 0 Unknown, 0 Unchecked, 2.8s Time] [2024-11-09 06:07:11,623 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1818 states. [2024-11-09 06:07:12,187 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1818 to 1818. [2024-11-09 06:07:12,189 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1818 states, 1209 states have (on average 1.0016542597187759) internal successors, (1211), 1210 states have internal predecessors, (1211), 306 states have call successors, (306), 302 states have call predecessors, (306), 302 states have return successors, (305), 305 states have call predecessors, (305), 305 states have call successors, (305) [2024-11-09 06:07:12,194 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1818 states to 1818 states and 1822 transitions. [2024-11-09 06:07:12,197 INFO L78 Accepts]: Start accepts. Automaton has 1818 states and 1822 transitions. Word has length 1706 [2024-11-09 06:07:12,198 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 06:07:12,199 INFO L471 AbstractCegarLoop]: Abstraction has 1818 states and 1822 transitions. [2024-11-09 06:07:12,200 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 106 states, 106 states have (on average 5.650943396226415) internal successors, (599), 106 states have internal predecessors, (599), 102 states have call successors, (586), 97 states have call predecessors, (586), 96 states have return successors, (585), 101 states have call predecessors, (585), 101 states have call successors, (585) [2024-11-09 06:07:12,200 INFO L276 IsEmpty]: Start isEmpty. Operand 1818 states and 1822 transitions. [2024-11-09 06:07:12,265 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1815 [2024-11-09 06:07:12,265 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 06:07:12,266 INFO L215 NwaCegarLoop]: trace histogram [301, 300, 300, 101, 100, 100, 100, 100, 100, 100, 100, 100, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 06:07:12,291 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2024-11-09 06:07:12,466 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,17 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b2c9c06b-7042-4c4f-89ba-d46ab246284e/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 06:07:12,467 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 06:07:12,467 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 06:07:12,467 INFO L85 PathProgramCache]: Analyzing trace with hash -1954101628, now seen corresponding path program 7 times [2024-11-09 06:07:12,467 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 06:07:12,468 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1827833184] [2024-11-09 06:07:12,468 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 06:07:12,468 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms