./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/ps4-ll_unwindbound100.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_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/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_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/ps4-ll_unwindbound100.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/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_822c0387-2888-4052-afd6-604797d4ea01/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 47fbdb3da16165eeeef0687b73275c90a2682f5a520ac2387154637187559fe6 --- Real Ultimate output --- This is Ultimate 0.3.0-dev-826ab2b [2024-11-14 03:31:13,910 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-14 03:31:13,993 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-32bit-Taipan_Default.epf [2024-11-14 03:31:14,000 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-14 03:31:14,000 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-14 03:31:14,030 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-14 03:31:14,031 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-14 03:31:14,031 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-14 03:31:14,032 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-14 03:31:14,032 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-14 03:31:14,032 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-14 03:31:14,032 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-14 03:31:14,033 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-14 03:31:14,033 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-14 03:31:14,033 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-14 03:31:14,033 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-14 03:31:14,033 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-14 03:31:14,034 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-14 03:31:14,034 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-14 03:31:14,034 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-14 03:31:14,035 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-14 03:31:14,035 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-14 03:31:14,036 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-14 03:31:14,036 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-14 03:31:14,036 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-14 03:31:14,036 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-14 03:31:14,036 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-14 03:31:14,036 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-14 03:31:14,037 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-14 03:31:14,037 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-14 03:31:14,037 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-14 03:31:14,037 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-14 03:31:14,037 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-14 03:31:14,037 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-14 03:31:14,037 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-14 03:31:14,037 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-14 03:31:14,038 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-14 03:31:14,038 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-14 03:31:14,038 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 03:31:14,038 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-14 03:31:14,038 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-14 03:31:14,038 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-14 03:31:14,038 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-14 03:31:14,039 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-14 03:31:14,040 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-14 03:31:14,040 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-14 03:31:14,040 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-14 03:31:14,040 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_822c0387-2888-4052-afd6-604797d4ea01/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 -> 47fbdb3da16165eeeef0687b73275c90a2682f5a520ac2387154637187559fe6 [2024-11-14 03:31:14,425 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-14 03:31:14,439 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-14 03:31:14,444 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-14 03:31:14,447 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-14 03:31:14,448 INFO L274 PluginConnector]: CDTParser initialized [2024-11-14 03:31:14,449 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/../../sv-benchmarks/c/nla-digbench-scaling/ps4-ll_unwindbound100.c Unable to find full path for "g++" [2024-11-14 03:31:16,734 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-14 03:31:17,120 INFO L384 CDTParser]: Found 1 translation units. [2024-11-14 03:31:17,121 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/sv-benchmarks/c/nla-digbench-scaling/ps4-ll_unwindbound100.c [2024-11-14 03:31:17,149 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/data/36cb26584/b2a88d7f3990404796d1c27d562dbfa1/FLAG7be4673cd [2024-11-14 03:31:17,343 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/data/36cb26584/b2a88d7f3990404796d1c27d562dbfa1 [2024-11-14 03:31:17,348 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-14 03:31:17,350 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-14 03:31:17,354 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-14 03:31:17,355 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-14 03:31:17,360 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-14 03:31:17,361 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 03:31:17" (1/1) ... [2024-11-14 03:31:17,365 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@78d948de and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:31:17, skipping insertion in model container [2024-11-14 03:31:17,366 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 03:31:17" (1/1) ... [2024-11-14 03:31:17,387 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-14 03:31:17,601 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_822c0387-2888-4052-afd6-604797d4ea01/sv-benchmarks/c/nla-digbench-scaling/ps4-ll_unwindbound100.c[458,471] [2024-11-14 03:31:17,633 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 03:31:17,647 INFO L200 MainTranslator]: Completed pre-run [2024-11-14 03:31:17,662 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_822c0387-2888-4052-afd6-604797d4ea01/sv-benchmarks/c/nla-digbench-scaling/ps4-ll_unwindbound100.c[458,471] [2024-11-14 03:31:17,675 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 03:31:17,695 INFO L204 MainTranslator]: Completed translation [2024-11-14 03:31:17,696 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:31:17 WrapperNode [2024-11-14 03:31:17,696 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-14 03:31:17,698 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-14 03:31:17,698 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-14 03:31:17,699 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-14 03:31:17,707 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:31:17" (1/1) ... [2024-11-14 03:31:17,715 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:31:17" (1/1) ... [2024-11-14 03:31:17,738 INFO L138 Inliner]: procedures = 14, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 38 [2024-11-14 03:31:17,738 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-14 03:31:17,739 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-14 03:31:17,739 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-14 03:31:17,739 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-14 03:31:17,748 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:31:17" (1/1) ... [2024-11-14 03:31:17,748 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:31:17" (1/1) ... [2024-11-14 03:31:17,749 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:31:17" (1/1) ... [2024-11-14 03:31:17,749 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:31:17" (1/1) ... [2024-11-14 03:31:17,753 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:31:17" (1/1) ... [2024-11-14 03:31:17,761 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:31:17" (1/1) ... [2024-11-14 03:31:17,763 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:31:17" (1/1) ... [2024-11-14 03:31:17,764 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:31:17" (1/1) ... [2024-11-14 03:31:17,766 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-14 03:31:17,768 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-14 03:31:17,769 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-14 03:31:17,769 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-14 03:31:17,770 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:31:17" (1/1) ... [2024-11-14 03:31:17,784 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 03:31:17,800 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:31:17,817 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-14 03:31:17,824 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-14 03:31:17,856 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-14 03:31:17,857 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-14 03:31:17,857 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-14 03:31:17,857 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-14 03:31:17,857 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-14 03:31:17,858 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-14 03:31:17,952 INFO L238 CfgBuilder]: Building ICFG [2024-11-14 03:31:17,954 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-14 03:31:18,154 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2024-11-14 03:31:18,154 INFO L287 CfgBuilder]: Performing block encoding [2024-11-14 03:31:18,186 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-14 03:31:18,187 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-14 03:31:18,187 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 03:31:18 BoogieIcfgContainer [2024-11-14 03:31:18,187 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-14 03:31:18,190 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-14 03:31:18,190 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-14 03:31:18,196 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-14 03:31:18,196 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.11 03:31:17" (1/3) ... [2024-11-14 03:31:18,197 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3d6ce08c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 03:31:18, skipping insertion in model container [2024-11-14 03:31:18,197 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:31:17" (2/3) ... [2024-11-14 03:31:18,200 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3d6ce08c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 03:31:18, skipping insertion in model container [2024-11-14 03:31:18,200 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 03:31:18" (3/3) ... [2024-11-14 03:31:18,202 INFO L112 eAbstractionObserver]: Analyzing ICFG ps4-ll_unwindbound100.c [2024-11-14 03:31:18,223 INFO L217 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-14 03:31:18,225 INFO L154 ceAbstractionStarter]: Applying trace abstraction to ICFG ps4-ll_unwindbound100.c that has 2 procedures, 15 locations, 1 initial locations, 1 loop locations, and 1 error locations. [2024-11-14 03:31:18,290 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-14 03:31:18,309 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;@76c11c5, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-14 03:31:18,310 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-14 03:31:18,316 INFO L276 IsEmpty]: Start isEmpty. Operand has 15 states, 9 states have (on average 1.5555555555555556) internal successors, (14), 10 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-14 03:31:18,324 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2024-11-14 03:31:18,324 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:31:18,325 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2024-11-14 03:31:18,325 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:31:18,330 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:31:18,331 INFO L85 PathProgramCache]: Analyzing trace with hash -2100386372, now seen corresponding path program 1 times [2024-11-14 03:31:18,339 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:31:18,340 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [21712343] [2024-11-14 03:31:18,340 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:31:18,341 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:31:18,432 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:31:18,483 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 03:31:18,484 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:31:18,484 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [21712343] [2024-11-14 03:31:18,485 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [21712343] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 03:31:18,485 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 03:31:18,486 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-14 03:31:18,487 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [332586438] [2024-11-14 03:31:18,488 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 03:31:18,493 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-14 03:31:18,493 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:31:18,520 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-14 03:31:18,521 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-14 03:31:18,524 INFO L87 Difference]: Start difference. First operand has 15 states, 9 states have (on average 1.5555555555555556) internal successors, (14), 10 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 03:31:18,553 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:31:18,554 INFO L93 Difference]: Finished difference Result 29 states and 42 transitions. [2024-11-14 03:31:18,555 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-14 03:31:18,557 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 6 [2024-11-14 03:31:18,557 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:31:18,565 INFO L225 Difference]: With dead ends: 29 [2024-11-14 03:31:18,565 INFO L226 Difference]: Without dead ends: 13 [2024-11-14 03:31:18,568 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 03:31:18,572 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 16 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 03:31:18,573 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 16 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 03:31:18,591 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 13 states. [2024-11-14 03:31:18,606 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 13 to 13. [2024-11-14 03:31:18,607 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 13 states, 8 states have (on average 1.375) internal successors, (11), 9 states have internal predecessors, (11), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 03:31:18,611 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 16 transitions. [2024-11-14 03:31:18,613 INFO L78 Accepts]: Start accepts. Automaton has 13 states and 16 transitions. Word has length 6 [2024-11-14 03:31:18,614 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:31:18,614 INFO L471 AbstractCegarLoop]: Abstraction has 13 states and 16 transitions. [2024-11-14 03:31:18,614 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 03:31:18,614 INFO L276 IsEmpty]: Start isEmpty. Operand 13 states and 16 transitions. [2024-11-14 03:31:18,615 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-14 03:31:18,616 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:31:18,616 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:31:18,616 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-14 03:31:18,616 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:31:18,617 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:31:18,617 INFO L85 PathProgramCache]: Analyzing trace with hash -1087891836, now seen corresponding path program 1 times [2024-11-14 03:31:18,617 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:31:18,618 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [183479695] [2024-11-14 03:31:18,618 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:31:18,618 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:31:18,644 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:31:18,802 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 03:31:18,802 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:31:18,802 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [183479695] [2024-11-14 03:31:18,802 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [183479695] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 03:31:18,803 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 03:31:18,803 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-14 03:31:18,803 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [919932078] [2024-11-14 03:31:18,803 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 03:31:18,804 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-14 03:31:18,805 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:31:18,805 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-14 03:31:18,805 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 03:31:18,806 INFO L87 Difference]: Start difference. First operand 13 states and 16 transitions. Second operand has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 03:31:18,843 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:31:18,844 INFO L93 Difference]: Finished difference Result 23 states and 27 transitions. [2024-11-14 03:31:18,844 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-14 03:31:18,844 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2024-11-14 03:31:18,845 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:31:18,845 INFO L225 Difference]: With dead ends: 23 [2024-11-14 03:31:18,845 INFO L226 Difference]: Without dead ends: 15 [2024-11-14 03:31:18,846 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 03:31:18,847 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 0 mSDsluCounter, 25 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 38 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 03:31:18,847 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 38 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 03:31:18,848 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2024-11-14 03:31:18,853 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2024-11-14 03:31:18,854 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 15 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 03:31:18,855 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 18 transitions. [2024-11-14 03:31:18,855 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 18 transitions. Word has length 7 [2024-11-14 03:31:18,855 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:31:18,855 INFO L471 AbstractCegarLoop]: Abstraction has 15 states and 18 transitions. [2024-11-14 03:31:18,855 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 03:31:18,855 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 18 transitions. [2024-11-14 03:31:18,856 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-14 03:31:18,856 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:31:18,856 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:31:18,856 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-14 03:31:18,856 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:31:18,857 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:31:18,857 INFO L85 PathProgramCache]: Analyzing trace with hash -1086104376, now seen corresponding path program 1 times [2024-11-14 03:31:18,857 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:31:18,857 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1649684023] [2024-11-14 03:31:18,858 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:31:18,858 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:31:18,873 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 03:31:18,875 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2009722936] [2024-11-14 03:31:18,876 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:31:18,876 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:31:18,876 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:31:18,878 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:31:18,883 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-14 03:31:18,942 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:31:18,946 INFO L255 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-14 03:31:18,951 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:31:19,079 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 03:31:19,079 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 03:31:19,079 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:31:19,080 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1649684023] [2024-11-14 03:31:19,080 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 03:31:19,082 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2009722936] [2024-11-14 03:31:19,086 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2009722936] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 03:31:19,086 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 03:31:19,086 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-14 03:31:19,087 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [303781594] [2024-11-14 03:31:19,087 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 03:31:19,087 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 03:31:19,087 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:31:19,088 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 03:31:19,088 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-14 03:31:19,088 INFO L87 Difference]: Start difference. First operand 15 states and 18 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 03:31:19,215 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:31:19,216 INFO L93 Difference]: Finished difference Result 25 states and 30 transitions. [2024-11-14 03:31:19,216 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 03:31:19,216 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 03:31:19,217 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:31:19,217 INFO L225 Difference]: With dead ends: 25 [2024-11-14 03:31:19,218 INFO L226 Difference]: Without dead ends: 21 [2024-11-14 03:31:19,218 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-14 03:31:19,219 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 4 mSDsluCounter, 33 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 03:31:19,220 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 45 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 03:31:19,221 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2024-11-14 03:31:19,229 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2024-11-14 03:31:19,229 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 15 states have internal predecessors, (17), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-14 03:31:19,230 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 24 transitions. [2024-11-14 03:31:19,230 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 24 transitions. Word has length 7 [2024-11-14 03:31:19,231 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:31:19,231 INFO L471 AbstractCegarLoop]: Abstraction has 21 states and 24 transitions. [2024-11-14 03:31:19,231 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 03:31:19,231 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 24 transitions. [2024-11-14 03:31:19,232 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-14 03:31:19,232 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:31:19,232 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:31:19,259 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-14 03:31:19,437 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2024-11-14 03:31:19,437 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:31:19,438 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:31:19,438 INFO L85 PathProgramCache]: Analyzing trace with hash 1170848234, now seen corresponding path program 1 times [2024-11-14 03:31:19,438 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:31:19,438 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [316317308] [2024-11-14 03:31:19,438 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:31:19,449 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:31:19,507 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:31:19,671 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 03:31:19,671 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:31:19,671 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [316317308] [2024-11-14 03:31:19,672 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [316317308] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 03:31:19,672 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1295836082] [2024-11-14 03:31:19,672 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:31:19,672 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:31:19,672 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:31:19,674 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:31:19,677 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-14 03:31:19,761 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:31:19,767 INFO L255 TraceCheckSpWp]: Trace formula consists of 66 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-14 03:31:19,769 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:31:19,851 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 03:31:19,851 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:31:19,942 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 03:31:19,942 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1295836082] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:31:19,942 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1255779249] [2024-11-14 03:31:19,975 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2024-11-14 03:31:19,976 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:31:19,980 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:31:19,986 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:31:19,987 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:31:21,996 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 78 for LOIs [2024-11-14 03:31:22,371 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:31:25,338 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '329#(and (or (exists ((|v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_10| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11| Int) (|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_11| Int) (|v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_10| Int)) (and (exists ((|v_ULTIMATE.start_main_#t~post5#1_21| Int)) (and (<= 1 |#StackHeapBarrier|) (<= 0 (+ |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_10| 32768)) (<= 1 ~counter~0) (<= |v_ULTIMATE.start_main_#t~post5#1_21| 99) (<= |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_10| 32767) (<= 0 |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_11|) (<= 0 |v_ULTIMATE.start_main_#t~post5#1_21|) (<= 0 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11|) (<= 0 |v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_10|))) (not (= (* |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_11| 4) (+ (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11|) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11|) (* (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11|) 2)))))) (exists ((|v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_7| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| Int) (|v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_7| Int) (|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_8| Int)) (and (<= 0 |v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_7|) (<= 1 |#StackHeapBarrier|) (<= 0 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|) (<= |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_7| 32767) (<= 1 ~counter~0) (<= 0 |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_8|) (<= 0 (+ |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_7| 32768)) (not (= (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|) (* |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_7| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|)))))) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-14 03:31:25,338 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:31:25,338 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 03:31:25,338 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 4, 5] total 10 [2024-11-14 03:31:25,338 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [706205041] [2024-11-14 03:31:25,338 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 03:31:25,339 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-14 03:31:25,339 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:31:25,340 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-14 03:31:25,341 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=282, Unknown=0, NotChecked=0, Total=342 [2024-11-14 03:31:25,341 INFO L87 Difference]: Start difference. First operand 21 states and 24 transitions. Second operand has 10 states, 10 states have (on average 2.4) internal successors, (24), 10 states have internal predecessors, (24), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-14 03:31:25,484 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:31:25,484 INFO L93 Difference]: Finished difference Result 55 states and 65 transitions. [2024-11-14 03:31:25,485 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-14 03:31:25,486 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.4) internal successors, (24), 10 states have internal predecessors, (24), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 15 [2024-11-14 03:31:25,486 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:31:25,487 INFO L225 Difference]: With dead ends: 55 [2024-11-14 03:31:25,487 INFO L226 Difference]: Without dead ends: 47 [2024-11-14 03:31:25,487 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 31 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 118 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=73, Invalid=347, Unknown=0, NotChecked=0, Total=420 [2024-11-14 03:31:25,491 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 29 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 71 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 03:31:25,492 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 71 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 03:31:25,493 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-11-14 03:31:25,506 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 43. [2024-11-14 03:31:25,506 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 28 states have (on average 1.25) internal successors, (35), 31 states have internal predecessors, (35), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-14 03:31:25,509 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 52 transitions. [2024-11-14 03:31:25,509 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 52 transitions. Word has length 15 [2024-11-14 03:31:25,509 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:31:25,509 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 52 transitions. [2024-11-14 03:31:25,510 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.4) internal successors, (24), 10 states have internal predecessors, (24), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-14 03:31:25,510 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 52 transitions. [2024-11-14 03:31:25,512 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-14 03:31:25,512 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:31:25,512 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:31:25,537 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-14 03:31:25,712 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:31:25,713 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:31:25,713 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:31:25,713 INFO L85 PathProgramCache]: Analyzing trace with hash 1172635694, now seen corresponding path program 1 times [2024-11-14 03:31:25,714 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:31:25,714 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [331070678] [2024-11-14 03:31:25,714 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:31:25,714 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:31:25,736 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 03:31:25,737 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1253236619] [2024-11-14 03:31:25,738 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:31:25,738 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:31:25,738 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:31:25,740 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:31:25,742 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-14 03:31:25,798 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:31:25,800 INFO L255 TraceCheckSpWp]: Trace formula consists of 66 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-14 03:31:25,802 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:31:25,924 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 03:31:25,924 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:31:26,085 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 03:31:26,085 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:31:26,085 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [331070678] [2024-11-14 03:31:26,085 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 03:31:26,085 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1253236619] [2024-11-14 03:31:26,085 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1253236619] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:31:26,086 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [103357833] [2024-11-14 03:31:26,090 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 03:31:26,090 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:31:26,090 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:31:26,091 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:31:26,091 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:31:27,021 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 51 for LOIs [2024-11-14 03:31:27,141 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:31:28,267 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '585#(and (= |__VERIFIER_assert_#in~cond| 0) (exists ((|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_23| Int) (|v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_19| Int) (|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_23| Int) (|v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_19| Int) (|v_ULTIMATE.start_main_#t~post5#1_26| Int)) (and (<= 0 (+ |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_19| 32768)) (<= 1 |#StackHeapBarrier|) (<= |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_19| 32767) (<= 0 |v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_19|) (<= 0 |v_ULTIMATE.start_main_#t~post5#1_26|) (<= 0 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_23|) (not (= (* |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_23| 4) (+ (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_23| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_23|) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_23| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_23| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_23| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_23|) (* 2 (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_23| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_23| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_23|))))) (<= 0 |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_23|) (<= 1 ~counter~0) (<= |v_ULTIMATE.start_main_#t~post5#1_26| 99))))' at error location [2024-11-14 03:31:28,267 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:31:28,267 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 03:31:28,268 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6] total 11 [2024-11-14 03:31:28,268 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [672856415] [2024-11-14 03:31:28,268 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 03:31:28,268 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-14 03:31:28,269 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:31:28,269 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-14 03:31:28,269 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=288, Unknown=0, NotChecked=0, Total=342 [2024-11-14 03:31:28,270 INFO L87 Difference]: Start difference. First operand 43 states and 52 transitions. Second operand has 11 states, 11 states have (on average 2.0) internal successors, (22), 10 states have internal predecessors, (22), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 03:31:28,392 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:31:28,393 INFO L93 Difference]: Finished difference Result 57 states and 65 transitions. [2024-11-14 03:31:28,394 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-14 03:31:28,394 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.0) internal successors, (22), 10 states have internal predecessors, (22), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 15 [2024-11-14 03:31:28,394 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:31:28,395 INFO L225 Difference]: With dead ends: 57 [2024-11-14 03:31:28,395 INFO L226 Difference]: Without dead ends: 46 [2024-11-14 03:31:28,396 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 25 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 68 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=62, Invalid=318, Unknown=0, NotChecked=0, Total=380 [2024-11-14 03:31:28,397 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 8 mSDsluCounter, 47 mSDsCounter, 0 mSdLazyCounter, 52 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 59 SdHoareTripleChecker+Invalid, 61 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 52 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 03:31:28,397 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 59 Invalid, 61 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 52 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 03:31:28,400 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2024-11-14 03:31:28,425 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 40. [2024-11-14 03:31:28,427 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 30 states have (on average 1.1333333333333333) internal successors, (34), 30 states have internal predecessors, (34), 5 states have call successors, (5), 5 states have call predecessors, (5), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-14 03:31:28,427 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 43 transitions. [2024-11-14 03:31:28,430 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 43 transitions. Word has length 15 [2024-11-14 03:31:28,430 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:31:28,430 INFO L471 AbstractCegarLoop]: Abstraction has 40 states and 43 transitions. [2024-11-14 03:31:28,431 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.0) internal successors, (22), 10 states have internal predecessors, (22), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-14 03:31:28,431 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 43 transitions. [2024-11-14 03:31:28,431 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2024-11-14 03:31:28,431 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:31:28,431 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2024-11-14 03:31:28,457 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-14 03:31:28,632 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:31:28,632 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:31:28,633 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:31:28,633 INFO L85 PathProgramCache]: Analyzing trace with hash 1524344587, now seen corresponding path program 1 times [2024-11-14 03:31:28,633 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:31:28,633 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2012494058] [2024-11-14 03:31:28,633 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:31:28,633 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:31:28,669 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 03:31:28,673 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1170935349] [2024-11-14 03:31:28,676 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:31:28,677 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:31:28,677 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:31:28,680 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:31:28,684 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-14 03:31:28,748 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:31:28,749 INFO L255 TraceCheckSpWp]: Trace formula consists of 76 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-14 03:31:28,751 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:31:28,928 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 3 proven. 8 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-14 03:31:28,929 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:31:29,240 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 3 proven. 8 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-14 03:31:29,241 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:31:29,241 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2012494058] [2024-11-14 03:31:29,241 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 03:31:29,242 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1170935349] [2024-11-14 03:31:29,242 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1170935349] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:31:29,242 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [136322569] [2024-11-14 03:31:29,245 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2024-11-14 03:31:29,246 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:31:29,246 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:31:29,246 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:31:29,246 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:31:30,048 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 87 for LOIs [2024-11-14 03:31:30,306 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:31:35,629 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '875#(and (= |__VERIFIER_assert_#in~cond| 0) (or (exists ((|v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_31| Int) (|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_34| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_37| Int)) (and (exists ((|v_ULTIMATE.start_main_#t~post5#1_32| Int) (|v_ULTIMATE.start_main_~c~0#1_30| Int)) (and (<= 1 |#StackHeapBarrier|) (<= |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_31| 32767) (<= 0 |v_ULTIMATE.start_main_~c~0#1_30|) (<= 0 (+ |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_31| 32768)) (<= |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_31| |v_ULTIMATE.start_main_~c~0#1_30|) (<= |v_ULTIMATE.start_main_#t~post5#1_32| 99) (<= 1 ~counter~0) (<= 0 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_37|) (<= 0 |v_ULTIMATE.start_main_#t~post5#1_32|))) (= (* |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_34| 4) (+ (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_37| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_37|) (* (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_37| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_37| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_37|) 2) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_37| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_37| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_37| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_37|))) (not (= (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_37| |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_31|) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_37| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_37|))))) (exists ((|v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_32| Int) (|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_35| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_38| Int) (|v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_32| Int)) (and (exists ((|v_ULTIMATE.start_main_#t~post5#1_32| Int)) (and (<= 0 (+ |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_32| 32768)) (<= 1 |#StackHeapBarrier|) (<= 0 |v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_32|) (<= 0 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_38|) (<= |v_ULTIMATE.start_main_#t~post5#1_32| 99) (<= 1 ~counter~0) (<= 0 |v_ULTIMATE.start_main_#t~post5#1_32|) (<= |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_32| 32767) (<= 0 |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_35|))) (not (= (+ (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_38| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_38|) (* 2 (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_38| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_38| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_38|)) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_38| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_38| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_38| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_38|)) (* |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_35| 4)))))))' at error location [2024-11-14 03:31:35,629 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:31:35,630 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 03:31:35,630 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 15 [2024-11-14 03:31:35,630 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [840646433] [2024-11-14 03:31:35,630 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 03:31:35,631 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-14 03:31:35,631 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:31:35,631 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-14 03:31:35,634 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=478, Unknown=1, NotChecked=0, Total=552 [2024-11-14 03:31:35,635 INFO L87 Difference]: Start difference. First operand 40 states and 43 transitions. Second operand has 15 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 12 states have internal predecessors, (25), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-14 03:31:35,877 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:31:35,877 INFO L93 Difference]: Finished difference Result 48 states and 52 transitions. [2024-11-14 03:31:35,878 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-14 03:31:35,878 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 12 states have internal predecessors, (25), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 21 [2024-11-14 03:31:35,878 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:31:35,879 INFO L225 Difference]: With dead ends: 48 [2024-11-14 03:31:35,879 INFO L226 Difference]: Without dead ends: 42 [2024-11-14 03:31:35,880 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 35 SyntacticMatches, 4 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 136 ImplicationChecksByTransitivity, 5.7s TimeCoverageRelationStatistics Valid=94, Invalid=607, Unknown=1, NotChecked=0, Total=702 [2024-11-14 03:31:35,881 INFO L432 NwaCegarLoop]: 10 mSDtfsCounter, 8 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 75 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 76 SdHoareTripleChecker+Invalid, 80 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 75 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 03:31:35,881 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 76 Invalid, 80 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 75 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 03:31:35,882 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2024-11-14 03:31:35,891 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 42. [2024-11-14 03:31:35,891 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 31 states have (on average 1.064516129032258) internal successors, (33), 31 states have internal predecessors, (33), 6 states have call successors, (6), 5 states have call predecessors, (6), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-14 03:31:35,892 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 44 transitions. [2024-11-14 03:31:35,892 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 44 transitions. Word has length 21 [2024-11-14 03:31:35,893 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:31:35,893 INFO L471 AbstractCegarLoop]: Abstraction has 42 states and 44 transitions. [2024-11-14 03:31:35,893 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 12 states have internal predecessors, (25), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-14 03:31:35,893 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 44 transitions. [2024-11-14 03:31:35,894 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-11-14 03:31:35,894 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:31:35,894 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1] [2024-11-14 03:31:35,919 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-14 03:31:36,099 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:31:36,099 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:31:36,099 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:31:36,099 INFO L85 PathProgramCache]: Analyzing trace with hash 300810268, now seen corresponding path program 2 times [2024-11-14 03:31:36,100 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:31:36,100 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [979789037] [2024-11-14 03:31:36,100 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:31:36,100 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:31:36,127 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:31:36,397 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 32 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-14 03:31:36,398 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:31:36,398 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [979789037] [2024-11-14 03:31:36,398 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [979789037] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 03:31:36,398 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1273240773] [2024-11-14 03:31:36,398 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 03:31:36,399 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:31:36,399 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:31:36,401 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:31:36,402 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-14 03:31:36,464 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-14 03:31:36,464 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 03:31:36,465 INFO L255 TraceCheckSpWp]: Trace formula consists of 129 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-14 03:31:36,467 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:31:36,545 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 56 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 03:31:36,545 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:31:36,692 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 32 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-14 03:31:36,692 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1273240773] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:31:36,693 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [262091824] [2024-11-14 03:31:36,695 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2024-11-14 03:31:36,695 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:31:36,699 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:31:36,699 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:31:36,699 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:31:37,360 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 78 for LOIs [2024-11-14 03:31:37,492 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:31:38,749 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1267#(and (= |__VERIFIER_assert_#in~cond| 0) (or (exists ((|v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_42| Int) (|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_45| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_48| Int) (|v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_42| Int)) (and (not (= (* |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_45| 4) (+ (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_48| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_48| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_48| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_48|) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_48| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_48|) (* 2 (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_48| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_48| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_48|))))) (exists ((|v_ULTIMATE.start_main_#t~post5#1_43| Int)) (and (<= 1 |#StackHeapBarrier|) (<= 0 |v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_42|) (<= |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_42| 32767) (<= 0 (+ |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_42| 32768)) (<= |v_ULTIMATE.start_main_#t~post5#1_43| 99) (<= 1 ~counter~0) (<= 0 |v_ULTIMATE.start_main_#t~post5#1_43|) (<= 0 |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_45|) (<= 0 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_48|))))) (exists ((|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_45| Int) (|v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_39| Int) (|v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_39| Int) (|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_42| Int)) (and (<= 1 |#StackHeapBarrier|) (<= 0 (+ |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_39| 32768)) (<= 0 |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_42|) (<= |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_39| 32767) (<= 1 ~counter~0) (<= 0 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_45|) (not (= (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_45| |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_39|) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_45| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_45|))) (<= 0 |v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_39|)))))' at error location [2024-11-14 03:31:38,749 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:31:38,749 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 03:31:38,749 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 8] total 16 [2024-11-14 03:31:38,750 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1974059222] [2024-11-14 03:31:38,750 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 03:31:38,750 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-14 03:31:38,750 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:31:38,751 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-14 03:31:38,751 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=123, Invalid=477, Unknown=0, NotChecked=0, Total=600 [2024-11-14 03:31:38,753 INFO L87 Difference]: Start difference. First operand 42 states and 44 transitions. Second operand has 16 states, 16 states have (on average 3.1875) internal successors, (51), 16 states have internal predecessors, (51), 9 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) [2024-11-14 03:31:39,032 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:31:39,032 INFO L93 Difference]: Finished difference Result 118 states and 124 transitions. [2024-11-14 03:31:39,033 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-14 03:31:39,034 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.1875) internal successors, (51), 16 states have internal predecessors, (51), 9 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) Word has length 39 [2024-11-14 03:31:39,034 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:31:39,035 INFO L225 Difference]: With dead ends: 118 [2024-11-14 03:31:39,035 INFO L226 Difference]: Without dead ends: 113 [2024-11-14 03:31:39,036 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 97 SyntacticMatches, 4 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 352 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=223, Invalid=833, Unknown=0, NotChecked=0, Total=1056 [2024-11-14 03:31:39,036 INFO L432 NwaCegarLoop]: 11 mSDtfsCounter, 73 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 73 SdHoareTripleChecker+Valid, 89 SdHoareTripleChecker+Invalid, 64 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 53 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 03:31:39,036 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [73 Valid, 89 Invalid, 64 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 53 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 03:31:39,037 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 113 states. [2024-11-14 03:31:39,060 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 113 to 88. [2024-11-14 03:31:39,061 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 66 states have (on average 1.106060606060606) internal successors, (73), 66 states have internal predecessors, (73), 11 states have call successors, (11), 11 states have call predecessors, (11), 10 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-14 03:31:39,062 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 94 transitions. [2024-11-14 03:31:39,064 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 94 transitions. Word has length 39 [2024-11-14 03:31:39,064 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:31:39,064 INFO L471 AbstractCegarLoop]: Abstraction has 88 states and 94 transitions. [2024-11-14 03:31:39,064 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.1875) internal successors, (51), 16 states have internal predecessors, (51), 9 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) [2024-11-14 03:31:39,065 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 94 transitions. [2024-11-14 03:31:39,067 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2024-11-14 03:31:39,067 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:31:39,067 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1] [2024-11-14 03:31:39,086 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-14 03:31:39,267 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2024-11-14 03:31:39,267 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:31:39,268 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:31:39,268 INFO L85 PathProgramCache]: Analyzing trace with hash -987037763, now seen corresponding path program 2 times [2024-11-14 03:31:39,268 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:31:39,268 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2030174983] [2024-11-14 03:31:39,268 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:31:39,268 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:31:39,289 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 03:31:39,290 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1391399299] [2024-11-14 03:31:39,290 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 03:31:39,290 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:31:39,290 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:31:39,292 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:31:39,296 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_822c0387-2888-4052-afd6-604797d4ea01/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-14 03:31:39,362 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-14 03:31:39,362 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 03:31:39,364 INFO L255 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-14 03:31:39,366 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:31:39,591 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 21 proven. 41 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-14 03:31:39,591 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:32:10,930 WARN L873 $PredicateComparison]: unable to prove that (or (not (= |c___VERIFIER_assert_#in~cond| 0)) (forall ((|v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_45| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| Int)) (or (= (mod (+ (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| 3) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| 2) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| 3)) 4) 0) (= (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55|) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_45|))))) is different from true [2024-11-14 03:32:28,982 WARN L873 $PredicateComparison]: unable to prove that (or (not (= |c___VERIFIER_assert_#in~cond| 0)) (forall ((|v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_45| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| Int)) (or (= (mod (+ (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| 3) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| 2) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| 3)) 4) 0) (= (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55|) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_55| |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_45|)))) (= c___VERIFIER_assert_~cond 0)) is different from true [2024-11-14 03:32:37,051 WARN L851 $PredicateComparison]: unable to prove that (or (= (+ |c_ULTIMATE.start_main_~y~0#1| (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1|)) (+ |c_ULTIMATE.start_main_~c~0#1| (* |c_ULTIMATE.start_main_~c~0#1| |c_ULTIMATE.start_main_~y~0#1|))) (not (= (mod (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 2) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 3) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 3)) 4) 0))) is different from false [2024-11-14 03:32:47,100 WARN L851 $PredicateComparison]: unable to prove that (or (not (= (mod (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 2) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 3) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 3)) 4) 0)) (= (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1|) (* |c_ULTIMATE.start_main_~y~0#1| 2)) (+ (* |c_ULTIMATE.start_main_~c~0#1| 2) (* |c_ULTIMATE.start_main_~c~0#1| |c_ULTIMATE.start_main_~y~0#1|)))) is different from false [2024-11-14 03:32:57,172 WARN L851 $PredicateComparison]: unable to prove that (or (= (+ (* |c_ULTIMATE.start_main_~c~0#1| 3) (* |c_ULTIMATE.start_main_~c~0#1| |c_ULTIMATE.start_main_~y~0#1|)) (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1|) (* |c_ULTIMATE.start_main_~y~0#1| 3))) (not (= (mod (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 2) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 3) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 3)) 4) 0))) is different from false [2024-11-14 03:33:07,268 WARN L851 $PredicateComparison]: unable to prove that (or (= (+ (* |c_ULTIMATE.start_main_~c~0#1| |c_ULTIMATE.start_main_~y~0#1|) (* |c_ULTIMATE.start_main_~c~0#1| 4)) (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1|) (* |c_ULTIMATE.start_main_~y~0#1| 4))) (not (= (mod (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 2) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 3) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 3)) 4) 0))) is different from false [2024-11-14 03:33:13,321 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 21 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 41 not checked. [2024-11-14 03:33:13,321 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:33:13,321 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2030174983] [2024-11-14 03:33:13,321 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 03:33:13,321 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1391399299] [2024-11-14 03:33:13,321 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1391399299] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:33:13,322 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1710248665] [2024-11-14 03:33:13,327 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2024-11-14 03:33:13,327 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:33:13,327 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:33:13,328 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:33:13,328 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:33:13,940 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 87 for LOIs [2024-11-14 03:33:14,156 INFO L180 IcfgInterpreter]: Interpretation finished