./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/hard2_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_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/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_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound5.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/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_e48d3106-b77b-4b24-a7c4-12be3d0a049f/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 5f094e7ea34d2025ab25ab51a4a0b06d8f845826c76dbd06e91f3d4a761fa19b --- Real Ultimate output --- This is Ultimate 0.3.0-dev-826ab2b [2024-11-14 04:35:03,703 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-14 04:35:03,765 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-32bit-Taipan_Default.epf [2024-11-14 04:35:03,770 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-14 04:35:03,771 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-14 04:35:03,798 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-14 04:35:03,799 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-14 04:35:03,799 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-14 04:35:03,800 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-14 04:35:03,800 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-14 04:35:03,800 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-14 04:35:03,800 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-14 04:35:03,800 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-14 04:35:03,800 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-14 04:35:03,801 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-14 04:35:03,801 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-14 04:35:03,801 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-14 04:35:03,801 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-14 04:35:03,801 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-14 04:35:03,801 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-14 04:35:03,802 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-14 04:35:03,802 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-14 04:35:03,802 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-14 04:35:03,802 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-14 04:35:03,802 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-14 04:35:03,802 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-14 04:35:03,803 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-14 04:35:03,803 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-14 04:35:03,803 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-14 04:35:03,803 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-14 04:35:03,803 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-14 04:35:03,803 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-14 04:35:03,803 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-14 04:35:03,803 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-14 04:35:03,803 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-14 04:35:03,803 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-14 04:35:03,804 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-14 04:35:03,804 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-14 04:35:03,804 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 04:35:03,804 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-14 04:35:03,804 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-14 04:35:03,804 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-14 04:35:03,804 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-14 04:35:03,804 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-14 04:35:03,804 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-14 04:35:03,805 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-14 04:35:03,805 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-14 04:35:03,805 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_e48d3106-b77b-4b24-a7c4-12be3d0a049f/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 -> 5f094e7ea34d2025ab25ab51a4a0b06d8f845826c76dbd06e91f3d4a761fa19b [2024-11-14 04:35:04,095 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-14 04:35:04,105 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-14 04:35:04,107 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-14 04:35:04,109 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-14 04:35:04,109 INFO L274 PluginConnector]: CDTParser initialized [2024-11-14 04:35:04,111 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/../../sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound5.c Unable to find full path for "g++" [2024-11-14 04:35:06,104 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-14 04:35:06,432 INFO L384 CDTParser]: Found 1 translation units. [2024-11-14 04:35:06,433 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound5.c [2024-11-14 04:35:06,444 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/data/47f9cdd55/2f6d7eefd02945699ebc2f61559d9d5e/FLAG4ed4e3a0d [2024-11-14 04:35:06,691 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/data/47f9cdd55/2f6d7eefd02945699ebc2f61559d9d5e [2024-11-14 04:35:06,693 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-14 04:35:06,695 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-14 04:35:06,696 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-14 04:35:06,696 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-14 04:35:06,701 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-14 04:35:06,702 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 04:35:06" (1/1) ... [2024-11-14 04:35:06,703 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@48d9f3b1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:35:06, skipping insertion in model container [2024-11-14 04:35:06,704 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 04:35:06" (1/1) ... [2024-11-14 04:35:06,720 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-14 04:35:06,906 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_e48d3106-b77b-4b24-a7c4-12be3d0a049f/sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound5.c[526,539] [2024-11-14 04:35:06,939 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 04:35:06,957 INFO L200 MainTranslator]: Completed pre-run [2024-11-14 04:35:06,975 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_e48d3106-b77b-4b24-a7c4-12be3d0a049f/sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound5.c[526,539] [2024-11-14 04:35:06,988 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 04:35:07,008 INFO L204 MainTranslator]: Completed translation [2024-11-14 04:35:07,009 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:35:07 WrapperNode [2024-11-14 04:35:07,009 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-14 04:35:07,011 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-14 04:35:07,011 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-14 04:35:07,012 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-14 04:35:07,019 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:35:07" (1/1) ... [2024-11-14 04:35:07,029 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:35:07" (1/1) ... [2024-11-14 04:35:07,053 INFO L138 Inliner]: procedures = 14, calls = 22, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 67 [2024-11-14 04:35:07,054 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-14 04:35:07,055 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-14 04:35:07,056 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-14 04:35:07,056 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-14 04:35:07,065 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:35:07" (1/1) ... [2024-11-14 04:35:07,065 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:35:07" (1/1) ... [2024-11-14 04:35:07,066 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:35:07" (1/1) ... [2024-11-14 04:35:07,067 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:35:07" (1/1) ... [2024-11-14 04:35:07,071 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:35:07" (1/1) ... [2024-11-14 04:35:07,079 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:35:07" (1/1) ... [2024-11-14 04:35:07,081 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:35:07" (1/1) ... [2024-11-14 04:35:07,083 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:35:07" (1/1) ... [2024-11-14 04:35:07,088 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-14 04:35:07,089 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-14 04:35:07,089 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-14 04:35:07,089 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-14 04:35:07,090 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:35:07" (1/1) ... [2024-11-14 04:35:07,099 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 04:35:07,119 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:35:07,136 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-14 04:35:07,141 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-14 04:35:07,178 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-14 04:35:07,178 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-14 04:35:07,178 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-14 04:35:07,179 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-14 04:35:07,179 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-14 04:35:07,180 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-14 04:35:07,267 INFO L238 CfgBuilder]: Building ICFG [2024-11-14 04:35:07,270 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-14 04:35:07,503 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2024-11-14 04:35:07,503 INFO L287 CfgBuilder]: Performing block encoding [2024-11-14 04:35:07,549 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-14 04:35:07,550 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-14 04:35:07,550 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 04:35:07 BoogieIcfgContainer [2024-11-14 04:35:07,550 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-14 04:35:07,552 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-14 04:35:07,553 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-14 04:35:07,558 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-14 04:35:07,558 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.11 04:35:06" (1/3) ... [2024-11-14 04:35:07,559 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7fcd39ae and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 04:35:07, skipping insertion in model container [2024-11-14 04:35:07,559 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:35:07" (2/3) ... [2024-11-14 04:35:07,559 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7fcd39ae and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 04:35:07, skipping insertion in model container [2024-11-14 04:35:07,559 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 04:35:07" (3/3) ... [2024-11-14 04:35:07,560 INFO L112 eAbstractionObserver]: Analyzing ICFG hard2_unwindbound5.c [2024-11-14 04:35:07,578 INFO L217 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-14 04:35:07,579 INFO L154 ceAbstractionStarter]: Applying trace abstraction to ICFG hard2_unwindbound5.c that has 2 procedures, 22 locations, 1 initial locations, 2 loop locations, and 1 error locations. [2024-11-14 04:35:07,638 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-14 04:35:07,654 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;@6da75d10, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-14 04:35:07,655 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-14 04:35:07,660 INFO L276 IsEmpty]: Start isEmpty. Operand has 22 states, 12 states have (on average 1.6666666666666667) internal successors, (20), 13 states have internal predecessors, (20), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-14 04:35:07,667 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-14 04:35:07,668 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:35:07,668 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:35:07,669 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:35:07,675 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:35:07,675 INFO L85 PathProgramCache]: Analyzing trace with hash -513815021, now seen corresponding path program 1 times [2024-11-14 04:35:07,687 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:35:07,688 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1096419798] [2024-11-14 04:35:07,688 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:07,688 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:35:07,793 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:07,839 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 04:35:07,840 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:35:07,840 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1096419798] [2024-11-14 04:35:07,841 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1096419798] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:35:07,841 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:35:07,841 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-14 04:35:07,843 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2117635847] [2024-11-14 04:35:07,843 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:35:07,847 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-14 04:35:07,848 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:35:07,870 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-14 04:35:07,871 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-14 04:35:07,873 INFO L87 Difference]: Start difference. First operand has 22 states, 12 states have (on average 1.6666666666666667) internal successors, (20), 13 states have internal predecessors, (20), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 04:35:07,901 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:35:07,901 INFO L93 Difference]: Finished difference Result 43 states and 74 transitions. [2024-11-14 04:35:07,907 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-14 04:35:07,909 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2024-11-14 04:35:07,909 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:35:07,914 INFO L225 Difference]: With dead ends: 43 [2024-11-14 04:35:07,914 INFO L226 Difference]: Without dead ends: 20 [2024-11-14 04:35:07,917 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 04:35:07,921 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 3 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 28 SdHoareTripleChecker+Invalid, 3 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 3 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 04:35:07,921 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 28 Invalid, 3 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 3 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 04:35:07,937 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2024-11-14 04:35:07,952 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2024-11-14 04:35:07,953 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 12 states have internal predecessors, (16), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-14 04:35:07,960 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 29 transitions. [2024-11-14 04:35:07,962 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 29 transitions. Word has length 7 [2024-11-14 04:35:07,962 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:35:07,963 INFO L471 AbstractCegarLoop]: Abstraction has 20 states and 29 transitions. [2024-11-14 04:35:07,963 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 04:35:07,963 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 29 transitions. [2024-11-14 04:35:07,963 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-14 04:35:07,964 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:35:07,964 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:35:07,964 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-14 04:35:07,964 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:35:07,965 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:35:07,965 INFO L85 PathProgramCache]: Analyzing trace with hash -974949910, now seen corresponding path program 1 times [2024-11-14 04:35:07,965 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:35:07,965 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1350258716] [2024-11-14 04:35:07,965 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:07,966 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:35:08,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:08,149 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 04:35:08,149 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:35:08,149 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1350258716] [2024-11-14 04:35:08,149 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1350258716] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:35:08,149 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:35:08,150 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-14 04:35:08,150 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1001751816] [2024-11-14 04:35:08,150 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:35:08,151 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 04:35:08,151 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:35:08,152 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 04:35:08,152 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-14 04:35:08,152 INFO L87 Difference]: Start difference. First operand 20 states and 29 transitions. Second operand has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 04:35:08,248 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:35:08,249 INFO L93 Difference]: Finished difference Result 33 states and 46 transitions. [2024-11-14 04:35:08,249 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 04:35:08,250 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 04:35:08,250 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:35:08,251 INFO L225 Difference]: With dead ends: 33 [2024-11-14 04:35:08,251 INFO L226 Difference]: Without dead ends: 31 [2024-11-14 04:35:08,251 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-14 04:35:08,253 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 10 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 04:35:08,253 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 82 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 04:35:08,254 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2024-11-14 04:35:08,262 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 24. [2024-11-14 04:35:08,263 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 14 states have (on average 1.3571428571428572) internal successors, (19), 15 states have internal predecessors, (19), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-14 04:35:08,264 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 32 transitions. [2024-11-14 04:35:08,264 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 32 transitions. Word has length 7 [2024-11-14 04:35:08,264 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:35:08,265 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 32 transitions. [2024-11-14 04:35:08,265 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 04:35:08,265 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 32 transitions. [2024-11-14 04:35:08,266 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-11-14 04:35:08,266 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:35:08,266 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:35:08,266 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-14 04:35:08,266 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:35:08,267 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:35:08,267 INFO L85 PathProgramCache]: Analyzing trace with hash 756875265, now seen corresponding path program 1 times [2024-11-14 04:35:08,267 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:35:08,267 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [597296176] [2024-11-14 04:35:08,268 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:08,268 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:35:08,304 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:08,415 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 04:35:08,415 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:35:08,416 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [597296176] [2024-11-14 04:35:08,416 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [597296176] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:35:08,416 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:35:08,416 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-14 04:35:08,416 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2065002844] [2024-11-14 04:35:08,416 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:35:08,417 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-14 04:35:08,417 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:35:08,417 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-14 04:35:08,417 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 04:35:08,418 INFO L87 Difference]: Start difference. First operand 24 states and 32 transitions. Second operand has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 04:35:08,455 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:35:08,455 INFO L93 Difference]: Finished difference Result 39 states and 52 transitions. [2024-11-14 04:35:08,455 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-14 04:35:08,455 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2024-11-14 04:35:08,456 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:35:08,456 INFO L225 Difference]: With dead ends: 39 [2024-11-14 04:35:08,456 INFO L226 Difference]: Without dead ends: 26 [2024-11-14 04:35:08,457 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 04:35:08,457 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 0 mSDsluCounter, 48 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 13 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 04:35:08,458 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 73 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 04:35:08,458 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2024-11-14 04:35:08,463 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2024-11-14 04:35:08,463 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 16 states have (on average 1.3125) internal successors, (21), 17 states have internal predecessors, (21), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-14 04:35:08,464 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 34 transitions. [2024-11-14 04:35:08,464 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 34 transitions. Word has length 9 [2024-11-14 04:35:08,464 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:35:08,464 INFO L471 AbstractCegarLoop]: Abstraction has 26 states and 34 transitions. [2024-11-14 04:35:08,465 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 04:35:08,465 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 34 transitions. [2024-11-14 04:35:08,465 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2024-11-14 04:35:08,465 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:35:08,465 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:35:08,465 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-14 04:35:08,466 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:35:08,467 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:35:08,467 INFO L85 PathProgramCache]: Analyzing trace with hash -408725012, now seen corresponding path program 1 times [2024-11-14 04:35:08,467 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:35:08,467 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1854668580] [2024-11-14 04:35:08,467 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:08,467 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:35:08,480 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:08,634 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 04:35:08,634 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:35:08,634 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1854668580] [2024-11-14 04:35:08,635 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1854668580] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:35:08,635 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:35:08,635 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-14 04:35:08,635 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [61596191] [2024-11-14 04:35:08,635 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:35:08,636 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 04:35:08,636 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:35:08,637 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 04:35:08,637 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-14 04:35:08,637 INFO L87 Difference]: Start difference. First operand 26 states and 34 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-14 04:35:08,710 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:35:08,710 INFO L93 Difference]: Finished difference Result 39 states and 51 transitions. [2024-11-14 04:35:08,711 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 04:35:08,712 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 04:35:08,712 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:35:08,712 INFO L225 Difference]: With dead ends: 39 [2024-11-14 04:35:08,713 INFO L226 Difference]: Without dead ends: 37 [2024-11-14 04:35:08,713 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-14 04:35:08,714 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 10 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 04:35:08,714 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 83 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 04:35:08,715 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2024-11-14 04:35:08,720 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 30. [2024-11-14 04:35:08,721 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-14 04:35:08,722 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 37 transitions. [2024-11-14 04:35:08,722 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 37 transitions. Word has length 12 [2024-11-14 04:35:08,722 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:35:08,722 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 37 transitions. [2024-11-14 04:35:08,723 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 04:35:08,723 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 37 transitions. [2024-11-14 04:35:08,723 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-11-14 04:35:08,723 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:35:08,723 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:35:08,724 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-14 04:35:08,724 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:35:08,724 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:35:08,724 INFO L85 PathProgramCache]: Analyzing trace with hash -316982550, now seen corresponding path program 1 times [2024-11-14 04:35:08,725 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:35:08,725 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [78980135] [2024-11-14 04:35:08,725 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:08,725 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:35:08,737 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 04:35:08,739 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [461251314] [2024-11-14 04:35:08,739 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:08,740 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:35:08,740 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:35:08,742 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:35:08,747 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-14 04:35:08,828 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:08,831 INFO L255 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-14 04:35:08,835 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:35:08,964 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 04:35:08,964 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 04:35:08,965 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:35:08,965 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [78980135] [2024-11-14 04:35:08,965 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 04:35:08,965 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [461251314] [2024-11-14 04:35:08,965 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [461251314] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:35:08,966 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:35:08,966 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-14 04:35:08,966 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [284996933] [2024-11-14 04:35:08,966 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:35:08,966 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 04:35:08,966 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:35:08,967 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 04:35:08,967 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-14 04:35:08,967 INFO L87 Difference]: Start difference. First operand 30 states and 37 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-14 04:35:09,080 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:35:09,080 INFO L93 Difference]: Finished difference Result 58 states and 78 transitions. [2024-11-14 04:35:09,081 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 04:35:09,081 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2024-11-14 04:35:09,081 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:35:09,082 INFO L225 Difference]: With dead ends: 58 [2024-11-14 04:35:09,082 INFO L226 Difference]: Without dead ends: 44 [2024-11-14 04:35:09,082 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-14 04:35:09,083 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 7 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 04:35:09,084 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 82 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 04:35:09,084 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2024-11-14 04:35:09,096 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 44. [2024-11-14 04:35:09,097 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 28 states have internal predecessors, (33), 13 states have call successors, (13), 4 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-14 04:35:09,098 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 57 transitions. [2024-11-14 04:35:09,098 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 57 transitions. Word has length 17 [2024-11-14 04:35:09,098 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:35:09,098 INFO L471 AbstractCegarLoop]: Abstraction has 44 states and 57 transitions. [2024-11-14 04:35:09,098 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-14 04:35:09,099 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 57 transitions. [2024-11-14 04:35:09,099 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-11-14 04:35:09,099 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:35:09,099 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:35:09,122 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-14 04:35:09,304 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:35:09,304 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:35:09,305 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:35:09,305 INFO L85 PathProgramCache]: Analyzing trace with hash 65356806, now seen corresponding path program 1 times [2024-11-14 04:35:09,305 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:35:09,305 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [193914608] [2024-11-14 04:35:09,305 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:09,305 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:35:09,328 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:09,452 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-14 04:35:09,452 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:35:09,452 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [193914608] [2024-11-14 04:35:09,452 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [193914608] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:35:09,452 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:35:09,452 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-14 04:35:09,453 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [128138110] [2024-11-14 04:35:09,453 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:35:09,453 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-14 04:35:09,453 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:35:09,454 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-14 04:35:09,454 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-14 04:35:09,454 INFO L87 Difference]: Start difference. First operand 44 states and 57 transitions. Second operand has 6 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 04:35:09,535 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:35:09,535 INFO L93 Difference]: Finished difference Result 63 states and 72 transitions. [2024-11-14 04:35:09,536 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-14 04:35:09,536 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 25 [2024-11-14 04:35:09,538 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:35:09,540 INFO L225 Difference]: With dead ends: 63 [2024-11-14 04:35:09,540 INFO L226 Difference]: Without dead ends: 56 [2024-11-14 04:35:09,540 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 04:35:09,541 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 7 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 102 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 04:35:09,541 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 102 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 04:35:09,544 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2024-11-14 04:35:09,556 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 55. [2024-11-14 04:35:09,559 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 35 states have (on average 1.1714285714285715) internal successors, (41), 36 states have internal predecessors, (41), 12 states have call successors, (12), 7 states have call predecessors, (12), 7 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-14 04:35:09,560 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 64 transitions. [2024-11-14 04:35:09,561 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 64 transitions. Word has length 25 [2024-11-14 04:35:09,561 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:35:09,561 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 64 transitions. [2024-11-14 04:35:09,561 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 04:35:09,563 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 64 transitions. [2024-11-14 04:35:09,564 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-11-14 04:35:09,564 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:35:09,564 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:35:09,564 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-14 04:35:09,565 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:35:09,565 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:35:09,565 INFO L85 PathProgramCache]: Analyzing trace with hash 67084684, now seen corresponding path program 1 times [2024-11-14 04:35:09,565 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:35:09,565 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [671085280] [2024-11-14 04:35:09,565 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:09,565 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:35:09,587 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 04:35:09,589 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [239462195] [2024-11-14 04:35:09,591 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:09,592 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:35:09,592 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:35:09,594 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:35:09,598 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-14 04:35:09,680 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:09,681 INFO L255 TraceCheckSpWp]: Trace formula consists of 98 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-14 04:35:09,683 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:35:09,873 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-14 04:35:09,873 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:35:10,148 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-14 04:35:10,149 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:35:10,149 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [671085280] [2024-11-14 04:35:10,149 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 04:35:10,149 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [239462195] [2024-11-14 04:35:10,149 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [239462195] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:35:10,149 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [354770503] [2024-11-14 04:35:10,172 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2024-11-14 04:35:10,173 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:35:10,178 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:35:10,182 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:35:10,183 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:35:11,282 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2024-11-14 04:35:11,290 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:35:12,691 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [354770503] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:35:12,691 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2024-11-14 04:35:12,691 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [7, 7] total 18 [2024-11-14 04:35:12,692 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [485109781] [2024-11-14 04:35:12,692 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:35:12,692 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-14 04:35:12,692 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:35:12,693 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-14 04:35:12,693 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=242, Unknown=0, NotChecked=0, Total=306 [2024-11-14 04:35:12,694 INFO L87 Difference]: Start difference. First operand 55 states and 64 transitions. Second operand has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 04:35:12,973 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:35:12,973 INFO L93 Difference]: Finished difference Result 61 states and 69 transitions. [2024-11-14 04:35:12,974 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-14 04:35:12,974 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 25 [2024-11-14 04:35:12,974 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:35:12,975 INFO L225 Difference]: With dead ends: 61 [2024-11-14 04:35:12,975 INFO L226 Difference]: Without dead ends: 59 [2024-11-14 04:35:12,976 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 53 SyntacticMatches, 4 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=64, Invalid=242, Unknown=0, NotChecked=0, Total=306 [2024-11-14 04:35:12,976 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 0 mSDsluCounter, 54 mSDsCounter, 0 mSdLazyCounter, 145 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 67 SdHoareTripleChecker+Invalid, 146 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 145 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-14 04:35:12,977 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 67 Invalid, 146 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 145 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-14 04:35:12,977 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2024-11-14 04:35:13,002 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 59. [2024-11-14 04:35:13,002 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 38 states have (on average 1.1578947368421053) internal successors, (44), 39 states have internal predecessors, (44), 12 states have call successors, (12), 8 states have call predecessors, (12), 8 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-14 04:35:13,003 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 67 transitions. [2024-11-14 04:35:13,003 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 67 transitions. Word has length 25 [2024-11-14 04:35:13,004 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:35:13,004 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 67 transitions. [2024-11-14 04:35:13,004 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 04:35:13,004 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 67 transitions. [2024-11-14 04:35:13,005 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-11-14 04:35:13,005 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:35:13,005 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:35:13,029 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-14 04:35:13,205 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2024-11-14 04:35:13,205 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:35:13,206 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:35:13,206 INFO L85 PathProgramCache]: Analyzing trace with hash -798302453, now seen corresponding path program 1 times [2024-11-14 04:35:13,206 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:35:13,206 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [974528455] [2024-11-14 04:35:13,206 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:13,206 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:35:13,219 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:13,319 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-14 04:35:13,319 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:35:13,319 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [974528455] [2024-11-14 04:35:13,319 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [974528455] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 04:35:13,320 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [286171296] [2024-11-14 04:35:13,320 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:13,320 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:35:13,320 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:35:13,324 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:35:13,326 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-14 04:35:13,386 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:13,388 INFO L255 TraceCheckSpWp]: Trace formula consists of 107 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-14 04:35:13,389 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:35:13,442 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-14 04:35:13,443 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:35:13,519 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-14 04:35:13,520 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [286171296] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:35:13,521 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2102947366] [2024-11-14 04:35:13,523 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2024-11-14 04:35:13,526 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:35:13,527 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:35:13,527 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:35:13,527 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:35:15,522 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2024-11-14 04:35:15,534 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:35:16,909 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1352#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-14 04:35:16,910 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 04:35:16,910 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 04:35:16,910 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 4, 5] total 10 [2024-11-14 04:35:16,910 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1196072252] [2024-11-14 04:35:16,910 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 04:35:16,911 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-14 04:35:16,911 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:35:16,911 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-14 04:35:16,912 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=374, Unknown=0, NotChecked=0, Total=462 [2024-11-14 04:35:16,912 INFO L87 Difference]: Start difference. First operand 59 states and 67 transitions. Second operand has 10 states, 10 states have (on average 2.6) internal successors, (26), 10 states have internal predecessors, (26), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-14 04:35:17,131 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:35:17,131 INFO L93 Difference]: Finished difference Result 124 states and 147 transitions. [2024-11-14 04:35:17,132 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-14 04:35:17,132 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.6) internal successors, (26), 10 states have internal predecessors, (26), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 27 [2024-11-14 04:35:17,133 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:35:17,134 INFO L225 Difference]: With dead ends: 124 [2024-11-14 04:35:17,134 INFO L226 Difference]: Without dead ends: 111 [2024-11-14 04:35:17,135 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 65 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 148 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=101, Invalid=451, Unknown=0, NotChecked=0, Total=552 [2024-11-14 04:35:17,136 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 52 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 85 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 52 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 99 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 85 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 04:35:17,137 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [52 Valid, 112 Invalid, 99 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 85 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 04:35:17,138 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2024-11-14 04:35:17,163 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 106. [2024-11-14 04:35:17,164 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 67 states have (on average 1.1791044776119404) internal successors, (79), 70 states have internal predecessors, (79), 24 states have call successors, (24), 14 states have call predecessors, (24), 14 states have return successors, (21), 21 states have call predecessors, (21), 21 states have call successors, (21) [2024-11-14 04:35:17,167 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 124 transitions. [2024-11-14 04:35:17,167 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 124 transitions. Word has length 27 [2024-11-14 04:35:17,170 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:35:17,170 INFO L471 AbstractCegarLoop]: Abstraction has 106 states and 124 transitions. [2024-11-14 04:35:17,171 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.6) internal successors, (26), 10 states have internal predecessors, (26), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-14 04:35:17,171 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 124 transitions. [2024-11-14 04:35:17,171 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-14 04:35:17,171 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:35:17,172 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2024-11-14 04:35:17,196 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-14 04:35:17,372 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2024-11-14 04:35:17,373 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:35:17,373 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:35:17,373 INFO L85 PathProgramCache]: Analyzing trace with hash 1522954228, now seen corresponding path program 1 times [2024-11-14 04:35:17,373 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:35:17,374 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [836445150] [2024-11-14 04:35:17,374 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:17,374 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:35:17,400 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 04:35:17,401 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1327522033] [2024-11-14 04:35:17,401 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:17,401 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:35:17,401 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:35:17,406 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:35:17,409 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-14 04:35:17,465 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:17,467 INFO L255 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-14 04:35:17,469 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:35:17,579 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-14 04:35:17,580 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:35:17,671 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-14 04:35:17,672 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:35:17,674 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [836445150] [2024-11-14 04:35:17,674 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 04:35:17,674 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1327522033] [2024-11-14 04:35:17,674 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1327522033] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-14 04:35:17,674 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-14 04:35:17,674 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-14 04:35:17,674 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [188921118] [2024-11-14 04:35:17,675 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:35:17,675 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 04:35:17,675 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:35:17,675 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 04:35:17,675 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-14 04:35:17,676 INFO L87 Difference]: Start difference. First operand 106 states and 124 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 04:35:17,780 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:35:17,781 INFO L93 Difference]: Finished difference Result 129 states and 152 transitions. [2024-11-14 04:35:17,782 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 04:35:17,783 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 35 [2024-11-14 04:35:17,783 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:35:17,784 INFO L225 Difference]: With dead ends: 129 [2024-11-14 04:35:17,784 INFO L226 Difference]: Without dead ends: 127 [2024-11-14 04:35:17,785 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 61 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-14 04:35:17,785 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 8 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 04:35:17,786 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 85 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 04:35:17,787 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2024-11-14 04:35:17,806 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 122. [2024-11-14 04:35:17,807 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 78 states have (on average 1.1666666666666667) internal successors, (91), 82 states have internal predecessors, (91), 26 states have call successors, (26), 17 states have call predecessors, (26), 17 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2024-11-14 04:35:17,808 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 140 transitions. [2024-11-14 04:35:17,809 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 140 transitions. Word has length 35 [2024-11-14 04:35:17,810 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:35:17,811 INFO L471 AbstractCegarLoop]: Abstraction has 122 states and 140 transitions. [2024-11-14 04:35:17,811 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 04:35:17,811 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 140 transitions. [2024-11-14 04:35:17,812 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-11-14 04:35:17,813 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:35:17,813 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 04:35:17,836 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-14 04:35:18,014 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2024-11-14 04:35:18,014 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:35:18,014 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:35:18,015 INFO L85 PathProgramCache]: Analyzing trace with hash -1979605679, now seen corresponding path program 1 times [2024-11-14 04:35:18,015 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:35:18,015 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [692039100] [2024-11-14 04:35:18,015 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:18,015 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:35:18,027 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 04:35:18,028 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1579048962] [2024-11-14 04:35:18,028 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:18,028 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:35:18,028 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:35:18,031 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:35:18,033 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-14 04:35:18,088 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:18,089 INFO L255 TraceCheckSpWp]: Trace formula consists of 118 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-14 04:35:18,090 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:35:18,183 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 9 proven. 13 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-14 04:35:18,183 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:35:18,325 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 9 proven. 13 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-14 04:35:18,326 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:35:18,326 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [692039100] [2024-11-14 04:35:18,326 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 04:35:18,326 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1579048962] [2024-11-14 04:35:18,326 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1579048962] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:35:18,326 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1586168698] [2024-11-14 04:35:18,329 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2024-11-14 04:35:18,330 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:35:18,331 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:35:18,331 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:35:18,331 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:35:18,904 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2024-11-14 04:35:18,908 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:35:20,095 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [1586168698] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:35:20,095 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2024-11-14 04:35:20,095 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [7, 7] total 19 [2024-11-14 04:35:20,095 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [196326911] [2024-11-14 04:35:20,095 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:35:20,096 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-14 04:35:20,096 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:35:20,096 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-14 04:35:20,096 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=272, Unknown=0, NotChecked=0, Total=342 [2024-11-14 04:35:20,097 INFO L87 Difference]: Start difference. First operand 122 states and 140 transitions. Second operand has 11 states, 10 states have (on average 1.2) internal successors, (12), 10 states have internal predecessors, (12), 3 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-14 04:35:20,348 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:35:20,348 INFO L93 Difference]: Finished difference Result 124 states and 141 transitions. [2024-11-14 04:35:20,348 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-14 04:35:20,348 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 1.2) internal successors, (12), 10 states have internal predecessors, (12), 3 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 36 [2024-11-14 04:35:20,349 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:35:20,351 INFO L225 Difference]: With dead ends: 124 [2024-11-14 04:35:20,351 INFO L226 Difference]: Without dead ends: 103 [2024-11-14 04:35:20,352 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 106 GetRequests, 83 SyntacticMatches, 6 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 114 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=70, Invalid=272, Unknown=0, NotChecked=0, Total=342 [2024-11-14 04:35:20,352 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 0 mSDsluCounter, 40 mSDsCounter, 0 mSdLazyCounter, 166 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 52 SdHoareTripleChecker+Invalid, 167 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 166 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 04:35:20,352 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 52 Invalid, 167 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 166 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 04:35:20,353 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2024-11-14 04:35:20,365 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 103. [2024-11-14 04:35:20,366 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 66 states have (on average 1.1666666666666667) internal successors, (77), 69 states have internal predecessors, (77), 22 states have call successors, (22), 14 states have call predecessors, (22), 14 states have return successors, (20), 19 states have call predecessors, (20), 20 states have call successors, (20) [2024-11-14 04:35:20,367 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 119 transitions. [2024-11-14 04:35:20,367 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 119 transitions. Word has length 36 [2024-11-14 04:35:20,367 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:35:20,367 INFO L471 AbstractCegarLoop]: Abstraction has 103 states and 119 transitions. [2024-11-14 04:35:20,367 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 1.2) internal successors, (12), 10 states have internal predecessors, (12), 3 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-14 04:35:20,367 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 119 transitions. [2024-11-14 04:35:20,368 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-14 04:35:20,368 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:35:20,368 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:35:20,389 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-14 04:35:20,569 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-14 04:35:20,569 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:35:20,570 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:35:20,570 INFO L85 PathProgramCache]: Analyzing trace with hash -1942499568, now seen corresponding path program 1 times [2024-11-14 04:35:20,570 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:35:20,570 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1551917136] [2024-11-14 04:35:20,570 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:20,570 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:35:20,581 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:20,712 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-14 04:35:20,712 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:35:20,713 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1551917136] [2024-11-14 04:35:20,713 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1551917136] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 04:35:20,713 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2103031233] [2024-11-14 04:35:20,713 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:20,713 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:35:20,713 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:35:20,715 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:35:20,717 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-14 04:35:20,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:20,772 INFO L255 TraceCheckSpWp]: Trace formula consists of 135 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-14 04:35:20,773 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:35:20,838 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 42 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-14 04:35:20,838 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:35:20,936 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-14 04:35:20,937 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2103031233] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:35:20,937 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [101580254] [2024-11-14 04:35:20,939 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2024-11-14 04:35:20,939 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:35:20,939 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:35:20,940 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:35:20,940 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:35:22,246 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2024-11-14 04:35:22,258 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:35:23,297 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3178#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-14 04:35:23,297 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 04:35:23,297 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 04:35:23,297 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 5, 6] total 11 [2024-11-14 04:35:23,298 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1103056281] [2024-11-14 04:35:23,298 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 04:35:23,298 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-14 04:35:23,298 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:35:23,299 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-14 04:35:23,299 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=90, Invalid=416, Unknown=0, NotChecked=0, Total=506 [2024-11-14 04:35:23,299 INFO L87 Difference]: Start difference. First operand 103 states and 119 transitions. Second operand has 11 states, 11 states have (on average 3.0) internal successors, (33), 11 states have internal predecessors, (33), 5 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2024-11-14 04:35:23,466 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:35:23,466 INFO L93 Difference]: Finished difference Result 157 states and 183 transitions. [2024-11-14 04:35:23,467 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-14 04:35:23,467 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 3.0) internal successors, (33), 11 states have internal predecessors, (33), 5 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) Word has length 43 [2024-11-14 04:35:23,467 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:35:23,469 INFO L225 Difference]: With dead ends: 157 [2024-11-14 04:35:23,469 INFO L226 Difference]: Without dead ends: 143 [2024-11-14 04:35:23,469 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 136 GetRequests, 112 SyntacticMatches, 1 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 155 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=101, Invalid=499, Unknown=0, NotChecked=0, Total=600 [2024-11-14 04:35:23,470 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 39 mSDsluCounter, 112 mSDsCounter, 0 mSdLazyCounter, 103 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 105 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 103 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 04:35:23,470 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 135 Invalid, 105 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 103 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 04:35:23,473 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2024-11-14 04:35:23,492 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 138. [2024-11-14 04:35:23,492 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 138 states, 88 states have (on average 1.1477272727272727) internal successors, (101), 93 states have internal predecessors, (101), 31 states have call successors, (31), 18 states have call predecessors, (31), 18 states have return successors, (28), 26 states have call predecessors, (28), 28 states have call successors, (28) [2024-11-14 04:35:23,493 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 160 transitions. [2024-11-14 04:35:23,494 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 160 transitions. Word has length 43 [2024-11-14 04:35:23,494 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:35:23,494 INFO L471 AbstractCegarLoop]: Abstraction has 138 states and 160 transitions. [2024-11-14 04:35:23,494 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 3.0) internal successors, (33), 11 states have internal predecessors, (33), 5 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2024-11-14 04:35:23,495 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 160 transitions. [2024-11-14 04:35:23,495 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-14 04:35:23,495 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:35:23,495 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:35:23,516 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-14 04:35:23,696 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-14 04:35:23,697 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:35:23,697 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:35:23,697 INFO L85 PathProgramCache]: Analyzing trace with hash -1940771690, now seen corresponding path program 1 times [2024-11-14 04:35:23,697 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:35:23,697 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1100241688] [2024-11-14 04:35:23,697 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:23,697 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:35:23,711 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 04:35:23,711 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [161403321] [2024-11-14 04:35:23,712 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:23,712 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:35:23,712 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:35:23,714 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:35:23,718 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-14 04:35:23,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:23,771 INFO L255 TraceCheckSpWp]: Trace formula consists of 135 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-14 04:35:23,772 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:35:23,854 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-11-14 04:35:23,854 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 04:35:23,854 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:35:23,854 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1100241688] [2024-11-14 04:35:23,854 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 04:35:23,854 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [161403321] [2024-11-14 04:35:23,855 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [161403321] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:35:23,855 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:35:23,855 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-14 04:35:23,855 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1342894287] [2024-11-14 04:35:23,855 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:35:23,855 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 04:35:23,855 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:35:23,856 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 04:35:23,856 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-14 04:35:23,856 INFO L87 Difference]: Start difference. First operand 138 states and 160 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 04:35:23,916 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:35:23,916 INFO L93 Difference]: Finished difference Result 158 states and 183 transitions. [2024-11-14 04:35:23,916 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 04:35:23,917 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 43 [2024-11-14 04:35:23,917 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:35:23,918 INFO L225 Difference]: With dead ends: 158 [2024-11-14 04:35:23,918 INFO L226 Difference]: Without dead ends: 154 [2024-11-14 04:35:23,918 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 39 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 04:35:23,919 INFO L432 NwaCegarLoop]: 19 mSDtfsCounter, 6 mSDsluCounter, 48 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 67 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 04:35:23,919 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 67 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 04:35:23,920 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 154 states. [2024-11-14 04:35:23,937 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 154 to 152. [2024-11-14 04:35:23,937 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 152 states, 98 states have (on average 1.1428571428571428) internal successors, (112), 102 states have internal predecessors, (112), 33 states have call successors, (33), 21 states have call predecessors, (33), 20 states have return successors, (30), 28 states have call predecessors, (30), 30 states have call successors, (30) [2024-11-14 04:35:23,938 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 152 states to 152 states and 175 transitions. [2024-11-14 04:35:23,939 INFO L78 Accepts]: Start accepts. Automaton has 152 states and 175 transitions. Word has length 43 [2024-11-14 04:35:23,939 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:35:23,939 INFO L471 AbstractCegarLoop]: Abstraction has 152 states and 175 transitions. [2024-11-14 04:35:23,940 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 04:35:23,940 INFO L276 IsEmpty]: Start isEmpty. Operand 152 states and 175 transitions. [2024-11-14 04:35:23,941 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2024-11-14 04:35:23,941 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:35:23,941 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:35:23,960 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-14 04:35:24,146 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2024-11-14 04:35:24,146 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:35:24,146 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:35:24,146 INFO L85 PathProgramCache]: Analyzing trace with hash -1115004513, now seen corresponding path program 1 times [2024-11-14 04:35:24,146 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:35:24,146 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1316280431] [2024-11-14 04:35:24,146 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:24,146 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:35:24,173 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 04:35:24,174 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [269567922] [2024-11-14 04:35:24,174 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:24,174 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:35:24,174 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:35:24,176 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:35:24,182 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-14 04:35:24,247 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:24,249 INFO L255 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 23 conjuncts are in the unsatisfiable core [2024-11-14 04:35:24,251 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:35:24,557 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2024-11-14 04:35:24,557 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:35:28,153 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2024-11-14 04:35:28,153 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:35:28,153 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1316280431] [2024-11-14 04:35:28,154 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 04:35:28,154 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [269567922] [2024-11-14 04:35:28,154 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [269567922] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:35:28,154 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1436390486] [2024-11-14 04:35:28,156 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2024-11-14 04:35:28,156 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:35:28,156 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:35:28,156 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:35:28,156 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:35:29,792 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 04:35:29,795 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:35:30,855 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4614#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 04:35:30,855 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 04:35:30,855 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 04:35:30,855 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2024-11-14 04:35:30,856 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [441698624] [2024-11-14 04:35:30,856 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 04:35:30,856 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-14 04:35:30,856 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:35:30,857 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-14 04:35:30,857 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=389, Unknown=0, NotChecked=0, Total=462 [2024-11-14 04:35:30,857 INFO L87 Difference]: Start difference. First operand 152 states and 175 transitions. Second operand has 10 states, 10 states have (on average 3.0) internal successors, (30), 9 states have internal predecessors, (30), 6 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2024-11-14 04:35:31,700 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:35:31,700 INFO L93 Difference]: Finished difference Result 190 states and 215 transitions. [2024-11-14 04:35:31,700 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-14 04:35:31,701 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.0) internal successors, (30), 9 states have internal predecessors, (30), 6 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) Word has length 56 [2024-11-14 04:35:31,701 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:35:31,702 INFO L225 Difference]: With dead ends: 190 [2024-11-14 04:35:31,702 INFO L226 Difference]: Without dead ends: 180 [2024-11-14 04:35:31,703 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 170 GetRequests, 143 SyntacticMatches, 3 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 126 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=106, Invalid=544, Unknown=0, NotChecked=0, Total=650 [2024-11-14 04:35:31,704 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 26 mSDsluCounter, 162 mSDsCounter, 0 mSdLazyCounter, 124 mSolverCounterSat, 32 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 195 SdHoareTripleChecker+Invalid, 156 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 124 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-14 04:35:31,704 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 195 Invalid, 156 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 124 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-14 04:35:31,704 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 180 states. [2024-11-14 04:35:31,747 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 180 to 171. [2024-11-14 04:35:31,748 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 171 states, 113 states have (on average 1.1238938053097345) internal successors, (127), 118 states have internal predecessors, (127), 32 states have call successors, (32), 25 states have call predecessors, (32), 25 states have return successors, (30), 27 states have call predecessors, (30), 30 states have call successors, (30) [2024-11-14 04:35:31,750 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 171 states to 171 states and 189 transitions. [2024-11-14 04:35:31,750 INFO L78 Accepts]: Start accepts. Automaton has 171 states and 189 transitions. Word has length 56 [2024-11-14 04:35:31,750 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:35:31,751 INFO L471 AbstractCegarLoop]: Abstraction has 171 states and 189 transitions. [2024-11-14 04:35:31,751 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.0) internal successors, (30), 9 states have internal predecessors, (30), 6 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2024-11-14 04:35:31,751 INFO L276 IsEmpty]: Start isEmpty. Operand 171 states and 189 transitions. [2024-11-14 04:35:31,752 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2024-11-14 04:35:31,752 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:35:31,753 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:35:31,776 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-14 04:35:31,955 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-14 04:35:31,955 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:35:31,955 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:35:31,955 INFO L85 PathProgramCache]: Analyzing trace with hash -751945065, now seen corresponding path program 2 times [2024-11-14 04:35:31,955 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:35:31,956 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1787676299] [2024-11-14 04:35:31,956 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:31,956 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:35:31,990 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 04:35:31,991 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1210145353] [2024-11-14 04:35:31,992 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 04:35:31,992 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:35:31,992 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:35:31,995 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:35:32,006 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-14 04:35:32,063 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-14 04:35:32,063 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 04:35:32,065 INFO L255 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 31 conjuncts are in the unsatisfiable core [2024-11-14 04:35:32,067 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:35:32,293 INFO L134 CoverageAnalysis]: Checked inductivity of 172 backedges. 26 proven. 26 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2024-11-14 04:35:32,293 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:35:33,563 INFO L134 CoverageAnalysis]: Checked inductivity of 172 backedges. 26 proven. 26 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2024-11-14 04:35:33,563 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:35:33,563 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1787676299] [2024-11-14 04:35:33,563 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 04:35:33,563 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1210145353] [2024-11-14 04:35:33,563 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1210145353] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:35:33,564 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1476432401] [2024-11-14 04:35:33,565 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2024-11-14 04:35:33,565 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:35:33,566 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:35:33,567 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:35:33,567 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:35:35,111 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 04:35:35,122 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:35:36,225 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5574#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 04:35:36,225 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 04:35:36,225 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 04:35:36,225 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 16 [2024-11-14 04:35:36,225 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1972514656] [2024-11-14 04:35:36,225 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 04:35:36,226 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-14 04:35:36,226 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:35:36,226 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-14 04:35:36,227 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=104, Invalid=546, Unknown=0, NotChecked=0, Total=650 [2024-11-14 04:35:36,227 INFO L87 Difference]: Start difference. First operand 171 states and 189 transitions. Second operand has 16 states, 16 states have (on average 2.3125) internal successors, (37), 15 states have internal predecessors, (37), 8 states have call successors, (20), 3 states have call predecessors, (20), 2 states have return successors, (18), 6 states have call predecessors, (18), 8 states have call successors, (18) [2024-11-14 04:35:36,753 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:35:36,753 INFO L93 Difference]: Finished difference Result 204 states and 229 transitions. [2024-11-14 04:35:36,753 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-14 04:35:36,753 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 2.3125) internal successors, (37), 15 states have internal predecessors, (37), 8 states have call successors, (20), 3 states have call predecessors, (20), 2 states have return successors, (18), 6 states have call predecessors, (18), 8 states have call successors, (18) Word has length 61 [2024-11-14 04:35:36,754 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:35:36,755 INFO L225 Difference]: With dead ends: 204 [2024-11-14 04:35:36,755 INFO L226 Difference]: Without dead ends: 184 [2024-11-14 04:35:36,756 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 183 GetRequests, 155 SyntacticMatches, 2 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 207 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=126, Invalid=630, Unknown=0, NotChecked=0, Total=756 [2024-11-14 04:35:36,756 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 18 mSDsluCounter, 149 mSDsCounter, 0 mSdLazyCounter, 211 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 176 SdHoareTripleChecker+Invalid, 233 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 211 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-14 04:35:36,756 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 176 Invalid, 233 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 211 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-14 04:35:36,757 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2024-11-14 04:35:36,805 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 180. [2024-11-14 04:35:36,806 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 180 states, 119 states have (on average 1.1092436974789917) internal successors, (132), 124 states have internal predecessors, (132), 33 states have call successors, (33), 27 states have call predecessors, (33), 27 states have return successors, (31), 28 states have call predecessors, (31), 31 states have call successors, (31) [2024-11-14 04:35:36,807 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 180 states to 180 states and 196 transitions. [2024-11-14 04:35:36,808 INFO L78 Accepts]: Start accepts. Automaton has 180 states and 196 transitions. Word has length 61 [2024-11-14 04:35:36,808 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:35:36,808 INFO L471 AbstractCegarLoop]: Abstraction has 180 states and 196 transitions. [2024-11-14 04:35:36,808 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 2.3125) internal successors, (37), 15 states have internal predecessors, (37), 8 states have call successors, (20), 3 states have call predecessors, (20), 2 states have return successors, (18), 6 states have call predecessors, (18), 8 states have call successors, (18) [2024-11-14 04:35:36,809 INFO L276 IsEmpty]: Start isEmpty. Operand 180 states and 196 transitions. [2024-11-14 04:35:36,810 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2024-11-14 04:35:36,810 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:35:36,810 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:35:36,826 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-11-14 04:35:37,014 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-11-14 04:35:37,014 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:35:37,014 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:35:37,014 INFO L85 PathProgramCache]: Analyzing trace with hash 611197790, now seen corresponding path program 1 times [2024-11-14 04:35:37,014 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:35:37,014 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1051490239] [2024-11-14 04:35:37,014 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:37,014 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:35:37,040 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 04:35:37,042 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1388005524] [2024-11-14 04:35:37,042 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:37,042 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:35:37,042 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:35:37,045 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:35:37,047 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-14 04:35:37,114 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:37,115 INFO L255 TraceCheckSpWp]: Trace formula consists of 184 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-14 04:35:37,117 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:35:37,400 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 19 proven. 39 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2024-11-14 04:35:37,400 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:35:38,132 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 19 proven. 39 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2024-11-14 04:35:38,132 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:35:38,132 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1051490239] [2024-11-14 04:35:38,132 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 04:35:38,132 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1388005524] [2024-11-14 04:35:38,132 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1388005524] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:35:38,132 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [8651753] [2024-11-14 04:35:38,134 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2024-11-14 04:35:38,134 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:35:38,135 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:35:38,135 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:35:38,135 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:35:39,450 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 04:35:39,453 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:35:40,547 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '6602#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 04:35:40,547 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 04:35:40,547 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 04:35:40,547 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 19 [2024-11-14 04:35:40,547 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [829954706] [2024-11-14 04:35:40,547 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 04:35:40,548 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-14 04:35:40,548 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:35:40,549 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-14 04:35:40,549 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=139, Invalid=731, Unknown=0, NotChecked=0, Total=870 [2024-11-14 04:35:40,549 INFO L87 Difference]: Start difference. First operand 180 states and 196 transitions. Second operand has 19 states, 17 states have (on average 2.2941176470588234) internal successors, (39), 17 states have internal predecessors, (39), 11 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 8 states have call predecessors, (20), 9 states have call successors, (20) [2024-11-14 04:35:41,277 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:35:41,278 INFO L93 Difference]: Finished difference Result 201 states and 220 transitions. [2024-11-14 04:35:41,278 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-14 04:35:41,279 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 17 states have (on average 2.2941176470588234) internal successors, (39), 17 states have internal predecessors, (39), 11 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 8 states have call predecessors, (20), 9 states have call successors, (20) Word has length 67 [2024-11-14 04:35:41,279 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:35:41,282 INFO L225 Difference]: With dead ends: 201 [2024-11-14 04:35:41,282 INFO L226 Difference]: Without dead ends: 197 [2024-11-14 04:35:41,284 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 202 GetRequests, 169 SyntacticMatches, 2 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 301 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=179, Invalid=877, Unknown=0, NotChecked=0, Total=1056 [2024-11-14 04:35:41,284 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 23 mSDsluCounter, 216 mSDsCounter, 0 mSdLazyCounter, 240 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 243 SdHoareTripleChecker+Invalid, 276 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 240 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-14 04:35:41,284 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 243 Invalid, 276 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 240 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-14 04:35:41,285 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 197 states. [2024-11-14 04:35:41,339 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 197 to 178. [2024-11-14 04:35:41,339 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 178 states, 119 states have (on average 1.1092436974789917) internal successors, (132), 121 states have internal predecessors, (132), 32 states have call successors, (32), 27 states have call predecessors, (32), 26 states have return successors, (30), 29 states have call predecessors, (30), 30 states have call successors, (30) [2024-11-14 04:35:41,341 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 178 states to 178 states and 194 transitions. [2024-11-14 04:35:41,341 INFO L78 Accepts]: Start accepts. Automaton has 178 states and 194 transitions. Word has length 67 [2024-11-14 04:35:41,341 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:35:41,342 INFO L471 AbstractCegarLoop]: Abstraction has 178 states and 194 transitions. [2024-11-14 04:35:41,342 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 17 states have (on average 2.2941176470588234) internal successors, (39), 17 states have internal predecessors, (39), 11 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 8 states have call predecessors, (20), 9 states have call successors, (20) [2024-11-14 04:35:41,342 INFO L276 IsEmpty]: Start isEmpty. Operand 178 states and 194 transitions. [2024-11-14 04:35:41,343 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2024-11-14 04:35:41,343 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:35:41,343 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:35:41,357 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2024-11-14 04:35:41,544 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:35:41,544 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:35:41,544 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:35:41,544 INFO L85 PathProgramCache]: Analyzing trace with hash -542971976, now seen corresponding path program 1 times [2024-11-14 04:35:41,544 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:35:41,544 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1316543635] [2024-11-14 04:35:41,544 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:41,545 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:35:41,566 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:42,005 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-14 04:35:42,005 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:35:42,005 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1316543635] [2024-11-14 04:35:42,005 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1316543635] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 04:35:42,005 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1832112143] [2024-11-14 04:35:42,005 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:42,005 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:35:42,005 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:35:42,008 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:35:42,010 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-14 04:35:42,077 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:42,079 INFO L255 TraceCheckSpWp]: Trace formula consists of 193 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-14 04:35:42,081 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:35:42,267 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-14 04:35:42,267 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:35:42,805 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-14 04:35:42,805 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1832112143] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:35:42,805 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1347009353] [2024-11-14 04:35:42,807 INFO L159 IcfgInterpreter]: Started Sifa with 20 locations of interest [2024-11-14 04:35:42,807 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:35:42,807 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:35:42,808 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:35:42,808 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:35:43,921 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 04:35:43,924 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:35:44,989 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '7648#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 04:35:44,990 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 04:35:44,990 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 04:35:44,990 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 14 [2024-11-14 04:35:44,990 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1791319456] [2024-11-14 04:35:44,990 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 04:35:44,990 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-14 04:35:44,991 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:35:44,991 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-14 04:35:44,991 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=605, Unknown=0, NotChecked=0, Total=702 [2024-11-14 04:35:44,992 INFO L87 Difference]: Start difference. First operand 178 states and 194 transitions. Second operand has 14 states, 13 states have (on average 3.6153846153846154) internal successors, (47), 12 states have internal predecessors, (47), 8 states have call successors, (35), 3 states have call predecessors, (35), 1 states have return successors, (32), 8 states have call predecessors, (32), 8 states have call successors, (32) [2024-11-14 04:35:45,230 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:35:45,230 INFO L93 Difference]: Finished difference Result 191 states and 209 transitions. [2024-11-14 04:35:45,231 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-14 04:35:45,231 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 3.6153846153846154) internal successors, (47), 12 states have internal predecessors, (47), 8 states have call successors, (35), 3 states have call predecessors, (35), 1 states have return successors, (32), 8 states have call predecessors, (32), 8 states have call successors, (32) Word has length 72 [2024-11-14 04:35:45,231 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:35:45,232 INFO L225 Difference]: With dead ends: 191 [2024-11-14 04:35:45,232 INFO L226 Difference]: Without dead ends: 147 [2024-11-14 04:35:45,233 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 225 GetRequests, 193 SyntacticMatches, 4 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 243 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=121, Invalid=749, Unknown=0, NotChecked=0, Total=870 [2024-11-14 04:35:45,233 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 15 mSDsluCounter, 211 mSDsCounter, 0 mSdLazyCounter, 123 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 250 SdHoareTripleChecker+Invalid, 137 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 123 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 04:35:45,233 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 250 Invalid, 137 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 123 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 04:35:45,234 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 147 states. [2024-11-14 04:35:45,267 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 147 to 144. [2024-11-14 04:35:45,268 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 144 states, 96 states have (on average 1.09375) internal successors, (105), 98 states have internal predecessors, (105), 26 states have call successors, (26), 21 states have call predecessors, (26), 21 states have return successors, (25), 24 states have call predecessors, (25), 25 states have call successors, (25) [2024-11-14 04:35:45,268 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 144 states to 144 states and 156 transitions. [2024-11-14 04:35:45,268 INFO L78 Accepts]: Start accepts. Automaton has 144 states and 156 transitions. Word has length 72 [2024-11-14 04:35:45,269 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:35:45,269 INFO L471 AbstractCegarLoop]: Abstraction has 144 states and 156 transitions. [2024-11-14 04:35:45,269 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 3.6153846153846154) internal successors, (47), 12 states have internal predecessors, (47), 8 states have call successors, (35), 3 states have call predecessors, (35), 1 states have return successors, (32), 8 states have call predecessors, (32), 8 states have call successors, (32) [2024-11-14 04:35:45,269 INFO L276 IsEmpty]: Start isEmpty. Operand 144 states and 156 transitions. [2024-11-14 04:35:45,270 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2024-11-14 04:35:45,270 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:35:45,270 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 5, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:35:45,286 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-14 04:35:45,470 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2024-11-14 04:35:45,471 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:35:45,471 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:35:45,471 INFO L85 PathProgramCache]: Analyzing trace with hash 429788365, now seen corresponding path program 1 times [2024-11-14 04:35:45,471 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:35:45,471 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1590010837] [2024-11-14 04:35:45,471 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:45,471 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:35:45,485 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:45,700 INFO L134 CoverageAnalysis]: Checked inductivity of 382 backedges. 26 proven. 44 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2024-11-14 04:35:45,700 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:35:45,700 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1590010837] [2024-11-14 04:35:45,701 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1590010837] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 04:35:45,701 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2123774133] [2024-11-14 04:35:45,701 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:45,701 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:35:45,701 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:35:45,703 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:35:45,706 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-14 04:35:45,781 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:45,783 INFO L255 TraceCheckSpWp]: Trace formula consists of 227 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-14 04:35:45,785 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:35:45,910 INFO L134 CoverageAnalysis]: Checked inductivity of 382 backedges. 72 proven. 260 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2024-11-14 04:35:45,910 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:35:46,043 INFO L134 CoverageAnalysis]: Checked inductivity of 382 backedges. 26 proven. 44 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2024-11-14 04:35:46,044 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2123774133] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:35:46,044 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [860938965] [2024-11-14 04:35:46,045 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2024-11-14 04:35:46,046 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:35:46,047 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:35:46,047 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:35:46,047 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:35:47,151 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2024-11-14 04:35:47,161 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:35:48,286 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '8708#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-14 04:35:48,286 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 04:35:48,287 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 04:35:48,287 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 8] total 10 [2024-11-14 04:35:48,287 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [377283981] [2024-11-14 04:35:48,287 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 04:35:48,287 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-14 04:35:48,287 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:35:48,288 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-14 04:35:48,288 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=370, Unknown=0, NotChecked=0, Total=462 [2024-11-14 04:35:48,289 INFO L87 Difference]: Start difference. First operand 144 states and 156 transitions. Second operand has 10 states, 10 states have (on average 4.0) internal successors, (40), 10 states have internal predecessors, (40), 5 states have call successors, (27), 6 states have call predecessors, (27), 6 states have return successors, (26), 5 states have call predecessors, (26), 5 states have call successors, (26) [2024-11-14 04:35:48,462 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:35:48,463 INFO L93 Difference]: Finished difference Result 190 states and 209 transitions. [2024-11-14 04:35:48,463 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-14 04:35:48,463 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 4.0) internal successors, (40), 10 states have internal predecessors, (40), 5 states have call successors, (27), 6 states have call predecessors, (27), 6 states have return successors, (26), 5 states have call predecessors, (26), 5 states have call successors, (26) Word has length 86 [2024-11-14 04:35:48,464 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:35:48,465 INFO L225 Difference]: With dead ends: 190 [2024-11-14 04:35:48,465 INFO L226 Difference]: Without dead ends: 146 [2024-11-14 04:35:48,466 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 268 GetRequests, 239 SyntacticMatches, 6 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 173 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=113, Invalid=487, Unknown=0, NotChecked=0, Total=600 [2024-11-14 04:35:48,466 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 8 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 73 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 122 SdHoareTripleChecker+Invalid, 74 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 73 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 04:35:48,467 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 122 Invalid, 74 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 73 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 04:35:48,467 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 146 states. [2024-11-14 04:35:48,502 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 146 to 146. [2024-11-14 04:35:48,503 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 146 states, 98 states have (on average 1.0918367346938775) internal successors, (107), 100 states have internal predecessors, (107), 26 states have call successors, (26), 21 states have call predecessors, (26), 21 states have return successors, (25), 24 states have call predecessors, (25), 25 states have call successors, (25) [2024-11-14 04:35:48,504 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 146 states to 146 states and 158 transitions. [2024-11-14 04:35:48,504 INFO L78 Accepts]: Start accepts. Automaton has 146 states and 158 transitions. Word has length 86 [2024-11-14 04:35:48,504 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:35:48,504 INFO L471 AbstractCegarLoop]: Abstraction has 146 states and 158 transitions. [2024-11-14 04:35:48,504 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 4.0) internal successors, (40), 10 states have internal predecessors, (40), 5 states have call successors, (27), 6 states have call predecessors, (27), 6 states have return successors, (26), 5 states have call predecessors, (26), 5 states have call successors, (26) [2024-11-14 04:35:48,504 INFO L276 IsEmpty]: Start isEmpty. Operand 146 states and 158 transitions. [2024-11-14 04:35:48,505 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2024-11-14 04:35:48,505 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:35:48,506 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2024-11-14 04:35:48,519 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-14 04:35:48,706 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2024-11-14 04:35:48,706 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:35:48,707 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:35:48,707 INFO L85 PathProgramCache]: Analyzing trace with hash 1274522042, now seen corresponding path program 1 times [2024-11-14 04:35:48,707 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:35:48,707 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1494215642] [2024-11-14 04:35:48,707 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:48,707 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:35:48,741 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 04:35:48,742 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [544822213] [2024-11-14 04:35:48,743 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:48,743 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:35:48,743 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:35:48,746 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:35:48,748 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-14 04:35:48,834 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:48,836 INFO L255 TraceCheckSpWp]: Trace formula consists of 230 conjuncts, 40 conjuncts are in the unsatisfiable core [2024-11-14 04:35:48,839 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:35:49,262 INFO L134 CoverageAnalysis]: Checked inductivity of 365 backedges. 25 proven. 64 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2024-11-14 04:35:49,262 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:37:04,953 INFO L134 CoverageAnalysis]: Checked inductivity of 365 backedges. 25 proven. 64 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2024-11-14 04:37:04,953 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:37:04,953 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1494215642] [2024-11-14 04:37:04,953 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 04:37:04,953 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [544822213] [2024-11-14 04:37:04,953 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [544822213] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:37:04,953 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1738509191] [2024-11-14 04:37:04,955 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2024-11-14 04:37:04,955 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:37:04,955 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:37:04,955 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:37:04,955 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:37:06,270 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 04:37:06,273 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:37:07,582 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '9781#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 04:37:07,582 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 04:37:07,583 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 04:37:07,583 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 19 [2024-11-14 04:37:07,583 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1727239249] [2024-11-14 04:37:07,583 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 04:37:07,583 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-14 04:37:07,583 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:37:07,584 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-14 04:37:07,584 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=770, Unknown=0, NotChecked=0, Total=870 [2024-11-14 04:37:07,584 INFO L87 Difference]: Start difference. First operand 146 states and 158 transitions. Second operand has 19 states, 19 states have (on average 2.5789473684210527) internal successors, (49), 17 states have internal predecessors, (49), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 8 states have call predecessors, (26), 9 states have call successors, (26) [2024-11-14 04:37:10,312 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:37:10,312 INFO L93 Difference]: Finished difference Result 174 states and 199 transitions. [2024-11-14 04:37:10,313 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-14 04:37:10,313 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 2.5789473684210527) internal successors, (49), 17 states have internal predecessors, (49), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 8 states have call predecessors, (26), 9 states have call successors, (26) Word has length 87 [2024-11-14 04:37:10,313 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:37:10,315 INFO L225 Difference]: With dead ends: 174 [2024-11-14 04:37:10,315 INFO L226 Difference]: Without dead ends: 172 [2024-11-14 04:37:10,315 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 264 GetRequests, 229 SyntacticMatches, 2 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 261 ImplicationChecksByTransitivity, 8.3s TimeCoverageRelationStatistics Valid=135, Invalid=1055, Unknown=0, NotChecked=0, Total=1190 [2024-11-14 04:37:10,316 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 26 mSDsluCounter, 364 mSDsCounter, 0 mSdLazyCounter, 364 mSolverCounterSat, 42 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 400 SdHoareTripleChecker+Invalid, 406 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 42 IncrementalHoareTripleChecker+Valid, 364 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2024-11-14 04:37:10,316 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 400 Invalid, 406 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [42 Valid, 364 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2024-11-14 04:37:10,317 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 172 states. [2024-11-14 04:37:10,370 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 172 to 154. [2024-11-14 04:37:10,371 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 154 states, 102 states have (on average 1.107843137254902) internal successors, (113), 104 states have internal predecessors, (113), 30 states have call successors, (30), 21 states have call predecessors, (30), 21 states have return successors, (29), 28 states have call predecessors, (29), 29 states have call successors, (29) [2024-11-14 04:37:10,372 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 154 states to 154 states and 172 transitions. [2024-11-14 04:37:10,372 INFO L78 Accepts]: Start accepts. Automaton has 154 states and 172 transitions. Word has length 87 [2024-11-14 04:37:10,373 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:37:10,373 INFO L471 AbstractCegarLoop]: Abstraction has 154 states and 172 transitions. [2024-11-14 04:37:10,373 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 2.5789473684210527) internal successors, (49), 17 states have internal predecessors, (49), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 8 states have call predecessors, (26), 9 states have call successors, (26) [2024-11-14 04:37:10,373 INFO L276 IsEmpty]: Start isEmpty. Operand 154 states and 172 transitions. [2024-11-14 04:37:10,374 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2024-11-14 04:37:10,374 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:37:10,375 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1] [2024-11-14 04:37:10,392 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-11-14 04:37:10,575 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2024-11-14 04:37:10,575 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:37:10,576 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:37:10,576 INFO L85 PathProgramCache]: Analyzing trace with hash 1276249920, now seen corresponding path program 3 times [2024-11-14 04:37:10,576 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:37:10,576 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [861726504] [2024-11-14 04:37:10,576 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:37:10,576 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:37:10,591 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:37:10,836 INFO L134 CoverageAnalysis]: Checked inductivity of 367 backedges. 49 proven. 6 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2024-11-14 04:37:10,837 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:37:10,837 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [861726504] [2024-11-14 04:37:10,837 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [861726504] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 04:37:10,837 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1207041567] [2024-11-14 04:37:10,837 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-14 04:37:10,837 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:37:10,837 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:37:10,839 INFO L229 MonitoredProcess]: Starting monitored process 15 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:37:10,841 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-14 04:37:10,958 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-14 04:37:10,958 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 04:37:10,964 INFO L255 TraceCheckSpWp]: Trace formula consists of 181 conjuncts, 62 conjuncts are in the unsatisfiable core [2024-11-14 04:37:10,967 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:37:18,173 INFO L134 CoverageAnalysis]: Checked inductivity of 367 backedges. 128 proven. 53 refuted. 0 times theorem prover too weak. 186 trivial. 0 not checked. [2024-11-14 04:37:18,173 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:37:52,970 WARN L286 SmtUtils]: Spent 9.68s on a formula simplification that was a NOOP. DAG size: 122 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 04:38:40,398 WARN L286 SmtUtils]: Spent 7.97s on a formula simplification that was a NOOP. DAG size: 114 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 04:40:17,337 INFO L134 CoverageAnalysis]: Checked inductivity of 367 backedges. 113 proven. 32 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2024-11-14 04:40:17,337 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1207041567] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:40:17,337 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [664006495] [2024-11-14 04:40:17,338 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2024-11-14 04:40:17,338 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:40:17,338 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:40:17,338 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:40:17,338 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:40:18,457 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 04:40:18,460 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:40:20,124 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '10862#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 04:40:20,124 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 04:40:20,124 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 04:40:20,124 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 14, 14] total 33 [2024-11-14 04:40:20,124 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1316688841] [2024-11-14 04:40:20,124 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 04:40:20,125 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2024-11-14 04:40:20,125 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:40:20,125 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2024-11-14 04:40:20,126 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=254, Invalid=1551, Unknown=1, NotChecked=0, Total=1806 [2024-11-14 04:40:20,126 INFO L87 Difference]: Start difference. First operand 154 states and 172 transitions. Second operand has 33 states, 32 states have (on average 2.0625) internal successors, (66), 25 states have internal predecessors, (66), 22 states have call successors, (39), 4 states have call predecessors, (39), 2 states have return successors, (37), 16 states have call predecessors, (37), 19 states have call successors, (37) [2024-11-14 04:40:39,319 WARN L286 SmtUtils]: Spent 18.71s on a formula simplification. DAG size of input: 171 DAG size of output: 101 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 04:40:59,862 WARN L286 SmtUtils]: Spent 19.63s on a formula simplification. DAG size of input: 173 DAG size of output: 103 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 04:41:23,260 WARN L286 SmtUtils]: Spent 22.91s on a formula simplification. DAG size of input: 171 DAG size of output: 101 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 04:41:25,210 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.05s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 04:41:27,231 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.32s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 04:41:34,140 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.27s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 04:41:43,120 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.38s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 04:41:52,587 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-14 04:42:33,192 WARN L286 SmtUtils]: Spent 31.48s on a formula simplification. DAG size of input: 185 DAG size of output: 123 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 04:42:43,759 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:42:43,759 INFO L93 Difference]: Finished difference Result 198 states and 217 transitions. [2024-11-14 04:42:43,759 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2024-11-14 04:42:43,759 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 32 states have (on average 2.0625) internal successors, (66), 25 states have internal predecessors, (66), 22 states have call successors, (39), 4 states have call predecessors, (39), 2 states have return successors, (37), 16 states have call predecessors, (37), 19 states have call successors, (37) Word has length 87 [2024-11-14 04:42:43,759 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:42:43,760 INFO L225 Difference]: With dead ends: 198 [2024-11-14 04:42:43,760 INFO L226 Difference]: Without dead ends: 151 [2024-11-14 04:42:43,762 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 312 GetRequests, 228 SyntacticMatches, 4 SemanticMatches, 80 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1781 ImplicationChecksByTransitivity, 167.9s TimeCoverageRelationStatistics Valid=918, Invalid=5723, Unknown=1, NotChecked=0, Total=6642 [2024-11-14 04:42:43,763 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 93 mSDsluCounter, 459 mSDsCounter, 0 mSdLazyCounter, 1062 mSolverCounterSat, 103 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 19.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 93 SdHoareTripleChecker+Valid, 505 SdHoareTripleChecker+Invalid, 1166 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 103 IncrementalHoareTripleChecker+Valid, 1062 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 19.7s IncrementalHoareTripleChecker+Time [2024-11-14 04:42:43,763 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [93 Valid, 505 Invalid, 1166 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [103 Valid, 1062 Invalid, 1 Unknown, 0 Unchecked, 19.7s Time] [2024-11-14 04:42:43,764 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 151 states. [2024-11-14 04:42:43,820 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 151 to 139. [2024-11-14 04:42:43,821 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 139 states, 94 states have (on average 1.0425531914893618) internal successors, (98), 95 states have internal predecessors, (98), 24 states have call successors, (24), 21 states have call predecessors, (24), 20 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-11-14 04:42:43,822 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 144 transitions. [2024-11-14 04:42:43,822 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 144 transitions. Word has length 87 [2024-11-14 04:42:43,822 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:42:43,822 INFO L471 AbstractCegarLoop]: Abstraction has 139 states and 144 transitions. [2024-11-14 04:42:43,823 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 32 states have (on average 2.0625) internal successors, (66), 25 states have internal predecessors, (66), 22 states have call successors, (39), 4 states have call predecessors, (39), 2 states have return successors, (37), 16 states have call predecessors, (37), 19 states have call successors, (37) [2024-11-14 04:42:43,823 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 144 transitions. [2024-11-14 04:42:43,824 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2024-11-14 04:42:43,824 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:42:43,824 INFO L215 NwaCegarLoop]: trace histogram [15, 14, 14, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:42:43,842 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2024-11-14 04:42:44,027 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,15 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:42:44,027 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:42:44,027 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:42:44,027 INFO L85 PathProgramCache]: Analyzing trace with hash 1276836572, now seen corresponding path program 1 times [2024-11-14 04:42:44,027 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:42:44,027 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [121508468] [2024-11-14 04:42:44,027 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:42:44,027 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:42:44,078 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:42:44,500 INFO L134 CoverageAnalysis]: Checked inductivity of 419 backedges. 28 proven. 27 refuted. 0 times theorem prover too weak. 364 trivial. 0 not checked. [2024-11-14 04:42:44,501 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:42:44,501 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [121508468] [2024-11-14 04:42:44,501 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [121508468] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 04:42:44,501 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1225202825] [2024-11-14 04:42:44,501 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:42:44,501 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:42:44,501 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:42:44,503 INFO L229 MonitoredProcess]: Starting monitored process 16 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:42:44,506 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-14 04:42:44,579 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:42:44,581 INFO L255 TraceCheckSpWp]: Trace formula consists of 239 conjuncts, 33 conjuncts are in the unsatisfiable core [2024-11-14 04:42:44,583 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:42:44,862 INFO L134 CoverageAnalysis]: Checked inductivity of 419 backedges. 27 proven. 67 refuted. 0 times theorem prover too weak. 325 trivial. 0 not checked. [2024-11-14 04:42:44,862 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:42:45,874 INFO L134 CoverageAnalysis]: Checked inductivity of 419 backedges. 27 proven. 67 refuted. 0 times theorem prover too weak. 325 trivial. 0 not checked. [2024-11-14 04:42:45,874 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1225202825] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 04:42:45,874 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [438518785] [2024-11-14 04:42:45,875 INFO L159 IcfgInterpreter]: Started Sifa with 20 locations of interest [2024-11-14 04:42:45,875 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:42:45,875 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:42:45,876 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:42:45,876 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:42:47,318 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2024-11-14 04:42:47,323 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:42:48,771 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '12042#(= |__VERIFIER_assert_#in~cond| 0)' at error location [2024-11-14 04:42:48,771 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 04:42:48,772 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 04:42:48,772 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 12, 9] total 19 [2024-11-14 04:42:48,772 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [281308176] [2024-11-14 04:42:48,772 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 04:42:48,772 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-14 04:42:48,773 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:42:48,773 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-14 04:42:48,774 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=830, Unknown=0, NotChecked=0, Total=930 [2024-11-14 04:42:48,774 INFO L87 Difference]: Start difference. First operand 139 states and 144 transitions. Second operand has 19 states, 19 states have (on average 3.263157894736842) internal successors, (62), 17 states have internal predecessors, (62), 11 states have call successors, (42), 3 states have call predecessors, (42), 2 states have return successors, (39), 9 states have call predecessors, (39), 11 states have call successors, (39) [2024-11-14 04:42:49,192 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:42:49,192 INFO L93 Difference]: Finished difference Result 151 states and 155 transitions. [2024-11-14 04:42:49,193 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-14 04:42:49,193 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 3.263157894736842) internal successors, (62), 17 states have internal predecessors, (62), 11 states have call successors, (42), 3 states have call predecessors, (42), 2 states have return successors, (39), 9 states have call predecessors, (39), 11 states have call successors, (39) Word has length 92 [2024-11-14 04:42:49,194 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:42:49,194 INFO L225 Difference]: With dead ends: 151 [2024-11-14 04:42:49,195 INFO L226 Difference]: Without dead ends: 117 [2024-11-14 04:42:49,195 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 284 GetRequests, 252 SyntacticMatches, 2 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 298 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=108, Invalid=884, Unknown=0, NotChecked=0, Total=992 [2024-11-14 04:42:49,196 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 7 mSDsluCounter, 247 mSDsCounter, 0 mSdLazyCounter, 296 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 277 SdHoareTripleChecker+Invalid, 304 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 296 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-14 04:42:49,196 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 277 Invalid, 304 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 296 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-14 04:42:49,199 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2024-11-14 04:42:49,276 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 117. [2024-11-14 04:42:49,277 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 117 states, 79 states have (on average 1.0379746835443038) internal successors, (82), 80 states have internal predecessors, (82), 20 states have call successors, (20), 18 states have call predecessors, (20), 17 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2024-11-14 04:42:49,278 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 117 states to 117 states and 120 transitions. [2024-11-14 04:42:49,280 INFO L78 Accepts]: Start accepts. Automaton has 117 states and 120 transitions. Word has length 92 [2024-11-14 04:42:49,280 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:42:49,281 INFO L471 AbstractCegarLoop]: Abstraction has 117 states and 120 transitions. [2024-11-14 04:42:49,281 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 3.263157894736842) internal successors, (62), 17 states have internal predecessors, (62), 11 states have call successors, (42), 3 states have call predecessors, (42), 2 states have return successors, (39), 9 states have call predecessors, (39), 11 states have call successors, (39) [2024-11-14 04:42:49,281 INFO L276 IsEmpty]: Start isEmpty. Operand 117 states and 120 transitions. [2024-11-14 04:42:49,282 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2024-11-14 04:42:49,282 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:42:49,282 INFO L215 NwaCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:42:49,304 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2024-11-14 04:42:49,483 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,16 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:42:49,483 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:42:49,483 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:42:49,484 INFO L85 PathProgramCache]: Analyzing trace with hash 1798302213, now seen corresponding path program 2 times [2024-11-14 04:42:49,484 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:42:49,484 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [88757266] [2024-11-14 04:42:49,484 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:42:49,484 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:42:49,520 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 04:42:49,529 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1934440638] [2024-11-14 04:42:49,529 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 04:42:49,529 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:42:49,529 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:42:49,538 INFO L229 MonitoredProcess]: Starting monitored process 17 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:42:49,539 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-11-14 04:42:49,675 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-11-14 04:42:49,675 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-14 04:42:49,675 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-14 04:42:49,704 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-14 04:42:49,740 INFO L130 FreeRefinementEngine]: Strategy SIFA_TAIPAN found a feasible trace [2024-11-14 04:42:49,740 INFO L325 BasicCegarLoop]: Counterexample is feasible [2024-11-14 04:42:49,741 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-14 04:42:49,762 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2024-11-14 04:42:49,943 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable20 [2024-11-14 04:42:49,946 INFO L407 BasicCegarLoop]: Path program histogram: [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:42:49,984 INFO L173 ceAbstractionStarter]: Computing trace abstraction results [2024-11-14 04:42:49,988 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 14.11 04:42:49 BoogieIcfgContainer [2024-11-14 04:42:49,988 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-14 04:42:49,988 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-14 04:42:49,988 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-14 04:42:49,989 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-14 04:42:49,989 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 04:35:07" (3/4) ... [2024-11-14 04:42:49,990 INFO L136 WitnessPrinter]: Generating witness for reachability counterexample [2024-11-14 04:42:50,077 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/witness.graphml [2024-11-14 04:42:50,077 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-14 04:42:50,078 INFO L158 Benchmark]: Toolchain (without parser) took 463383.17ms. Allocated memory was 117.4MB in the beginning and 981.5MB in the end (delta: 864.0MB). Free memory was 92.4MB in the beginning and 843.4MB in the end (delta: -751.0MB). Peak memory consumption was 112.9MB. Max. memory is 16.1GB. [2024-11-14 04:42:50,079 INFO L158 Benchmark]: CDTParser took 0.41ms. Allocated memory is still 117.4MB. Free memory is still 72.6MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 04:42:50,079 INFO L158 Benchmark]: CACSL2BoogieTranslator took 313.40ms. Allocated memory is still 117.4MB. Free memory was 92.4MB in the beginning and 81.2MB in the end (delta: 11.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-14 04:42:50,081 INFO L158 Benchmark]: Boogie Procedure Inliner took 43.72ms. Allocated memory is still 117.4MB. Free memory was 81.2MB in the beginning and 79.9MB in the end (delta: 1.4MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 04:42:50,081 INFO L158 Benchmark]: Boogie Preprocessor took 32.54ms. Allocated memory is still 117.4MB. Free memory was 79.9MB in the beginning and 79.3MB in the end (delta: 606.6kB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-14 04:42:50,081 INFO L158 Benchmark]: RCFGBuilder took 461.47ms. Allocated memory is still 117.4MB. Free memory was 79.0MB in the beginning and 66.7MB in the end (delta: 12.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-14 04:42:50,083 INFO L158 Benchmark]: TraceAbstraction took 462435.37ms. Allocated memory was 117.4MB in the beginning and 981.5MB in the end (delta: 864.0MB). Free memory was 66.2MB in the beginning and 847.7MB in the end (delta: -781.6MB). Peak memory consumption was 79.4MB. Max. memory is 16.1GB. [2024-11-14 04:42:50,084 INFO L158 Benchmark]: Witness Printer took 88.68ms. Allocated memory is still 981.5MB. Free memory was 847.7MB in the beginning and 843.4MB in the end (delta: 4.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-14 04:42:50,085 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.41ms. Allocated memory is still 117.4MB. Free memory is still 72.6MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 313.40ms. Allocated memory is still 117.4MB. Free memory was 92.4MB in the beginning and 81.2MB in the end (delta: 11.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 43.72ms. Allocated memory is still 117.4MB. Free memory was 81.2MB in the beginning and 79.9MB in the end (delta: 1.4MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 32.54ms. Allocated memory is still 117.4MB. Free memory was 79.9MB in the beginning and 79.3MB in the end (delta: 606.6kB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * RCFGBuilder took 461.47ms. Allocated memory is still 117.4MB. Free memory was 79.0MB in the beginning and 66.7MB in the end (delta: 12.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * TraceAbstraction took 462435.37ms. Allocated memory was 117.4MB in the beginning and 981.5MB in the end (delta: 864.0MB). Free memory was 66.2MB in the beginning and 847.7MB in the end (delta: -781.6MB). Peak memory consumption was 79.4MB. Max. memory is 16.1GB. * Witness Printer took 88.68ms. Allocated memory is still 981.5MB. Free memory was 847.7MB in the beginning and 843.4MB 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 - CounterExampleResult [Line: 17]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L22] int counter = 0; [L24] int A, B; [L25] int r, d, p, q; [L26] A = __VERIFIER_nondet_int() [L27] B = 1 [L29] r = A [L30] d = B [L31] p = 1 [L32] q = 0 VAL [A=4, B=1, counter=0, d=1, p=1, q=0, r=4] [L34] EXPR counter++ VAL [A=4, B=1, counter=1, d=1, p=1, q=0, r=4] [L34] COND TRUE counter++<5 [L35] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=1] [L35] RET __VERIFIER_assert(q == 0) VAL [A=4, B=1, counter=1, d=1, p=1, q=0, r=4] [L36] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=1] [L36] RET __VERIFIER_assert(r == A) VAL [A=4, B=1, counter=1, d=1, p=1, q=0, r=4] [L37] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=1] [L37] RET __VERIFIER_assert(d == B * p) VAL [A=4, B=1, counter=1, d=1, p=1, q=0, r=4] [L38] COND FALSE !(!(r >= d)) [L40] d = 2 * d [L41] p = 2 * p VAL [A=4, B=1, counter=1, d=2, p=2, q=0, r=4] [L34] EXPR counter++ VAL [A=4, B=1, counter=2, d=2, p=2, q=0, r=4] [L34] COND TRUE counter++<5 [L35] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=2] [L35] RET __VERIFIER_assert(q == 0) VAL [A=4, B=1, counter=2, d=2, p=2, q=0, r=4] [L36] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=2] [L36] RET __VERIFIER_assert(r == A) VAL [A=4, B=1, counter=2, d=2, p=2, q=0, r=4] [L37] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=2] [L37] RET __VERIFIER_assert(d == B * p) VAL [A=4, B=1, counter=2, d=2, p=2, q=0, r=4] [L38] COND FALSE !(!(r >= d)) [L40] d = 2 * d [L41] p = 2 * p VAL [A=4, B=1, counter=2, d=4, p=4, q=0, r=4] [L34] EXPR counter++ VAL [A=4, B=1, counter=3, d=4, p=4, q=0, r=4] [L34] COND TRUE counter++<5 [L35] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=3] [L35] RET __VERIFIER_assert(q == 0) VAL [A=4, B=1, counter=3, d=4, p=4, q=0, r=4] [L36] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=3] [L36] RET __VERIFIER_assert(r == A) VAL [A=4, B=1, counter=3, d=4, p=4, q=0, r=4] [L37] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=3] [L37] RET __VERIFIER_assert(d == B * p) VAL [A=4, B=1, counter=3, d=4, p=4, q=0, r=4] [L38] COND FALSE !(!(r >= d)) [L40] d = 2 * d [L41] p = 2 * p VAL [A=4, B=1, counter=3, d=8, p=8, q=0, r=4] [L34] EXPR counter++ VAL [A=4, B=1, counter=4, d=8, p=8, q=0, r=4] [L34] COND TRUE counter++<5 [L35] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=4] [L35] RET __VERIFIER_assert(q == 0) VAL [A=4, B=1, counter=4, d=8, p=8, q=0, r=4] [L36] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=4] [L36] RET __VERIFIER_assert(r == A) VAL [A=4, B=1, counter=4, d=8, p=8, q=0, r=4] [L37] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=4] [L37] RET __VERIFIER_assert(d == B * p) VAL [A=4, B=1, counter=4, d=8, p=8, q=0, r=4] [L38] COND TRUE !(r >= d) VAL [A=4, B=1, counter=4, d=8, p=8, q=0, r=4] [L44] EXPR counter++ VAL [A=4, B=1, counter=5, d=8, p=8, q=0, r=4] [L44] COND TRUE counter++<5 [L45] CALL __VERIFIER_assert(A == q*B + r) VAL [\old(cond)=1, counter=5] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=5] [L45] RET __VERIFIER_assert(A == q*B + r) VAL [A=4, B=1, counter=5, d=8, p=8, q=0, r=4] [L46] CALL __VERIFIER_assert(d == B*p) VAL [\old(cond)=1, counter=5] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=5] [L46] RET __VERIFIER_assert(d == B*p) VAL [A=4, B=1, counter=5, d=8, p=8, q=0, r=4] [L48] COND FALSE !(!(p != 1)) [L50] d = d / 2 [L51] p = p / 2 [L52] COND TRUE r >= d [L53] r = r - d [L54] q = q + p VAL [A=4, B=1, counter=5, d=4, p=4, q=4, r=0] [L44] EXPR counter++ VAL [A=4, B=1, counter=6, d=4, p=4, q=4, r=0] [L44] COND FALSE !(counter++<5) [L58] CALL __VERIFIER_assert(A == d*q + r) VAL [\old(cond)=0, counter=6] [L15] COND TRUE !(cond) VAL [\old(cond)=0, counter=6] [L17] reach_error() VAL [\old(cond)=0, counter=6] - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 22 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 462.3s, OverallIterations: 21, TraceHistogramMax: 15, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 151.0s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 1 mSolverCounterUnknown, 406 SdHoareTripleChecker+Valid, 23.4s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 355 mSDsluCounter, 3136 SdHoareTripleChecker+Invalid, 22.9s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2609 mSDsCounter, 283 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 3223 IncrementalHoareTripleChecker+Invalid, 3507 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 283 mSolverCounterUnsat, 527 mSDtfsCounter, 3223 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 2461 GetRequests, 2042 SyntacticMatches, 38 SemanticMatches, 381 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3895 ImplicationChecksByTransitivity, 190.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=180occurred in iteration=14, InterpolantAutomatonStates: 210, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.6s AutomataMinimizationTime, 20 MinimizatonAttempts, 97 StatesRemovedByMinimization, 13 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.2s SsaConstructionTime, 0.9s SatisfiabilityAnalysisTime, 274.8s InterpolantComputationTime, 1912 NumberOfCodeBlocks, 1883 NumberOfCodeBlocksAsserted, 44 NumberOfCheckSat, 2036 ConstructedInterpolants, 0 QuantifiedInterpolants, 42394 SizeOfPredicates, 34 NumberOfNonLiveVariables, 2336 ConjunctsInSsa, 324 ConjunctsInUnsatCore, 39 InterpolantComputations, 8 PerfectInterpolantSequences, 5665/6679 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: OVERALL_TIME: 1.7s, ICFG_INTERPRETER_ENTERED_PROCEDURES: 4, DAG_INTERPRETER_EARLY_EXIT_QUERIES_NONTRIVIAL: 39, DAG_INTERPRETER_EARLY_EXITS: 2, TOOLS_POST_APPLICATIONS: 27, TOOLS_POST_TIME: 0.3s, TOOLS_POST_CALL_APPLICATIONS: 26, TOOLS_POST_CALL_TIME: 0.5s, TOOLS_POST_RETURN_APPLICATIONS: 16, TOOLS_POST_RETURN_TIME: 0.3s, TOOLS_QUANTIFIERELIM_APPLICATIONS: 69, TOOLS_QUANTIFIERELIM_TIME: 1.0s, TOOLS_QUANTIFIERELIM_MAX_TIME: 0.0s, FLUID_QUERY_TIME: 0.0s, FLUID_QUERIES: 92, FLUID_YES_ANSWERS: 0, DOMAIN_JOIN_APPLICATIONS: 34, DOMAIN_JOIN_TIME: 0.5s, DOMAIN_ALPHA_APPLICATIONS: 0, DOMAIN_ALPHA_TIME: 0.0s, DOMAIN_WIDEN_APPLICATIONS: 0, DOMAIN_WIDEN_TIME: 0.0s, DOMAIN_ISSUBSETEQ_APPLICATIONS: 0, DOMAIN_ISSUBSETEQ_TIME: 0.0s, DOMAIN_ISBOTTOM_APPLICATIONS: 39, DOMAIN_ISBOTTOM_TIME: 0.1s, LOOP_SUMMARIZER_APPLICATIONS: 0, LOOP_SUMMARIZER_CACHE_MISSES: 0, LOOP_SUMMARIZER_OVERALL_TIME: 0.0s, LOOP_SUMMARIZER_NEW_COMPUTATION_TIME: 0.0s, LOOP_SUMMARIZER_FIXPOINT_ITERATIONS: 0, CALL_SUMMARIZER_APPLICATIONS: 16, CALL_SUMMARIZER_CACHE_MISSES: 2, CALL_SUMMARIZER_OVERALL_TIME: 0.0s, CALL_SUMMARIZER_NEW_COMPUTATION_TIME: 0.0s, PROCEDURE_GRAPH_BUILDER_TIME: 0.0s, PATH_EXPR_TIME: 0.0s, REGEX_TO_DAG_TIME: 0.0s, DAG_COMPRESSION_TIME: 0.0s, DAG_COMPRESSION_PROCESSED_NODES: 408, DAG_COMPRESSION_RETAINED_NODES: 100, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2024-11-14 04:42:50,306 WARN L435 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forcibly destroying the process [2024-11-14 04:42:50,346 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e48d3106-b77b-4b24-a7c4-12be3d0a049f/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 137 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Writing human readable error path to file UltimateCounterExample.errorpath Result: FALSE