./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/hard-u_unwindbound50.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version a0165632 Calling Ultimate with: /usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/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_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/hard-u_unwindbound50.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/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_370b82d2-9f95-4a96-a176-7652d6ec3e6a/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 9692f5b55a240b01d2d0c222255869fb052ffe02a605ab1c8e72ef46a070f8cd --- Real Ultimate output --- This is Ultimate 0.2.5-dev-a016563 [2024-11-09 05:18:04,583 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 05:18:04,675 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/config/svcomp-Reach-32bit-Taipan_Default.epf [2024-11-09 05:18:04,683 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 05:18:04,684 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 05:18:04,720 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 05:18:04,720 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 05:18:04,721 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 05:18:04,722 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-09 05:18:04,724 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-09 05:18:04,724 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-09 05:18:04,725 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-09 05:18:04,725 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-09 05:18:04,728 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-09 05:18:04,728 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-09 05:18:04,729 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-09 05:18:04,729 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-09 05:18:04,729 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-09 05:18:04,730 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-09 05:18:04,730 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-09 05:18:04,731 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-09 05:18:04,733 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-09 05:18:04,736 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 05:18:04,737 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-09 05:18:04,737 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 05:18:04,737 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 05:18:04,738 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 05:18:04,738 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 05:18:04,738 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-09 05:18:04,738 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-09 05:18:04,739 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-09 05:18:04,739 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 05:18:04,740 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 05:18:04,740 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 05:18:04,741 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 05:18:04,741 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-09 05:18:04,742 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-09 05:18:04,742 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-09 05:18:04,743 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-09 05:18:04,743 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 05:18:04,743 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-09 05:18:04,744 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-09 05:18:04,744 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-09 05:18:04,744 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-09 05:18:04,744 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-09 05:18:04,744 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-09 05:18:04,745 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-09 05:18:04,745 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_370b82d2-9f95-4a96-a176-7652d6ec3e6a/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_370b82d2-9f95-4a96-a176-7652d6ec3e6a/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 -> 9692f5b55a240b01d2d0c222255869fb052ffe02a605ab1c8e72ef46a070f8cd [2024-11-09 05:18:05,055 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 05:18:05,088 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 05:18:05,091 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 05:18:05,094 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 05:18:05,099 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 05:18:05,100 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/../../sv-benchmarks/c/nla-digbench-scaling/hard-u_unwindbound50.c Unable to find full path for "g++" [2024-11-09 05:18:07,426 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 05:18:07,620 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 05:18:07,621 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/sv-benchmarks/c/nla-digbench-scaling/hard-u_unwindbound50.c [2024-11-09 05:18:07,628 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/data/da158d926/e3145cbb0be5458684e3e6e27e0a6eda/FLAG1d35996d4 [2024-11-09 05:18:07,642 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/data/da158d926/e3145cbb0be5458684e3e6e27e0a6eda [2024-11-09 05:18:07,644 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 05:18:07,646 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 05:18:07,647 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 05:18:07,647 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 05:18:07,654 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 05:18:07,654 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 05:18:07" (1/1) ... [2024-11-09 05:18:07,655 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4f6f65b4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:18:07, skipping insertion in model container [2024-11-09 05:18:07,656 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 05:18:07" (1/1) ... [2024-11-09 05:18:07,681 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 05:18:07,893 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_370b82d2-9f95-4a96-a176-7652d6ec3e6a/sv-benchmarks/c/nla-digbench-scaling/hard-u_unwindbound50.c[537,550] [2024-11-09 05:18:07,915 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 05:18:07,924 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 05:18:07,941 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_370b82d2-9f95-4a96-a176-7652d6ec3e6a/sv-benchmarks/c/nla-digbench-scaling/hard-u_unwindbound50.c[537,550] [2024-11-09 05:18:07,952 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 05:18:07,974 INFO L204 MainTranslator]: Completed translation [2024-11-09 05:18:07,974 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:18:07 WrapperNode [2024-11-09 05:18:07,974 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 05:18:07,976 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 05:18:07,976 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 05:18:07,976 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 05:18:07,984 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:18:07" (1/1) ... [2024-11-09 05:18:07,992 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:18:07" (1/1) ... [2024-11-09 05:18:08,011 INFO L138 Inliner]: procedures = 14, calls = 15, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 64 [2024-11-09 05:18:08,012 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 05:18:08,013 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 05:18:08,013 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 05:18:08,013 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 05:18:08,020 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:18:07" (1/1) ... [2024-11-09 05:18:08,021 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:18:07" (1/1) ... [2024-11-09 05:18:08,022 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:18:07" (1/1) ... [2024-11-09 05:18:08,023 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:18:07" (1/1) ... [2024-11-09 05:18:08,026 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:18:07" (1/1) ... [2024-11-09 05:18:08,030 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:18:07" (1/1) ... [2024-11-09 05:18:08,031 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:18:07" (1/1) ... [2024-11-09 05:18:08,032 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:18:07" (1/1) ... [2024-11-09 05:18:08,034 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 05:18:08,035 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-09 05:18:08,035 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-09 05:18:08,035 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-09 05:18:08,036 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:18:07" (1/1) ... [2024-11-09 05:18:08,043 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-09 05:18:08,056 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:18:08,072 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/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:18:08,075 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/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:18:08,098 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 05:18:08,098 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-09 05:18:08,098 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 05:18:08,098 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 05:18:08,099 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-09 05:18:08,099 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-09 05:18:08,168 INFO L238 CfgBuilder]: Building ICFG [2024-11-09 05:18:08,172 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 05:18:08,413 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-09 05:18:08,413 INFO L287 CfgBuilder]: Performing block encoding [2024-11-09 05:18:08,492 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 05:18:08,492 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-09 05:18:08,493 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 05:18:08 BoogieIcfgContainer [2024-11-09 05:18:08,493 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-09 05:18:08,496 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-09 05:18:08,497 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-09 05:18:08,502 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-09 05:18:08,503 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.11 05:18:07" (1/3) ... [2024-11-09 05:18:08,504 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7607bd76 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 05:18:08, skipping insertion in model container [2024-11-09 05:18:08,505 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:18:07" (2/3) ... [2024-11-09 05:18:08,506 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7607bd76 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 05:18:08, skipping insertion in model container [2024-11-09 05:18:08,507 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 05:18:08" (3/3) ... [2024-11-09 05:18:08,510 INFO L112 eAbstractionObserver]: Analyzing ICFG hard-u_unwindbound50.c [2024-11-09 05:18:08,530 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-09 05:18:08,530 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-09 05:18:08,592 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-09 05:18:08,600 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;@769edadf, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-09 05:18:08,600 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-09 05:18:08,604 INFO L276 IsEmpty]: Start isEmpty. Operand has 22 states, 12 states have (on average 1.6666666666666667) internal successors, (20), 13 states have internal predecessors, (20), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-09 05:18:08,612 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-09 05:18:08,613 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:18:08,613 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:18:08,614 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:18:08,620 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:18:08,620 INFO L85 PathProgramCache]: Analyzing trace with hash -1654084864, now seen corresponding path program 1 times [2024-11-09 05:18:08,632 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:18:08,632 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [198404371] [2024-11-09 05:18:08,633 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:18:08,633 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:18:08,735 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:18:08,794 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 05:18:08,794 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:18:08,795 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [198404371] [2024-11-09 05:18:08,796 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [198404371] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 05:18:08,796 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 05:18:08,796 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-09 05:18:08,798 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1610022278] [2024-11-09 05:18:08,799 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 05:18:08,804 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-09 05:18:08,805 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:18:08,830 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-09 05:18:08,831 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-09 05:18:08,833 INFO L87 Difference]: Start difference. First operand has 22 states, 12 states have (on average 1.6666666666666667) internal successors, (20), 13 states have internal predecessors, (20), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 05:18:08,867 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:18:08,867 INFO L93 Difference]: Finished difference Result 43 states and 74 transitions. [2024-11-09 05:18:08,868 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-09 05:18:08,870 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2024-11-09 05:18:08,870 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:18:08,876 INFO L225 Difference]: With dead ends: 43 [2024-11-09 05:18:08,876 INFO L226 Difference]: Without dead ends: 20 [2024-11-09 05:18:08,879 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:18:08,883 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 3 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 28 SdHoareTripleChecker+Invalid, 3 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 3 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 05:18:08,884 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 28 Invalid, 3 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 3 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 05:18:08,905 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2024-11-09 05:18:08,920 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2024-11-09 05:18:08,921 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 12 states have internal predecessors, (16), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-09 05:18:08,922 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 29 transitions. [2024-11-09 05:18:08,925 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 29 transitions. Word has length 7 [2024-11-09 05:18:08,925 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:18:08,925 INFO L471 AbstractCegarLoop]: Abstraction has 20 states and 29 transitions. [2024-11-09 05:18:08,926 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 05:18:08,926 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 29 transitions. [2024-11-09 05:18:08,927 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-09 05:18:08,927 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:18:08,927 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:18:08,928 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-09 05:18:08,928 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:18:08,930 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:18:08,931 INFO L85 PathProgramCache]: Analyzing trace with hash -2115219753, now seen corresponding path program 1 times [2024-11-09 05:18:08,931 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:18:08,931 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2017186503] [2024-11-09 05:18:08,931 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:18:08,932 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:18:08,957 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:18:09,227 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 05:18:09,227 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:18:09,228 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2017186503] [2024-11-09 05:18:09,228 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2017186503] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 05:18:09,228 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 05:18:09,228 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-09 05:18:09,229 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1998342529] [2024-11-09 05:18:09,229 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 05:18:09,233 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 05:18:09,235 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:18:09,235 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 05:18:09,236 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 05:18:09,236 INFO L87 Difference]: Start difference. First operand 20 states and 29 transitions. Second operand has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 05:18:09,371 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:18:09,372 INFO L93 Difference]: Finished difference Result 33 states and 46 transitions. [2024-11-09 05:18:09,374 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 05:18:09,375 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2024-11-09 05:18:09,375 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:18:09,376 INFO L225 Difference]: With dead ends: 33 [2024-11-09 05:18:09,376 INFO L226 Difference]: Without dead ends: 31 [2024-11-09 05:18:09,377 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 05:18:09,378 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 10 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 05:18:09,380 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 82 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 05:18:09,381 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2024-11-09 05:18:09,390 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 24. [2024-11-09 05:18:09,391 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 14 states have (on average 1.3571428571428572) internal successors, (19), 15 states have internal predecessors, (19), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-09 05:18:09,392 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 32 transitions. [2024-11-09 05:18:09,392 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 32 transitions. Word has length 7 [2024-11-09 05:18:09,393 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:18:09,393 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 32 transitions. [2024-11-09 05:18:09,393 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 05:18:09,393 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 32 transitions. [2024-11-09 05:18:09,394 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-11-09 05:18:09,394 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:18:09,394 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:18:09,395 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-09 05:18:09,395 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:18:09,395 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:18:09,396 INFO L85 PathProgramCache]: Analyzing trace with hash 174216846, now seen corresponding path program 1 times [2024-11-09 05:18:09,396 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:18:09,396 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1522653432] [2024-11-09 05:18:09,396 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:18:09,397 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:18:09,407 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:18:09,483 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 05:18:09,483 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:18:09,484 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1522653432] [2024-11-09 05:18:09,484 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1522653432] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 05:18:09,484 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 05:18:09,484 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-09 05:18:09,485 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [443239421] [2024-11-09 05:18:09,485 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 05:18:09,485 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-09 05:18:09,486 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:18:09,486 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-09 05:18:09,487 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-09 05:18:09,487 INFO L87 Difference]: Start difference. First operand 24 states and 32 transitions. Second operand has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 05:18:09,515 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:18:09,515 INFO L93 Difference]: Finished difference Result 39 states and 52 transitions. [2024-11-09 05:18:09,516 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-09 05:18:09,516 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2024-11-09 05:18:09,516 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:18:09,517 INFO L225 Difference]: With dead ends: 39 [2024-11-09 05:18:09,517 INFO L226 Difference]: Without dead ends: 26 [2024-11-09 05:18:09,518 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 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:18:09,519 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 0 mSDsluCounter, 48 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 13 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 05:18:09,520 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 73 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 05:18:09,521 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2024-11-09 05:18:09,526 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2024-11-09 05:18:09,526 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 16 states have (on average 1.3125) internal successors, (21), 17 states have internal predecessors, (21), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-09 05:18:09,527 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 34 transitions. [2024-11-09 05:18:09,528 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 34 transitions. Word has length 9 [2024-11-09 05:18:09,528 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:18:09,528 INFO L471 AbstractCegarLoop]: Abstraction has 26 states and 34 transitions. [2024-11-09 05:18:09,528 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 05:18:09,528 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 34 transitions. [2024-11-09 05:18:09,529 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2024-11-09 05:18:09,529 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:18:09,529 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:18:09,529 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-09 05:18:09,530 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:18:09,530 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:18:09,530 INFO L85 PathProgramCache]: Analyzing trace with hash 1872131942, now seen corresponding path program 1 times [2024-11-09 05:18:09,530 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:18:09,531 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [46939197] [2024-11-09 05:18:09,532 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:18:09,532 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:18:09,560 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:18:09,842 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 05:18:09,843 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:18:09,843 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [46939197] [2024-11-09 05:18:09,843 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [46939197] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 05:18:09,844 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 05:18:09,844 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 05:18:09,845 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [954380266] [2024-11-09 05:18:09,845 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 05:18:09,846 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 05:18:09,846 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:18:09,847 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 05:18:09,847 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 05:18:09,848 INFO L87 Difference]: Start difference. First operand 26 states and 34 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 05:18:09,999 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:18:10,000 INFO L93 Difference]: Finished difference Result 39 states and 51 transitions. [2024-11-09 05:18:10,000 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 05:18:10,001 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2024-11-09 05:18:10,001 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:18:10,002 INFO L225 Difference]: With dead ends: 39 [2024-11-09 05:18:10,002 INFO L226 Difference]: Without dead ends: 37 [2024-11-09 05:18:10,002 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 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:18:10,004 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 10 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 05:18:10,004 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 83 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 05:18:10,005 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2024-11-09 05:18:10,011 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 30. [2024-11-09 05:18:10,012 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-09 05:18:10,012 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 37 transitions. [2024-11-09 05:18:10,013 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 37 transitions. Word has length 12 [2024-11-09 05:18:10,013 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:18:10,013 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 37 transitions. [2024-11-09 05:18:10,014 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 05:18:10,014 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 37 transitions. [2024-11-09 05:18:10,014 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-11-09 05:18:10,014 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:18:10,014 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:18:10,015 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-09 05:18:10,015 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:18:10,015 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:18:10,016 INFO L85 PathProgramCache]: Analyzing trace with hash -1306040329, now seen corresponding path program 1 times [2024-11-09 05:18:10,016 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:18:10,016 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1620843297] [2024-11-09 05:18:10,016 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:18:10,017 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:18:10,045 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:18:10,050 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [500884366] [2024-11-09 05:18:10,050 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:18:10,051 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:18:10,051 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:18:10,053 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:18:10,058 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-09 05:18:10,121 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:18:10,123 INFO L255 TraceCheckSpWp]: Trace formula consists of 64 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-09 05:18:10,130 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:18:10,347 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 05:18:10,347 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 05:18:10,347 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:18:10,347 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1620843297] [2024-11-09 05:18:10,348 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:18:10,348 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [500884366] [2024-11-09 05:18:10,350 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [500884366] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 05:18:10,350 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 05:18:10,351 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 05:18:10,351 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [994081867] [2024-11-09 05:18:10,351 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 05:18:10,352 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 05:18:10,353 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:18:10,354 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 05:18:10,354 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 05:18:10,354 INFO L87 Difference]: Start difference. First operand 30 states and 37 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 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:18:10,472 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:18:10,473 INFO L93 Difference]: Finished difference Result 58 states and 78 transitions. [2024-11-09 05:18:10,473 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 05:18:10,474 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 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 17 [2024-11-09 05:18:10,474 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:18:10,476 INFO L225 Difference]: With dead ends: 58 [2024-11-09 05:18:10,477 INFO L226 Difference]: Without dead ends: 44 [2024-11-09 05:18:10,478 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 13 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:18:10,479 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 7 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 05:18:10,483 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 82 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 05:18:10,484 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2024-11-09 05:18:10,500 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 44. [2024-11-09 05:18:10,501 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 28 states have internal predecessors, (33), 13 states have call successors, (13), 4 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-09 05:18:10,502 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 57 transitions. [2024-11-09 05:18:10,504 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 57 transitions. Word has length 17 [2024-11-09 05:18:10,504 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:18:10,505 INFO L471 AbstractCegarLoop]: Abstraction has 44 states and 57 transitions. [2024-11-09 05:18:10,505 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 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:18:10,505 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 57 transitions. [2024-11-09 05:18:10,506 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-11-09 05:18:10,508 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:18:10,508 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:18:10,529 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-09 05:18:10,708 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:18:10,709 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:18:10,710 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:18:10,710 INFO L85 PathProgramCache]: Analyzing trace with hash -507918445, now seen corresponding path program 1 times [2024-11-09 05:18:10,710 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:18:10,710 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1898548513] [2024-11-09 05:18:10,710 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:18:10,711 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:18:10,736 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:18:10,894 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-09 05:18:10,895 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:18:10,895 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1898548513] [2024-11-09 05:18:10,895 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1898548513] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 05:18:10,895 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 05:18:10,896 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-09 05:18:10,896 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1894328527] [2024-11-09 05:18:10,896 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 05:18:10,896 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-09 05:18:10,897 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:18:10,897 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-09 05:18:10,898 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 05:18:10,898 INFO L87 Difference]: Start difference. First operand 44 states and 57 transitions. Second operand has 6 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-09 05:18:10,981 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:18:10,982 INFO L93 Difference]: Finished difference Result 63 states and 72 transitions. [2024-11-09 05:18:10,983 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-09 05:18:10,983 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 25 [2024-11-09 05:18:10,983 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:18:10,984 INFO L225 Difference]: With dead ends: 63 [2024-11-09 05:18:10,986 INFO L226 Difference]: Without dead ends: 56 [2024-11-09 05:18:10,986 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 05:18:10,987 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 7 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 102 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 05:18:10,988 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 102 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 05:18:10,990 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2024-11-09 05:18:11,006 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 55. [2024-11-09 05:18:11,006 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 35 states have (on average 1.1714285714285715) internal successors, (41), 36 states have internal predecessors, (41), 12 states have call successors, (12), 7 states have call predecessors, (12), 7 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-09 05:18:11,007 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 64 transitions. [2024-11-09 05:18:11,009 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 64 transitions. Word has length 25 [2024-11-09 05:18:11,009 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:18:11,010 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 64 transitions. [2024-11-09 05:18:11,010 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-09 05:18:11,011 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 64 transitions. [2024-11-09 05:18:11,012 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-11-09 05:18:11,012 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:18:11,012 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:18:11,013 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-09 05:18:11,013 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:18:11,014 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:18:11,014 INFO L85 PathProgramCache]: Analyzing trace with hash -506190567, now seen corresponding path program 1 times [2024-11-09 05:18:11,014 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:18:11,014 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1566578072] [2024-11-09 05:18:11,014 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:18:11,015 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:18:11,038 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:18:11,039 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [488369144] [2024-11-09 05:18:11,040 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:18:11,040 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:18:11,040 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:18:11,042 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:18:11,044 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-09 05:18:11,106 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:18:11,111 INFO L255 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-09 05:18:11,114 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:18:11,459 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 10 proven. 2 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-09 05:18:11,459 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:18:11,861 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:18:11,861 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1566578072] [2024-11-09 05:18:11,861 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:18:11,861 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [488369144] [2024-11-09 05:18:11,861 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [488369144] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 05:18:11,861 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1291710347] [2024-11-09 05:18:11,882 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2024-11-09 05:18:11,882 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:18:11,886 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:18:11,891 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:18:11,892 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:18:12,543 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 48 for LOIs [2024-11-09 05:18:12,615 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:18:13,792 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [1291710347] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 05:18:13,793 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-09 05:18:13,793 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [10] total 18 [2024-11-09 05:18:13,794 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [920993438] [2024-11-09 05:18:13,794 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 05:18:13,794 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-09 05:18:13,794 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:18:13,795 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-09 05:18:13,795 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=320, Unknown=0, NotChecked=0, Total=420 [2024-11-09 05:18:13,796 INFO L87 Difference]: Start difference. First operand 55 states and 64 transitions. Second operand has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-09 05:18:14,016 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:18:14,016 INFO L93 Difference]: Finished difference Result 61 states and 69 transitions. [2024-11-09 05:18:14,017 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-09 05:18:14,017 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 25 [2024-11-09 05:18:14,018 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:18:14,018 INFO L225 Difference]: With dead ends: 61 [2024-11-09 05:18:14,018 INFO L226 Difference]: Without dead ends: 59 [2024-11-09 05:18:14,019 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 28 SyntacticMatches, 10 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 162 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=100, Invalid=320, Unknown=0, NotChecked=0, Total=420 [2024-11-09 05:18:14,020 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 0 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 149 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 63 SdHoareTripleChecker+Invalid, 150 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 149 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 05:18:14,020 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 63 Invalid, 150 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 149 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 05:18:14,020 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2024-11-09 05:18:14,031 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 59. [2024-11-09 05:18:14,032 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 38 states have (on average 1.1578947368421053) internal successors, (44), 39 states have internal predecessors, (44), 12 states have call successors, (12), 8 states have call predecessors, (12), 8 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-09 05:18:14,032 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 67 transitions. [2024-11-09 05:18:14,033 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 67 transitions. Word has length 25 [2024-11-09 05:18:14,033 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:18:14,033 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 67 transitions. [2024-11-09 05:18:14,033 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-09 05:18:14,033 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 67 transitions. [2024-11-09 05:18:14,034 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-11-09 05:18:14,034 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:18:14,034 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:18:14,056 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-09 05:18:14,235 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2024-11-09 05:18:14,236 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:18:14,236 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:18:14,236 INFO L85 PathProgramCache]: Analyzing trace with hash -1960004552, now seen corresponding path program 1 times [2024-11-09 05:18:14,236 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:18:14,236 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1028324974] [2024-11-09 05:18:14,236 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:18:14,237 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:18:14,252 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:18:14,351 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-09 05:18:14,352 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:18:14,352 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1028324974] [2024-11-09 05:18:14,353 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1028324974] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 05:18:14,353 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1601350974] [2024-11-09 05:18:14,353 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:18:14,353 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:18:14,354 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:18:14,356 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:18:14,357 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-09 05:18:14,406 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:18:14,407 INFO L255 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-09 05:18:14,409 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:18:14,463 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-09 05:18:14,463 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:18:14,520 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-09 05:18:14,521 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1601350974] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:18:14,521 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1948669031] [2024-11-09 05:18:14,523 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2024-11-09 05:18:14,526 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:18:14,527 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:18:14,527 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:18:14,527 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:18:16,529 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-09 05:18:16,539 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:18:30,629 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1307#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-09 05:18:30,629 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:18:30,629 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 05:18:30,630 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 4, 5] total 10 [2024-11-09 05:18:30,630 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [212849981] [2024-11-09 05:18:30,634 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 05:18:30,634 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-09 05:18:30,634 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:18:30,635 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-09 05:18:30,635 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=386, Unknown=5, NotChecked=0, Total=462 [2024-11-09 05:18:30,636 INFO L87 Difference]: Start difference. First operand 59 states and 67 transitions. Second operand has 10 states, 10 states have (on average 2.6) internal successors, (26), 10 states have internal predecessors, (26), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-09 05:18:30,850 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:18:30,850 INFO L93 Difference]: Finished difference Result 124 states and 147 transitions. [2024-11-09 05:18:30,851 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-09 05:18:30,851 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.6) internal successors, (26), 10 states have internal predecessors, (26), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 27 [2024-11-09 05:18:30,851 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:18:30,852 INFO L225 Difference]: With dead ends: 124 [2024-11-09 05:18:30,853 INFO L226 Difference]: Without dead ends: 111 [2024-11-09 05:18:30,853 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 65 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 126 ImplicationChecksByTransitivity, 14.2s TimeCoverageRelationStatistics Valid=84, Invalid=463, Unknown=5, NotChecked=0, Total=552 [2024-11-09 05:18:30,854 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 52 mSDsluCounter, 111 mSDsCounter, 0 mSdLazyCounter, 90 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 52 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 104 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 90 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 05:18:30,855 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [52 Valid, 135 Invalid, 104 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 90 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 05:18:30,855 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2024-11-09 05:18:30,871 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 106. [2024-11-09 05:18:30,871 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 67 states have (on average 1.1791044776119404) internal successors, (79), 70 states have internal predecessors, (79), 24 states have call successors, (24), 14 states have call predecessors, (24), 14 states have return successors, (21), 21 states have call predecessors, (21), 21 states have call successors, (21) [2024-11-09 05:18:30,872 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 124 transitions. [2024-11-09 05:18:30,872 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 124 transitions. Word has length 27 [2024-11-09 05:18:30,873 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:18:30,873 INFO L471 AbstractCegarLoop]: Abstraction has 106 states and 124 transitions. [2024-11-09 05:18:30,873 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.6) internal successors, (26), 10 states have internal predecessors, (26), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-09 05:18:30,873 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 124 transitions. [2024-11-09 05:18:30,874 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-09 05:18:30,874 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:18:30,874 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2024-11-09 05:18:30,895 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-09 05:18:31,079 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:18:31,080 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:18:31,081 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:18:31,081 INFO L85 PathProgramCache]: Analyzing trace with hash 448166817, now seen corresponding path program 1 times [2024-11-09 05:18:31,081 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:18:31,081 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1099629745] [2024-11-09 05:18:31,081 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:18:31,082 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:18:31,099 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:18:31,100 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1086704287] [2024-11-09 05:18:31,100 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:18:31,100 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:18:31,105 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:18:31,108 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:18:31,112 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-09 05:18:31,306 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:18:31,307 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 05:18:31,308 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:18:31,410 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-09 05:18:31,410 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:18:31,552 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 15 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-09 05:18:31,552 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:18:31,552 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1099629745] [2024-11-09 05:18:31,553 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:18:31,553 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1086704287] [2024-11-09 05:18:31,553 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1086704287] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-09 05:18:31,553 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-09 05:18:31,553 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 8 [2024-11-09 05:18:31,553 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2075486505] [2024-11-09 05:18:31,554 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 05:18:31,554 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-09 05:18:31,554 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:18:31,555 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-09 05:18:31,555 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2024-11-09 05:18:31,555 INFO L87 Difference]: Start difference. First operand 106 states and 124 transitions. Second operand has 6 states, 6 states have (on average 2.0) internal successors, (12), 5 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:18:34,620 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:18:36,624 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:18:38,627 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:18:40,629 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:18:41,085 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:18:41,085 INFO L93 Difference]: Finished difference Result 129 states and 152 transitions. [2024-11-09 05:18:41,086 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 05:18:41,086 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 5 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 35 [2024-11-09 05:18:41,087 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:18:41,088 INFO L225 Difference]: With dead ends: 129 [2024-11-09 05:18:41,088 INFO L226 Difference]: Without dead ends: 127 [2024-11-09 05:18:41,088 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 60 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2024-11-09 05:18:41,089 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 8 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 2 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 9.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 106 SdHoareTripleChecker+Invalid, 48 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 9.5s IncrementalHoareTripleChecker+Time [2024-11-09 05:18:41,090 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 106 Invalid, 48 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 42 Invalid, 4 Unknown, 0 Unchecked, 9.5s Time] [2024-11-09 05:18:41,092 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2024-11-09 05:18:41,112 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 122. [2024-11-09 05:18:41,113 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 78 states have (on average 1.1666666666666667) internal successors, (91), 82 states have internal predecessors, (91), 26 states have call successors, (26), 17 states have call predecessors, (26), 17 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2024-11-09 05:18:41,114 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 140 transitions. [2024-11-09 05:18:41,114 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 140 transitions. Word has length 35 [2024-11-09 05:18:41,115 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:18:41,115 INFO L471 AbstractCegarLoop]: Abstraction has 122 states and 140 transitions. [2024-11-09 05:18:41,115 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 5 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:18:41,115 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 140 transitions. [2024-11-09 05:18:41,116 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-11-09 05:18:41,116 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:18:41,116 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:18:41,124 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-09 05:18:41,317 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2024-11-09 05:18:41,317 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:18:41,318 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:18:41,318 INFO L85 PathProgramCache]: Analyzing trace with hash -938277045, now seen corresponding path program 1 times [2024-11-09 05:18:41,318 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:18:41,318 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1053332234] [2024-11-09 05:18:41,318 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:18:41,318 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:18:41,355 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:18:41,357 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [323894676] [2024-11-09 05:18:41,357 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:18:41,357 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:18:41,357 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:18:41,359 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:18:41,366 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-09 05:18:41,425 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:18:41,426 INFO L255 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-09 05:18:41,428 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:18:41,534 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 18 proven. 4 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-09 05:18:41,534 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:18:41,603 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:18:41,603 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1053332234] [2024-11-09 05:18:41,603 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:18:41,604 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [323894676] [2024-11-09 05:18:41,604 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [323894676] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 05:18:41,606 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2087518015] [2024-11-09 05:18:41,608 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2024-11-09 05:18:41,608 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:18:41,610 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:18:41,611 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:18:41,611 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:18:42,101 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 48 for LOIs [2024-11-09 05:18:42,135 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:18:43,337 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [2087518015] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 05:18:43,337 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-09 05:18:43,338 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [8] total 17 [2024-11-09 05:18:43,338 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [78808486] [2024-11-09 05:18:43,338 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 05:18:43,339 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-09 05:18:43,339 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:18:43,339 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-09 05:18:43,340 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=237, Unknown=0, NotChecked=0, Total=306 [2024-11-09 05:18:43,340 INFO L87 Difference]: Start difference. First operand 122 states and 140 transitions. Second operand has 11 states, 10 states have (on average 1.2) internal successors, (12), 10 states have internal predecessors, (12), 3 states have call successors, (6), 1 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:18:43,614 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:18:43,614 INFO L93 Difference]: Finished difference Result 124 states and 141 transitions. [2024-11-09 05:18:43,615 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-09 05:18:43,615 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 1.2) internal successors, (12), 10 states have internal predecessors, (12), 3 states have call successors, (6), 1 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 36 [2024-11-09 05:18:43,615 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:18:43,617 INFO L225 Difference]: With dead ends: 124 [2024-11-09 05:18:43,618 INFO L226 Difference]: Without dead ends: 103 [2024-11-09 05:18:43,618 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 47 SyntacticMatches, 14 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 158 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=69, Invalid=237, Unknown=0, NotChecked=0, Total=306 [2024-11-09 05:18:43,620 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 0 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 181 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 58 SdHoareTripleChecker+Invalid, 182 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 181 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 05:18:43,621 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 58 Invalid, 182 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 181 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 05:18:43,622 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2024-11-09 05:18:43,643 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 103. [2024-11-09 05:18:43,643 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 66 states have (on average 1.1666666666666667) internal successors, (77), 69 states have internal predecessors, (77), 22 states have call successors, (22), 14 states have call predecessors, (22), 14 states have return successors, (20), 19 states have call predecessors, (20), 20 states have call successors, (20) [2024-11-09 05:18:43,644 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 119 transitions. [2024-11-09 05:18:43,645 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 119 transitions. Word has length 36 [2024-11-09 05:18:43,645 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:18:43,645 INFO L471 AbstractCegarLoop]: Abstraction has 103 states and 119 transitions. [2024-11-09 05:18:43,646 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 1.2) internal successors, (12), 10 states have internal predecessors, (12), 3 states have call successors, (6), 1 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:18:43,646 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 119 transitions. [2024-11-09 05:18:43,647 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-09 05:18:43,647 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:18:43,647 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:18:43,668 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-09 05:18:43,851 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-09 05:18:43,851 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:18:43,851 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:18:43,852 INFO L85 PathProgramCache]: Analyzing trace with hash -721972931, now seen corresponding path program 1 times [2024-11-09 05:18:43,852 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:18:43,852 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1288960265] [2024-11-09 05:18:43,852 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:18:43,852 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:18:43,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:18:43,985 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-09 05:18:43,985 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:18:43,985 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1288960265] [2024-11-09 05:18:43,986 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1288960265] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 05:18:43,986 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1431111556] [2024-11-09 05:18:43,986 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:18:43,986 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:18:43,986 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:18:43,990 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:18:43,991 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-09 05:18:44,043 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:18:44,044 INFO L255 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 05:18:44,047 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:18:44,131 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 42 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-09 05:18:44,131 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:18:44,231 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-09 05:18:44,231 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1431111556] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:18:44,231 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [348752005] [2024-11-09 05:18:44,234 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2024-11-09 05:18:44,234 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:18:44,234 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:18:44,234 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:18:44,234 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:18:45,537 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-09 05:18:45,547 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:18:51,079 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3047#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-09 05:18:51,079 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:18:51,080 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 05:18:51,080 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 5, 6] total 12 [2024-11-09 05:18:51,080 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1558671827] [2024-11-09 05:18:51,080 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 05:18:51,081 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-09 05:18:51,081 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:18:51,082 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-09 05:18:51,082 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=87, Invalid=465, Unknown=0, NotChecked=0, Total=552 [2024-11-09 05:18:51,082 INFO L87 Difference]: Start difference. First operand 103 states and 119 transitions. Second operand has 12 states, 12 states have (on average 2.75) internal successors, (33), 12 states have internal predecessors, (33), 5 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2024-11-09 05:18:51,411 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:18:51,412 INFO L93 Difference]: Finished difference Result 192 states and 227 transitions. [2024-11-09 05:18:51,412 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-09 05:18:51,412 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.75) internal successors, (33), 12 states have internal predecessors, (33), 5 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) Word has length 43 [2024-11-09 05:18:51,413 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:18:51,415 INFO L225 Difference]: With dead ends: 192 [2024-11-09 05:18:51,416 INFO L226 Difference]: Without dead ends: 178 [2024-11-09 05:18:51,416 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 112 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 167 ImplicationChecksByTransitivity, 5.7s TimeCoverageRelationStatistics Valid=106, Invalid=596, Unknown=0, NotChecked=0, Total=702 [2024-11-09 05:18:51,418 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 73 mSDsluCounter, 113 mSDsCounter, 0 mSdLazyCounter, 99 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 73 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 114 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 99 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 05:18:51,418 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [73 Valid, 136 Invalid, 114 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 99 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 05:18:51,419 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 178 states. [2024-11-09 05:18:51,460 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 178 to 171. [2024-11-09 05:18:51,461 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 171 states, 108 states have (on average 1.1574074074074074) internal successors, (125), 115 states have internal predecessors, (125), 40 states have call successors, (40), 22 states have call predecessors, (40), 22 states have return successors, (36), 33 states have call predecessors, (36), 36 states have call successors, (36) [2024-11-09 05:18:51,463 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 171 states to 171 states and 201 transitions. [2024-11-09 05:18:51,463 INFO L78 Accepts]: Start accepts. Automaton has 171 states and 201 transitions. Word has length 43 [2024-11-09 05:18:51,464 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:18:51,464 INFO L471 AbstractCegarLoop]: Abstraction has 171 states and 201 transitions. [2024-11-09 05:18:51,464 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.75) internal successors, (33), 12 states have internal predecessors, (33), 5 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2024-11-09 05:18:51,464 INFO L276 IsEmpty]: Start isEmpty. Operand 171 states and 201 transitions. [2024-11-09 05:18:51,465 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-09 05:18:51,465 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:18:51,465 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:18:51,480 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-09 05:18:51,666 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-09 05:18:51,666 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:18:51,667 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:18:51,667 INFO L85 PathProgramCache]: Analyzing trace with hash -720245053, now seen corresponding path program 1 times [2024-11-09 05:18:51,667 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:18:51,667 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1277734554] [2024-11-09 05:18:51,667 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:18:51,667 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:18:51,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:18:51,726 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1312268699] [2024-11-09 05:18:51,727 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:18:51,728 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:18:51,728 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:18:51,730 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:18:51,736 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-09 05:18:51,800 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:18:51,802 INFO L255 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-11-09 05:18:51,804 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:18:52,211 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 16 proven. 26 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-09 05:18:52,211 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:18:53,599 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 22 proven. 20 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-09 05:18:53,599 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:18:53,599 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1277734554] [2024-11-09 05:18:53,600 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:18:53,600 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1312268699] [2024-11-09 05:18:53,600 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1312268699] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:18:53,600 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1233589306] [2024-11-09 05:18:53,602 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2024-11-09 05:18:53,602 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:18:53,602 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:18:53,603 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:18:53,603 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:18:54,927 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-09 05:18:54,935 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:19:03,497 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3903#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-09 05:19:03,498 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:19:03,498 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 05:19:03,498 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11] total 16 [2024-11-09 05:19:03,498 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2067448706] [2024-11-09 05:19:03,498 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 05:19:03,498 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-09 05:19:03,498 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:19:03,499 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-09 05:19:03,499 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=537, Unknown=2, NotChecked=0, Total=650 [2024-11-09 05:19:03,500 INFO L87 Difference]: Start difference. First operand 171 states and 201 transitions. Second operand has 16 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 12 states have internal predecessors, (29), 7 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 7 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-09 05:19:03,899 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:19:03,899 INFO L93 Difference]: Finished difference Result 209 states and 250 transitions. [2024-11-09 05:19:03,900 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-09 05:19:03,900 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 12 states have internal predecessors, (29), 7 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 7 states have call predecessors, (12), 5 states have call successors, (12) Word has length 43 [2024-11-09 05:19:03,900 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:19:03,902 INFO L225 Difference]: With dead ends: 209 [2024-11-09 05:19:03,902 INFO L226 Difference]: Without dead ends: 205 [2024-11-09 05:19:03,903 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 101 SyntacticMatches, 2 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 137 ImplicationChecksByTransitivity, 9.4s TimeCoverageRelationStatistics Valid=127, Invalid=627, Unknown=2, NotChecked=0, Total=756 [2024-11-09 05:19:03,904 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 18 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 119 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 133 SdHoareTripleChecker+Invalid, 148 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 119 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-09 05:19:03,904 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 133 Invalid, 148 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 119 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-09 05:19:03,905 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 205 states. [2024-11-09 05:19:03,944 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 205 to 191. [2024-11-09 05:19:03,945 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 191 states, 122 states have (on average 1.1557377049180328) internal successors, (141), 128 states have internal predecessors, (141), 43 states have call successors, (43), 26 states have call predecessors, (43), 25 states have return successors, (39), 36 states have call predecessors, (39), 39 states have call successors, (39) [2024-11-09 05:19:03,946 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 191 states to 191 states and 223 transitions. [2024-11-09 05:19:03,947 INFO L78 Accepts]: Start accepts. Automaton has 191 states and 223 transitions. Word has length 43 [2024-11-09 05:19:03,947 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:19:03,947 INFO L471 AbstractCegarLoop]: Abstraction has 191 states and 223 transitions. [2024-11-09 05:19:03,947 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 12 states have internal predecessors, (29), 7 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 7 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-09 05:19:03,947 INFO L276 IsEmpty]: Start isEmpty. Operand 191 states and 223 transitions. [2024-11-09 05:19:03,949 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2024-11-09 05:19:03,949 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:19:03,949 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:19:03,963 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-09 05:19:04,149 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2024-11-09 05:19:04,150 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:19:04,150 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:19:04,150 INFO L85 PathProgramCache]: Analyzing trace with hash -1991197863, now seen corresponding path program 1 times [2024-11-09 05:19:04,150 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:19:04,150 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1510523857] [2024-11-09 05:19:04,150 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:19:04,151 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:19:04,190 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:19:04,191 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [733164211] [2024-11-09 05:19:04,192 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:19:04,192 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:19:04,192 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:19:04,194 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:19:04,199 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-09 05:19:05,293 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:19:05,294 INFO L255 TraceCheckSpWp]: Trace formula consists of 145 conjuncts, 29 conjuncts are in the unsatisfiable core [2024-11-09 05:19:05,296 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:19:05,988 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 27 proven. 19 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2024-11-09 05:19:05,988 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:19:23,018 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 27 proven. 19 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2024-11-09 05:19:23,018 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:19:23,018 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1510523857] [2024-11-09 05:19:23,018 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:19:23,018 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [733164211] [2024-11-09 05:19:23,018 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [733164211] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:19:23,018 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [579907524] [2024-11-09 05:19:23,021 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2024-11-09 05:19:23,021 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:19:23,021 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:19:23,021 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:19:23,021 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:19:28,713 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-09 05:19:28,719 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:20:11,013 WARN L286 SmtUtils]: Spent 32.93s on a formula simplification. DAG size of input: 59 DAG size of output: 59 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 05:20:16,242 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4893#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-09 05:20:16,243 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:20:16,243 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 05:20:16,243 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11] total 16 [2024-11-09 05:20:16,243 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1784012177] [2024-11-09 05:20:16,243 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 05:20:16,244 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-09 05:20:16,244 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:20:16,245 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-09 05:20:16,245 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=471, Unknown=6, NotChecked=0, Total=552 [2024-11-09 05:20:16,245 INFO L87 Difference]: Start difference. First operand 191 states and 223 transitions. Second operand has 16 states, 16 states have (on average 2.1875) internal successors, (35), 14 states have internal predecessors, (35), 9 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) [2024-11-09 05:20:24,830 WARN L286 SmtUtils]: Spent 8.55s on a formula simplification. DAG size of input: 37 DAG size of output: 32 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 05:20:27,320 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:20:29,327 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:20:31,336 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:20:33,341 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:20:35,429 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:20:37,811 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:20:40,050 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:20:46,277 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:20:47,916 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.64s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:20:49,921 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:20:51,926 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:21:01,236 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.57s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:21:04,175 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.61s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:21:10,152 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.89s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:21:15,133 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:21:17,137 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:21:19,142 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:21:21,333 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:21:23,337 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:21:25,732 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:21:27,289 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.56s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:21:28,058 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:21:28,059 INFO L93 Difference]: Finished difference Result 238 states and 273 transitions. [2024-11-09 05:21:28,059 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-09 05:21:28,060 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 2.1875) internal successors, (35), 14 states have internal predecessors, (35), 9 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) Word has length 56 [2024-11-09 05:21:28,060 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:21:28,062 INFO L225 Difference]: With dead ends: 238 [2024-11-09 05:21:28,062 INFO L226 Difference]: Without dead ends: 228 [2024-11-09 05:21:28,063 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 173 GetRequests, 140 SyntacticMatches, 4 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 162 ImplicationChecksByTransitivity, 89.4s TimeCoverageRelationStatistics Valid=135, Invalid=786, Unknown=9, NotChecked=0, Total=930 [2024-11-09 05:21:28,063 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 19 mSDsluCounter, 159 mSDsCounter, 0 mSdLazyCounter, 234 mSolverCounterSat, 31 mSolverCounterUnsat, 16 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 45.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 186 SdHoareTripleChecker+Invalid, 281 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 234 IncrementalHoareTripleChecker+Invalid, 16 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 45.2s IncrementalHoareTripleChecker+Time [2024-11-09 05:21:28,064 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [24 Valid, 186 Invalid, 281 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 234 Invalid, 16 Unknown, 0 Unchecked, 45.2s Time] [2024-11-09 05:21:28,065 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 228 states. [2024-11-09 05:21:28,106 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 228 to 214. [2024-11-09 05:21:28,106 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 214 states, 140 states have (on average 1.1285714285714286) internal successors, (158), 147 states have internal predecessors, (158), 42 states have call successors, (42), 31 states have call predecessors, (42), 31 states have return successors, (39), 35 states have call predecessors, (39), 39 states have call successors, (39) [2024-11-09 05:21:28,107 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 214 states to 214 states and 239 transitions. [2024-11-09 05:21:28,108 INFO L78 Accepts]: Start accepts. Automaton has 214 states and 239 transitions. Word has length 56 [2024-11-09 05:21:28,108 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:21:28,109 INFO L471 AbstractCegarLoop]: Abstraction has 214 states and 239 transitions. [2024-11-09 05:21:28,109 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 2.1875) internal successors, (35), 14 states have internal predecessors, (35), 9 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) [2024-11-09 05:21:28,109 INFO L276 IsEmpty]: Start isEmpty. Operand 214 states and 239 transitions. [2024-11-09 05:21:28,110 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2024-11-09 05:21:28,110 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:21:28,110 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:21:28,118 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-09 05:21:28,310 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-09 05:21:28,311 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:21:28,312 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:21:28,312 INFO L85 PathProgramCache]: Analyzing trace with hash -1874668700, now seen corresponding path program 2 times [2024-11-09 05:21:28,312 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:21:28,312 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [29628746] [2024-11-09 05:21:28,312 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:21:28,313 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:21:28,397 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:21:28,398 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [67051865] [2024-11-09 05:21:28,399 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 05:21:28,399 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:21:28,399 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:21:28,401 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:21:28,404 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-09 05:21:28,686 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-09 05:21:28,686 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 05:21:28,688 INFO L255 TraceCheckSpWp]: Trace formula consists of 103 conjuncts, 31 conjuncts are in the unsatisfiable core [2024-11-09 05:21:28,690 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:21:29,720 INFO L134 CoverageAnalysis]: Checked inductivity of 172 backedges. 41 proven. 11 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2024-11-09 05:21:29,720 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:21:34,613 INFO L134 CoverageAnalysis]: Checked inductivity of 172 backedges. 41 proven. 11 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2024-11-09 05:21:34,613 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:21:34,613 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [29628746] [2024-11-09 05:21:34,613 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:21:34,614 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [67051865] [2024-11-09 05:21:34,614 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [67051865] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:21:34,614 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [952359898] [2024-11-09 05:21:34,616 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2024-11-09 05:21:34,616 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:21:34,617 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:21:34,617 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:21:34,617 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:21:40,438 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-09 05:21:40,442 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:22:30,298 WARN L286 SmtUtils]: Spent 36.29s on a formula simplification. DAG size of input: 59 DAG size of output: 59 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 05:22:35,123 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5998#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-09 05:22:35,123 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:22:35,123 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 05:22:35,124 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 16 [2024-11-09 05:22:35,124 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1017245166] [2024-11-09 05:22:35,124 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 05:22:35,124 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-09 05:22:35,124 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:22:35,125 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-09 05:22:35,125 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=512, Unknown=6, NotChecked=0, Total=600 [2024-11-09 05:22:35,126 INFO L87 Difference]: Start difference. First operand 214 states and 239 transitions. Second operand has 16 states, 14 states have (on average 2.642857142857143) internal successors, (37), 13 states have internal predecessors, (37), 8 states have call successors, (20), 3 states have call predecessors, (20), 2 states have return successors, (18), 6 states have call predecessors, (18), 6 states have call successors, (18) [2024-11-09 05:23:33,866 WARN L286 SmtUtils]: Spent 54.27s on a formula simplification that was a NOOP. DAG size: 55 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 05:23:35,878 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:23:37,871 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.86s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:23:39,883 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:23:42,534 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:23:44,542 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:23:50,804 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:23:52,814 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:23:54,819 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:23:56,829 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:23:59,067 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:24:01,150 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:24:09,654 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:24:11,660 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:24:13,664 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:24:17,306 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:24:19,656 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.02s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:24:21,670 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:24:23,676 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:24:25,415 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.74s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:24:27,463 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:24:29,486 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:24:31,276 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.78s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:24:33,308 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:24:35,312 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:24:37,548 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:24:39,739 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:24:39,744 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:24:39,744 INFO L93 Difference]: Finished difference Result 276 states and 313 transitions. [2024-11-09 05:24:39,745 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-09 05:24:39,745 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 2.642857142857143) internal successors, (37), 13 states have internal predecessors, (37), 8 states have call successors, (20), 3 states have call predecessors, (20), 2 states have return successors, (18), 6 states have call predecessors, (18), 6 states have call successors, (18) Word has length 61 [2024-11-09 05:24:39,745 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:24:39,747 INFO L225 Difference]: With dead ends: 276 [2024-11-09 05:24:39,747 INFO L226 Difference]: Without dead ends: 246 [2024-11-09 05:24:39,748 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 186 GetRequests, 156 SyntacticMatches, 2 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 138 ImplicationChecksByTransitivity, 127.4s TimeCoverageRelationStatistics Valid=131, Invalid=731, Unknown=8, NotChecked=0, Total=870 [2024-11-09 05:24:39,748 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 24 mSDsluCounter, 249 mSDsCounter, 0 mSdLazyCounter, 242 mSolverCounterSat, 51 mSolverCounterUnsat, 23 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 53.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 280 SdHoareTripleChecker+Invalid, 316 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 51 IncrementalHoareTripleChecker+Valid, 242 IncrementalHoareTripleChecker+Invalid, 23 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 54.0s IncrementalHoareTripleChecker+Time [2024-11-09 05:24:39,749 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 280 Invalid, 316 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [51 Valid, 242 Invalid, 23 Unknown, 0 Unchecked, 54.0s Time] [2024-11-09 05:24:39,749 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 246 states. [2024-11-09 05:24:39,807 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 246 to 239. [2024-11-09 05:24:39,808 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 239 states, 157 states have (on average 1.10828025477707) internal successors, (174), 165 states have internal predecessors, (174), 45 states have call successors, (45), 36 states have call predecessors, (45), 36 states have return successors, (42), 37 states have call predecessors, (42), 42 states have call successors, (42) [2024-11-09 05:24:39,809 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 239 states to 239 states and 261 transitions. [2024-11-09 05:24:39,810 INFO L78 Accepts]: Start accepts. Automaton has 239 states and 261 transitions. Word has length 61 [2024-11-09 05:24:39,810 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:24:39,810 INFO L471 AbstractCegarLoop]: Abstraction has 239 states and 261 transitions. [2024-11-09 05:24:39,810 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 2.642857142857143) internal successors, (37), 13 states have internal predecessors, (37), 8 states have call successors, (20), 3 states have call predecessors, (20), 2 states have return successors, (18), 6 states have call predecessors, (18), 6 states have call successors, (18) [2024-11-09 05:24:39,810 INFO L276 IsEmpty]: Start isEmpty. Operand 239 states and 261 transitions. [2024-11-09 05:24:39,811 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2024-11-09 05:24:39,811 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:24:39,811 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:24:39,817 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-09 05:24:40,012 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-11-09 05:24:40,012 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:24:40,013 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:24:40,013 INFO L85 PathProgramCache]: Analyzing trace with hash -563738357, now seen corresponding path program 1 times [2024-11-09 05:24:40,013 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:24:40,013 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [745047939] [2024-11-09 05:24:40,013 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:24:40,013 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:24:40,048 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:24:40,049 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [547694313] [2024-11-09 05:24:40,049 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:24:40,049 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:24:40,049 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:24:40,051 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:24:40,056 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-09 05:24:40,268 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:24:40,275 INFO L255 TraceCheckSpWp]: Trace formula consists of 165 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-09 05:24:40,278 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:24:41,443 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 39 proven. 40 refuted. 0 times theorem prover too weak. 132 trivial. 0 not checked. [2024-11-09 05:24:41,444 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:24:55,144 WARN L286 SmtUtils]: Spent 12.41s on a formula simplification. DAG size of input: 51 DAG size of output: 43 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 05:25:31,250 WARN L286 SmtUtils]: Spent 7.04s on a formula simplification. DAG size of input: 73 DAG size of output: 20 (called from [L 188] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionTir.tryToEliminateOne) [2024-11-09 05:25:43,385 WARN L873 $PredicateComparison]: unable to prove that (let ((.cse1 (mod |c_ULTIMATE.start_main_~d~0#1| 4294967296)) (.cse0 (mod |c_ULTIMATE.start_main_~d~0#1| 2147483648))) (or (< (* 2 .cse0) (+ .cse1 1)) (not (= .cse1 (mod (* |c_ULTIMATE.start_main_~p~0#1| |c_ULTIMATE.start_main_~B~0#1|) 4294967296))) (< 4294967294 (mod (+ (* .cse0 |c_ULTIMATE.start_main_~q~0#1|) 4294967295 (* 4294967295 |c_ULTIMATE.start_main_~B~0#1| |c_ULTIMATE.start_main_~q~0#1|)) 4294967296)) (not (= (mod |c_ULTIMATE.start_main_~p~0#1| 2147483648) 1)))) is different from true [2024-11-09 05:26:18,080 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 39 proven. 35 refuted. 0 times theorem prover too weak. 132 trivial. 5 not checked. [2024-11-09 05:26:18,080 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:26:18,080 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [745047939] [2024-11-09 05:26:18,080 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:26:18,080 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [547694313] [2024-11-09 05:26:18,080 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [547694313] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:26:18,080 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [788301231] [2024-11-09 05:26:18,082 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2024-11-09 05:26:18,082 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:26:18,086 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:26:18,086 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:26:18,086 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:26:23,583 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-09 05:26:23,587 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:26:54,647 WARN L286 SmtUtils]: Spent 22.46s on a formula simplification. DAG size of input: 59 DAG size of output: 59 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 05:27:12,672 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '7239#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-09 05:27:12,672 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:27:12,672 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 05:27:12,672 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13] total 20 [2024-11-09 05:27:12,673 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1958465474] [2024-11-09 05:27:12,673 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 05:27:12,673 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-09 05:27:12,673 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:27:12,674 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-09 05:27:12,674 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=119, Invalid=687, Unknown=10, NotChecked=54, Total=870 [2024-11-09 05:27:12,674 INFO L87 Difference]: Start difference. First operand 239 states and 261 transitions. Second operand has 20 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 16 states have internal predecessors, (37), 12 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (20), 9 states have call predecessors, (20), 10 states have call successors, (20) [2024-11-09 05:27:41,553 WARN L286 SmtUtils]: Spent 21.39s on a formula simplification that was a NOOP. DAG size: 76 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 05:27:47,907 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:27:51,173 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:27:53,175 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:27:56,856 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:28:02,059 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.86s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:28:07,712 WARN L286 SmtUtils]: Spent 5.33s on a formula simplification that was a NOOP. DAG size: 58 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 05:28:09,718 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:28:11,048 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.12s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:28:14,420 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:28:25,045 WARN L286 SmtUtils]: Spent 8.58s on a formula simplification that was a NOOP. DAG size: 79 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 05:28:26,622 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.56s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:28:29,347 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:28:31,381 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:28:46,701 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:28:46,701 INFO L93 Difference]: Finished difference Result 276 states and 308 transitions. [2024-11-09 05:28:46,701 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-09 05:28:46,702 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 16 states have internal predecessors, (37), 12 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (20), 9 states have call predecessors, (20), 10 states have call successors, (20) Word has length 67 [2024-11-09 05:28:46,702 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:28:46,703 INFO L225 Difference]: With dead ends: 276 [2024-11-09 05:28:46,704 INFO L226 Difference]: Without dead ends: 272 [2024-11-09 05:28:46,705 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 214 GetRequests, 167 SyntacticMatches, 5 SemanticMatches, 42 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 405 ImplicationChecksByTransitivity, 132.8s TimeCoverageRelationStatistics Valid=316, Invalid=1477, Unknown=17, NotChecked=82, Total=1892 [2024-11-09 05:28:46,705 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 56 mSDsluCounter, 290 mSDsCounter, 0 mSdLazyCounter, 278 mSolverCounterSat, 104 mSolverCounterUnsat, 8 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 27.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 320 SdHoareTripleChecker+Invalid, 511 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 104 IncrementalHoareTripleChecker+Valid, 278 IncrementalHoareTripleChecker+Invalid, 8 IncrementalHoareTripleChecker+Unknown, 121 IncrementalHoareTripleChecker+Unchecked, 27.6s IncrementalHoareTripleChecker+Time [2024-11-09 05:28:46,706 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [57 Valid, 320 Invalid, 511 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [104 Valid, 278 Invalid, 8 Unknown, 121 Unchecked, 27.6s Time] [2024-11-09 05:28:46,706 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 272 states. [2024-11-09 05:28:46,797 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 272 to 244. [2024-11-09 05:28:46,798 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 244 states, 161 states have (on average 1.1180124223602483) internal successors, (180), 167 states have internal predecessors, (180), 47 states have call successors, (47), 36 states have call predecessors, (47), 35 states have return successors, (44), 40 states have call predecessors, (44), 44 states have call successors, (44) [2024-11-09 05:28:46,799 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 244 states to 244 states and 271 transitions. [2024-11-09 05:28:46,800 INFO L78 Accepts]: Start accepts. Automaton has 244 states and 271 transitions. Word has length 67 [2024-11-09 05:28:46,800 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:28:46,800 INFO L471 AbstractCegarLoop]: Abstraction has 244 states and 271 transitions. [2024-11-09 05:28:46,800 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 16 states have internal predecessors, (37), 12 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (20), 9 states have call predecessors, (20), 10 states have call successors, (20) [2024-11-09 05:28:46,801 INFO L276 IsEmpty]: Start isEmpty. Operand 244 states and 271 transitions. [2024-11-09 05:28:46,802 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2024-11-09 05:28:46,802 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:28:46,802 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:28:46,809 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-09 05:28:47,006 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-11-09 05:28:47,006 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:28:47,007 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:28:47,007 INFO L85 PathProgramCache]: Analyzing trace with hash -1251052430, now seen corresponding path program 1 times [2024-11-09 05:28:47,007 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:28:47,007 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [350811053] [2024-11-09 05:28:47,007 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:28:47,008 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:28:47,061 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:28:49,435 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-09 05:28:49,435 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:28:49,436 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [350811053] [2024-11-09 05:28:49,436 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [350811053] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 05:28:49,436 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1769617548] [2024-11-09 05:28:49,436 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:28:49,436 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:28:49,436 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:28:49,438 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:28:49,441 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-09 05:28:49,560 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:28:49,561 INFO L255 TraceCheckSpWp]: Trace formula consists of 174 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-09 05:28:49,563 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:29:07,344 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 27 proven. 36 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2024-11-09 05:29:07,344 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:29:16,117 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 27 proven. 36 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2024-11-09 05:29:16,118 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1769617548] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:29:16,118 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1610154906] [2024-11-09 05:29:16,120 INFO L159 IcfgInterpreter]: Started Sifa with 20 locations of interest [2024-11-09 05:29:16,120 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:29:16,120 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:29:16,120 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:29:16,121 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:29:21,718 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-09 05:29:21,723 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:29:59,590 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '8538#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-09 05:29:59,590 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:29:59,590 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 05:29:59,591 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 11, 11] total 20 [2024-11-09 05:29:59,591 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [4127070] [2024-11-09 05:29:59,591 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 05:29:59,591 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-09 05:29:59,591 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:29:59,592 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-09 05:29:59,592 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=824, Unknown=11, NotChecked=0, Total=930 [2024-11-09 05:29:59,593 INFO L87 Difference]: Start difference. First operand 244 states and 271 transitions. Second operand has 20 states, 20 states have (on average 2.5) internal successors, (50), 18 states have internal predecessors, (50), 11 states have call successors, (34), 3 states have call predecessors, (34), 2 states have return successors, (31), 12 states have call predecessors, (31), 11 states have call successors, (31) [2024-11-09 05:30:08,244 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-11-09 05:30:14,301 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.51s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [0] [2024-11-09 05:30:16,325 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.16s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [0] [2024-11-09 05:30:17,750 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.37s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [0] [2024-11-09 05:30:17,814 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:30:17,814 INFO L93 Difference]: Finished difference Result 250 states and 277 transitions. [2024-11-09 05:30:17,815 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-09 05:30:17,815 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 2.5) internal successors, (50), 18 states have internal predecessors, (50), 11 states have call successors, (34), 3 states have call predecessors, (34), 2 states have return successors, (31), 12 states have call predecessors, (31), 11 states have call successors, (31) Word has length 72 [2024-11-09 05:30:17,815 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:30:17,816 INFO L225 Difference]: With dead ends: 250 [2024-11-09 05:30:17,816 INFO L226 Difference]: Without dead ends: 218 [2024-11-09 05:30:17,817 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 227 GetRequests, 188 SyntacticMatches, 8 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 228 ImplicationChecksByTransitivity, 56.5s TimeCoverageRelationStatistics Valid=110, Invalid=935, Unknown=11, NotChecked=0, Total=1056 [2024-11-09 05:30:17,817 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 6 mSDsluCounter, 215 mSDsCounter, 0 mSdLazyCounter, 202 mSolverCounterSat, 4 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 13.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 242 SdHoareTripleChecker+Invalid, 207 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 202 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 13.7s IncrementalHoareTripleChecker+Time [2024-11-09 05:30:17,817 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 242 Invalid, 207 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 202 Invalid, 1 Unknown, 0 Unchecked, 13.7s Time] [2024-11-09 05:30:17,818 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 218 states. [2024-11-09 05:30:17,890 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 218 to 218. [2024-11-09 05:30:17,890 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 218 states, 143 states have (on average 1.1258741258741258) internal successors, (161), 149 states have internal predecessors, (161), 43 states have call successors, (43), 32 states have call predecessors, (43), 31 states have return successors, (40), 36 states have call predecessors, (40), 40 states have call successors, (40) [2024-11-09 05:30:17,891 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 218 states to 218 states and 244 transitions. [2024-11-09 05:30:17,891 INFO L78 Accepts]: Start accepts. Automaton has 218 states and 244 transitions. Word has length 72 [2024-11-09 05:30:17,892 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:30:17,892 INFO L471 AbstractCegarLoop]: Abstraction has 218 states and 244 transitions. [2024-11-09 05:30:17,892 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 2.5) internal successors, (50), 18 states have internal predecessors, (50), 11 states have call successors, (34), 3 states have call predecessors, (34), 2 states have return successors, (31), 12 states have call predecessors, (31), 11 states have call successors, (31) [2024-11-09 05:30:17,892 INFO L276 IsEmpty]: Start isEmpty. Operand 218 states and 244 transitions. [2024-11-09 05:30:17,893 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2024-11-09 05:30:17,893 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:30:17,893 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:30:17,907 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2024-11-09 05:30:18,094 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:30:18,094 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:30:18,094 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:30:18,094 INFO L85 PathProgramCache]: Analyzing trace with hash -1062978449, now seen corresponding path program 3 times [2024-11-09 05:30:18,094 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:30:18,094 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [34736606] [2024-11-09 05:30:18,094 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:30:18,094 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:30:18,156 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:30:18,160 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [284233018] [2024-11-09 05:30:18,161 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-09 05:30:18,165 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:30:18,165 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:30:18,169 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:30:18,171 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_370b82d2-9f95-4a96-a176-7652d6ec3e6a/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-09 05:30:51,105 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-09 05:30:51,105 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 05:30:51,110 INFO L255 TraceCheckSpWp]: Trace formula consists of 182 conjuncts, 52 conjuncts are in the unsatisfiable core [2024-11-09 05:30:51,112 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:30:52,412 INFO L134 CoverageAnalysis]: Checked inductivity of 263 backedges. 54 proven. 73 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2024-11-09 05:30:52,412 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:31:17,309 WARN L286 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 8 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 05:31:25,332 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 11 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 05:31:37,464 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 8 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 05:31:47,495 WARN L286 SmtUtils]: Spent 10.03s on a formula simplification that was a NOOP. DAG size: 21 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 05:31:49,525 WARN L873 $PredicateComparison]: unable to prove that (let ((.cse3 (mod |c_ULTIMATE.start_main_~d~0#1| 4294967296))) (let ((.cse1 (mod |c_ULTIMATE.start_main_~r~0#1| 4294967296)) (.cse0 (mod |c_ULTIMATE.start_main_~p~0#1| 4294967296)) (.cse4 (* |c_ULTIMATE.start_main_~B~0#1| |c_ULTIMATE.start_main_~q~0#1|)) (.cse2 (div .cse3 2))) (or (= .cse0 1) (< .cse1 .cse2) (not (= .cse3 (mod (* |c_ULTIMATE.start_main_~p~0#1| |c_ULTIMATE.start_main_~B~0#1|) 4294967296))) (< .cse3 (+ .cse1 1)) (not (= (mod (+ .cse4 |c_ULTIMATE.start_main_~r~0#1|) 4294967296) (mod |c_ULTIMATE.start_main_~A~0#1| 4294967296))) (< 4294967294 (mod (+ (* |c_ULTIMATE.start_main_~B~0#1| (div .cse0 2)) (* 4294967295 |c_ULTIMATE.start_main_~A~0#1|) 4294967295 .cse4 |c_ULTIMATE.start_main_~r~0#1| (* 4294967295 .cse2)) 4294967296))))) is different from true [2024-11-09 05:32:07,730 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 8 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 05:32:15,742 WARN L286 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 11 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 05:32:25,825 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 8 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 05:32:35,853 WARN L286 SmtUtils]: Spent 10.03s on a formula simplification that was a NOOP. DAG size: 21 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 05:32:47,253 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 8 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 05:32:55,271 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 11 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 05:33:05,672 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 8 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 05:33:15,694 WARN L286 SmtUtils]: Spent 10.02s on a formula simplification that was a NOOP. DAG size: 21 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify)