./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/cohendiv-ll_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_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/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_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/cohendiv-ll_unwindbound5.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/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_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/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 011044826c7a01c153d09406112c335d599fb158d7a4b72e6a624d5427477c0d --- Real Ultimate output --- This is Ultimate 0.3.0-dev-826ab2b [2024-11-14 05:00:59,712 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-14 05:00:59,812 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-32bit-Taipan_Default.epf [2024-11-14 05:00:59,816 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-14 05:00:59,821 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-14 05:00:59,856 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-14 05:00:59,857 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-14 05:00:59,857 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-14 05:00:59,857 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-14 05:00:59,857 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-14 05:00:59,858 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-14 05:00:59,858 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-14 05:00:59,858 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-14 05:00:59,858 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-14 05:00:59,858 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-14 05:00:59,858 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-14 05:00:59,858 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-14 05:00:59,858 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-14 05:00:59,861 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-14 05:00:59,861 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-14 05:00:59,861 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-14 05:00:59,861 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-14 05:00:59,862 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-14 05:00:59,862 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-14 05:00:59,862 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-14 05:00:59,862 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-14 05:00:59,862 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-14 05:00:59,862 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-14 05:00:59,862 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-14 05:00:59,862 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-14 05:00:59,863 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-14 05:00:59,863 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-14 05:00:59,863 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-14 05:00:59,863 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-14 05:00:59,863 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-14 05:00:59,863 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-14 05:00:59,863 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-14 05:00:59,863 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-14 05:00:59,863 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 05:00:59,863 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-14 05:00:59,864 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-14 05:00:59,864 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-14 05:00:59,864 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-14 05:00:59,864 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-14 05:00:59,864 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-14 05:00:59,864 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-14 05:00:59,864 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-14 05:00:59,864 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_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/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 -> 011044826c7a01c153d09406112c335d599fb158d7a4b72e6a624d5427477c0d [2024-11-14 05:01:00,236 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-14 05:01:00,247 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-14 05:01:00,250 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-14 05:01:00,251 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-14 05:01:00,251 INFO L274 PluginConnector]: CDTParser initialized [2024-11-14 05:01:00,253 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/../../sv-benchmarks/c/nla-digbench-scaling/cohendiv-ll_unwindbound5.c Unable to find full path for "g++" [2024-11-14 05:01:02,105 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-14 05:01:02,375 INFO L384 CDTParser]: Found 1 translation units. [2024-11-14 05:01:02,378 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/sv-benchmarks/c/nla-digbench-scaling/cohendiv-ll_unwindbound5.c [2024-11-14 05:01:02,389 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/data/0e70c4a81/fcee9deae8fd425d9be78cb813bf7e2e/FLAGc7f6b6474 [2024-11-14 05:01:02,670 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/data/0e70c4a81/fcee9deae8fd425d9be78cb813bf7e2e [2024-11-14 05:01:02,675 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-14 05:01:02,677 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-14 05:01:02,679 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-14 05:01:02,680 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-14 05:01:02,685 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-14 05:01:02,686 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 05:01:02" (1/1) ... [2024-11-14 05:01:02,689 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@505cd523 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:01:02, skipping insertion in model container [2024-11-14 05:01:02,689 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 05:01:02" (1/1) ... [2024-11-14 05:01:02,706 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-14 05:01:02,865 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_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/sv-benchmarks/c/nla-digbench-scaling/cohendiv-ll_unwindbound5.c[576,589] [2024-11-14 05:01:02,884 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 05:01:02,894 INFO L200 MainTranslator]: Completed pre-run [2024-11-14 05:01:02,905 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_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/sv-benchmarks/c/nla-digbench-scaling/cohendiv-ll_unwindbound5.c[576,589] [2024-11-14 05:01:02,916 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 05:01:02,927 INFO L204 MainTranslator]: Completed translation [2024-11-14 05:01:02,928 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:01:02 WrapperNode [2024-11-14 05:01:02,928 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-14 05:01:02,929 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-14 05:01:02,929 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-14 05:01:02,929 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-14 05:01:02,934 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:01:02" (1/1) ... [2024-11-14 05:01:02,939 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:01:02" (1/1) ... [2024-11-14 05:01:02,955 INFO L138 Inliner]: procedures = 14, calls = 15, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 65 [2024-11-14 05:01:02,956 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-14 05:01:02,956 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-14 05:01:02,956 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-14 05:01:02,956 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-14 05:01:02,962 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:01:02" (1/1) ... [2024-11-14 05:01:02,963 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:01:02" (1/1) ... [2024-11-14 05:01:02,964 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:01:02" (1/1) ... [2024-11-14 05:01:02,964 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:01:02" (1/1) ... [2024-11-14 05:01:02,967 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:01:02" (1/1) ... [2024-11-14 05:01:02,971 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:01:02" (1/1) ... [2024-11-14 05:01:02,972 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:01:02" (1/1) ... [2024-11-14 05:01:02,972 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:01:02" (1/1) ... [2024-11-14 05:01:02,974 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-14 05:01:02,975 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-14 05:01:02,975 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-14 05:01:02,975 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-14 05:01:02,976 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:01:02" (1/1) ... [2024-11-14 05:01:02,982 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 05:01:02,995 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:01:03,008 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-14 05:01:03,011 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-14 05:01:03,038 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-14 05:01:03,038 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-14 05:01:03,039 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-14 05:01:03,039 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-14 05:01:03,039 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-14 05:01:03,039 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-14 05:01:03,111 INFO L238 CfgBuilder]: Building ICFG [2024-11-14 05:01:03,113 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-14 05:01:03,319 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-14 05:01:03,319 INFO L287 CfgBuilder]: Performing block encoding [2024-11-14 05:01:03,387 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-14 05:01:03,388 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-14 05:01:03,389 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 05:01:03 BoogieIcfgContainer [2024-11-14 05:01:03,389 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-14 05:01:03,392 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-14 05:01:03,392 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-14 05:01:03,397 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-14 05:01:03,398 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.11 05:01:02" (1/3) ... [2024-11-14 05:01:03,399 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5fb3ec77 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 05:01:03, skipping insertion in model container [2024-11-14 05:01:03,400 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 05:01:02" (2/3) ... [2024-11-14 05:01:03,400 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5fb3ec77 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 05:01:03, skipping insertion in model container [2024-11-14 05:01:03,400 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 05:01:03" (3/3) ... [2024-11-14 05:01:03,402 INFO L112 eAbstractionObserver]: Analyzing ICFG cohendiv-ll_unwindbound5.c [2024-11-14 05:01:03,423 INFO L217 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-14 05:01:03,425 INFO L154 ceAbstractionStarter]: Applying trace abstraction to ICFG cohendiv-ll_unwindbound5.c that has 2 procedures, 24 locations, 1 initial locations, 2 loop locations, and 1 error locations. [2024-11-14 05:01:03,493 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-14 05:01:03,506 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;@741bde42, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-14 05:01:03,507 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-14 05:01:03,511 INFO L276 IsEmpty]: Start isEmpty. Operand has 24 states, 14 states have (on average 1.5714285714285714) internal successors, (22), 15 states have internal predecessors, (22), 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 05:01:03,517 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2024-11-14 05:01:03,518 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:01:03,518 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2024-11-14 05:01:03,519 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:01:03,523 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:01:03,524 INFO L85 PathProgramCache]: Analyzing trace with hash -868111449, now seen corresponding path program 1 times [2024-11-14 05:01:03,532 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:01:03,532 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1356053086] [2024-11-14 05:01:03,532 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:01:03,533 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:01:03,610 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:01:03,654 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 05:01:03,654 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:01:03,655 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1356053086] [2024-11-14 05:01:03,655 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1356053086] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 05:01:03,655 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 05:01:03,656 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-14 05:01:03,657 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1790573996] [2024-11-14 05:01:03,657 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 05:01:03,661 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-14 05:01:03,661 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:01:03,680 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-14 05:01:03,680 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-14 05:01:03,682 INFO L87 Difference]: Start difference. First operand has 24 states, 14 states have (on average 1.5714285714285714) internal successors, (22), 15 states have internal predecessors, (22), 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 2.5) internal successors, (5), 2 states have internal predecessors, (5), 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 05:01:03,707 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:01:03,707 INFO L93 Difference]: Finished difference Result 47 states and 78 transitions. [2024-11-14 05:01:03,709 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-14 05:01:03,710 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 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 6 [2024-11-14 05:01:03,711 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:01:03,716 INFO L225 Difference]: With dead ends: 47 [2024-11-14 05:01:03,717 INFO L226 Difference]: Without dead ends: 22 [2024-11-14 05:01:03,720 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 05:01:03,723 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 31 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 05:01:03,724 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 31 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 05:01:03,738 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2024-11-14 05:01:03,751 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2024-11-14 05:01:03,752 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 13 states have (on average 1.3846153846153846) internal successors, (18), 14 states have internal predecessors, (18), 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 05:01:03,756 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 31 transitions. [2024-11-14 05:01:03,758 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 31 transitions. Word has length 6 [2024-11-14 05:01:03,758 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:01:03,759 INFO L471 AbstractCegarLoop]: Abstraction has 22 states and 31 transitions. [2024-11-14 05:01:03,759 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 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 05:01:03,759 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 31 transitions. [2024-11-14 05:01:03,760 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-14 05:01:03,760 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:01:03,760 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-14 05:01:03,761 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-14 05:01:03,761 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:01:03,761 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:01:03,762 INFO L85 PathProgramCache]: Analyzing trace with hash 2035614532, now seen corresponding path program 1 times [2024-11-14 05:01:03,762 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:01:03,762 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1690604261] [2024-11-14 05:01:03,762 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:01:03,762 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:01:03,779 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:01:03,867 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 05:01:03,867 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:01:03,867 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1690604261] [2024-11-14 05:01:03,867 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1690604261] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 05:01:03,867 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 05:01:03,868 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-14 05:01:03,868 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [316317308] [2024-11-14 05:01:03,868 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 05:01:03,869 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-14 05:01:03,869 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:01:03,869 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-14 05:01:03,869 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 05:01:03,870 INFO L87 Difference]: Start difference. First operand 22 states and 31 transitions. Second operand has 4 states, 4 states have (on average 1.5) 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 05:01:03,893 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:01:03,893 INFO L93 Difference]: Finished difference Result 31 states and 40 transitions. [2024-11-14 05:01:03,894 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-14 05:01:03,894 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 1.5) 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 05:01:03,894 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:01:03,895 INFO L225 Difference]: With dead ends: 31 [2024-11-14 05:01:03,895 INFO L226 Difference]: Without dead ends: 24 [2024-11-14 05:01:03,896 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 05:01:03,896 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 0 mSDsluCounter, 54 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 05:01:03,897 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 82 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 05:01:03,898 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2024-11-14 05:01:03,902 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-14 05:01:03,902 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 15 states have (on average 1.3333333333333333) internal successors, (20), 16 states have internal predecessors, (20), 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 05:01:03,904 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 33 transitions. [2024-11-14 05:01:03,904 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 33 transitions. Word has length 7 [2024-11-14 05:01:03,904 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:01:03,904 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 33 transitions. [2024-11-14 05:01:03,904 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 1.5) 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 05:01:03,905 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 33 transitions. [2024-11-14 05:01:03,905 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-14 05:01:03,905 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:01:03,905 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-14 05:01:03,905 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-14 05:01:03,906 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:01:03,906 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:01:03,906 INFO L85 PathProgramCache]: Analyzing trace with hash 2037104082, now seen corresponding path program 1 times [2024-11-14 05:01:03,907 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:01:03,907 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [743585463] [2024-11-14 05:01:03,907 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:01:03,907 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:01:03,922 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 05:01:03,924 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [879792389] [2024-11-14 05:01:03,924 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:01:03,924 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:01:03,924 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:01:03,927 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:01:03,929 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-14 05:01:03,994 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:01:03,996 INFO L255 TraceCheckSpWp]: Trace formula consists of 50 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-14 05:01:04,002 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:01:04,137 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 05:01:04,137 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 05:01:04,137 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:01:04,137 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [743585463] [2024-11-14 05:01:04,138 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 05:01:04,138 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [879792389] [2024-11-14 05:01:04,138 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [879792389] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 05:01:04,138 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 05:01:04,138 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-14 05:01:04,139 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2105936539] [2024-11-14 05:01:04,139 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 05:01:04,139 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 05:01:04,139 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:01:04,140 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 05:01:04,140 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-14 05:01:04,140 INFO L87 Difference]: Start difference. First operand 24 states and 33 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 05:01:04,205 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:01:04,206 INFO L93 Difference]: Finished difference Result 34 states and 45 transitions. [2024-11-14 05:01:04,206 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 05:01:04,206 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 05:01:04,207 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:01:04,207 INFO L225 Difference]: With dead ends: 34 [2024-11-14 05:01:04,208 INFO L226 Difference]: Without dead ends: 32 [2024-11-14 05:01:04,208 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-14 05:01:04,209 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 4 mSDsluCounter, 70 mSDsCounter, 0 mSdLazyCounter, 26 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 97 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 26 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 05:01:04,210 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 97 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 26 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 05:01:04,210 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2024-11-14 05:01:04,216 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 29. [2024-11-14 05:01:04,217 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 18 states have (on average 1.2777777777777777) internal successors, (23), 20 states have internal predecessors, (23), 8 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-14 05:01:04,218 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 38 transitions. [2024-11-14 05:01:04,218 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 38 transitions. Word has length 7 [2024-11-14 05:01:04,219 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:01:04,219 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 38 transitions. [2024-11-14 05:01:04,219 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 05:01:04,219 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 38 transitions. [2024-11-14 05:01:04,219 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2024-11-14 05:01:04,220 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:01:04,220 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 05:01:04,237 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-14 05:01:04,420 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:01:04,421 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:01:04,421 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:01:04,421 INFO L85 PathProgramCache]: Analyzing trace with hash -1330610680, now seen corresponding path program 1 times [2024-11-14 05:01:04,421 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:01:04,421 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1600532314] [2024-11-14 05:01:04,421 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:01:04,422 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:01:04,454 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 05:01:04,459 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [136095141] [2024-11-14 05:01:04,463 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:01:04,463 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:01:04,463 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:01:04,465 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:01:04,468 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-14 05:01:04,543 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:01:04,544 INFO L255 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-14 05:01:04,546 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:01:04,620 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 05:01:04,622 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 05:01:04,622 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:01:04,622 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1600532314] [2024-11-14 05:01:04,622 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 05:01:04,622 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [136095141] [2024-11-14 05:01:04,622 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [136095141] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 05:01:04,623 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 05:01:04,623 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-14 05:01:04,623 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1766584486] [2024-11-14 05:01:04,625 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 05:01:04,626 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 05:01:04,626 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:01:04,627 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 05:01:04,627 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-14 05:01:04,627 INFO L87 Difference]: Start difference. First operand 29 states and 38 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 05:01:04,718 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:01:04,718 INFO L93 Difference]: Finished difference Result 47 states and 63 transitions. [2024-11-14 05:01:04,718 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 05:01:04,719 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 05:01:04,719 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:01:04,722 INFO L225 Difference]: With dead ends: 47 [2024-11-14 05:01:04,722 INFO L226 Difference]: Without dead ends: 44 [2024-11-14 05:01:04,722 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 8 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 05:01:04,723 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 11 mSDsluCounter, 62 mSDsCounter, 0 mSdLazyCounter, 45 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 86 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 45 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 05:01:04,723 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 86 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 05:01:04,724 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2024-11-14 05:01:04,732 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 43. [2024-11-14 05:01:04,733 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 27 states have internal predecessors, (33), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-14 05:01:04,734 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 58 transitions. [2024-11-14 05:01:04,734 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 58 transitions. Word has length 12 [2024-11-14 05:01:04,735 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:01:04,735 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 58 transitions. [2024-11-14 05:01:04,735 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 05:01:04,735 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 58 transitions. [2024-11-14 05:01:04,736 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2024-11-14 05:01:04,736 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:01:04,736 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 05:01:04,754 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-14 05:01:04,940 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:01:04,940 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:01:04,940 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:01:04,940 INFO L85 PathProgramCache]: Analyzing trace with hash 698864434, now seen corresponding path program 1 times [2024-11-14 05:01:04,940 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:01:04,941 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2041867049] [2024-11-14 05:01:04,941 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:01:04,941 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:01:04,960 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 05:01:04,962 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1930138833] [2024-11-14 05:01:04,962 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:01:04,962 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:01:04,962 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:01:04,964 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:01:04,968 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-14 05:01:05,034 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:01:05,035 INFO L255 TraceCheckSpWp]: Trace formula consists of 78 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-14 05:01:05,037 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:01:05,112 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 05:01:05,113 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 05:01:05,113 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:01:05,113 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2041867049] [2024-11-14 05:01:05,113 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 05:01:05,113 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1930138833] [2024-11-14 05:01:05,113 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1930138833] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 05:01:05,113 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 05:01:05,114 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-14 05:01:05,114 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [875411898] [2024-11-14 05:01:05,114 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 05:01:05,114 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 05:01:05,115 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:01:05,115 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 05:01:05,117 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-14 05:01:05,117 INFO L87 Difference]: Start difference. First operand 43 states and 58 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (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 05:01:05,221 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:01:05,223 INFO L93 Difference]: Finished difference Result 72 states and 102 transitions. [2024-11-14 05:01:05,225 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 05:01:05,225 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (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 20 [2024-11-14 05:01:05,225 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:01:05,227 INFO L225 Difference]: With dead ends: 72 [2024-11-14 05:01:05,227 INFO L226 Difference]: Without dead ends: 70 [2024-11-14 05:01:05,227 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 16 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 05:01:05,230 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 11 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 51 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 05:01:05,231 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 103 Invalid, 51 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 05:01:05,231 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2024-11-14 05:01:05,251 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 63. [2024-11-14 05:01:05,252 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 38 states have (on average 1.3157894736842106) internal successors, (50), 40 states have internal predecessors, (50), 20 states have call successors, (20), 4 states have call predecessors, (20), 4 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2024-11-14 05:01:05,256 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 89 transitions. [2024-11-14 05:01:05,256 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 89 transitions. Word has length 20 [2024-11-14 05:01:05,257 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:01:05,257 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 89 transitions. [2024-11-14 05:01:05,260 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (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 05:01:05,260 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 89 transitions. [2024-11-14 05:01:05,261 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2024-11-14 05:01:05,261 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:01:05,261 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 05:01:05,279 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-14 05:01:05,461 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:01:05,462 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:01:05,462 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:01:05,462 INFO L85 PathProgramCache]: Analyzing trace with hash 1848239713, now seen corresponding path program 1 times [2024-11-14 05:01:05,462 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:01:05,462 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1877877531] [2024-11-14 05:01:05,462 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:01:05,462 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:01:05,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:01:05,649 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-14 05:01:05,649 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:01:05,649 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1877877531] [2024-11-14 05:01:05,649 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1877877531] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 05:01:05,649 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 05:01:05,650 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-14 05:01:05,650 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [533926513] [2024-11-14 05:01:05,650 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 05:01:05,650 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-14 05:01:05,650 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:01:05,651 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-14 05:01:05,651 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-14 05:01:05,651 INFO L87 Difference]: Start difference. First operand 63 states and 89 transitions. Second operand has 6 states, 6 states have (on average 2.5) internal successors, (15), 6 states have internal predecessors, (15), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-14 05:01:05,704 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:01:05,705 INFO L93 Difference]: Finished difference Result 102 states and 142 transitions. [2024-11-14 05:01:05,705 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-14 05:01:05,705 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 6 states have internal predecessors, (15), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 23 [2024-11-14 05:01:05,705 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:01:05,707 INFO L225 Difference]: With dead ends: 102 [2024-11-14 05:01:05,708 INFO L226 Difference]: Without dead ends: 67 [2024-11-14 05:01:05,708 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 05:01:05,709 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 5 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 05:01:05,709 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 121 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 05:01:05,710 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2024-11-14 05:01:05,721 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 67. [2024-11-14 05:01:05,723 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 41 states have (on average 1.2682926829268293) internal successors, (52), 43 states have internal predecessors, (52), 20 states have call successors, (20), 5 states have call predecessors, (20), 5 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2024-11-14 05:01:05,724 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 91 transitions. [2024-11-14 05:01:05,724 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 91 transitions. Word has length 23 [2024-11-14 05:01:05,724 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:01:05,725 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 91 transitions. [2024-11-14 05:01:05,725 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 6 states have internal predecessors, (15), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-14 05:01:05,725 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 91 transitions. [2024-11-14 05:01:05,728 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2024-11-14 05:01:05,728 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:01:05,728 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 05:01:05,728 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-14 05:01:05,728 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:01:05,729 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:01:05,729 INFO L85 PathProgramCache]: Analyzing trace with hash -1295969102, now seen corresponding path program 1 times [2024-11-14 05:01:05,729 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:01:05,729 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [959441250] [2024-11-14 05:01:05,729 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:01:05,729 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:01:05,756 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:01:05,990 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-14 05:01:05,991 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:01:05,991 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [959441250] [2024-11-14 05:01:05,992 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [959441250] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 05:01:05,992 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 05:01:05,992 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-14 05:01:05,992 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1375812145] [2024-11-14 05:01:05,993 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 05:01:05,993 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-14 05:01:05,993 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:01:05,994 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-14 05:01:05,994 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-14 05:01:05,994 INFO L87 Difference]: Start difference. First operand 67 states and 91 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-14 05:01:06,088 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:01:06,088 INFO L93 Difference]: Finished difference Result 73 states and 96 transitions. [2024-11-14 05:01:06,089 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-14 05:01:06,090 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2024-11-14 05:01:06,091 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:01:06,093 INFO L225 Difference]: With dead ends: 73 [2024-11-14 05:01:06,093 INFO L226 Difference]: Without dead ends: 71 [2024-11-14 05:01:06,093 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-14 05:01:06,096 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 17 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 94 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 05:01:06,096 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 94 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 05:01:06,097 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2024-11-14 05:01:06,115 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 71. [2024-11-14 05:01:06,116 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 44 states have (on average 1.25) internal successors, (55), 46 states have internal predecessors, (55), 20 states have call successors, (20), 6 states have call predecessors, (20), 6 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2024-11-14 05:01:06,117 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 94 transitions. [2024-11-14 05:01:06,117 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 94 transitions. Word has length 30 [2024-11-14 05:01:06,117 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:01:06,117 INFO L471 AbstractCegarLoop]: Abstraction has 71 states and 94 transitions. [2024-11-14 05:01:06,118 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-14 05:01:06,118 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 94 transitions. [2024-11-14 05:01:06,118 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-11-14 05:01:06,118 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:01:06,122 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 05:01:06,122 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2024-11-14 05:01:06,122 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:01:06,122 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:01:06,123 INFO L85 PathProgramCache]: Analyzing trace with hash 947234108, now seen corresponding path program 1 times [2024-11-14 05:01:06,123 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:01:06,123 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1389710655] [2024-11-14 05:01:06,123 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:01:06,123 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:01:06,158 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:01:06,361 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 15 proven. 7 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-14 05:01:06,362 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:01:06,362 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1389710655] [2024-11-14 05:01:06,362 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1389710655] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:01:06,362 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2134688261] [2024-11-14 05:01:06,362 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:01:06,362 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:01:06,362 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:01:06,364 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:01:06,368 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-14 05:01:06,433 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:01:06,435 INFO L255 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-14 05:01:06,436 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:01:06,583 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-14 05:01:06,583 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 05:01:06,583 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2134688261] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 05:01:06,583 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-14 05:01:06,584 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [7] total 11 [2024-11-14 05:01:06,584 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [356676918] [2024-11-14 05:01:06,584 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 05:01:06,584 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-14 05:01:06,584 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:01:06,585 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-14 05:01:06,585 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2024-11-14 05:01:06,585 INFO L87 Difference]: Start difference. First operand 71 states and 94 transitions. Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 3 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 05:01:06,727 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:01:06,727 INFO L93 Difference]: Finished difference Result 84 states and 110 transitions. [2024-11-14 05:01:06,729 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-14 05:01:06,729 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 3 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 36 [2024-11-14 05:01:06,730 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:01:06,731 INFO L225 Difference]: With dead ends: 84 [2024-11-14 05:01:06,731 INFO L226 Difference]: Without dead ends: 82 [2024-11-14 05:01:06,731 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=33, Invalid=123, Unknown=0, NotChecked=0, Total=156 [2024-11-14 05:01:06,732 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 11 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 64 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 139 SdHoareTripleChecker+Invalid, 66 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 64 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 05:01:06,732 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 139 Invalid, 66 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 64 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 05:01:06,736 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2024-11-14 05:01:06,758 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 77. [2024-11-14 05:01:06,758 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 77 states, 47 states have (on average 1.2340425531914894) internal successors, (58), 51 states have internal predecessors, (58), 22 states have call successors, (22), 7 states have call predecessors, (22), 7 states have return successors, (21), 18 states have call predecessors, (21), 21 states have call successors, (21) [2024-11-14 05:01:06,762 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 101 transitions. [2024-11-14 05:01:06,763 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 101 transitions. Word has length 36 [2024-11-14 05:01:06,763 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:01:06,763 INFO L471 AbstractCegarLoop]: Abstraction has 77 states and 101 transitions. [2024-11-14 05:01:06,763 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 3 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 05:01:06,763 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 101 transitions. [2024-11-14 05:01:06,764 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-11-14 05:01:06,764 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:01:06,764 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 05:01:06,787 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-14 05:01:06,970 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2024-11-14 05:01:06,970 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:01:06,970 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:01:06,970 INFO L85 PathProgramCache]: Analyzing trace with hash -229507951, now seen corresponding path program 1 times [2024-11-14 05:01:06,971 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:01:06,971 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [710693126] [2024-11-14 05:01:06,971 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:01:06,971 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:01:06,985 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:01:07,151 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 10 proven. 2 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-14 05:01:07,152 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:01:07,152 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [710693126] [2024-11-14 05:01:07,152 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [710693126] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:01:07,152 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [865488550] [2024-11-14 05:01:07,152 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:01:07,152 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:01:07,152 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:01:07,154 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:01:07,157 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-14 05:01:07,223 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:01:07,224 INFO L255 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-14 05:01:07,226 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:01:07,315 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 10 proven. 26 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-11-14 05:01:07,316 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:01:07,433 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 10 proven. 2 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-14 05:01:07,435 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [865488550] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 05:01:07,435 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1825208314] [2024-11-14 05:01:07,457 INFO L159 IcfgInterpreter]: Started Sifa with 20 locations of interest [2024-11-14 05:01:07,457 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:01:07,460 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:01:07,465 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:01:07,465 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:01:12,973 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2024-11-14 05:01:12,983 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:01:15,592 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1897#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (<= ~counter~0 5))' at error location [2024-11-14 05:01:15,592 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:01:15,592 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 05:01:15,593 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 5, 6] total 11 [2024-11-14 05:01:15,593 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1042074037] [2024-11-14 05:01:15,593 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 05:01:15,593 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-14 05:01:15,593 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:01:15,594 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-14 05:01:15,594 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=116, Invalid=436, Unknown=0, NotChecked=0, Total=552 [2024-11-14 05:01:15,595 INFO L87 Difference]: Start difference. First operand 77 states and 101 transitions. Second operand has 11 states, 11 states have (on average 3.1818181818181817) internal successors, (35), 11 states have internal predecessors, (35), 5 states have call successors, (16), 4 states have call predecessors, (16), 3 states have return successors, (15), 4 states have call predecessors, (15), 4 states have call successors, (15) [2024-11-14 05:01:15,765 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:01:15,765 INFO L93 Difference]: Finished difference Result 188 states and 226 transitions. [2024-11-14 05:01:15,766 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-14 05:01:15,766 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 3.1818181818181817) internal successors, (35), 11 states have internal predecessors, (35), 5 states have call successors, (16), 4 states have call predecessors, (16), 3 states have return successors, (15), 4 states have call predecessors, (15), 4 states have call successors, (15) Word has length 39 [2024-11-14 05:01:15,766 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:01:15,767 INFO L225 Difference]: With dead ends: 188 [2024-11-14 05:01:15,768 INFO L226 Difference]: Without dead ends: 181 [2024-11-14 05:01:15,768 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 96 SyntacticMatches, 4 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 263 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=131, Invalid=519, Unknown=0, NotChecked=0, Total=650 [2024-11-14 05:01:15,769 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 59 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 68 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 80 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 68 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 05:01:15,769 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [59 Valid, 124 Invalid, 80 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 68 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 05:01:15,770 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 181 states. [2024-11-14 05:01:15,788 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 181 to 167. [2024-11-14 05:01:15,788 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 167 states, 108 states have (on average 1.1944444444444444) internal successors, (129), 114 states have internal predecessors, (129), 39 states have call successors, (39), 19 states have call predecessors, (39), 19 states have return successors, (36), 33 states have call predecessors, (36), 36 states have call successors, (36) [2024-11-14 05:01:15,790 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 167 states to 167 states and 204 transitions. [2024-11-14 05:01:15,790 INFO L78 Accepts]: Start accepts. Automaton has 167 states and 204 transitions. Word has length 39 [2024-11-14 05:01:15,791 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:01:15,791 INFO L471 AbstractCegarLoop]: Abstraction has 167 states and 204 transitions. [2024-11-14 05:01:15,791 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 3.1818181818181817) internal successors, (35), 11 states have internal predecessors, (35), 5 states have call successors, (16), 4 states have call predecessors, (16), 3 states have return successors, (15), 4 states have call predecessors, (15), 4 states have call successors, (15) [2024-11-14 05:01:15,791 INFO L276 IsEmpty]: Start isEmpty. Operand 167 states and 204 transitions. [2024-11-14 05:01:15,792 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2024-11-14 05:01:15,792 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:01:15,792 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 05:01:15,811 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-14 05:01:15,996 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:01:15,996 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:01:15,997 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:01:15,997 INFO L85 PathProgramCache]: Analyzing trace with hash -548647717, now seen corresponding path program 1 times [2024-11-14 05:01:15,997 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:01:15,997 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1188763641] [2024-11-14 05:01:15,997 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:01:15,997 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:01:16,019 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 05:01:16,021 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1985367875] [2024-11-14 05:01:16,022 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:01:16,022 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:01:16,022 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:01:16,024 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:01:16,026 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-14 05:01:16,081 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:01:16,082 INFO L255 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-14 05:01:16,085 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:01:16,391 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 23 proven. 8 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-14 05:01:16,391 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:01:16,727 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 27 proven. 4 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-14 05:01:16,727 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:01:16,727 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1188763641] [2024-11-14 05:01:16,727 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 05:01:16,727 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1985367875] [2024-11-14 05:01:16,727 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1985367875] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 05:01:16,727 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [941101429] [2024-11-14 05:01:16,732 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2024-11-14 05:01:16,732 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:01:16,733 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:01:16,733 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:01:16,733 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:01:19,894 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2024-11-14 05:01:19,901 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:01:22,159 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2733#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (<= ~counter~0 5))' at error location [2024-11-14 05:01:22,159 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:01:22,159 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 05:01:22,159 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2024-11-14 05:01:22,160 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1631618454] [2024-11-14 05:01:22,160 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 05:01:22,160 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-14 05:01:22,160 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:01:22,161 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-14 05:01:22,162 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=136, Invalid=620, Unknown=0, NotChecked=0, Total=756 [2024-11-14 05:01:22,162 INFO L87 Difference]: Start difference. First operand 167 states and 204 transitions. Second operand has 15 states, 15 states have (on average 2.2) internal successors, (33), 14 states have internal predecessors, (33), 6 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 7 states have call predecessors, (12), 6 states have call successors, (12) [2024-11-14 05:01:22,581 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:01:22,581 INFO L93 Difference]: Finished difference Result 200 states and 241 transitions. [2024-11-14 05:01:22,582 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-14 05:01:22,582 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.2) internal successors, (33), 14 states have internal predecessors, (33), 6 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 7 states have call predecessors, (12), 6 states have call successors, (12) Word has length 44 [2024-11-14 05:01:22,582 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:01:22,584 INFO L225 Difference]: With dead ends: 200 [2024-11-14 05:01:22,584 INFO L226 Difference]: Without dead ends: 195 [2024-11-14 05:01:22,585 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 101 SyntacticMatches, 3 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 316 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=179, Invalid=813, Unknown=0, NotChecked=0, Total=992 [2024-11-14 05:01:22,585 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 65 mSDsluCounter, 150 mSDsCounter, 0 mSdLazyCounter, 189 mSolverCounterSat, 91 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 66 SdHoareTripleChecker+Valid, 176 SdHoareTripleChecker+Invalid, 280 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 91 IncrementalHoareTripleChecker+Valid, 189 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-14 05:01:22,586 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [66 Valid, 176 Invalid, 280 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [91 Valid, 189 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-14 05:01:22,586 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 195 states. [2024-11-14 05:01:22,612 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 195 to 186. [2024-11-14 05:01:22,613 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 186 states, 120 states have (on average 1.15) internal successors, (138), 125 states have internal predecessors, (138), 41 states have call successors, (41), 24 states have call predecessors, (41), 24 states have return successors, (41), 36 states have call predecessors, (41), 41 states have call successors, (41) [2024-11-14 05:01:22,615 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 186 states to 186 states and 220 transitions. [2024-11-14 05:01:22,615 INFO L78 Accepts]: Start accepts. Automaton has 186 states and 220 transitions. Word has length 44 [2024-11-14 05:01:22,615 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:01:22,616 INFO L471 AbstractCegarLoop]: Abstraction has 186 states and 220 transitions. [2024-11-14 05:01:22,616 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.2) internal successors, (33), 14 states have internal predecessors, (33), 6 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 7 states have call predecessors, (12), 6 states have call successors, (12) [2024-11-14 05:01:22,616 INFO L276 IsEmpty]: Start isEmpty. Operand 186 states and 220 transitions. [2024-11-14 05:01:22,618 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2024-11-14 05:01:22,618 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 05:01:22,618 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 05:01:22,633 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-14 05:01:22,822 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-14 05:01:22,822 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 05:01:22,822 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 05:01:22,823 INFO L85 PathProgramCache]: Analyzing trace with hash -1736423621, now seen corresponding path program 1 times [2024-11-14 05:01:22,823 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 05:01:22,823 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1350805344] [2024-11-14 05:01:22,823 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:01:22,823 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 05:01:22,842 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:01:23,035 INFO L134 CoverageAnalysis]: Checked inductivity of 169 backedges. 39 proven. 7 refuted. 0 times theorem prover too weak. 123 trivial. 0 not checked. [2024-11-14 05:01:23,035 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 05:01:23,035 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1350805344] [2024-11-14 05:01:23,035 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1350805344] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 05:01:23,035 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1780071988] [2024-11-14 05:01:23,035 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 05:01:23,036 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 05:01:23,036 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 05:01:23,038 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 05:01:23,040 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-14 05:01:23,100 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 05:01:23,102 INFO L255 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-14 05:01:23,104 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 05:01:23,389 INFO L134 CoverageAnalysis]: Checked inductivity of 169 backedges. 49 proven. 18 refuted. 0 times theorem prover too weak. 102 trivial. 0 not checked. [2024-11-14 05:01:23,390 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 05:01:23,528 INFO L134 CoverageAnalysis]: Checked inductivity of 169 backedges. 39 proven. 7 refuted. 0 times theorem prover too weak. 123 trivial. 0 not checked. [2024-11-14 05:01:23,529 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1780071988] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 05:01:23,529 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1905197521] [2024-11-14 05:01:23,532 INFO L159 IcfgInterpreter]: Started Sifa with 20 locations of interest [2024-11-14 05:01:23,532 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 05:01:23,533 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 05:01:23,533 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 05:01:23,533 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 05:01:25,475 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 05:01:25,483 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 05:01:27,226 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3720#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 05:01:27,227 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 05:01:27,227 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 05:01:27,227 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 12, 7] total 17 [2024-11-14 05:01:27,227 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1428846812] [2024-11-14 05:01:27,227 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 05:01:27,227 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-14 05:01:27,227 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 05:01:27,228 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-14 05:01:27,228 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=101, Invalid=655, Unknown=0, NotChecked=0, Total=756 [2024-11-14 05:01:27,229 INFO L87 Difference]: Start difference. First operand 186 states and 220 transitions. Second operand has 17 states, 15 states have (on average 2.2666666666666666) internal successors, (34), 13 states have internal predecessors, (34), 10 states have call successors, (21), 3 states have call predecessors, (21), 2 states have return successors, (21), 7 states have call predecessors, (21), 8 states have call successors, (21) [2024-11-14 05:01:27,648 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 05:01:27,649 INFO L93 Difference]: Finished difference Result 200 states and 231 transitions. [2024-11-14 05:01:27,649 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-14 05:01:27,649 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 2.2666666666666666) internal successors, (34), 13 states have internal predecessors, (34), 10 states have call successors, (21), 3 states have call predecessors, (21), 2 states have return successors, (21), 7 states have call predecessors, (21), 8 states have call successors, (21) Word has length 60 [2024-11-14 05:01:27,650 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 05:01:27,650 INFO L225 Difference]: With dead ends: 200 [2024-11-14 05:01:27,650 INFO L226 Difference]: Without dead ends: 0 [2024-11-14 05:01:27,651 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 195 GetRequests, 160 SyntacticMatches, 3 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 230 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=162, Invalid=960, Unknown=0, NotChecked=0, Total=1122 [2024-11-14 05:01:27,652 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 35 mSDsluCounter, 116 mSDsCounter, 0 mSdLazyCounter, 169 mSolverCounterSat, 32 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 201 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 169 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 05:01:27,652 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 138 Invalid, 201 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 169 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 05:01:27,652 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2024-11-14 05:01:27,656 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2024-11-14 05:01:27,657 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 05:01:27,657 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2024-11-14 05:01:27,657 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 60 [2024-11-14 05:01:27,657 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 05:01:27,657 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-14 05:01:27,657 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 2.2666666666666666) internal successors, (34), 13 states have internal predecessors, (34), 10 states have call successors, (21), 3 states have call predecessors, (21), 2 states have return successors, (21), 7 states have call predecessors, (21), 8 states have call successors, (21) [2024-11-14 05:01:27,658 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2024-11-14 05:01:27,658 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2024-11-14 05:01:27,660 INFO L782 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-14 05:01:27,681 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-14 05:01:27,865 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-14 05:01:27,868 INFO L407 BasicCegarLoop]: Path program histogram: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 05:01:27,869 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2024-11-14 05:01:29,162 INFO L173 ceAbstractionStarter]: Computing trace abstraction results [2024-11-14 05:01:29,182 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 14.11 05:01:29 BoogieIcfgContainer [2024-11-14 05:01:29,183 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-14 05:01:29,183 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-14 05:01:29,183 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-14 05:01:29,184 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-14 05:01:29,184 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 05:01:03" (3/4) ... [2024-11-14 05:01:29,186 INFO L142 WitnessPrinter]: Generating witness for correct program [2024-11-14 05:01:29,189 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2024-11-14 05:01:29,193 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 14 nodes and edges [2024-11-14 05:01:29,193 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 6 nodes and edges [2024-11-14 05:01:29,193 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2024-11-14 05:01:29,193 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2024-11-14 05:01:29,263 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/witness.graphml [2024-11-14 05:01:29,263 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/witness.yml [2024-11-14 05:01:29,263 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-14 05:01:29,264 INFO L158 Benchmark]: Toolchain (without parser) took 26587.76ms. Allocated memory was 142.6MB in the beginning and 780.1MB in the end (delta: 637.5MB). Free memory was 119.1MB in the beginning and 421.1MB in the end (delta: -302.0MB). Peak memory consumption was 333.7MB. Max. memory is 16.1GB. [2024-11-14 05:01:29,264 INFO L158 Benchmark]: CDTParser took 0.32ms. Allocated memory is still 142.6MB. Free memory is still 80.2MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 05:01:29,265 INFO L158 Benchmark]: CACSL2BoogieTranslator took 249.04ms. Allocated memory is still 142.6MB. Free memory was 118.8MB in the beginning and 107.8MB in the end (delta: 11.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-14 05:01:29,265 INFO L158 Benchmark]: Boogie Procedure Inliner took 27.01ms. Allocated memory is still 142.6MB. Free memory was 107.5MB in the beginning and 106.4MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 05:01:29,265 INFO L158 Benchmark]: Boogie Preprocessor took 17.61ms. Allocated memory is still 142.6MB. Free memory was 106.4MB in the beginning and 105.8MB in the end (delta: 604.7kB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 05:01:29,265 INFO L158 Benchmark]: RCFGBuilder took 414.32ms. Allocated memory is still 142.6MB. Free memory was 105.6MB in the beginning and 92.7MB in the end (delta: 12.9MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. [2024-11-14 05:01:29,266 INFO L158 Benchmark]: TraceAbstraction took 25790.56ms. Allocated memory was 142.6MB in the beginning and 780.1MB in the end (delta: 637.5MB). Free memory was 92.2MB in the beginning and 429.3MB in the end (delta: -337.1MB). Peak memory consumption was 300.1MB. Max. memory is 16.1GB. [2024-11-14 05:01:29,266 INFO L158 Benchmark]: Witness Printer took 80.13ms. Allocated memory is still 780.1MB. Free memory was 425.4MB in the beginning and 421.1MB in the end (delta: 4.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-14 05:01:29,268 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.32ms. Allocated memory is still 142.6MB. Free memory is still 80.2MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 249.04ms. Allocated memory is still 142.6MB. Free memory was 118.8MB in the beginning and 107.8MB in the end (delta: 11.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 27.01ms. Allocated memory is still 142.6MB. Free memory was 107.5MB in the beginning and 106.4MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 17.61ms. Allocated memory is still 142.6MB. Free memory was 106.4MB in the beginning and 105.8MB in the end (delta: 604.7kB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 414.32ms. Allocated memory is still 142.6MB. Free memory was 105.6MB in the beginning and 92.7MB in the end (delta: 12.9MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. * TraceAbstraction took 25790.56ms. Allocated memory was 142.6MB in the beginning and 780.1MB in the end (delta: 637.5MB). Free memory was 92.2MB in the beginning and 429.3MB in the end (delta: -337.1MB). Peak memory consumption was 300.1MB. Max. memory is 16.1GB. * Witness Printer took 80.13ms. Allocated memory is still 780.1MB. Free memory was 425.4MB in the beginning and 421.1MB in the end (delta: 4.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 17]: a call to reach_error is unreachable For all program executions holds that a call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 24 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 24.4s, OverallIterations: 11, TraceHistogramMax: 10, PathProgramHistogramMax: 1, EmptinessCheckTime: 0.0s, AutomataDifference: 1.7s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 234 SdHoareTripleChecker+Valid, 1.0s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 218 mSDsluCounter, 1191 SdHoareTripleChecker+Invalid, 0.8s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 892 mSDsCounter, 146 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 696 IncrementalHoareTripleChecker+Invalid, 842 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 146 mSolverCounterUnsat, 299 mSDtfsCounter, 696 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 557 GetRequests, 426 SyntacticMatches, 10 SemanticMatches, 121 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 818 ImplicationChecksByTransitivity, 7.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=186occurred in iteration=10, InterpolantAutomatonStates: 72, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.2s AutomataMinimizationTime, 11 MinimizatonAttempts, 39 StatesRemovedByMinimization, 6 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 2.8s InterpolantComputationTime, 502 NumberOfCodeBlocks, 502 NumberOfCodeBlocksAsserted, 18 NumberOfCheckSat, 545 ConstructedInterpolants, 0 QuantifiedInterpolants, 1601 SizeOfPredicates, 13 NumberOfNonLiveVariables, 684 ConjunctsInSsa, 80 ConjunctsInUnsatCore, 17 InterpolantComputations, 8 PerfectInterpolantSequences, 886/967 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 46]: Loop Invariant Derived loop invariant: ((((((1 <= y) && (b == y)) && (a == 1)) && (1 <= r)) && (((__int128) b + x) == ((((__int128) a * y) + r) + ((__int128) q * y)))) || (((((((long long) 2 * y) <= b) && (x == (r + ((__int128) q * y)))) && (1 <= y)) && (1 <= r)) && (((__int128) b + x) == ((((__int128) a * y) + r) + ((__int128) q * y))))) - InvariantResult [Line: 37]: Loop Invariant Derived loop invariant: (((((((1 <= y) && (b == 0)) && (r == x)) && (q == 0)) && (counter == 0)) && (a == 0)) || ((((x == (r + ((__int128) q * y))) && (1 <= y)) && (y <= b)) && (((__int128) b + x) == ((((__int128) a * y) + r) + ((__int128) q * y))))) - ProcedureContractResult [Line: 14]: Procedure Contract for __VERIFIER_assert Derived contract for procedure __VERIFIER_assert. Requires: (1 <= cond) Ensures: ((1 <= cond) && (counter == \old(counter))) RESULT: Ultimate proved your program to be correct! [2024-11-14 05:01:29,290 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_3134b0b4-3f0b-44fc-bf7e-3c455e79e49c/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE