./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/hard-u_unwindbound5.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 826ab2ba Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/hard-u_unwindbound5.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E --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 082e5acb2a505af9e43ec1a894890509a127a32d8ecd4c5193a456bddcb0f4a3 --- Real Ultimate output --- This is Ultimate 0.3.0-dev-826ab2b [2024-11-14 02:59:40,411 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-14 02:59:40,511 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-32bit-Taipan_Default.epf [2024-11-14 02:59:40,519 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-14 02:59:40,519 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-14 02:59:40,553 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-14 02:59:40,554 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-14 02:59:40,555 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-14 02:59:40,555 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-14 02:59:40,556 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-14 02:59:40,556 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-14 02:59:40,557 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-14 02:59:40,557 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-14 02:59:40,557 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-14 02:59:40,557 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-14 02:59:40,557 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-14 02:59:40,557 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-14 02:59:40,557 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-14 02:59:40,557 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-14 02:59:40,557 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-14 02:59:40,557 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-14 02:59:40,558 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-14 02:59:40,558 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-14 02:59:40,558 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-14 02:59:40,558 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-14 02:59:40,558 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-14 02:59:40,558 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-14 02:59:40,558 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-14 02:59:40,558 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-14 02:59:40,558 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-14 02:59:40,559 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-14 02:59:40,559 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-14 02:59:40,559 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-14 02:59:40,559 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-14 02:59:40,559 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-14 02:59:40,560 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-14 02:59:40,560 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-14 02:59:40,560 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-14 02:59:40,561 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 02:59:40,561 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-14 02:59:40,561 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-14 02:59:40,561 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-14 02:59:40,561 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-14 02:59:40,561 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-14 02:59:40,562 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-14 02:59:40,562 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-14 02:59:40,562 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-14 02:59:40,562 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES 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_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E 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 -> 082e5acb2a505af9e43ec1a894890509a127a32d8ecd4c5193a456bddcb0f4a3 [2024-11-14 02:59:40,917 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-14 02:59:40,932 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-14 02:59:40,935 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-14 02:59:40,938 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-14 02:59:40,938 INFO L274 PluginConnector]: CDTParser initialized [2024-11-14 02:59:40,940 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/../../sv-benchmarks/c/nla-digbench-scaling/hard-u_unwindbound5.c Unable to find full path for "g++" [2024-11-14 02:59:42,838 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-14 02:59:43,157 INFO L384 CDTParser]: Found 1 translation units. [2024-11-14 02:59:43,159 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/sv-benchmarks/c/nla-digbench-scaling/hard-u_unwindbound5.c [2024-11-14 02:59:43,168 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/data/d5804f032/6b58c668440b4edbb4daa61dbe3732da/FLAG9c854aa8b [2024-11-14 02:59:43,429 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/data/d5804f032/6b58c668440b4edbb4daa61dbe3732da [2024-11-14 02:59:43,432 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-14 02:59:43,434 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-14 02:59:43,436 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-14 02:59:43,436 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-14 02:59:43,442 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-14 02:59:43,443 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 02:59:43" (1/1) ... [2024-11-14 02:59:43,446 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5af0f20b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:59:43, skipping insertion in model container [2024-11-14 02:59:43,447 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 02:59:43" (1/1) ... [2024-11-14 02:59:43,466 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-14 02:59:43,683 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/sv-benchmarks/c/nla-digbench-scaling/hard-u_unwindbound5.c[537,550] [2024-11-14 02:59:43,715 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 02:59:43,728 INFO L200 MainTranslator]: Completed pre-run [2024-11-14 02:59:43,743 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/sv-benchmarks/c/nla-digbench-scaling/hard-u_unwindbound5.c[537,550] [2024-11-14 02:59:43,762 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 02:59:43,788 INFO L204 MainTranslator]: Completed translation [2024-11-14 02:59:43,789 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:59:43 WrapperNode [2024-11-14 02:59:43,789 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-14 02:59:43,790 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-14 02:59:43,790 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-14 02:59:43,790 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-14 02:59:43,800 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:59:43" (1/1) ... [2024-11-14 02:59:43,807 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:59:43" (1/1) ... [2024-11-14 02:59:43,831 INFO L138 Inliner]: procedures = 14, calls = 15, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 64 [2024-11-14 02:59:43,832 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-14 02:59:43,832 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-14 02:59:43,833 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-14 02:59:43,834 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-14 02:59:43,843 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:59:43" (1/1) ... [2024-11-14 02:59:43,844 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:59:43" (1/1) ... [2024-11-14 02:59:43,845 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:59:43" (1/1) ... [2024-11-14 02:59:43,849 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:59:43" (1/1) ... [2024-11-14 02:59:43,856 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:59:43" (1/1) ... [2024-11-14 02:59:43,862 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:59:43" (1/1) ... [2024-11-14 02:59:43,867 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:59:43" (1/1) ... [2024-11-14 02:59:43,868 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:59:43" (1/1) ... [2024-11-14 02:59:43,870 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-14 02:59:43,875 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-14 02:59:43,875 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-14 02:59:43,875 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-14 02:59:43,876 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:59:43" (1/1) ... [2024-11-14 02:59:43,886 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 02:59:43,904 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:59:43,925 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-14 02:59:43,929 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-14 02:59:43,962 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-14 02:59:43,962 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-14 02:59:43,963 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-14 02:59:43,963 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-14 02:59:43,963 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-14 02:59:43,964 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-14 02:59:44,043 INFO L238 CfgBuilder]: Building ICFG [2024-11-14 02:59:44,046 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-14 02:59:44,237 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-14 02:59:44,237 INFO L287 CfgBuilder]: Performing block encoding [2024-11-14 02:59:44,297 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-14 02:59:44,297 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-14 02:59:44,297 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 02:59:44 BoogieIcfgContainer [2024-11-14 02:59:44,298 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-14 02:59:44,300 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-14 02:59:44,300 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-14 02:59:44,306 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-14 02:59:44,307 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.11 02:59:43" (1/3) ... [2024-11-14 02:59:44,308 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6f9f8885 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 02:59:44, skipping insertion in model container [2024-11-14 02:59:44,308 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:59:43" (2/3) ... [2024-11-14 02:59:44,309 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6f9f8885 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 02:59:44, skipping insertion in model container [2024-11-14 02:59:44,309 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 02:59:44" (3/3) ... [2024-11-14 02:59:44,311 INFO L112 eAbstractionObserver]: Analyzing ICFG hard-u_unwindbound5.c [2024-11-14 02:59:44,337 INFO L217 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-14 02:59:44,340 INFO L154 ceAbstractionStarter]: Applying trace abstraction to ICFG hard-u_unwindbound5.c that has 2 procedures, 22 locations, 1 initial locations, 2 loop locations, and 1 error locations. [2024-11-14 02:59:44,416 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-14 02:59:44,436 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@2b270239, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-14 02:59:44,437 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-14 02:59:44,442 INFO L276 IsEmpty]: Start isEmpty. Operand has 22 states, 12 states have (on average 1.6666666666666667) internal successors, (20), 13 states have internal predecessors, (20), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-14 02:59:44,450 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-14 02:59:44,450 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:59:44,451 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:59:44,452 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:59:44,456 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:59:44,457 INFO L85 PathProgramCache]: Analyzing trace with hash -1654084864, now seen corresponding path program 1 times [2024-11-14 02:59:44,466 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:59:44,467 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2143706667] [2024-11-14 02:59:44,467 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:59:44,468 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:59:44,557 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:59:44,606 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:59:44,607 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:59:44,607 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2143706667] [2024-11-14 02:59:44,608 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2143706667] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:59:44,608 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:59:44,608 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-14 02:59:44,609 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1111071664] [2024-11-14 02:59:44,610 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:59:44,618 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-14 02:59:44,621 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:59:44,644 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-14 02:59:44,645 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-14 02:59:44,648 INFO L87 Difference]: Start difference. First operand has 22 states, 12 states have (on average 1.6666666666666667) internal successors, (20), 13 states have internal predecessors, (20), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:59:44,686 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:59:44,687 INFO L93 Difference]: Finished difference Result 43 states and 74 transitions. [2024-11-14 02:59:44,688 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-14 02:59:44,690 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2024-11-14 02:59:44,690 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:59:44,697 INFO L225 Difference]: With dead ends: 43 [2024-11-14 02:59:44,697 INFO L226 Difference]: Without dead ends: 20 [2024-11-14 02:59:44,700 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-14 02:59:44,703 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 3 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 28 SdHoareTripleChecker+Invalid, 3 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 3 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 02:59:44,704 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 28 Invalid, 3 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 3 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 02:59:44,719 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2024-11-14 02:59:44,734 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2024-11-14 02:59:44,736 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 12 states have internal predecessors, (16), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-14 02:59:44,740 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 29 transitions. [2024-11-14 02:59:44,742 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 29 transitions. Word has length 7 [2024-11-14 02:59:44,742 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:59:44,743 INFO L471 AbstractCegarLoop]: Abstraction has 20 states and 29 transitions. [2024-11-14 02:59:44,743 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:59:44,743 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 29 transitions. [2024-11-14 02:59:44,744 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-14 02:59:44,744 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:59:44,744 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:59:44,745 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-14 02:59:44,745 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:59:44,746 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:59:44,746 INFO L85 PathProgramCache]: Analyzing trace with hash -2115219753, now seen corresponding path program 1 times [2024-11-14 02:59:44,746 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:59:44,746 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [903561913] [2024-11-14 02:59:44,747 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:59:44,747 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:59:44,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:59:45,046 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:59:45,046 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:59:45,046 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [903561913] [2024-11-14 02:59:45,046 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [903561913] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:59:45,047 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:59:45,047 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-14 02:59:45,047 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [439545232] [2024-11-14 02:59:45,047 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:59:45,048 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 02:59:45,048 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:59:45,048 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 02:59:45,049 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-14 02:59:45,049 INFO L87 Difference]: Start difference. First operand 20 states and 29 transitions. Second operand has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:59:45,154 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:59:45,155 INFO L93 Difference]: Finished difference Result 33 states and 46 transitions. [2024-11-14 02:59:45,158 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 02:59:45,158 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2024-11-14 02:59:45,159 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:59:45,159 INFO L225 Difference]: With dead ends: 33 [2024-11-14 02:59:45,159 INFO L226 Difference]: Without dead ends: 31 [2024-11-14 02:59:45,160 INFO L431 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 [2024-11-14 02:59:45,161 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 10 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 02:59:45,162 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 82 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 02:59:45,163 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2024-11-14 02:59:45,178 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 24. [2024-11-14 02:59:45,179 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 14 states have (on average 1.3571428571428572) internal successors, (19), 15 states have internal predecessors, (19), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-14 02:59:45,179 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 32 transitions. [2024-11-14 02:59:45,180 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 32 transitions. Word has length 7 [2024-11-14 02:59:45,180 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:59:45,180 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 32 transitions. [2024-11-14 02:59:45,180 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:59:45,180 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 32 transitions. [2024-11-14 02:59:45,181 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-11-14 02:59:45,181 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:59:45,182 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:59:45,182 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-14 02:59:45,183 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:59:45,184 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:59:45,185 INFO L85 PathProgramCache]: Analyzing trace with hash 174216846, now seen corresponding path program 1 times [2024-11-14 02:59:45,185 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:59:45,185 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1860741002] [2024-11-14 02:59:45,185 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:59:45,185 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:59:45,198 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:59:45,300 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:59:45,300 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:59:45,300 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1860741002] [2024-11-14 02:59:45,300 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1860741002] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:59:45,300 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:59:45,300 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-14 02:59:45,301 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [412759631] [2024-11-14 02:59:45,301 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:59:45,301 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-14 02:59:45,301 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:59:45,302 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-14 02:59:45,302 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 02:59:45,302 INFO L87 Difference]: Start difference. First operand 24 states and 32 transitions. Second operand has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:59:45,333 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:59:45,333 INFO L93 Difference]: Finished difference Result 39 states and 52 transitions. [2024-11-14 02:59:45,334 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-14 02:59:45,334 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2024-11-14 02:59:45,334 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:59:45,335 INFO L225 Difference]: With dead ends: 39 [2024-11-14 02:59:45,335 INFO L226 Difference]: Without dead ends: 26 [2024-11-14 02:59:45,335 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 02:59:45,336 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 0 mSDsluCounter, 48 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 13 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 02:59:45,337 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 73 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 02:59:45,339 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2024-11-14 02:59:45,347 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2024-11-14 02:59:45,348 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 16 states have (on average 1.3125) internal successors, (21), 17 states have internal predecessors, (21), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-14 02:59:45,348 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 34 transitions. [2024-11-14 02:59:45,349 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 34 transitions. Word has length 9 [2024-11-14 02:59:45,349 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:59:45,349 INFO L471 AbstractCegarLoop]: Abstraction has 26 states and 34 transitions. [2024-11-14 02:59:45,351 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:59:45,351 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 34 transitions. [2024-11-14 02:59:45,352 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2024-11-14 02:59:45,352 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:59:45,352 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:59:45,352 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-14 02:59:45,352 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:59:45,353 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:59:45,353 INFO L85 PathProgramCache]: Analyzing trace with hash 1872131942, now seen corresponding path program 1 times [2024-11-14 02:59:45,353 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:59:45,353 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [112646488] [2024-11-14 02:59:45,353 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:59:45,353 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:59:45,377 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:59:45,610 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:59:45,610 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:59:45,610 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [112646488] [2024-11-14 02:59:45,610 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [112646488] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:59:45,610 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:59:45,610 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-14 02:59:45,611 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1842856238] [2024-11-14 02:59:45,611 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:59:45,611 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 02:59:45,611 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:59:45,612 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 02:59:45,612 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-14 02:59:45,612 INFO L87 Difference]: Start difference. First operand 26 states and 34 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-14 02:59:45,792 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:59:45,792 INFO L93 Difference]: Finished difference Result 39 states and 51 transitions. [2024-11-14 02:59:45,794 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 02:59:45,794 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2024-11-14 02:59:45,795 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:59:45,795 INFO L225 Difference]: With dead ends: 39 [2024-11-14 02:59:45,795 INFO L226 Difference]: Without dead ends: 37 [2024-11-14 02:59:45,796 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-14 02:59:45,799 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 10 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 02:59:45,800 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 83 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 02:59:45,801 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2024-11-14 02:59:45,812 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 30. [2024-11-14 02:59:45,813 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-14 02:59:45,814 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 37 transitions. [2024-11-14 02:59:45,814 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 37 transitions. Word has length 12 [2024-11-14 02:59:45,814 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:59:45,814 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 37 transitions. [2024-11-14 02:59:45,814 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-14 02:59:45,814 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 37 transitions. [2024-11-14 02:59:45,815 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-11-14 02:59:45,816 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:59:45,817 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:59:45,817 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-14 02:59:45,817 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:59:45,817 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:59:45,817 INFO L85 PathProgramCache]: Analyzing trace with hash -1306040329, now seen corresponding path program 1 times [2024-11-14 02:59:45,818 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:59:45,818 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1377941776] [2024-11-14 02:59:45,818 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:59:45,818 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:59:45,862 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 02:59:45,868 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1686422476] [2024-11-14 02:59:45,868 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:59:45,868 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:59:45,868 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:59:45,874 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:59:45,876 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-14 02:59:45,963 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:59:45,965 INFO L255 TraceCheckSpWp]: Trace formula consists of 64 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-14 02:59:45,970 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:59:46,211 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-14 02:59:46,212 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 02:59:46,212 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:59:46,213 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1377941776] [2024-11-14 02:59:46,214 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 02:59:46,214 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1686422476] [2024-11-14 02:59:46,214 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1686422476] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:59:46,214 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:59:46,214 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-14 02:59:46,214 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [163701212] [2024-11-14 02:59:46,215 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:59:46,215 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 02:59:46,215 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:59:46,215 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 02:59:46,216 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-14 02:59:46,216 INFO L87 Difference]: Start difference. First operand 30 states and 37 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-14 02:59:46,335 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:59:46,335 INFO L93 Difference]: Finished difference Result 58 states and 78 transitions. [2024-11-14 02:59:46,335 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 02:59:46,336 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2024-11-14 02:59:46,336 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:59:46,337 INFO L225 Difference]: With dead ends: 58 [2024-11-14 02:59:46,339 INFO L226 Difference]: Without dead ends: 44 [2024-11-14 02:59:46,339 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-14 02:59:46,340 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 7 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 02:59:46,340 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 82 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 02:59:46,344 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2024-11-14 02:59:46,356 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 44. [2024-11-14 02:59:46,357 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 28 states have internal predecessors, (33), 13 states have call successors, (13), 4 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-14 02:59:46,358 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 57 transitions. [2024-11-14 02:59:46,358 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 57 transitions. Word has length 17 [2024-11-14 02:59:46,358 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:59:46,358 INFO L471 AbstractCegarLoop]: Abstraction has 44 states and 57 transitions. [2024-11-14 02:59:46,359 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-14 02:59:46,359 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 57 transitions. [2024-11-14 02:59:46,359 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-11-14 02:59:46,360 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:59:46,360 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:59:46,385 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-14 02:59:46,564 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:59:46,565 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:59:46,565 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:59:46,565 INFO L85 PathProgramCache]: Analyzing trace with hash -507918445, now seen corresponding path program 1 times [2024-11-14 02:59:46,565 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:59:46,565 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1392886226] [2024-11-14 02:59:46,565 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:59:46,566 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:59:46,582 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:59:46,793 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-14 02:59:46,793 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:59:46,793 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1392886226] [2024-11-14 02:59:46,794 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1392886226] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:59:46,794 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:59:46,794 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-14 02:59:46,794 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1382961784] [2024-11-14 02:59:46,794 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:59:46,797 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-14 02:59:46,797 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:59:46,797 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-14 02:59:46,798 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-14 02:59:46,798 INFO L87 Difference]: Start difference. First operand 44 states and 57 transitions. Second operand has 6 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 02:59:46,908 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:59:46,908 INFO L93 Difference]: Finished difference Result 63 states and 72 transitions. [2024-11-14 02:59:46,909 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-14 02:59:46,909 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 25 [2024-11-14 02:59:46,911 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:59:46,912 INFO L225 Difference]: With dead ends: 63 [2024-11-14 02:59:46,913 INFO L226 Difference]: Without dead ends: 56 [2024-11-14 02:59:46,914 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-14 02:59:46,914 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 7 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 102 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 02:59:46,915 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 102 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 02:59:46,916 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2024-11-14 02:59:46,934 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 55. [2024-11-14 02:59:46,934 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 35 states have (on average 1.1714285714285715) internal successors, (41), 36 states have internal predecessors, (41), 12 states have call successors, (12), 7 states have call predecessors, (12), 7 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-14 02:59:46,939 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 64 transitions. [2024-11-14 02:59:46,939 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 64 transitions. Word has length 25 [2024-11-14 02:59:46,940 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:59:46,940 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 64 transitions. [2024-11-14 02:59:46,940 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 02:59:46,940 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 64 transitions. [2024-11-14 02:59:46,941 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-11-14 02:59:46,941 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:59:46,941 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:59:46,941 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-14 02:59:46,941 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:59:46,942 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:59:46,942 INFO L85 PathProgramCache]: Analyzing trace with hash -506190567, now seen corresponding path program 1 times [2024-11-14 02:59:46,944 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:59:46,944 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2071976913] [2024-11-14 02:59:46,944 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:59:46,944 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:59:46,977 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 02:59:46,978 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [894953468] [2024-11-14 02:59:46,979 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:59:46,979 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:59:46,979 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:59:46,983 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:59:46,985 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-14 02:59:47,057 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:59:47,062 INFO L255 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-14 02:59:47,065 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:59:47,420 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 10 proven. 2 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-14 02:59:47,421 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:59:47,866 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:59:47,866 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2071976913] [2024-11-14 02:59:47,866 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 02:59:47,866 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [894953468] [2024-11-14 02:59:47,866 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [894953468] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 02:59:47,866 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [232261014] [2024-11-14 02:59:47,899 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2024-11-14 02:59:47,900 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:59:47,903 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:59:47,908 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:59:47,909 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:59:48,590 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 48 for LOIs [2024-11-14 02:59:48,690 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 02:59:50,161 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [232261014] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:59:50,161 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-14 02:59:50,161 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [10] total 18 [2024-11-14 02:59:50,161 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [714964239] [2024-11-14 02:59:50,162 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:59:50,162 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-14 02:59:50,162 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:59:50,163 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-14 02:59:50,164 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=320, Unknown=0, NotChecked=0, Total=420 [2024-11-14 02:59:50,164 INFO L87 Difference]: Start difference. First operand 55 states and 64 transitions. Second operand has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 02:59:50,422 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:59:50,424 INFO L93 Difference]: Finished difference Result 61 states and 69 transitions. [2024-11-14 02:59:50,424 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-14 02:59:50,425 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 25 [2024-11-14 02:59:50,425 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:59:50,425 INFO L225 Difference]: With dead ends: 61 [2024-11-14 02:59:50,425 INFO L226 Difference]: Without dead ends: 59 [2024-11-14 02:59:50,426 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 28 SyntacticMatches, 10 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 162 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=100, Invalid=320, Unknown=0, NotChecked=0, Total=420 [2024-11-14 02:59:50,426 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 0 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 149 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 63 SdHoareTripleChecker+Invalid, 150 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 149 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 02:59:50,427 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 63 Invalid, 150 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 149 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 02:59:50,427 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2024-11-14 02:59:50,442 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 59. [2024-11-14 02:59:50,443 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 38 states have (on average 1.1578947368421053) internal successors, (44), 39 states have internal predecessors, (44), 12 states have call successors, (12), 8 states have call predecessors, (12), 8 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-14 02:59:50,443 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 67 transitions. [2024-11-14 02:59:50,444 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 67 transitions. Word has length 25 [2024-11-14 02:59:50,444 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:59:50,444 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 67 transitions. [2024-11-14 02:59:50,444 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 02:59:50,444 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 67 transitions. [2024-11-14 02:59:50,445 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-11-14 02:59:50,445 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:59:50,445 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:59:50,467 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-14 02:59:50,649 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:59:50,650 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:59:50,650 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:59:50,650 INFO L85 PathProgramCache]: Analyzing trace with hash -1960004552, now seen corresponding path program 1 times [2024-11-14 02:59:50,650 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:59:50,650 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1273843706] [2024-11-14 02:59:50,650 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:59:50,650 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:59:50,663 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:59:50,776 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-14 02:59:50,776 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:59:50,776 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1273843706] [2024-11-14 02:59:50,776 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1273843706] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 02:59:50,776 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [763369651] [2024-11-14 02:59:50,777 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:59:50,777 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:59:50,777 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:59:50,779 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:59:50,781 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-14 02:59:50,837 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:59:50,839 INFO L255 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-14 02:59:50,840 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:59:50,894 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-14 02:59:50,894 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:59:50,956 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-14 02:59:50,956 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [763369651] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:59:50,956 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1145263305] [2024-11-14 02:59:50,958 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2024-11-14 02:59:50,958 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:59:50,959 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:59:50,959 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:59:50,959 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:59:52,974 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 02:59:52,980 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:00:07,258 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1307#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 03:00:07,258 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:00:07,259 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 03:00:07,259 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 4, 5] total 10 [2024-11-14 03:00:07,259 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [471800009] [2024-11-14 03:00:07,259 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 03:00:07,260 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-14 03:00:07,260 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:00:07,260 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-14 03:00:07,261 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=385, Unknown=4, NotChecked=0, Total=462 [2024-11-14 03:00:07,261 INFO L87 Difference]: Start difference. First operand 59 states and 67 transitions. Second operand has 10 states, 10 states have (on average 2.6) internal successors, (26), 10 states have internal predecessors, (26), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-14 03:00:07,553 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:00:07,553 INFO L93 Difference]: Finished difference Result 124 states and 147 transitions. [2024-11-14 03:00:07,554 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-14 03:00:07,554 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.6) internal successors, (26), 10 states have internal predecessors, (26), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 27 [2024-11-14 03:00:07,554 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:00:07,555 INFO L225 Difference]: With dead ends: 124 [2024-11-14 03:00:07,555 INFO L226 Difference]: Without dead ends: 111 [2024-11-14 03:00:07,556 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 65 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 129 ImplicationChecksByTransitivity, 14.4s TimeCoverageRelationStatistics Valid=86, Invalid=462, Unknown=4, NotChecked=0, Total=552 [2024-11-14 03:00:07,556 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 52 mSDsluCounter, 111 mSDsCounter, 0 mSdLazyCounter, 90 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 52 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 104 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 90 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 03:00:07,557 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [52 Valid, 135 Invalid, 104 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 90 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 03:00:07,559 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2024-11-14 03:00:07,582 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 106. [2024-11-14 03:00:07,582 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 67 states have (on average 1.1791044776119404) internal successors, (79), 70 states have internal predecessors, (79), 24 states have call successors, (24), 14 states have call predecessors, (24), 14 states have return successors, (21), 21 states have call predecessors, (21), 21 states have call successors, (21) [2024-11-14 03:00:07,586 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 124 transitions. [2024-11-14 03:00:07,586 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 124 transitions. Word has length 27 [2024-11-14 03:00:07,586 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:00:07,586 INFO L471 AbstractCegarLoop]: Abstraction has 106 states and 124 transitions. [2024-11-14 03:00:07,589 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.6) internal successors, (26), 10 states have internal predecessors, (26), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-14 03:00:07,590 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 124 transitions. [2024-11-14 03:00:07,590 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-14 03:00:07,590 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:00:07,590 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2024-11-14 03:00:07,612 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-14 03:00:07,791 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2024-11-14 03:00:07,791 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:00:07,792 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:00:07,792 INFO L85 PathProgramCache]: Analyzing trace with hash 448166817, now seen corresponding path program 1 times [2024-11-14 03:00:07,792 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:00:07,792 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [45833021] [2024-11-14 03:00:07,792 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:00:07,792 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:00:07,827 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 03:00:07,828 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [804147406] [2024-11-14 03:00:07,828 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:00:07,828 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:00:07,828 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:00:07,830 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:00:07,839 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-14 03:00:07,972 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:00:07,973 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-14 03:00:07,975 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:00:08,074 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-14 03:00:08,074 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:00:08,240 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 15 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-14 03:00:08,240 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:00:08,240 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [45833021] [2024-11-14 03:00:08,240 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 03:00:08,240 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [804147406] [2024-11-14 03:00:08,240 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [804147406] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-14 03:00:08,240 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-14 03:00:08,240 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 8 [2024-11-14 03:00:08,240 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [997540822] [2024-11-14 03:00:08,240 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 03:00:08,241 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-14 03:00:08,241 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:00:08,241 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-14 03:00:08,241 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2024-11-14 03:00:08,242 INFO L87 Difference]: Start difference. First operand 106 states and 124 transitions. Second operand has 6 states, 6 states have (on average 2.0) internal successors, (12), 5 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-14 03:00:10,556 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:00:12,558 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:00:14,560 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:00:16,565 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:00:18,631 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.07s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:00:18,651 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:00:18,651 INFO L93 Difference]: Finished difference Result 129 states and 152 transitions. [2024-11-14 03:00:18,651 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 03:00:18,652 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 5 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 35 [2024-11-14 03:00:18,652 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:00:18,653 INFO L225 Difference]: With dead ends: 129 [2024-11-14 03:00:18,653 INFO L226 Difference]: Without dead ends: 127 [2024-11-14 03:00:18,653 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 60 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2024-11-14 03:00:18,654 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 8 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 2 mSolverCounterUnsat, 5 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 10.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 106 SdHoareTripleChecker+Invalid, 51 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 5 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 10.4s IncrementalHoareTripleChecker+Time [2024-11-14 03:00:18,654 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 106 Invalid, 51 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 44 Invalid, 5 Unknown, 0 Unchecked, 10.4s Time] [2024-11-14 03:00:18,655 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2024-11-14 03:00:18,684 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 122. [2024-11-14 03:00:18,685 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 78 states have (on average 1.1666666666666667) internal successors, (91), 82 states have internal predecessors, (91), 26 states have call successors, (26), 17 states have call predecessors, (26), 17 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2024-11-14 03:00:18,686 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 140 transitions. [2024-11-14 03:00:18,688 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 140 transitions. Word has length 35 [2024-11-14 03:00:18,689 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:00:18,689 INFO L471 AbstractCegarLoop]: Abstraction has 122 states and 140 transitions. [2024-11-14 03:00:18,689 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 5 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-14 03:00:18,689 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 140 transitions. [2024-11-14 03:00:18,690 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-11-14 03:00:18,691 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:00:18,691 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:00:18,697 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-14 03:00:18,892 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2024-11-14 03:00:18,892 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:00:18,892 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:00:18,892 INFO L85 PathProgramCache]: Analyzing trace with hash -938277045, now seen corresponding path program 1 times [2024-11-14 03:00:18,892 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:00:18,892 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [641943480] [2024-11-14 03:00:18,893 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:00:18,893 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:00:18,918 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 03:00:18,919 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [180745101] [2024-11-14 03:00:18,919 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:00:18,919 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:00:18,919 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:00:18,921 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:00:18,924 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-14 03:00:18,974 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:00:18,975 INFO L255 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-14 03:00:18,977 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:00:19,073 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 18 proven. 4 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-14 03:00:19,073 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:00:19,137 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:00:19,138 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [641943480] [2024-11-14 03:00:19,138 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 03:00:19,138 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [180745101] [2024-11-14 03:00:19,138 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [180745101] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 03:00:19,138 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [236134047] [2024-11-14 03:00:19,140 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2024-11-14 03:00:19,140 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:00:19,142 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:00:19,142 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:00:19,142 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:00:19,564 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 48 for LOIs [2024-11-14 03:00:19,603 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:00:20,606 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [236134047] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 03:00:20,606 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-14 03:00:20,606 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [8] total 17 [2024-11-14 03:00:20,607 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1905862328] [2024-11-14 03:00:20,607 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 03:00:20,607 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-14 03:00:20,607 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:00:20,608 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-14 03:00:20,608 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=237, Unknown=0, NotChecked=0, Total=306 [2024-11-14 03:00:20,608 INFO L87 Difference]: Start difference. First operand 122 states and 140 transitions. Second operand has 11 states, 10 states have (on average 1.2) internal successors, (12), 10 states have internal predecessors, (12), 3 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-14 03:00:20,858 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:00:20,858 INFO L93 Difference]: Finished difference Result 124 states and 141 transitions. [2024-11-14 03:00:20,858 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-14 03:00:20,858 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 1.2) internal successors, (12), 10 states have internal predecessors, (12), 3 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 36 [2024-11-14 03:00:20,859 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:00:20,861 INFO L225 Difference]: With dead ends: 124 [2024-11-14 03:00:20,861 INFO L226 Difference]: Without dead ends: 103 [2024-11-14 03:00:20,861 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 47 SyntacticMatches, 14 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 158 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=69, Invalid=237, Unknown=0, NotChecked=0, Total=306 [2024-11-14 03:00:20,862 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 0 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 181 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 58 SdHoareTripleChecker+Invalid, 182 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 181 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 03:00:20,862 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 58 Invalid, 182 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 181 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 03:00:20,863 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2024-11-14 03:00:20,875 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 103. [2024-11-14 03:00:20,875 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 66 states have (on average 1.1666666666666667) internal successors, (77), 69 states have internal predecessors, (77), 22 states have call successors, (22), 14 states have call predecessors, (22), 14 states have return successors, (20), 19 states have call predecessors, (20), 20 states have call successors, (20) [2024-11-14 03:00:20,883 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 119 transitions. [2024-11-14 03:00:20,883 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 119 transitions. Word has length 36 [2024-11-14 03:00:20,884 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:00:20,884 INFO L471 AbstractCegarLoop]: Abstraction has 103 states and 119 transitions. [2024-11-14 03:00:20,884 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 1.2) internal successors, (12), 10 states have internal predecessors, (12), 3 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-14 03:00:20,884 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 119 transitions. [2024-11-14 03:00:20,885 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-14 03:00:20,885 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:00:20,885 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:00:20,906 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-14 03:00:21,085 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-14 03:00:21,085 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:00:21,086 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:00:21,086 INFO L85 PathProgramCache]: Analyzing trace with hash -721972931, now seen corresponding path program 1 times [2024-11-14 03:00:21,086 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:00:21,086 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1493658158] [2024-11-14 03:00:21,086 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:00:21,086 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:00:21,097 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:00:21,223 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-14 03:00:21,224 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:00:21,224 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1493658158] [2024-11-14 03:00:21,224 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1493658158] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 03:00:21,224 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [568112023] [2024-11-14 03:00:21,224 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:00:21,224 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:00:21,224 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:00:21,227 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:00:21,228 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-14 03:00:21,289 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:00:21,290 INFO L255 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-14 03:00:21,292 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:00:21,378 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 42 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-14 03:00:21,378 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:00:21,475 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-14 03:00:21,476 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [568112023] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:00:21,476 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1752995777] [2024-11-14 03:00:21,477 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2024-11-14 03:00:21,478 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:00:21,478 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:00:21,478 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:00:21,478 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:00:22,826 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 03:00:22,831 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:00:27,114 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3046#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 03:00:27,114 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:00:27,114 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 03:00:27,114 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 5, 6] total 11 [2024-11-14 03:00:27,114 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1380948455] [2024-11-14 03:00:27,115 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 03:00:27,115 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-14 03:00:27,115 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:00:27,116 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-14 03:00:27,116 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=428, Unknown=0, NotChecked=0, Total=506 [2024-11-14 03:00:27,116 INFO L87 Difference]: Start difference. First operand 103 states and 119 transitions. Second operand has 11 states, 11 states have (on average 3.0) internal successors, (33), 11 states have internal predecessors, (33), 5 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2024-11-14 03:00:27,591 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:00:27,591 INFO L93 Difference]: Finished difference Result 157 states and 183 transitions. [2024-11-14 03:00:27,591 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-14 03:00:27,591 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 3.0) internal successors, (33), 11 states have internal predecessors, (33), 5 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) Word has length 43 [2024-11-14 03:00:27,592 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:00:27,593 INFO L225 Difference]: With dead ends: 157 [2024-11-14 03:00:27,593 INFO L226 Difference]: Without dead ends: 143 [2024-11-14 03:00:27,594 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 136 GetRequests, 112 SyntacticMatches, 1 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 136 ImplicationChecksByTransitivity, 4.6s TimeCoverageRelationStatistics Valid=89, Invalid=511, Unknown=0, NotChecked=0, Total=600 [2024-11-14 03:00:27,594 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 39 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 83 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 85 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 83 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 03:00:27,594 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 130 Invalid, 85 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 83 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 03:00:27,595 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2024-11-14 03:00:27,612 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 138. [2024-11-14 03:00:27,612 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 138 states, 88 states have (on average 1.1477272727272727) internal successors, (101), 93 states have internal predecessors, (101), 31 states have call successors, (31), 18 states have call predecessors, (31), 18 states have return successors, (28), 26 states have call predecessors, (28), 28 states have call successors, (28) [2024-11-14 03:00:27,613 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 160 transitions. [2024-11-14 03:00:27,614 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 160 transitions. Word has length 43 [2024-11-14 03:00:27,615 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:00:27,615 INFO L471 AbstractCegarLoop]: Abstraction has 138 states and 160 transitions. [2024-11-14 03:00:27,616 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 3.0) internal successors, (33), 11 states have internal predecessors, (33), 5 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2024-11-14 03:00:27,616 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 160 transitions. [2024-11-14 03:00:27,616 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-14 03:00:27,617 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:00:27,617 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:00:27,639 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-14 03:00:27,817 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-14 03:00:27,817 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:00:27,818 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:00:27,818 INFO L85 PathProgramCache]: Analyzing trace with hash -720245053, now seen corresponding path program 1 times [2024-11-14 03:00:27,818 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:00:27,818 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [916702136] [2024-11-14 03:00:27,818 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:00:27,818 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:00:27,850 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 03:00:27,852 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2136269659] [2024-11-14 03:00:27,852 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:00:27,852 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:00:27,852 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:00:27,854 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:00:27,860 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-14 03:00:27,924 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:00:27,925 INFO L255 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-11-14 03:00:27,927 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:00:28,303 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 16 proven. 26 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-14 03:00:28,303 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:00:29,514 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 22 proven. 20 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-14 03:00:29,514 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:00:29,514 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [916702136] [2024-11-14 03:00:29,515 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 03:00:29,515 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2136269659] [2024-11-14 03:00:29,515 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2136269659] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:00:29,515 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1183253052] [2024-11-14 03:00:29,516 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2024-11-14 03:00:29,517 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:00:29,517 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:00:29,517 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:00:29,517 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:00:30,649 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 03:00:30,653 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:00:41,823 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3792#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 03:00:41,823 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:00:41,823 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 03:00:41,823 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11] total 16 [2024-11-14 03:00:41,824 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1044157839] [2024-11-14 03:00:41,824 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 03:00:41,824 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-14 03:00:41,824 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:00:41,824 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-14 03:00:41,825 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=535, Unknown=4, NotChecked=0, Total=650 [2024-11-14 03:00:41,825 INFO L87 Difference]: Start difference. First operand 138 states and 160 transitions. Second operand has 16 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 12 states have internal predecessors, (29), 7 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 7 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-14 03:00:42,330 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:00:42,331 INFO L93 Difference]: Finished difference Result 167 states and 198 transitions. [2024-11-14 03:00:42,331 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-14 03:00:42,331 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 12 states have internal predecessors, (29), 7 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 7 states have call predecessors, (12), 5 states have call successors, (12) Word has length 43 [2024-11-14 03:00:42,332 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:00:42,333 INFO L225 Difference]: With dead ends: 167 [2024-11-14 03:00:42,333 INFO L226 Difference]: Without dead ends: 163 [2024-11-14 03:00:42,334 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 101 SyntacticMatches, 2 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 137 ImplicationChecksByTransitivity, 11.9s TimeCoverageRelationStatistics Valid=127, Invalid=625, Unknown=4, NotChecked=0, Total=756 [2024-11-14 03:00:42,334 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 19 mSDsluCounter, 142 mSDsCounter, 0 mSdLazyCounter, 162 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 164 SdHoareTripleChecker+Invalid, 184 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 162 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-14 03:00:42,334 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 164 Invalid, 184 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 162 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-14 03:00:42,335 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 163 states. [2024-11-14 03:00:42,366 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 163 to 152. [2024-11-14 03:00:42,367 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 152 states, 98 states have (on average 1.1428571428571428) internal successors, (112), 102 states have internal predecessors, (112), 33 states have call successors, (33), 21 states have call predecessors, (33), 20 states have return successors, (30), 28 states have call predecessors, (30), 30 states have call successors, (30) [2024-11-14 03:00:42,368 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 152 states to 152 states and 175 transitions. [2024-11-14 03:00:42,369 INFO L78 Accepts]: Start accepts. Automaton has 152 states and 175 transitions. Word has length 43 [2024-11-14 03:00:42,369 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:00:42,370 INFO L471 AbstractCegarLoop]: Abstraction has 152 states and 175 transitions. [2024-11-14 03:00:42,370 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 12 states have internal predecessors, (29), 7 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 7 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-14 03:00:42,370 INFO L276 IsEmpty]: Start isEmpty. Operand 152 states and 175 transitions. [2024-11-14 03:00:42,371 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2024-11-14 03:00:42,371 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:00:42,372 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:00:42,386 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-11-14 03:00:42,575 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2024-11-14 03:00:42,575 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:00:42,576 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:00:42,576 INFO L85 PathProgramCache]: Analyzing trace with hash -1991197863, now seen corresponding path program 1 times [2024-11-14 03:00:42,576 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:00:42,576 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1208777367] [2024-11-14 03:00:42,576 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:00:42,576 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:00:42,666 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 03:00:42,668 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [493137535] [2024-11-14 03:00:42,668 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:00:42,668 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:00:42,668 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:00:42,673 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:00:42,674 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-14 03:00:43,762 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:00:43,763 INFO L255 TraceCheckSpWp]: Trace formula consists of 145 conjuncts, 29 conjuncts are in the unsatisfiable core [2024-11-14 03:00:43,765 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:00:44,454 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 27 proven. 19 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2024-11-14 03:00:44,454 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:01:05,708 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 27 proven. 19 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2024-11-14 03:01:05,708 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:01:05,708 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1208777367] [2024-11-14 03:01:05,709 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 03:01:05,709 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [493137535] [2024-11-14 03:01:05,709 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [493137535] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:01:05,709 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [453857662] [2024-11-14 03:01:05,711 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2024-11-14 03:01:05,711 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:01:05,711 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:01:05,711 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:01:05,711 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:01:09,737 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 03:01:09,740 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:01:56,814 WARN L286 SmtUtils]: Spent 41.07s on a formula simplification. DAG size of input: 72 DAG size of output: 16 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 03:02:01,664 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4653#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 03:02:01,664 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:02:01,664 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 03:02:01,664 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11] total 16 [2024-11-14 03:02:01,665 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1589553857] [2024-11-14 03:02:01,665 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 03:02:01,665 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-14 03:02:01,665 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:02:01,666 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-14 03:02:01,666 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=79, Invalid=612, Unknown=11, NotChecked=0, Total=702 [2024-11-14 03:02:01,666 INFO L87 Difference]: Start difference. First operand 152 states and 175 transitions. Second operand has 16 states, 16 states have (on average 2.1875) internal successors, (35), 14 states have internal predecessors, (35), 9 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) [2024-11-14 03:02:08,366 WARN L286 SmtUtils]: Spent 6.66s on a formula simplification. DAG size of input: 37 DAG size of output: 16 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 03:02:10,608 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:02:12,611 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:02:17,808 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:02:28,900 WARN L286 SmtUtils]: Spent 6.78s on a formula simplification. DAG size of input: 44 DAG size of output: 31 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 03:02:30,903 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:02:33,215 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:02:35,403 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:02:37,851 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:02:42,168 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:02:44,175 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:02:46,181 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:03:08,609 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:03:12,186 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:03:12,186 INFO L93 Difference]: Finished difference Result 193 states and 220 transitions. [2024-11-14 03:03:12,186 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-14 03:03:12,187 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 2.1875) internal successors, (35), 14 states have internal predecessors, (35), 9 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) Word has length 56 [2024-11-14 03:03:12,187 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:03:12,189 INFO L225 Difference]: With dead ends: 193 [2024-11-14 03:03:12,189 INFO L226 Difference]: Without dead ends: 183 [2024-11-14 03:03:12,190 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 137 SyntacticMatches, 4 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 223 ImplicationChecksByTransitivity, 113.3s TimeCoverageRelationStatistics Valid=150, Invalid=1090, Unknown=20, NotChecked=0, Total=1260 [2024-11-14 03:03:12,190 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 21 mSDsluCounter, 201 mSDsCounter, 0 mSdLazyCounter, 217 mSolverCounterSat, 26 mSolverCounterUnsat, 11 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 28.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 228 SdHoareTripleChecker+Invalid, 254 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 217 IncrementalHoareTripleChecker+Invalid, 11 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 28.8s IncrementalHoareTripleChecker+Time [2024-11-14 03:03:12,191 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 228 Invalid, 254 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 217 Invalid, 11 Unknown, 0 Unchecked, 28.8s Time] [2024-11-14 03:03:12,191 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 183 states. [2024-11-14 03:03:12,223 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 183 to 171. [2024-11-14 03:03:12,223 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 171 states, 113 states have (on average 1.1150442477876106) internal successors, (126), 118 states have internal predecessors, (126), 32 states have call successors, (32), 25 states have call predecessors, (32), 25 states have return successors, (30), 27 states have call predecessors, (30), 30 states have call successors, (30) [2024-11-14 03:03:12,234 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 171 states to 171 states and 188 transitions. [2024-11-14 03:03:12,234 INFO L78 Accepts]: Start accepts. Automaton has 171 states and 188 transitions. Word has length 56 [2024-11-14 03:03:12,235 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:03:12,235 INFO L471 AbstractCegarLoop]: Abstraction has 171 states and 188 transitions. [2024-11-14 03:03:12,235 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 2.1875) internal successors, (35), 14 states have internal predecessors, (35), 9 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) [2024-11-14 03:03:12,235 INFO L276 IsEmpty]: Start isEmpty. Operand 171 states and 188 transitions. [2024-11-14 03:03:12,236 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2024-11-14 03:03:12,236 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:03:12,236 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:03:12,245 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-14 03:03:12,436 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-14 03:03:12,436 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:03:12,437 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:03:12,437 INFO L85 PathProgramCache]: Analyzing trace with hash -1874668700, now seen corresponding path program 2 times [2024-11-14 03:03:12,437 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:03:12,437 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [448402996] [2024-11-14 03:03:12,437 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:03:12,437 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:03:12,510 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 03:03:12,512 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [985680143] [2024-11-14 03:03:12,512 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 03:03:12,512 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:03:12,512 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:03:12,514 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:03:12,520 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-14 03:03:12,705 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-14 03:03:12,705 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 03:03:12,706 INFO L255 TraceCheckSpWp]: Trace formula consists of 103 conjuncts, 31 conjuncts are in the unsatisfiable core [2024-11-14 03:03:12,708 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:03:13,684 INFO L134 CoverageAnalysis]: Checked inductivity of 172 backedges. 41 proven. 11 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2024-11-14 03:03:13,684 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:03:17,816 INFO L134 CoverageAnalysis]: Checked inductivity of 172 backedges. 41 proven. 11 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2024-11-14 03:03:17,816 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:03:17,817 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [448402996] [2024-11-14 03:03:17,817 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 03:03:17,817 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [985680143] [2024-11-14 03:03:17,817 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [985680143] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:03:17,817 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [923148057] [2024-11-14 03:03:17,818 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2024-11-14 03:03:17,819 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:03:17,819 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:03:17,819 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:03:17,819 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:03:19,647 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 03:03:19,656 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:04:04,454 WARN L286 SmtUtils]: Spent 29.75s on a formula simplification. DAG size of input: 72 DAG size of output: 66 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 03:04:08,195 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5626#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 03:04:08,195 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:04:08,195 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 03:04:08,195 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 16 [2024-11-14 03:04:08,196 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [960431737] [2024-11-14 03:04:08,196 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 03:04:08,196 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-14 03:04:08,196 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:04:08,197 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-14 03:04:08,197 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=613, Unknown=4, NotChecked=0, Total=702 [2024-11-14 03:04:08,197 INFO L87 Difference]: Start difference. First operand 171 states and 188 transitions. Second operand has 16 states, 14 states have (on average 2.642857142857143) internal successors, (37), 13 states have internal predecessors, (37), 8 states have call successors, (20), 3 states have call predecessors, (20), 2 states have return successors, (18), 6 states have call predecessors, (18), 6 states have call successors, (18) [2024-11-14 03:05:24,870 WARN L286 SmtUtils]: Spent 55.66s on a formula simplification that was a NOOP. DAG size: 54 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 03:05:26,884 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:05:29,563 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:05:31,573 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:05:33,579 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:05:35,582 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:05:37,863 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:05:39,879 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:05:41,883 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:05:43,895 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:05:46,177 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:05:48,182 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:06:37,476 WARN L286 SmtUtils]: Spent 38.54s on a formula simplification that was a NOOP. DAG size: 41 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 03:06:39,482 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:06:41,492 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:06:43,495 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:06:46,136 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:07:01,102 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:07:03,271 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:07:05,650 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:07:07,658 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:07:09,664 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:07:11,672 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:07:13,678 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:07:15,684 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:07:17,736 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:07:19,792 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:07:21,859 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:07:23,878 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:07:23,878 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:07:23,878 INFO L93 Difference]: Finished difference Result 224 states and 261 transitions. [2024-11-14 03:07:23,879 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-14 03:07:23,879 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 2.642857142857143) internal successors, (37), 13 states have internal predecessors, (37), 8 states have call successors, (20), 3 states have call predecessors, (20), 2 states have return successors, (18), 6 states have call predecessors, (18), 6 states have call successors, (18) Word has length 61 [2024-11-14 03:07:23,880 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:07:23,881 INFO L225 Difference]: With dead ends: 224 [2024-11-14 03:07:23,881 INFO L226 Difference]: Without dead ends: 204 [2024-11-14 03:07:23,882 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 186 GetRequests, 154 SyntacticMatches, 2 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 160 ImplicationChecksByTransitivity, 187.1s TimeCoverageRelationStatistics Valid=132, Invalid=842, Unknown=18, NotChecked=0, Total=992 [2024-11-14 03:07:23,882 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 24 mSDsluCounter, 191 mSDsCounter, 0 mSdLazyCounter, 189 mSolverCounterSat, 53 mSolverCounterUnsat, 27 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 58.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 220 SdHoareTripleChecker+Invalid, 269 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 189 IncrementalHoareTripleChecker+Invalid, 27 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 58.3s IncrementalHoareTripleChecker+Time [2024-11-14 03:07:23,883 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 220 Invalid, 269 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 189 Invalid, 27 Unknown, 0 Unchecked, 58.3s Time] [2024-11-14 03:07:23,883 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 204 states. [2024-11-14 03:07:23,921 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 204 to 193. [2024-11-14 03:07:23,921 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 193 states, 127 states have (on average 1.125984251968504) internal successors, (143), 133 states have internal predecessors, (143), 37 states have call successors, (37), 28 states have call predecessors, (37), 28 states have return successors, (35), 31 states have call predecessors, (35), 35 states have call successors, (35) [2024-11-14 03:07:23,922 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 193 states to 193 states and 215 transitions. [2024-11-14 03:07:23,922 INFO L78 Accepts]: Start accepts. Automaton has 193 states and 215 transitions. Word has length 61 [2024-11-14 03:07:23,923 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:07:23,923 INFO L471 AbstractCegarLoop]: Abstraction has 193 states and 215 transitions. [2024-11-14 03:07:23,923 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 2.642857142857143) internal successors, (37), 13 states have internal predecessors, (37), 8 states have call successors, (20), 3 states have call predecessors, (20), 2 states have return successors, (18), 6 states have call predecessors, (18), 6 states have call successors, (18) [2024-11-14 03:07:23,923 INFO L276 IsEmpty]: Start isEmpty. Operand 193 states and 215 transitions. [2024-11-14 03:07:23,924 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2024-11-14 03:07:23,924 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:07:23,924 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:07:23,929 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-11-14 03:07:24,125 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-11-14 03:07:24,125 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:07:24,125 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:07:24,125 INFO L85 PathProgramCache]: Analyzing trace with hash -563738357, now seen corresponding path program 1 times [2024-11-14 03:07:24,125 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:07:24,125 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [745380914] [2024-11-14 03:07:24,125 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:07:24,125 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:07:24,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 03:07:24,160 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1244786659] [2024-11-14 03:07:24,160 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:07:24,161 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:07:24,161 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:07:24,163 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:07:24,166 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-14 03:07:24,379 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:07:24,381 INFO L255 TraceCheckSpWp]: Trace formula consists of 165 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-14 03:07:24,386 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:07:27,739 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 39 proven. 40 refuted. 0 times theorem prover too weak. 132 trivial. 0 not checked. [2024-11-14 03:07:27,739 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:07:50,320 WARN L286 SmtUtils]: Spent 6.46s on a formula simplification that was a NOOP. DAG size: 28 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 03:08:09,093 WARN L286 SmtUtils]: Spent 7.01s on a formula simplification that was a NOOP. DAG size: 10 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-14 03:08:25,691 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 39 proven. 40 refuted. 0 times theorem prover too weak. 132 trivial. 0 not checked. [2024-11-14 03:08:25,691 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:08:25,691 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [745380914] [2024-11-14 03:08:25,691 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 03:08:25,691 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1244786659] [2024-11-14 03:08:25,692 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1244786659] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:08:25,692 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1741675337] [2024-11-14 03:08:25,693 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2024-11-14 03:08:25,693 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:08:25,693 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:08:25,694 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:08:25,694 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:08:31,104 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 03:08:31,109 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:08:57,407 WARN L286 SmtUtils]: Spent 10.33s on a formula simplification. DAG size of input: 59 DAG size of output: 59 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 03:09:13,711 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '6717#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 03:09:13,711 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:09:13,711 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 03:09:13,711 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13] total 20 [2024-11-14 03:09:13,711 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1438757428] [2024-11-14 03:09:13,711 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 03:09:13,712 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-14 03:09:13,712 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:09:13,712 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-14 03:09:13,713 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=130, Invalid=728, Unknown=12, NotChecked=0, Total=870 [2024-11-14 03:09:13,713 INFO L87 Difference]: Start difference. First operand 193 states and 215 transitions. Second operand has 20 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 16 states have internal predecessors, (37), 12 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (20), 9 states have call predecessors, (20), 10 states have call successors, (20) [2024-11-14 03:09:15,823 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:09:42,270 WARN L286 SmtUtils]: Spent 19.66s on a formula simplification that was a NOOP. DAG size: 47 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 03:09:43,338 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.02s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:09:45,404 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:09:46,845 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.42s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:09:48,305 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.45s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:09:55,090 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:09:59,194 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.25s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:10:02,018 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:10:04,020 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:10:12,812 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:10:15,201 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:10:22,260 WARN L286 SmtUtils]: Spent 6.72s on a formula simplification that was a NOOP. DAG size: 50 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 03:10:24,267 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:10:33,121 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:10:35,139 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:10:37,147 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:10:39,203 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:10:41,212 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:10:43,406 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:10:45,417 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:10:47,424 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:10:59,127 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:11:01,141 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 03:11:01,147 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:11:01,147 INFO L93 Difference]: Finished difference Result 225 states and 257 transitions. [2024-11-14 03:11:01,147 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-14 03:11:01,148 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 16 states have internal predecessors, (37), 12 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (20), 9 states have call predecessors, (20), 10 states have call successors, (20) Word has length 67 [2024-11-14 03:11:01,148 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:11:01,149 INFO L225 Difference]: With dead ends: 225 [2024-11-14 03:11:01,149 INFO L226 Difference]: Without dead ends: 221 [2024-11-14 03:11:01,150 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 212 GetRequests, 167 SyntacticMatches, 4 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 394 ImplicationChecksByTransitivity, 118.3s TimeCoverageRelationStatistics Valid=317, Invalid=1467, Unknown=22, NotChecked=0, Total=1806 [2024-11-14 03:11:01,151 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 69 mSDsluCounter, 198 mSDsCounter, 0 mSdLazyCounter, 239 mSolverCounterSat, 113 mSolverCounterUnsat, 18 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 47.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 71 SdHoareTripleChecker+Valid, 227 SdHoareTripleChecker+Invalid, 370 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 113 IncrementalHoareTripleChecker+Valid, 239 IncrementalHoareTripleChecker+Invalid, 18 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 47.7s IncrementalHoareTripleChecker+Time [2024-11-14 03:11:01,151 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [71 Valid, 227 Invalid, 370 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [113 Valid, 239 Invalid, 18 Unknown, 0 Unchecked, 47.7s Time] [2024-11-14 03:11:01,153 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 221 states. [2024-11-14 03:11:01,205 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 221 to 199. [2024-11-14 03:11:01,206 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 199 states, 131 states have (on average 1.1374045801526718) internal successors, (149), 136 states have internal predecessors, (149), 40 states have call successors, (40), 28 states have call predecessors, (40), 27 states have return successors, (38), 34 states have call predecessors, (38), 38 states have call successors, (38) [2024-11-14 03:11:01,207 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 199 states to 199 states and 227 transitions. [2024-11-14 03:11:01,207 INFO L78 Accepts]: Start accepts. Automaton has 199 states and 227 transitions. Word has length 67 [2024-11-14 03:11:01,208 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:11:01,208 INFO L471 AbstractCegarLoop]: Abstraction has 199 states and 227 transitions. [2024-11-14 03:11:01,208 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 16 states have internal predecessors, (37), 12 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (20), 9 states have call predecessors, (20), 10 states have call successors, (20) [2024-11-14 03:11:01,208 INFO L276 IsEmpty]: Start isEmpty. Operand 199 states and 227 transitions. [2024-11-14 03:11:01,209 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2024-11-14 03:11:01,209 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:11:01,209 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:11:01,216 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-14 03:11:01,413 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:11:01,414 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:11:01,414 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:11:01,414 INFO L85 PathProgramCache]: Analyzing trace with hash -1251052430, now seen corresponding path program 1 times [2024-11-14 03:11:01,414 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:11:01,414 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [745689441] [2024-11-14 03:11:01,414 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:11:01,414 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:11:01,445 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:11:03,323 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-14 03:11:03,323 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:11:03,323 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [745689441] [2024-11-14 03:11:03,323 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [745689441] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 03:11:03,323 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1903762278] [2024-11-14 03:11:03,323 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:11:03,324 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:11:03,324 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:11:03,325 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:11:03,327 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-14 03:11:03,427 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:11:03,428 INFO L255 TraceCheckSpWp]: Trace formula consists of 174 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-14 03:11:03,430 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:11:28,104 WARN L286 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 26 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-14 03:11:43,404 WARN L286 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 26 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-14 03:12:04,311 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 26 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-14 03:12:30,245 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 26 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-14 03:12:46,722 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 27 proven. 36 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2024-11-14 03:12:46,722 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:12:56,645 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 27 proven. 36 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2024-11-14 03:12:56,645 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1903762278] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:12:56,645 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1497405893] [2024-11-14 03:12:56,647 INFO L159 IcfgInterpreter]: Started Sifa with 20 locations of interest [2024-11-14 03:12:56,647 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:12:56,648 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:12:56,648 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:12:56,648 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:13:01,064 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 03:13:01,070 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:13:57,364 WARN L286 SmtUtils]: Spent 50.80s on a formula simplification. DAG size of input: 72 DAG size of output: 66 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 03:14:36,138 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '7863#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 03:14:36,138 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:14:36,138 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 03:14:36,138 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 11, 11] total 20 [2024-11-14 03:14:36,138 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [849715573] [2024-11-14 03:14:36,138 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 03:14:36,139 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-14 03:14:36,139 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:14:36,139 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-14 03:14:36,140 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=104, Invalid=937, Unknown=15, NotChecked=0, Total=1056 [2024-11-14 03:14:36,140 INFO L87 Difference]: Start difference. First operand 199 states and 227 transitions. Second operand has 20 states, 20 states have (on average 2.5) internal successors, (50), 18 states have internal predecessors, (50), 11 states have call successors, (34), 3 states have call predecessors, (34), 2 states have return successors, (31), 12 states have call predecessors, (31), 11 states have call successors, (31) [2024-11-14 03:14:40,209 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.12s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-11-14 03:14:41,411 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.18s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [0] [2024-11-14 03:14:44,299 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [0] [2024-11-14 03:14:47,350 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.13s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [0] [2024-11-14 03:14:48,123 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:14:48,123 INFO L93 Difference]: Finished difference Result 205 states and 233 transitions. [2024-11-14 03:14:48,124 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-14 03:14:48,124 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 2.5) internal successors, (50), 18 states have internal predecessors, (50), 11 states have call successors, (34), 3 states have call predecessors, (34), 2 states have return successors, (31), 12 states have call predecessors, (31), 11 states have call successors, (31) Word has length 72 [2024-11-14 03:14:48,124 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:14:48,125 INFO L225 Difference]: With dead ends: 205 [2024-11-14 03:14:48,125 INFO L226 Difference]: Without dead ends: 173 [2024-11-14 03:14:48,126 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 226 GetRequests, 186 SyntacticMatches, 7 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 277 ImplicationChecksByTransitivity, 105.4s TimeCoverageRelationStatistics Valid=119, Invalid=1056, Unknown=15, NotChecked=0, Total=1190 [2024-11-14 03:14:48,126 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 7 mSDsluCounter, 179 mSDsCounter, 0 mSdLazyCounter, 195 mSolverCounterSat, 4 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 11.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 206 SdHoareTripleChecker+Invalid, 200 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 195 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 11.3s IncrementalHoareTripleChecker+Time [2024-11-14 03:14:48,127 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 206 Invalid, 200 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 195 Invalid, 1 Unknown, 0 Unchecked, 11.3s Time] [2024-11-14 03:14:48,127 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 173 states. [2024-11-14 03:14:48,207 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 173 to 173. [2024-11-14 03:14:48,208 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 173 states, 113 states have (on average 1.1504424778761062) internal successors, (130), 118 states have internal predecessors, (130), 36 states have call successors, (36), 24 states have call predecessors, (36), 23 states have return successors, (34), 30 states have call predecessors, (34), 34 states have call successors, (34) [2024-11-14 03:14:48,209 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 173 states to 173 states and 200 transitions. [2024-11-14 03:14:48,210 INFO L78 Accepts]: Start accepts. Automaton has 173 states and 200 transitions. Word has length 72 [2024-11-14 03:14:48,210 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:14:48,210 INFO L471 AbstractCegarLoop]: Abstraction has 173 states and 200 transitions. [2024-11-14 03:14:48,210 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 2.5) internal successors, (50), 18 states have internal predecessors, (50), 11 states have call successors, (34), 3 states have call predecessors, (34), 2 states have return successors, (31), 12 states have call predecessors, (31), 11 states have call successors, (31) [2024-11-14 03:14:48,210 INFO L276 IsEmpty]: Start isEmpty. Operand 173 states and 200 transitions. [2024-11-14 03:14:48,211 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2024-11-14 03:14:48,211 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:14:48,212 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:14:48,231 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-14 03:14:48,412 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:14:48,412 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:14:48,412 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:14:48,413 INFO L85 PathProgramCache]: Analyzing trace with hash -1062978449, now seen corresponding path program 3 times [2024-11-14 03:14:48,413 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:14:48,413 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1842224548] [2024-11-14 03:14:48,413 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:14:48,413 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:14:48,499 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 03:14:48,501 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [816752877] [2024-11-14 03:14:48,501 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-14 03:14:48,502 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:14:48,502 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:14:48,504 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:14:48,509 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_61324fb2-7a1e-4fed-927a-9a219d06b91c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process