./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound10.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 0e0057cc Calling Ultimate with: /usr/lib/jvm/java-11-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound10.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh --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 c8cdca66dc863bfa94d37a0903946c6b89240a08b13e8fd34226289180db2a40 --- Real Ultimate output --- This is Ultimate 0.2.4-dev-0e0057c [2023-12-02 19:31:17,702 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-12-02 19:31:17,767 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-12-02 19:31:17,773 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-12-02 19:31:17,773 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-12-02 19:31:17,797 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-12-02 19:31:17,798 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-12-02 19:31:17,799 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-12-02 19:31:17,799 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-12-02 19:31:17,800 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-12-02 19:31:17,801 INFO L153 SettingsManager]: * User list type=DISABLED [2023-12-02 19:31:17,801 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-12-02 19:31:17,802 INFO L153 SettingsManager]: * Explicit value domain=true [2023-12-02 19:31:17,802 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-12-02 19:31:17,803 INFO L153 SettingsManager]: * Octagon Domain=false [2023-12-02 19:31:17,803 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-12-02 19:31:17,804 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-12-02 19:31:17,804 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-12-02 19:31:17,805 INFO L153 SettingsManager]: * Interval Domain=false [2023-12-02 19:31:17,805 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-12-02 19:31:17,806 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-12-02 19:31:17,807 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-12-02 19:31:17,808 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-12-02 19:31:17,808 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-12-02 19:31:17,809 INFO L153 SettingsManager]: * sizeof long=4 [2023-12-02 19:31:17,809 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-12-02 19:31:17,809 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-12-02 19:31:17,810 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-12-02 19:31:17,810 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-12-02 19:31:17,811 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-12-02 19:31:17,811 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-12-02 19:31:17,812 INFO L153 SettingsManager]: * sizeof long double=12 [2023-12-02 19:31:17,812 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-12-02 19:31:17,813 INFO L153 SettingsManager]: * Use constant arrays=true [2023-12-02 19:31:17,813 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-12-02 19:31:17,814 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-12-02 19:31:17,814 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-12-02 19:31:17,814 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-12-02 19:31:17,815 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-12-02 19:31:17,815 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-12-02 19:31:17,816 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-12-02 19:31:17,817 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-12-02 19:31:17,817 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-12-02 19:31:17,817 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-12-02 19:31:17,818 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-12-02 19:31:17,818 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-12-02 19:31:17,818 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-12-02 19:31:17,818 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_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/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_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh 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 -> c8cdca66dc863bfa94d37a0903946c6b89240a08b13e8fd34226289180db2a40 [2023-12-02 19:31:18,030 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-12-02 19:31:18,050 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-12-02 19:31:18,053 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-12-02 19:31:18,054 INFO L270 PluginConnector]: Initializing CDTParser... [2023-12-02 19:31:18,054 INFO L274 PluginConnector]: CDTParser initialized [2023-12-02 19:31:18,056 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/../../sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound10.c [2023-12-02 19:31:20,927 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-12-02 19:31:21,101 INFO L384 CDTParser]: Found 1 translation units. [2023-12-02 19:31:21,101 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound10.c [2023-12-02 19:31:21,109 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/data/a89cfec0b/634a0ed97b48413691742012b782667e/FLAG77d283a73 [2023-12-02 19:31:21,124 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/data/a89cfec0b/634a0ed97b48413691742012b782667e [2023-12-02 19:31:21,127 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-12-02 19:31:21,129 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-12-02 19:31:21,130 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-12-02 19:31:21,131 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-12-02 19:31:21,136 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-12-02 19:31:21,137 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.12 07:31:21" (1/1) ... [2023-12-02 19:31:21,138 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@12141b78 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 07:31:21, skipping insertion in model container [2023-12-02 19:31:21,138 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.12 07:31:21" (1/1) ... [2023-12-02 19:31:21,161 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-12-02 19:31:21,314 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound10.c[538,551] [2023-12-02 19:31:21,334 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-02 19:31:21,345 INFO L202 MainTranslator]: Completed pre-run [2023-12-02 19:31:21,358 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound10.c[538,551] [2023-12-02 19:31:21,366 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-02 19:31:21,381 INFO L206 MainTranslator]: Completed translation [2023-12-02 19:31:21,382 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 07:31:21 WrapperNode [2023-12-02 19:31:21,382 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-12-02 19:31:21,383 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-12-02 19:31:21,383 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-12-02 19:31:21,384 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-12-02 19:31:21,391 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 07:31:21" (1/1) ... [2023-12-02 19:31:21,398 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 07:31:21" (1/1) ... [2023-12-02 19:31:21,421 INFO L138 Inliner]: procedures = 14, calls = 15, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 66 [2023-12-02 19:31:21,421 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-12-02 19:31:21,422 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-12-02 19:31:21,422 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-12-02 19:31:21,422 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-12-02 19:31:21,432 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 07:31:21" (1/1) ... [2023-12-02 19:31:21,432 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 07:31:21" (1/1) ... [2023-12-02 19:31:21,434 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 07:31:21" (1/1) ... [2023-12-02 19:31:21,434 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 07:31:21" (1/1) ... [2023-12-02 19:31:21,437 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 07:31:21" (1/1) ... [2023-12-02 19:31:21,441 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 07:31:21" (1/1) ... [2023-12-02 19:31:21,442 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 07:31:21" (1/1) ... [2023-12-02 19:31:21,443 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 07:31:21" (1/1) ... [2023-12-02 19:31:21,445 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-12-02 19:31:21,446 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-12-02 19:31:21,446 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-12-02 19:31:21,447 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-12-02 19:31:21,447 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 07:31:21" (1/1) ... [2023-12-02 19:31:21,454 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-12-02 19:31:21,465 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 19:31:21,477 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-12-02 19:31:21,485 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-12-02 19:31:21,510 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-12-02 19:31:21,510 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-12-02 19:31:21,511 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-12-02 19:31:21,511 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-12-02 19:31:21,511 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-12-02 19:31:21,511 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-12-02 19:31:21,570 INFO L241 CfgBuilder]: Building ICFG [2023-12-02 19:31:21,572 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-12-02 19:31:21,731 INFO L282 CfgBuilder]: Performing block encoding [2023-12-02 19:31:21,788 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-12-02 19:31:21,789 INFO L309 CfgBuilder]: Removed 2 assume(true) statements. [2023-12-02 19:31:21,790 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.12 07:31:21 BoogieIcfgContainer [2023-12-02 19:31:21,791 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-12-02 19:31:21,793 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-12-02 19:31:21,794 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-12-02 19:31:21,796 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-12-02 19:31:21,796 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 02.12 07:31:21" (1/3) ... [2023-12-02 19:31:21,797 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@ff28592 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.12 07:31:21, skipping insertion in model container [2023-12-02 19:31:21,797 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 07:31:21" (2/3) ... [2023-12-02 19:31:21,798 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@ff28592 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.12 07:31:21, skipping insertion in model container [2023-12-02 19:31:21,798 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.12 07:31:21" (3/3) ... [2023-12-02 19:31:21,799 INFO L112 eAbstractionObserver]: Analyzing ICFG hard-ll_unwindbound10.c [2023-12-02 19:31:21,814 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-12-02 19:31:21,815 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-12-02 19:31:21,857 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-12-02 19:31:21,864 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@c9b649d, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-12-02 19:31:21,864 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-12-02 19:31:21,868 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) [2023-12-02 19:31:21,873 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-12-02 19:31:21,874 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 19:31:21,874 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-12-02 19:31:21,874 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 19:31:21,879 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 19:31:21,879 INFO L85 PathProgramCache]: Analyzing trace with hash 151460259, now seen corresponding path program 1 times [2023-12-02 19:31:21,887 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 19:31:21,887 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [834426958] [2023-12-02 19:31:21,887 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:21,888 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 19:31:21,968 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 19:31:21,989 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 19:31:21,989 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [834426958] [2023-12-02 19:31:21,990 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-12-02 19:31:21,990 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [161011976] [2023-12-02 19:31:21,990 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:21,990 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:31:21,990 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 19:31:21,992 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 19:31:21,998 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-12-02 19:31:22,051 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 19:31:22,053 INFO L262 TraceCheckSpWp]: Trace formula consists of 43 conjuncts, 1 conjunts are in the unsatisfiable core [2023-12-02 19:31:22,057 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 19:31:22,075 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 19:31:22,075 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-02 19:31:22,076 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [161011976] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 19:31:22,076 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 19:31:22,076 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-12-02 19:31:22,079 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1122944029] [2023-12-02 19:31:22,079 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 19:31:22,084 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-12-02 19:31:22,085 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 19:31:22,112 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-12-02 19:31:22,113 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-12-02 19:31:22,115 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) [2023-12-02 19:31:22,143 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 19:31:22,143 INFO L93 Difference]: Finished difference Result 43 states and 74 transitions. [2023-12-02 19:31:22,145 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-12-02 19:31:22,146 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 [2023-12-02 19:31:22,146 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 19:31:22,151 INFO L225 Difference]: With dead ends: 43 [2023-12-02 19:31:22,151 INFO L226 Difference]: Without dead ends: 20 [2023-12-02 19:31:22,153 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-12-02 19:31:22,157 INFO L413 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 [2023-12-02 19:31:22,158 INFO L414 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] [2023-12-02 19:31:22,176 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2023-12-02 19:31:22,193 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2023-12-02 19:31:22,195 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) [2023-12-02 19:31:22,196 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 29 transitions. [2023-12-02 19:31:22,197 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 29 transitions. Word has length 7 [2023-12-02 19:31:22,198 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 19:31:22,198 INFO L495 AbstractCegarLoop]: Abstraction has 20 states and 29 transitions. [2023-12-02 19:31:22,198 INFO L496 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) [2023-12-02 19:31:22,198 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 29 transitions. [2023-12-02 19:31:22,199 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-12-02 19:31:22,199 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 19:31:22,199 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-12-02 19:31:22,205 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-12-02 19:31:22,404 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2023-12-02 19:31:22,404 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 19:31:22,405 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 19:31:22,405 INFO L85 PathProgramCache]: Analyzing trace with hash -310598151, now seen corresponding path program 1 times [2023-12-02 19:31:22,405 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 19:31:22,406 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2111635228] [2023-12-02 19:31:22,406 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:22,406 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 19:31:22,425 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 19:31:22,547 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 19:31:22,547 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 19:31:22,548 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2111635228] [2023-12-02 19:31:22,548 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2111635228] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 19:31:22,548 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 19:31:22,548 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-12-02 19:31:22,549 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1317550026] [2023-12-02 19:31:22,549 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 19:31:22,549 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-02 19:31:22,550 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 19:31:22,550 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-02 19:31:22,551 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-12-02 19:31:22,551 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) [2023-12-02 19:31:22,609 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 19:31:22,610 INFO L93 Difference]: Finished difference Result 33 states and 46 transitions. [2023-12-02 19:31:22,610 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-02 19:31:22,610 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 [2023-12-02 19:31:22,611 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 19:31:22,612 INFO L225 Difference]: With dead ends: 33 [2023-12-02 19:31:22,612 INFO L226 Difference]: Without dead ends: 31 [2023-12-02 19:31:22,612 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-12-02 19:31:22,614 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 13 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 19:31:22,614 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 81 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 19:31:22,615 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2023-12-02 19:31:22,623 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 24. [2023-12-02 19:31:22,623 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) [2023-12-02 19:31:22,624 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 32 transitions. [2023-12-02 19:31:22,624 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 32 transitions. Word has length 7 [2023-12-02 19:31:22,624 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 19:31:22,625 INFO L495 AbstractCegarLoop]: Abstraction has 24 states and 32 transitions. [2023-12-02 19:31:22,625 INFO L496 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) [2023-12-02 19:31:22,625 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 32 transitions. [2023-12-02 19:31:22,626 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2023-12-02 19:31:22,626 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 19:31:22,626 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 19:31:22,626 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-12-02 19:31:22,626 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 19:31:22,627 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 19:31:22,627 INFO L85 PathProgramCache]: Analyzing trace with hash -751211152, now seen corresponding path program 1 times [2023-12-02 19:31:22,627 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 19:31:22,627 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [703256062] [2023-12-02 19:31:22,628 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:22,628 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 19:31:22,639 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 19:31:22,646 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 19:31:22,647 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [703256062] [2023-12-02 19:31:22,647 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-12-02 19:31:22,647 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1573311892] [2023-12-02 19:31:22,647 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:22,648 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:31:22,648 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 19:31:22,649 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 19:31:22,652 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-12-02 19:31:22,701 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 19:31:22,702 INFO L262 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 3 conjunts are in the unsatisfiable core [2023-12-02 19:31:22,703 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 19:31:22,736 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 19:31:22,736 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-02 19:31:22,737 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1573311892] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 19:31:22,737 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 19:31:22,737 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-12-02 19:31:22,737 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1944241184] [2023-12-02 19:31:22,737 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 19:31:22,738 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-12-02 19:31:22,738 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 19:31:22,738 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-12-02 19:31:22,739 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-12-02 19:31:22,739 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) [2023-12-02 19:31:22,762 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 19:31:22,763 INFO L93 Difference]: Finished difference Result 39 states and 52 transitions. [2023-12-02 19:31:22,763 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-12-02 19:31:22,763 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 [2023-12-02 19:31:22,763 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 19:31:22,764 INFO L225 Difference]: With dead ends: 39 [2023-12-02 19:31:22,764 INFO L226 Difference]: Without dead ends: 26 [2023-12-02 19:31:22,765 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-12-02 19:31:22,766 INFO L413 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 [2023-12-02 19:31:22,767 INFO L414 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] [2023-12-02 19:31:22,768 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2023-12-02 19:31:22,772 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2023-12-02 19:31:22,773 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) [2023-12-02 19:31:22,773 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 34 transitions. [2023-12-02 19:31:22,773 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 34 transitions. Word has length 9 [2023-12-02 19:31:22,774 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 19:31:22,774 INFO L495 AbstractCegarLoop]: Abstraction has 26 states and 34 transitions. [2023-12-02 19:31:22,774 INFO L496 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) [2023-12-02 19:31:22,774 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 34 transitions. [2023-12-02 19:31:22,774 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2023-12-02 19:31:22,775 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 19:31:22,775 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 19:31:22,779 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2023-12-02 19:31:22,975 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:31:22,976 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 19:31:22,976 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 19:31:22,976 INFO L85 PathProgramCache]: Analyzing trace with hash 1841718534, now seen corresponding path program 1 times [2023-12-02 19:31:22,976 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 19:31:22,976 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [355867172] [2023-12-02 19:31:22,977 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:22,977 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 19:31:22,985 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 19:31:23,080 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 19:31:23,080 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 19:31:23,080 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [355867172] [2023-12-02 19:31:23,081 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [355867172] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 19:31:23,081 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 19:31:23,081 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-12-02 19:31:23,081 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1742757744] [2023-12-02 19:31:23,081 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 19:31:23,082 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-02 19:31:23,082 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 19:31:23,083 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-02 19:31:23,083 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-12-02 19:31:23,083 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) [2023-12-02 19:31:23,142 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 19:31:23,142 INFO L93 Difference]: Finished difference Result 39 states and 51 transitions. [2023-12-02 19:31:23,143 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-02 19:31:23,143 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 [2023-12-02 19:31:23,143 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 19:31:23,144 INFO L225 Difference]: With dead ends: 39 [2023-12-02 19:31:23,144 INFO L226 Difference]: Without dead ends: 37 [2023-12-02 19:31:23,145 INFO L412 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 [2023-12-02 19:31:23,146 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 11 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 19:31:23,146 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 81 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 19:31:23,147 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2023-12-02 19:31:23,156 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 30. [2023-12-02 19:31:23,156 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) [2023-12-02 19:31:23,157 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 37 transitions. [2023-12-02 19:31:23,157 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 37 transitions. Word has length 12 [2023-12-02 19:31:23,157 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 19:31:23,158 INFO L495 AbstractCegarLoop]: Abstraction has 30 states and 37 transitions. [2023-12-02 19:31:23,158 INFO L496 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) [2023-12-02 19:31:23,158 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 37 transitions. [2023-12-02 19:31:23,158 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2023-12-02 19:31:23,159 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 19:31:23,159 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 19:31:23,159 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2023-12-02 19:31:23,159 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 19:31:23,160 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 19:31:23,160 INFO L85 PathProgramCache]: Analyzing trace with hash -1224204839, now seen corresponding path program 1 times [2023-12-02 19:31:23,160 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 19:31:23,160 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2081768120] [2023-12-02 19:31:23,160 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:23,160 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 19:31:23,172 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 19:31:23,172 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [895004574] [2023-12-02 19:31:23,172 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:23,172 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:31:23,172 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 19:31:23,173 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 19:31:23,179 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-12-02 19:31:23,225 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 19:31:23,226 INFO L262 TraceCheckSpWp]: Trace formula consists of 64 conjuncts, 19 conjunts are in the unsatisfiable core [2023-12-02 19:31:23,228 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 19:31:23,385 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-12-02 19:31:23,385 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 19:31:23,537 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-12-02 19:31:23,537 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 19:31:23,537 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2081768120] [2023-12-02 19:31:23,537 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 19:31:23,537 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [895004574] [2023-12-02 19:31:23,537 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [895004574] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 19:31:23,538 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1301629175] [2023-12-02 19:31:23,557 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2023-12-02 19:31:23,557 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 19:31:23,560 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 19:31:23,565 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 19:31:23,566 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 19:31:23,989 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2023-12-02 19:31:23,995 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 19:31:24,310 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [1301629175] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 19:31:24,310 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-12-02 19:31:24,310 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [8, 7] total 17 [2023-12-02 19:31:24,311 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [293296837] [2023-12-02 19:31:24,311 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 19:31:24,311 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-12-02 19:31:24,311 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 19:31:24,312 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-12-02 19:31:24,312 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2023-12-02 19:31:24,312 INFO L87 Difference]: Start difference. First operand 30 states and 37 transitions. Second operand has 7 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-12-02 19:31:24,421 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 19:31:24,421 INFO L93 Difference]: Finished difference Result 49 states and 57 transitions. [2023-12-02 19:31:24,422 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-12-02 19:31:24,422 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (3), 1 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 [2023-12-02 19:31:24,422 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 19:31:24,423 INFO L225 Difference]: With dead ends: 49 [2023-12-02 19:31:24,423 INFO L226 Difference]: Without dead ends: 47 [2023-12-02 19:31:24,424 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 63 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2023-12-02 19:31:24,425 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 1 mSDsluCounter, 41 mSDsCounter, 0 mSdLazyCounter, 65 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 58 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 65 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 19:31:24,425 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 58 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 65 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 19:31:24,426 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2023-12-02 19:31:24,438 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 45. [2023-12-02 19:31:24,439 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 28 states have (on average 1.1785714285714286) internal successors, (33), 30 states have internal predecessors, (33), 10 states have call successors, (10), 6 states have call predecessors, (10), 6 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-02 19:31:24,440 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 52 transitions. [2023-12-02 19:31:24,440 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 52 transitions. Word has length 17 [2023-12-02 19:31:24,440 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 19:31:24,440 INFO L495 AbstractCegarLoop]: Abstraction has 45 states and 52 transitions. [2023-12-02 19:31:24,440 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-12-02 19:31:24,441 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 52 transitions. [2023-12-02 19:31:24,441 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2023-12-02 19:31:24,442 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 19:31:24,442 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 19:31:24,446 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2023-12-02 19:31:24,642 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:31:24,643 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 19:31:24,643 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 19:31:24,643 INFO L85 PathProgramCache]: Analyzing trace with hash 1437524276, now seen corresponding path program 1 times [2023-12-02 19:31:24,643 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 19:31:24,643 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [35801773] [2023-12-02 19:31:24,644 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:24,644 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 19:31:24,654 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 19:31:24,654 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [980241436] [2023-12-02 19:31:24,655 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:24,655 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:31:24,655 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 19:31:24,656 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 19:31:24,658 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-12-02 19:31:24,704 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 19:31:24,705 INFO L262 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 5 conjunts are in the unsatisfiable core [2023-12-02 19:31:24,707 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 19:31:24,750 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-02 19:31:24,750 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-02 19:31:24,750 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 19:31:24,750 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [35801773] [2023-12-02 19:31:24,750 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 19:31:24,750 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [980241436] [2023-12-02 19:31:24,751 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [980241436] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 19:31:24,751 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 19:31:24,751 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-12-02 19:31:24,751 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [231903550] [2023-12-02 19:31:24,751 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 19:31:24,751 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-02 19:31:24,752 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 19:31:24,752 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-02 19:31:24,752 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-12-02 19:31:24,752 INFO L87 Difference]: Start difference. First operand 45 states and 52 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (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) [2023-12-02 19:31:24,795 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 19:31:24,795 INFO L93 Difference]: Finished difference Result 57 states and 66 transitions. [2023-12-02 19:31:24,796 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-12-02 19:31:24,796 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (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 [2023-12-02 19:31:24,796 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 19:31:24,797 INFO L225 Difference]: With dead ends: 57 [2023-12-02 19:31:24,797 INFO L226 Difference]: Without dead ends: 49 [2023-12-02 19:31:24,797 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-12-02 19:31:24,798 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 1 mSDsluCounter, 53 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 77 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 19:31:24,799 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 77 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 19:31:24,799 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2023-12-02 19:31:24,811 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 48. [2023-12-02 19:31:24,811 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 31 states have (on average 1.1935483870967742) internal successors, (37), 32 states have internal predecessors, (37), 10 states have call successors, (10), 6 states have call predecessors, (10), 6 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-02 19:31:24,812 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 56 transitions. [2023-12-02 19:31:24,812 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 56 transitions. Word has length 25 [2023-12-02 19:31:24,812 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 19:31:24,813 INFO L495 AbstractCegarLoop]: Abstraction has 48 states and 56 transitions. [2023-12-02 19:31:24,813 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (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) [2023-12-02 19:31:24,813 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 56 transitions. [2023-12-02 19:31:24,814 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2023-12-02 19:31:24,814 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 19:31:24,814 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 19:31:24,819 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2023-12-02 19:31:25,019 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2023-12-02 19:31:25,019 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 19:31:25,020 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 19:31:25,020 INFO L85 PathProgramCache]: Analyzing trace with hash 1439252154, now seen corresponding path program 1 times [2023-12-02 19:31:25,020 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 19:31:25,020 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [621753227] [2023-12-02 19:31:25,020 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:25,020 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 19:31:25,030 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 19:31:25,030 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1386184686] [2023-12-02 19:31:25,030 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:25,030 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:31:25,030 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 19:31:25,031 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 19:31:25,037 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-12-02 19:31:25,095 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 19:31:25,096 INFO L262 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 16 conjunts are in the unsatisfiable core [2023-12-02 19:31:25,098 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 19:31:25,244 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-12-02 19:31:25,245 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 19:31:25,432 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-12-02 19:31:25,432 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 19:31:25,432 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [621753227] [2023-12-02 19:31:25,432 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 19:31:25,432 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1386184686] [2023-12-02 19:31:25,432 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1386184686] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 19:31:25,433 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1941792515] [2023-12-02 19:31:25,448 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-12-02 19:31:25,448 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 19:31:25,449 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 19:31:25,449 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 19:31:25,449 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 19:31:25,953 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 48 for LOIs [2023-12-02 19:31:26,009 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 19:31:26,868 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [1941792515] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 19:31:26,869 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-12-02 19:31:26,869 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [7, 7] total 19 [2023-12-02 19:31:26,869 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [548244116] [2023-12-02 19:31:26,869 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 19:31:26,870 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-12-02 19:31:26,870 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 19:31:26,871 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-12-02 19:31:26,871 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=268, Unknown=0, NotChecked=0, Total=342 [2023-12-02 19:31:26,871 INFO L87 Difference]: Start difference. First operand 48 states and 56 transitions. Second operand has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 8 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) [2023-12-02 19:31:27,124 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 19:31:27,124 INFO L93 Difference]: Finished difference Result 70 states and 86 transitions. [2023-12-02 19:31:27,125 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-12-02 19:31:27,126 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 8 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 [2023-12-02 19:31:27,126 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 19:31:27,127 INFO L225 Difference]: With dead ends: 70 [2023-12-02 19:31:27,127 INFO L226 Difference]: Without dead ends: 46 [2023-12-02 19:31:27,128 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 50 SyntacticMatches, 6 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 143 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=74, Invalid=268, Unknown=0, NotChecked=0, Total=342 [2023-12-02 19:31:27,129 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 1 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 188 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 192 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 188 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-02 19:31:27,129 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 83 Invalid, 192 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 188 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-02 19:31:27,130 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2023-12-02 19:31:27,140 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 46. [2023-12-02 19:31:27,140 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 29 states have (on average 1.1724137931034482) internal successors, (34), 30 states have internal predecessors, (34), 10 states have call successors, (10), 6 states have call predecessors, (10), 6 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-02 19:31:27,141 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 53 transitions. [2023-12-02 19:31:27,141 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 53 transitions. Word has length 25 [2023-12-02 19:31:27,141 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 19:31:27,142 INFO L495 AbstractCegarLoop]: Abstraction has 46 states and 53 transitions. [2023-12-02 19:31:27,142 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 8 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) [2023-12-02 19:31:27,142 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 53 transitions. [2023-12-02 19:31:27,143 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2023-12-02 19:31:27,143 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 19:31:27,143 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 19:31:27,148 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2023-12-02 19:31:27,344 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:31:27,344 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 19:31:27,344 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 19:31:27,344 INFO L85 PathProgramCache]: Analyzing trace with hash 964329913, now seen corresponding path program 1 times [2023-12-02 19:31:27,344 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 19:31:27,344 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1221703344] [2023-12-02 19:31:27,344 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:27,345 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 19:31:27,353 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 19:31:27,354 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1277412855] [2023-12-02 19:31:27,354 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:27,354 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:31:27,354 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 19:31:27,355 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 19:31:27,356 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-12-02 19:31:27,396 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 19:31:27,397 INFO L262 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 5 conjunts are in the unsatisfiable core [2023-12-02 19:31:27,399 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 19:31:27,437 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-02 19:31:27,438 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 19:31:27,476 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-02 19:31:27,477 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 19:31:27,477 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1221703344] [2023-12-02 19:31:27,477 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 19:31:27,477 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1277412855] [2023-12-02 19:31:27,477 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1277412855] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 19:31:27,477 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1612018256] [2023-12-02 19:31:27,480 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-12-02 19:31:27,480 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 19:31:27,480 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 19:31:27,480 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 19:31:27,481 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 19:31:28,844 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 19:31:28,848 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 19:31:34,046 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1424#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 19:31:34,047 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 19:31:34,047 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 19:31:34,047 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5] total 8 [2023-12-02 19:31:34,047 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [921838360] [2023-12-02 19:31:34,047 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 19:31:34,048 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-12-02 19:31:34,048 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 19:31:34,048 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-12-02 19:31:34,049 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=315, Unknown=0, NotChecked=0, Total=380 [2023-12-02 19:31:34,049 INFO L87 Difference]: Start difference. First operand 46 states and 53 transitions. Second operand has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-12-02 19:31:34,229 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 19:31:34,229 INFO L93 Difference]: Finished difference Result 109 states and 130 transitions. [2023-12-02 19:31:34,230 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-12-02 19:31:34,230 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 27 [2023-12-02 19:31:34,230 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 19:31:34,231 INFO L225 Difference]: With dead ends: 109 [2023-12-02 19:31:34,231 INFO L226 Difference]: Without dead ends: 96 [2023-12-02 19:31:34,232 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 61 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 106 ImplicationChecksByTransitivity, 5.3s TimeCoverageRelationStatistics Valid=85, Invalid=421, Unknown=0, NotChecked=0, Total=506 [2023-12-02 19:31:34,233 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 40 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 63 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 68 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 63 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 19:31:34,234 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 119 Invalid, 68 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 63 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 19:31:34,235 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2023-12-02 19:31:34,250 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 91. [2023-12-02 19:31:34,251 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 58 states have (on average 1.1896551724137931) internal successors, (69), 60 states have internal predecessors, (69), 20 states have call successors, (20), 12 states have call predecessors, (20), 12 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2023-12-02 19:31:34,253 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 107 transitions. [2023-12-02 19:31:34,253 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 107 transitions. Word has length 27 [2023-12-02 19:31:34,253 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 19:31:34,253 INFO L495 AbstractCegarLoop]: Abstraction has 91 states and 107 transitions. [2023-12-02 19:31:34,254 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-12-02 19:31:34,254 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 107 transitions. [2023-12-02 19:31:34,255 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2023-12-02 19:31:34,255 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 19:31:34,255 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2023-12-02 19:31:34,261 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2023-12-02 19:31:34,461 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:31:34,461 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 19:31:34,462 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 19:31:34,462 INFO L85 PathProgramCache]: Analyzing trace with hash -327624414, now seen corresponding path program 1 times [2023-12-02 19:31:34,462 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 19:31:34,462 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [611257822] [2023-12-02 19:31:34,462 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:34,462 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 19:31:34,471 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 19:31:34,471 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1185350782] [2023-12-02 19:31:34,471 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:34,471 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:31:34,472 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 19:31:34,473 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 19:31:34,477 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-12-02 19:31:34,518 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 19:31:34,520 INFO L262 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 28 conjunts are in the unsatisfiable core [2023-12-02 19:31:34,522 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 19:31:34,710 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 11 proven. 22 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2023-12-02 19:31:34,711 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 19:31:34,816 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 20 proven. 7 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2023-12-02 19:31:34,816 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 19:31:34,816 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [611257822] [2023-12-02 19:31:34,816 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 19:31:34,816 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1185350782] [2023-12-02 19:31:34,816 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1185350782] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 19:31:34,816 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [656300087] [2023-12-02 19:31:34,819 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2023-12-02 19:31:34,819 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 19:31:34,819 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 19:31:34,819 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 19:31:34,819 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 19:31:35,945 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 19:31:35,948 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 19:31:45,371 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1944#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 19:31:45,371 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 19:31:45,371 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 19:31:45,372 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 6] total 13 [2023-12-02 19:31:45,372 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1727522432] [2023-12-02 19:31:45,372 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 19:31:45,372 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-12-02 19:31:45,372 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 19:31:45,373 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-12-02 19:31:45,373 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=354, Unknown=3, NotChecked=0, Total=420 [2023-12-02 19:31:45,373 INFO L87 Difference]: Start difference. First operand 91 states and 107 transitions. Second operand has 13 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 10 states have internal predecessors, (25), 5 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) [2023-12-02 19:31:45,702 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 19:31:45,703 INFO L93 Difference]: Finished difference Result 131 states and 161 transitions. [2023-12-02 19:31:45,703 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-12-02 19:31:45,703 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 10 states have internal predecessors, (25), 5 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) Word has length 35 [2023-12-02 19:31:45,704 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 19:31:45,706 INFO L225 Difference]: With dead ends: 131 [2023-12-02 19:31:45,706 INFO L226 Difference]: Without dead ends: 111 [2023-12-02 19:31:45,706 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 85 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 102 ImplicationChecksByTransitivity, 9.6s TimeCoverageRelationStatistics Valid=78, Invalid=425, Unknown=3, NotChecked=0, Total=506 [2023-12-02 19:31:45,707 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 34 mSDsluCounter, 161 mSDsCounter, 0 mSdLazyCounter, 162 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 188 SdHoareTripleChecker+Invalid, 188 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 162 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-12-02 19:31:45,707 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [44 Valid, 188 Invalid, 188 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 162 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-12-02 19:31:45,708 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2023-12-02 19:31:45,723 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 109. [2023-12-02 19:31:45,723 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 109 states, 69 states have (on average 1.1594202898550725) internal successors, (80), 73 states have internal predecessors, (80), 25 states have call successors, (25), 14 states have call predecessors, (25), 14 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) [2023-12-02 19:31:45,729 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 127 transitions. [2023-12-02 19:31:45,729 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 127 transitions. Word has length 35 [2023-12-02 19:31:45,729 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 19:31:45,729 INFO L495 AbstractCegarLoop]: Abstraction has 109 states and 127 transitions. [2023-12-02 19:31:45,729 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 10 states have internal predecessors, (25), 5 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) [2023-12-02 19:31:45,730 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 127 transitions. [2023-12-02 19:31:45,731 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2023-12-02 19:31:45,731 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 19:31:45,731 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 19:31:45,745 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2023-12-02 19:31:45,943 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:31:45,943 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 19:31:45,943 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 19:31:45,944 INFO L85 PathProgramCache]: Analyzing trace with hash 1605911421, now seen corresponding path program 1 times [2023-12-02 19:31:45,944 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 19:31:45,944 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [392521217] [2023-12-02 19:31:45,944 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:45,944 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 19:31:45,953 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 19:31:45,953 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1559981099] [2023-12-02 19:31:45,954 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:45,954 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:31:45,954 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 19:31:45,955 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 19:31:45,959 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-12-02 19:31:46,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 19:31:46,017 INFO L262 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 7 conjunts are in the unsatisfiable core [2023-12-02 19:31:46,019 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 19:31:46,082 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 42 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-12-02 19:31:46,082 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 19:31:46,133 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2023-12-02 19:31:46,133 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 19:31:46,133 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [392521217] [2023-12-02 19:31:46,133 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 19:31:46,133 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1559981099] [2023-12-02 19:31:46,133 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1559981099] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 19:31:46,133 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [816233200] [2023-12-02 19:31:46,136 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-12-02 19:31:46,136 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 19:31:46,136 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 19:31:46,136 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 19:31:46,136 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 19:31:47,020 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 19:31:47,023 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 19:31:52,368 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2568#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 19:31:52,369 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 19:31:52,369 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 19:31:52,369 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6] total 10 [2023-12-02 19:31:52,369 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [376578734] [2023-12-02 19:31:52,369 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 19:31:52,369 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-12-02 19:31:52,369 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 19:31:52,370 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-12-02 19:31:52,370 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=388, Unknown=0, NotChecked=0, Total=462 [2023-12-02 19:31:52,370 INFO L87 Difference]: Start difference. First operand 109 states and 127 transitions. Second operand has 10 states, 10 states have (on average 3.0) internal successors, (30), 10 states have internal predecessors, (30), 5 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-12-02 19:31:52,628 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 19:31:52,628 INFO L93 Difference]: Finished difference Result 193 states and 226 transitions. [2023-12-02 19:31:52,628 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-12-02 19:31:52,628 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.0) internal successors, (30), 10 states have internal predecessors, (30), 5 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 43 [2023-12-02 19:31:52,628 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 19:31:52,630 INFO L225 Difference]: With dead ends: 193 [2023-12-02 19:31:52,630 INFO L226 Difference]: Without dead ends: 178 [2023-12-02 19:31:52,631 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 107 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 145 ImplicationChecksByTransitivity, 5.4s TimeCoverageRelationStatistics Valid=93, Invalid=507, Unknown=0, NotChecked=0, Total=600 [2023-12-02 19:31:52,632 INFO L413 NwaCegarLoop]: 26 mSDtfsCounter, 69 mSDsluCounter, 121 mSDsCounter, 0 mSdLazyCounter, 102 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 147 SdHoareTripleChecker+Invalid, 114 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 102 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-02 19:31:52,632 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [69 Valid, 147 Invalid, 114 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 102 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-02 19:31:52,633 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 178 states. [2023-12-02 19:31:52,655 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 178 to 171. [2023-12-02 19:31:52,656 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 171 states, 109 states have (on average 1.146788990825688) internal successors, (125), 115 states have internal predecessors, (125), 39 states have call successors, (39), 22 states have call predecessors, (39), 22 states have return successors, (35), 33 states have call predecessors, (35), 35 states have call successors, (35) [2023-12-02 19:31:52,657 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 171 states to 171 states and 199 transitions. [2023-12-02 19:31:52,657 INFO L78 Accepts]: Start accepts. Automaton has 171 states and 199 transitions. Word has length 43 [2023-12-02 19:31:52,657 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 19:31:52,657 INFO L495 AbstractCegarLoop]: Abstraction has 171 states and 199 transitions. [2023-12-02 19:31:52,657 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.0) internal successors, (30), 10 states have internal predecessors, (30), 5 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-12-02 19:31:52,657 INFO L276 IsEmpty]: Start isEmpty. Operand 171 states and 199 transitions. [2023-12-02 19:31:52,659 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2023-12-02 19:31:52,659 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 19:31:52,659 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 19:31:52,664 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2023-12-02 19:31:52,859 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:31:52,860 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 19:31:52,860 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 19:31:52,860 INFO L85 PathProgramCache]: Analyzing trace with hash 1607639299, now seen corresponding path program 1 times [2023-12-02 19:31:52,860 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 19:31:52,860 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [367459095] [2023-12-02 19:31:52,860 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:52,860 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 19:31:52,867 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 19:31:52,867 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1598735537] [2023-12-02 19:31:52,867 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:52,868 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:31:52,868 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 19:31:52,869 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 19:31:52,870 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-12-02 19:31:52,914 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 19:31:52,915 INFO L262 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 16 conjunts are in the unsatisfiable core [2023-12-02 19:31:52,916 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 19:31:53,043 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 11 proven. 16 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2023-12-02 19:31:53,043 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 19:31:53,240 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 14 proven. 16 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2023-12-02 19:31:53,240 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 19:31:53,240 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [367459095] [2023-12-02 19:31:53,241 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 19:31:53,241 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1598735537] [2023-12-02 19:31:53,241 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1598735537] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 19:31:53,241 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [8679212] [2023-12-02 19:31:53,243 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-12-02 19:31:53,243 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 19:31:53,244 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 19:31:53,244 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 19:31:53,244 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 19:31:54,218 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 19:31:54,221 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 19:31:55,165 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3373#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 19:31:55,165 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 19:31:55,166 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 19:31:55,166 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 11 [2023-12-02 19:31:55,166 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [625431573] [2023-12-02 19:31:55,166 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 19:31:55,166 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-12-02 19:31:55,166 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 19:31:55,167 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-12-02 19:31:55,167 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=391, Unknown=0, NotChecked=0, Total=462 [2023-12-02 19:31:55,167 INFO L87 Difference]: Start difference. First operand 171 states and 199 transitions. Second operand has 11 states, 11 states have (on average 2.6363636363636362) internal successors, (29), 10 states have internal predecessors, (29), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2023-12-02 19:31:55,375 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 19:31:55,375 INFO L93 Difference]: Finished difference Result 193 states and 225 transitions. [2023-12-02 19:31:55,376 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-12-02 19:31:55,376 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.6363636363636362) internal successors, (29), 10 states have internal predecessors, (29), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) Word has length 43 [2023-12-02 19:31:55,376 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 19:31:55,378 INFO L225 Difference]: With dead ends: 193 [2023-12-02 19:31:55,378 INFO L226 Difference]: Without dead ends: 191 [2023-12-02 19:31:55,378 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 107 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 99 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=80, Invalid=426, Unknown=0, NotChecked=0, Total=506 [2023-12-02 19:31:55,379 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 18 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 88 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 100 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 88 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-02 19:31:55,379 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 104 Invalid, 100 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 88 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-02 19:31:55,379 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 191 states. [2023-12-02 19:31:55,402 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 191 to 187. [2023-12-02 19:31:55,402 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 187 states, 120 states have (on average 1.1416666666666666) internal successors, (137), 126 states have internal predecessors, (137), 41 states have call successors, (41), 25 states have call predecessors, (41), 25 states have return successors, (37), 35 states have call predecessors, (37), 37 states have call successors, (37) [2023-12-02 19:31:55,403 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 187 states to 187 states and 215 transitions. [2023-12-02 19:31:55,404 INFO L78 Accepts]: Start accepts. Automaton has 187 states and 215 transitions. Word has length 43 [2023-12-02 19:31:55,404 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 19:31:55,404 INFO L495 AbstractCegarLoop]: Abstraction has 187 states and 215 transitions. [2023-12-02 19:31:55,404 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.6363636363636362) internal successors, (29), 10 states have internal predecessors, (29), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2023-12-02 19:31:55,404 INFO L276 IsEmpty]: Start isEmpty. Operand 187 states and 215 transitions. [2023-12-02 19:31:55,406 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2023-12-02 19:31:55,406 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 19:31:55,406 INFO L195 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] [2023-12-02 19:31:55,411 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2023-12-02 19:31:55,607 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:31:55,607 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 19:31:55,607 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 19:31:55,607 INFO L85 PathProgramCache]: Analyzing trace with hash -2003316837, now seen corresponding path program 1 times [2023-12-02 19:31:55,607 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 19:31:55,608 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1269699969] [2023-12-02 19:31:55,608 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:55,608 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 19:31:55,615 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 19:31:55,615 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1887336262] [2023-12-02 19:31:55,615 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:31:55,615 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:31:55,616 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 19:31:55,616 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 19:31:55,619 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-12-02 19:31:55,672 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 19:31:55,673 INFO L262 TraceCheckSpWp]: Trace formula consists of 145 conjuncts, 30 conjunts are in the unsatisfiable core [2023-12-02 19:31:55,676 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 19:31:56,029 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 15 proven. 31 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-12-02 19:31:56,030 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 19:32:01,441 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 15 proven. 31 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-12-02 19:32:01,441 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 19:32:01,441 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1269699969] [2023-12-02 19:32:01,441 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 19:32:01,441 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1887336262] [2023-12-02 19:32:01,441 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1887336262] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 19:32:01,441 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [757990367] [2023-12-02 19:32:01,443 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2023-12-02 19:32:01,443 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 19:32:01,443 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 19:32:01,443 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 19:32:01,443 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 19:32:02,981 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 19:32:02,984 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 19:32:31,080 WARN L293 SmtUtils]: Spent 23.43s on a formula simplification. DAG size of input: 83 DAG size of output: 79 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 19:32:33,647 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4278#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 19:32:33,647 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 19:32:33,647 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 19:32:33,647 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2023-12-02 19:32:33,648 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1541788113] [2023-12-02 19:32:33,648 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 19:32:33,648 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-12-02 19:32:33,648 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 19:32:33,649 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-12-02 19:32:33,649 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=616, Unknown=1, NotChecked=0, Total=702 [2023-12-02 19:32:33,649 INFO L87 Difference]: Start difference. First operand 187 states and 215 transitions. Second operand has 15 states, 15 states have (on average 2.466666666666667) internal successors, (37), 13 states have internal predecessors, (37), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2023-12-02 19:32:36,905 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 19:32:36,905 INFO L93 Difference]: Finished difference Result 227 states and 254 transitions. [2023-12-02 19:32:36,906 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-12-02 19:32:36,906 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.466666666666667) internal successors, (37), 13 states have internal predecessors, (37), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) Word has length 56 [2023-12-02 19:32:36,906 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 19:32:36,908 INFO L225 Difference]: With dead ends: 227 [2023-12-02 19:32:36,908 INFO L226 Difference]: Without dead ends: 223 [2023-12-02 19:32:36,909 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 171 GetRequests, 139 SyntacticMatches, 3 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 192 ImplicationChecksByTransitivity, 33.6s TimeCoverageRelationStatistics Valid=117, Invalid=812, Unknown=1, NotChecked=0, Total=930 [2023-12-02 19:32:36,909 INFO L413 NwaCegarLoop]: 26 mSDtfsCounter, 42 mSDsluCounter, 212 mSDsCounter, 0 mSdLazyCounter, 185 mSolverCounterSat, 51 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 43 SdHoareTripleChecker+Valid, 238 SdHoareTripleChecker+Invalid, 236 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 51 IncrementalHoareTripleChecker+Valid, 185 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2023-12-02 19:32:36,910 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [43 Valid, 238 Invalid, 236 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [51 Valid, 185 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2023-12-02 19:32:36,910 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 223 states. [2023-12-02 19:32:36,954 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 223 to 218. [2023-12-02 19:32:36,954 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 218 states, 144 states have (on average 1.1180555555555556) internal successors, (161), 150 states have internal predecessors, (161), 42 states have call successors, (42), 32 states have call predecessors, (42), 31 states have return successors, (38), 35 states have call predecessors, (38), 38 states have call successors, (38) [2023-12-02 19:32:36,956 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 218 states to 218 states and 241 transitions. [2023-12-02 19:32:36,956 INFO L78 Accepts]: Start accepts. Automaton has 218 states and 241 transitions. Word has length 56 [2023-12-02 19:32:36,956 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 19:32:36,957 INFO L495 AbstractCegarLoop]: Abstraction has 218 states and 241 transitions. [2023-12-02 19:32:36,957 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.466666666666667) internal successors, (37), 13 states have internal predecessors, (37), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2023-12-02 19:32:36,957 INFO L276 IsEmpty]: Start isEmpty. Operand 218 states and 241 transitions. [2023-12-02 19:32:36,959 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2023-12-02 19:32:36,959 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 19:32:36,959 INFO L195 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] [2023-12-02 19:32:36,964 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2023-12-02 19:32:37,159 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:32:37,160 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 19:32:37,160 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 19:32:37,160 INFO L85 PathProgramCache]: Analyzing trace with hash -1317937589, now seen corresponding path program 1 times [2023-12-02 19:32:37,160 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 19:32:37,160 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1935520044] [2023-12-02 19:32:37,160 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:32:37,160 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 19:32:37,168 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 19:32:37,168 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1966088825] [2023-12-02 19:32:37,168 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:32:37,169 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:32:37,169 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 19:32:37,170 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 19:32:37,172 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-12-02 19:32:37,223 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 19:32:37,225 INFO L262 TraceCheckSpWp]: Trace formula consists of 165 conjuncts, 26 conjunts are in the unsatisfiable core [2023-12-02 19:32:37,227 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 19:32:37,615 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 19 proven. 39 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2023-12-02 19:32:37,615 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 19:32:38,500 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 22 proven. 36 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2023-12-02 19:32:38,500 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 19:32:38,500 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1935520044] [2023-12-02 19:32:38,500 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 19:32:38,500 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1966088825] [2023-12-02 19:32:38,500 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1966088825] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 19:32:38,500 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1293452849] [2023-12-02 19:32:38,502 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-12-02 19:32:38,503 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 19:32:38,503 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 19:32:38,503 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 19:32:38,503 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 19:32:39,896 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 19:32:39,899 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 19:33:02,120 WARN L293 SmtUtils]: Spent 20.86s on a formula simplification. DAG size of input: 83 DAG size of output: 79 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 19:33:03,804 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5344#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 19:33:03,804 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 19:33:03,804 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 19:33:03,805 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2023-12-02 19:33:03,805 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [743981408] [2023-12-02 19:33:03,805 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 19:33:03,805 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-12-02 19:33:03,806 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 19:33:03,806 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-12-02 19:33:03,807 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=115, Invalid=755, Unknown=0, NotChecked=0, Total=870 [2023-12-02 19:33:03,807 INFO L87 Difference]: Start difference. First operand 218 states and 241 transitions. Second operand has 17 states, 15 states have (on average 2.6) internal successors, (39), 15 states have internal predecessors, (39), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 7 states have call successors, (20) [2023-12-02 19:33:04,719 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 19:33:04,719 INFO L93 Difference]: Finished difference Result 238 states and 265 transitions. [2023-12-02 19:33:04,720 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-12-02 19:33:04,720 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 2.6) internal successors, (39), 15 states have internal predecessors, (39), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 7 states have call successors, (20) Word has length 67 [2023-12-02 19:33:04,720 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 19:33:04,722 INFO L225 Difference]: With dead ends: 238 [2023-12-02 19:33:04,722 INFO L226 Difference]: Without dead ends: 211 [2023-12-02 19:33:04,723 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 203 GetRequests, 169 SyntacticMatches, 3 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 245 ImplicationChecksByTransitivity, 24.4s TimeCoverageRelationStatistics Valid=138, Invalid=918, Unknown=0, NotChecked=0, Total=1056 [2023-12-02 19:33:04,724 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 25 mSDsluCounter, 132 mSDsCounter, 0 mSdLazyCounter, 208 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 160 SdHoareTripleChecker+Invalid, 231 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 208 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2023-12-02 19:33:04,724 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 160 Invalid, 231 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 208 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2023-12-02 19:33:04,725 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 211 states. [2023-12-02 19:33:04,780 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 211 to 196. [2023-12-02 19:33:04,781 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 196 states, 130 states have (on average 1.1307692307692307) internal successors, (147), 133 states have internal predecessors, (147), 37 states have call successors, (37), 29 states have call predecessors, (37), 28 states have return successors, (34), 33 states have call predecessors, (34), 34 states have call successors, (34) [2023-12-02 19:33:04,782 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 196 states to 196 states and 218 transitions. [2023-12-02 19:33:04,782 INFO L78 Accepts]: Start accepts. Automaton has 196 states and 218 transitions. Word has length 67 [2023-12-02 19:33:04,782 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 19:33:04,782 INFO L495 AbstractCegarLoop]: Abstraction has 196 states and 218 transitions. [2023-12-02 19:33:04,782 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 2.6) internal successors, (39), 15 states have internal predecessors, (39), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 7 states have call successors, (20) [2023-12-02 19:33:04,782 INFO L276 IsEmpty]: Start isEmpty. Operand 196 states and 218 transitions. [2023-12-02 19:33:04,783 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2023-12-02 19:33:04,783 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 19:33:04,784 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 19:33:04,791 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2023-12-02 19:33:04,984 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2023-12-02 19:33:04,984 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 19:33:04,985 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 19:33:04,985 INFO L85 PathProgramCache]: Analyzing trace with hash 575510565, now seen corresponding path program 1 times [2023-12-02 19:33:04,985 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 19:33:04,985 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1348375215] [2023-12-02 19:33:04,985 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:33:04,985 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 19:33:04,994 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 19:33:04,995 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [824210150] [2023-12-02 19:33:04,995 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:33:04,995 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:33:04,995 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 19:33:04,996 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 19:33:04,997 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-12-02 19:33:05,056 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 19:33:05,057 INFO L262 TraceCheckSpWp]: Trace formula consists of 182 conjuncts, 4 conjunts are in the unsatisfiable core [2023-12-02 19:33:05,060 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 19:33:05,100 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 84 proven. 0 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2023-12-02 19:33:05,100 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-02 19:33:05,100 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 19:33:05,100 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1348375215] [2023-12-02 19:33:05,100 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 19:33:05,101 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [824210150] [2023-12-02 19:33:05,101 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [824210150] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 19:33:05,101 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 19:33:05,101 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-12-02 19:33:05,101 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [543841521] [2023-12-02 19:33:05,101 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 19:33:05,102 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-02 19:33:05,102 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 19:33:05,102 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-02 19:33:05,103 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2023-12-02 19:33:05,103 INFO L87 Difference]: Start difference. First operand 196 states and 218 transitions. Second operand has 5 states, 5 states have (on average 4.2) internal successors, (21), 5 states have internal predecessors, (21), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-12-02 19:33:05,213 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 19:33:05,214 INFO L93 Difference]: Finished difference Result 215 states and 237 transitions. [2023-12-02 19:33:05,214 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-12-02 19:33:05,214 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 5 states have internal predecessors, (21), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 77 [2023-12-02 19:33:05,215 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 19:33:05,216 INFO L225 Difference]: With dead ends: 215 [2023-12-02 19:33:05,217 INFO L226 Difference]: Without dead ends: 185 [2023-12-02 19:33:05,217 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 73 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2023-12-02 19:33:05,218 INFO L413 NwaCegarLoop]: 43 mSDtfsCounter, 12 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 93 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 19:33:05,218 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 93 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 19:33:05,219 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 185 states. [2023-12-02 19:33:05,266 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 185 to 182. [2023-12-02 19:33:05,266 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 182 states, 122 states have (on average 1.098360655737705) internal successors, (134), 124 states have internal predecessors, (134), 33 states have call successors, (33), 26 states have call predecessors, (33), 26 states have return successors, (32), 31 states have call predecessors, (32), 32 states have call successors, (32) [2023-12-02 19:33:05,267 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 182 states to 182 states and 199 transitions. [2023-12-02 19:33:05,268 INFO L78 Accepts]: Start accepts. Automaton has 182 states and 199 transitions. Word has length 77 [2023-12-02 19:33:05,268 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 19:33:05,268 INFO L495 AbstractCegarLoop]: Abstraction has 182 states and 199 transitions. [2023-12-02 19:33:05,268 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 5 states have internal predecessors, (21), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-12-02 19:33:05,268 INFO L276 IsEmpty]: Start isEmpty. Operand 182 states and 199 transitions. [2023-12-02 19:33:05,269 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2023-12-02 19:33:05,269 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 19:33:05,270 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2023-12-02 19:33:05,274 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2023-12-02 19:33:05,470 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2023-12-02 19:33:05,470 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 19:33:05,471 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 19:33:05,471 INFO L85 PathProgramCache]: Analyzing trace with hash -362747475, now seen corresponding path program 2 times [2023-12-02 19:33:05,471 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 19:33:05,471 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1001077992] [2023-12-02 19:33:05,471 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:33:05,471 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 19:33:05,479 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 19:33:05,479 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2052936754] [2023-12-02 19:33:05,480 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-02 19:33:05,480 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:33:05,480 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 19:33:05,481 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 19:33:05,488 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-12-02 19:33:05,621 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-12-02 19:33:05,621 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 19:33:05,623 INFO L262 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 30 conjunts are in the unsatisfiable core [2023-12-02 19:33:05,627 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 19:33:06,009 INFO L134 CoverageAnalysis]: Checked inductivity of 310 backedges. 41 proven. 38 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-12-02 19:33:06,010 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 19:33:08,007 INFO L134 CoverageAnalysis]: Checked inductivity of 310 backedges. 41 proven. 32 refuted. 0 times theorem prover too weak. 237 trivial. 0 not checked. [2023-12-02 19:33:08,007 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 19:33:08,007 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1001077992] [2023-12-02 19:33:08,007 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 19:33:08,007 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2052936754] [2023-12-02 19:33:08,008 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2052936754] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 19:33:08,008 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1132590658] [2023-12-02 19:33:08,010 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2023-12-02 19:33:08,010 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 19:33:08,011 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 19:33:08,011 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 19:33:08,011 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 19:33:09,806 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 19:33:09,809 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 19:33:34,794 WARN L293 SmtUtils]: Spent 22.20s on a formula simplification. DAG size of input: 83 DAG size of output: 79 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 19:33:37,361 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '7258#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 19:33:37,361 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 19:33:37,361 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 19:33:37,361 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 17 [2023-12-02 19:33:37,361 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [497953571] [2023-12-02 19:33:37,361 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 19:33:37,362 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-12-02 19:33:37,362 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 19:33:37,363 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-12-02 19:33:37,363 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=98, Invalid=713, Unknown=1, NotChecked=0, Total=812 [2023-12-02 19:33:37,363 INFO L87 Difference]: Start difference. First operand 182 states and 199 transitions. Second operand has 17 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 9 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) [2023-12-02 19:33:38,865 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 19:33:38,865 INFO L93 Difference]: Finished difference Result 193 states and 212 transitions. [2023-12-02 19:33:38,865 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-12-02 19:33:38,866 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 9 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) Word has length 79 [2023-12-02 19:33:38,866 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 19:33:38,867 INFO L225 Difference]: With dead ends: 193 [2023-12-02 19:33:38,867 INFO L226 Difference]: Without dead ends: 191 [2023-12-02 19:33:38,868 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 238 GetRequests, 205 SyntacticMatches, 4 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 223 ImplicationChecksByTransitivity, 28.7s TimeCoverageRelationStatistics Valid=117, Invalid=812, Unknown=1, NotChecked=0, Total=930 [2023-12-02 19:33:38,869 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 27 mSDsluCounter, 237 mSDsCounter, 0 mSdLazyCounter, 289 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 270 SdHoareTripleChecker+Invalid, 308 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 289 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2023-12-02 19:33:38,869 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 270 Invalid, 308 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 289 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2023-12-02 19:33:38,870 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 191 states. [2023-12-02 19:33:38,911 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 191 to 188. [2023-12-02 19:33:38,912 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 188 states, 125 states have (on average 1.088) internal successors, (136), 128 states have internal predecessors, (136), 35 states have call successors, (35), 27 states have call predecessors, (35), 27 states have return successors, (34), 32 states have call predecessors, (34), 34 states have call successors, (34) [2023-12-02 19:33:38,913 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 188 states to 188 states and 205 transitions. [2023-12-02 19:33:38,913 INFO L78 Accepts]: Start accepts. Automaton has 188 states and 205 transitions. Word has length 79 [2023-12-02 19:33:38,913 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 19:33:38,913 INFO L495 AbstractCegarLoop]: Abstraction has 188 states and 205 transitions. [2023-12-02 19:33:38,913 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 9 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) [2023-12-02 19:33:38,913 INFO L276 IsEmpty]: Start isEmpty. Operand 188 states and 205 transitions. [2023-12-02 19:33:38,914 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2023-12-02 19:33:38,914 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 19:33:38,914 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1] [2023-12-02 19:33:38,918 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2023-12-02 19:33:39,115 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2023-12-02 19:33:39,115 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 19:33:39,115 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 19:33:39,115 INFO L85 PathProgramCache]: Analyzing trace with hash 11727052, now seen corresponding path program 3 times [2023-12-02 19:33:39,115 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 19:33:39,115 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1302767307] [2023-12-02 19:33:39,115 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:33:39,115 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 19:33:39,124 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 19:33:39,124 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2011709955] [2023-12-02 19:33:39,124 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-02 19:33:39,124 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:33:39,124 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 19:33:39,125 INFO L229 MonitoredProcess]: Starting monitored process 15 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 19:33:39,126 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_bedd8eb2-35e2-430a-a1a6-956b71cde8da/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2023-12-02 19:33:39,188 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-02 19:33:39,188 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 19:33:39,190 INFO L262 TraceCheckSpWp]: Trace formula consists of 211 conjuncts, 45 conjunts are in the unsatisfiable core [2023-12-02 19:33:39,193 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 19:33:39,990 INFO L134 CoverageAnalysis]: Checked inductivity of 367 backedges. 72 proven. 49 refuted. 0 times theorem prover too weak. 246 trivial. 0 not checked. [2023-12-02 19:33:39,991 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 19:34:02,099 WARN L293 SmtUtils]: Spent 5.40s on a formula simplification that was a NOOP. DAG size: 161 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate)