./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/ps4-ll_unwindbound5.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 826ab2ba Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/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_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/ps4-ll_unwindbound5.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/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_b7354932-de6c-409b-a2cb-dda660885954/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 d629f4eefc4b49512b7b1b628f28a13dcdca90b36cb521919e0cc9ad875c2764 --- Real Ultimate output --- This is Ultimate 0.3.0-dev-826ab2b [2024-11-14 02:43:25,008 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-14 02:43:25,092 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-32bit-Taipan_Default.epf [2024-11-14 02:43:25,105 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-14 02:43:25,105 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-14 02:43:25,147 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-14 02:43:25,148 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-14 02:43:25,148 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-14 02:43:25,149 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-14 02:43:25,149 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-14 02:43:25,150 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-14 02:43:25,151 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-14 02:43:25,151 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-14 02:43:25,151 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-14 02:43:25,151 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-14 02:43:25,151 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-14 02:43:25,151 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-14 02:43:25,151 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-14 02:43:25,152 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-14 02:43:25,152 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-14 02:43:25,152 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-14 02:43:25,153 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-14 02:43:25,153 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-14 02:43:25,153 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-14 02:43:25,153 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-14 02:43:25,153 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-14 02:43:25,154 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-14 02:43:25,154 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-14 02:43:25,154 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-14 02:43:25,154 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-14 02:43:25,154 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-14 02:43:25,155 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-14 02:43:25,155 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-14 02:43:25,155 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-14 02:43:25,155 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-14 02:43:25,155 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-14 02:43:25,157 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-14 02:43:25,158 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-14 02:43:25,158 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 02:43:25,158 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-14 02:43:25,158 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-14 02:43:25,158 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-14 02:43:25,158 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-14 02:43:25,158 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-14 02:43:25,159 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-14 02:43:25,159 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-14 02:43:25,159 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-14 02:43:25,159 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_b7354932-de6c-409b-a2cb-dda660885954/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 -> d629f4eefc4b49512b7b1b628f28a13dcdca90b36cb521919e0cc9ad875c2764 [2024-11-14 02:43:25,505 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-14 02:43:25,515 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-14 02:43:25,519 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-14 02:43:25,522 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-14 02:43:25,522 INFO L274 PluginConnector]: CDTParser initialized [2024-11-14 02:43:25,525 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/../../sv-benchmarks/c/nla-digbench-scaling/ps4-ll_unwindbound5.c Unable to find full path for "g++" [2024-11-14 02:43:27,390 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-14 02:43:27,703 INFO L384 CDTParser]: Found 1 translation units. [2024-11-14 02:43:27,704 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/sv-benchmarks/c/nla-digbench-scaling/ps4-ll_unwindbound5.c [2024-11-14 02:43:27,726 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/data/5a1014fc7/14d598f4b52f4e5886569ae1d0c024c4/FLAGe92f6cc24 [2024-11-14 02:43:27,781 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/data/5a1014fc7/14d598f4b52f4e5886569ae1d0c024c4 [2024-11-14 02:43:27,788 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-14 02:43:27,793 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-14 02:43:27,796 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-14 02:43:27,799 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-14 02:43:27,808 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-14 02:43:27,811 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 02:43:27" (1/1) ... [2024-11-14 02:43:27,813 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3a0c5168 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:43:27, skipping insertion in model container [2024-11-14 02:43:27,813 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 02:43:27" (1/1) ... [2024-11-14 02:43:27,832 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-14 02:43:28,022 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_b7354932-de6c-409b-a2cb-dda660885954/sv-benchmarks/c/nla-digbench-scaling/ps4-ll_unwindbound5.c[458,471] [2024-11-14 02:43:28,048 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 02:43:28,060 INFO L200 MainTranslator]: Completed pre-run [2024-11-14 02:43:28,072 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_b7354932-de6c-409b-a2cb-dda660885954/sv-benchmarks/c/nla-digbench-scaling/ps4-ll_unwindbound5.c[458,471] [2024-11-14 02:43:28,084 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 02:43:28,103 INFO L204 MainTranslator]: Completed translation [2024-11-14 02:43:28,104 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:43:28 WrapperNode [2024-11-14 02:43:28,104 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-14 02:43:28,105 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-14 02:43:28,105 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-14 02:43:28,105 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-14 02:43:28,113 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:43:28" (1/1) ... [2024-11-14 02:43:28,122 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:43:28" (1/1) ... [2024-11-14 02:43:28,143 INFO L138 Inliner]: procedures = 14, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 38 [2024-11-14 02:43:28,143 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-14 02:43:28,143 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-14 02:43:28,144 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-14 02:43:28,144 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-14 02:43:28,151 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:43:28" (1/1) ... [2024-11-14 02:43:28,152 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:43:28" (1/1) ... [2024-11-14 02:43:28,157 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:43:28" (1/1) ... [2024-11-14 02:43:28,158 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:43:28" (1/1) ... [2024-11-14 02:43:28,160 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:43:28" (1/1) ... [2024-11-14 02:43:28,167 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:43:28" (1/1) ... [2024-11-14 02:43:28,168 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:43:28" (1/1) ... [2024-11-14 02:43:28,168 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:43:28" (1/1) ... [2024-11-14 02:43:28,174 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-14 02:43:28,175 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-14 02:43:28,176 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-14 02:43:28,176 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-14 02:43:28,178 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:43:28" (1/1) ... [2024-11-14 02:43:28,184 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 02:43:28,204 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:43:28,222 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-14 02:43:28,228 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-14 02:43:28,254 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-14 02:43:28,254 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-14 02:43:28,255 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-14 02:43:28,255 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-14 02:43:28,255 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-14 02:43:28,255 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-14 02:43:28,339 INFO L238 CfgBuilder]: Building ICFG [2024-11-14 02:43:28,341 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-14 02:43:28,523 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2024-11-14 02:43:28,524 INFO L287 CfgBuilder]: Performing block encoding [2024-11-14 02:43:28,564 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-14 02:43:28,566 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-14 02:43:28,566 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 02:43:28 BoogieIcfgContainer [2024-11-14 02:43:28,566 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-14 02:43:28,571 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-14 02:43:28,571 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-14 02:43:28,579 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-14 02:43:28,579 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.11 02:43:27" (1/3) ... [2024-11-14 02:43:28,580 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@37f97ac2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 02:43:28, skipping insertion in model container [2024-11-14 02:43:28,581 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:43:28" (2/3) ... [2024-11-14 02:43:28,581 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@37f97ac2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 02:43:28, skipping insertion in model container [2024-11-14 02:43:28,582 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 02:43:28" (3/3) ... [2024-11-14 02:43:28,584 INFO L112 eAbstractionObserver]: Analyzing ICFG ps4-ll_unwindbound5.c [2024-11-14 02:43:28,603 INFO L217 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-14 02:43:28,604 INFO L154 ceAbstractionStarter]: Applying trace abstraction to ICFG ps4-ll_unwindbound5.c that has 2 procedures, 15 locations, 1 initial locations, 1 loop locations, and 1 error locations. [2024-11-14 02:43:28,674 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-14 02:43:28,686 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;@94915a5, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-14 02:43:28,686 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-14 02:43:28,690 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 02:43:28,700 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2024-11-14 02:43:28,700 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:28,701 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2024-11-14 02:43:28,701 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:28,707 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:28,707 INFO L85 PathProgramCache]: Analyzing trace with hash -2100386372, now seen corresponding path program 1 times [2024-11-14 02:43:28,713 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:28,714 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [27451089] [2024-11-14 02:43:28,714 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:28,714 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:28,804 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:28,854 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:43:28,854 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:43:28,854 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [27451089] [2024-11-14 02:43:28,855 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [27451089] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:43:28,855 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:43:28,856 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-14 02:43:28,857 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1374349329] [2024-11-14 02:43:28,858 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:43:28,862 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-14 02:43:28,862 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:43:28,883 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-14 02:43:28,884 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-14 02:43:28,886 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 02:43:28,910 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:28,911 INFO L93 Difference]: Finished difference Result 29 states and 42 transitions. [2024-11-14 02:43:28,912 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-14 02:43:28,914 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 02:43:28,914 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:28,921 INFO L225 Difference]: With dead ends: 29 [2024-11-14 02:43:28,922 INFO L226 Difference]: Without dead ends: 13 [2024-11-14 02:43:28,925 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-14 02:43:28,929 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 02:43:28,930 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 02:43:28,948 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 13 states. [2024-11-14 02:43:28,962 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 13 to 13. [2024-11-14 02:43:28,964 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 02:43:28,967 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 16 transitions. [2024-11-14 02:43:28,969 INFO L78 Accepts]: Start accepts. Automaton has 13 states and 16 transitions. Word has length 6 [2024-11-14 02:43:28,970 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:28,970 INFO L471 AbstractCegarLoop]: Abstraction has 13 states and 16 transitions. [2024-11-14 02:43:28,970 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 02:43:28,970 INFO L276 IsEmpty]: Start isEmpty. Operand 13 states and 16 transitions. [2024-11-14 02:43:28,971 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-14 02:43:28,971 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:28,971 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:28,972 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-14 02:43:28,972 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:28,973 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:28,973 INFO L85 PathProgramCache]: Analyzing trace with hash -1087891836, now seen corresponding path program 1 times [2024-11-14 02:43:28,973 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:28,973 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [305074070] [2024-11-14 02:43:28,973 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:28,973 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:28,988 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:29,131 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:43:29,131 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:43:29,131 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [305074070] [2024-11-14 02:43:29,131 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [305074070] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:43:29,132 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:43:29,132 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-14 02:43:29,132 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1652811045] [2024-11-14 02:43:29,132 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:43:29,133 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-14 02:43:29,133 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:43:29,134 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-14 02:43:29,134 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 02:43:29,134 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 02:43:29,154 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:29,155 INFO L93 Difference]: Finished difference Result 23 states and 27 transitions. [2024-11-14 02:43:29,155 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-14 02:43:29,155 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 02:43:29,155 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:29,156 INFO L225 Difference]: With dead ends: 23 [2024-11-14 02:43:29,156 INFO L226 Difference]: Without dead ends: 15 [2024-11-14 02:43:29,156 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 02:43:29,157 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 02:43:29,158 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 02:43:29,158 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2024-11-14 02:43:29,161 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2024-11-14 02:43:29,161 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 02:43:29,162 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 18 transitions. [2024-11-14 02:43:29,162 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 18 transitions. Word has length 7 [2024-11-14 02:43:29,162 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:29,162 INFO L471 AbstractCegarLoop]: Abstraction has 15 states and 18 transitions. [2024-11-14 02:43:29,162 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 02:43:29,163 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 18 transitions. [2024-11-14 02:43:29,163 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-14 02:43:29,163 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:29,163 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:29,163 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-14 02:43:29,163 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:29,164 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:29,164 INFO L85 PathProgramCache]: Analyzing trace with hash -1086104376, now seen corresponding path program 1 times [2024-11-14 02:43:29,164 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:29,164 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1204056579] [2024-11-14 02:43:29,164 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:29,164 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:29,184 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 02:43:29,190 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [921495994] [2024-11-14 02:43:29,190 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:29,190 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:29,190 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:43:29,195 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:43:29,197 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-14 02:43:29,255 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:29,257 INFO L255 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-14 02:43:29,262 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:29,412 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:43:29,412 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 02:43:29,412 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:43:29,412 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1204056579] [2024-11-14 02:43:29,413 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 02:43:29,413 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [921495994] [2024-11-14 02:43:29,413 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [921495994] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:43:29,413 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:43:29,414 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-14 02:43:29,414 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1083085313] [2024-11-14 02:43:29,414 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:43:29,417 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 02:43:29,417 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:43:29,418 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 02:43:29,418 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-14 02:43:29,418 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 02:43:29,514 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:29,514 INFO L93 Difference]: Finished difference Result 25 states and 30 transitions. [2024-11-14 02:43:29,517 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 02:43:29,518 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2024-11-14 02:43:29,518 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:29,519 INFO L225 Difference]: With dead ends: 25 [2024-11-14 02:43:29,519 INFO L226 Difference]: Without dead ends: 21 [2024-11-14 02:43:29,521 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 02:43:29,522 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 02:43:29,522 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 02:43:29,523 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2024-11-14 02:43:29,534 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2024-11-14 02:43:29,534 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 02:43:29,535 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 24 transitions. [2024-11-14 02:43:29,535 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 24 transitions. Word has length 7 [2024-11-14 02:43:29,535 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:29,535 INFO L471 AbstractCegarLoop]: Abstraction has 21 states and 24 transitions. [2024-11-14 02:43:29,536 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-14 02:43:29,536 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 24 transitions. [2024-11-14 02:43:29,537 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-14 02:43:29,537 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:29,538 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:29,562 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-14 02:43:29,738 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:29,739 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:29,739 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:29,739 INFO L85 PathProgramCache]: Analyzing trace with hash 1170848234, now seen corresponding path program 1 times [2024-11-14 02:43:29,739 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:29,740 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [764358737] [2024-11-14 02:43:29,740 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:29,740 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:29,780 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:29,971 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 02:43:29,971 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:43:29,971 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [764358737] [2024-11-14 02:43:29,971 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [764358737] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 02:43:29,971 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1041548468] [2024-11-14 02:43:29,971 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:29,971 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:29,972 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:43:29,974 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:43:29,976 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-14 02:43:30,061 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:30,062 INFO L255 TraceCheckSpWp]: Trace formula consists of 66 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-14 02:43:30,064 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:30,132 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 02:43:30,132 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:43:30,244 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 02:43:30,244 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1041548468] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:43:30,245 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1714591543] [2024-11-14 02:43:30,266 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2024-11-14 02:43:30,266 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:43:30,270 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:43:30,275 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:43:30,275 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:43:32,119 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 77 for LOIs [2024-11-14 02:43:32,484 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 02:43:33,987 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 (<= |v_ULTIMATE.start_main_#t~post5#1_21| 4) (<= 1 |#StackHeapBarrier|) (<= 0 (+ |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_10| 32768)) (<= 1 ~counter~0) (<= |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 02:43:33,987 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 02:43:33,987 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 02:43:33,988 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 4, 5] total 10 [2024-11-14 02:43:33,988 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2143026691] [2024-11-14 02:43:33,988 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 02:43:33,988 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-14 02:43:33,988 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:43:33,989 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-14 02:43:33,990 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=282, Unknown=0, NotChecked=0, Total=342 [2024-11-14 02:43:33,990 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 02:43:34,102 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:34,102 INFO L93 Difference]: Finished difference Result 55 states and 65 transitions. [2024-11-14 02:43:34,103 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-14 02:43:34,103 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 02:43:34,103 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:34,104 INFO L225 Difference]: With dead ends: 55 [2024-11-14 02:43:34,104 INFO L226 Difference]: Without dead ends: 47 [2024-11-14 02:43:34,104 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 31 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 118 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=73, Invalid=347, Unknown=0, NotChecked=0, Total=420 [2024-11-14 02:43:34,105 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 02:43:34,106 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 02:43:34,106 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-11-14 02:43:34,112 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 43. [2024-11-14 02:43:34,112 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 02:43:34,113 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 52 transitions. [2024-11-14 02:43:34,113 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 52 transitions. Word has length 15 [2024-11-14 02:43:34,113 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:34,114 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 52 transitions. [2024-11-14 02:43:34,114 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 02:43:34,114 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 52 transitions. [2024-11-14 02:43:34,114 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-14 02:43:34,114 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:34,115 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:34,134 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-14 02:43:34,318 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:34,319 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:34,319 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:34,319 INFO L85 PathProgramCache]: Analyzing trace with hash 1172635694, now seen corresponding path program 1 times [2024-11-14 02:43:34,320 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:34,320 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1316832218] [2024-11-14 02:43:34,320 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:34,320 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:34,337 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 02:43:34,338 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [949453536] [2024-11-14 02:43:34,338 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:34,338 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:34,338 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:43:34,340 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:43:34,345 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-14 02:43:34,402 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:34,404 INFO L255 TraceCheckSpWp]: Trace formula consists of 66 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-14 02:43:34,405 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:34,506 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 02:43:34,506 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:43:34,627 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 02:43:34,630 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:43:34,630 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1316832218] [2024-11-14 02:43:34,630 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 02:43:34,630 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [949453536] [2024-11-14 02:43:34,630 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [949453536] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:43:34,631 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1184953392] [2024-11-14 02:43:34,634 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2024-11-14 02:43:34,634 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:43:34,634 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:43:34,635 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:43:34,637 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:43:35,390 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 50 for LOIs [2024-11-14 02:43:35,486 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 02:43:40,400 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '585#(and (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| 4))) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-14 02:43:40,400 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 02:43:40,401 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 02:43:40,401 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6] total 11 [2024-11-14 02:43:40,405 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [120925085] [2024-11-14 02:43:40,405 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 02:43:40,406 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-14 02:43:40,406 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:43:40,406 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-14 02:43:40,407 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=287, Unknown=2, NotChecked=0, Total=342 [2024-11-14 02:43:40,407 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 02:43:40,506 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:40,506 INFO L93 Difference]: Finished difference Result 57 states and 65 transitions. [2024-11-14 02:43:40,506 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-14 02:43:40,507 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 02:43:40,507 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:40,507 INFO L225 Difference]: With dead ends: 57 [2024-11-14 02:43:40,507 INFO L226 Difference]: Without dead ends: 46 [2024-11-14 02:43:40,508 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 25 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 67 ImplicationChecksByTransitivity, 5.0s TimeCoverageRelationStatistics Valid=61, Invalid=317, Unknown=2, NotChecked=0, Total=380 [2024-11-14 02:43:40,508 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 02:43:40,509 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 02:43:40,509 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2024-11-14 02:43:40,515 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 40. [2024-11-14 02:43:40,515 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 02:43:40,516 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 43 transitions. [2024-11-14 02:43:40,516 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 43 transitions. Word has length 15 [2024-11-14 02:43:40,516 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:40,516 INFO L471 AbstractCegarLoop]: Abstraction has 40 states and 43 transitions. [2024-11-14 02:43:40,516 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 02:43:40,516 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 43 transitions. [2024-11-14 02:43:40,517 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2024-11-14 02:43:40,517 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:40,517 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2024-11-14 02:43:40,537 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-14 02:43:40,717 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:40,718 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:40,719 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:40,719 INFO L85 PathProgramCache]: Analyzing trace with hash 1524344587, now seen corresponding path program 1 times [2024-11-14 02:43:40,719 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:40,719 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [985463202] [2024-11-14 02:43:40,719 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:40,719 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:40,752 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 02:43:40,757 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1820555301] [2024-11-14 02:43:40,757 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:40,757 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:40,758 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:43:40,763 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:43:40,765 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-14 02:43:40,818 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:40,821 INFO L255 TraceCheckSpWp]: Trace formula consists of 76 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-14 02:43:40,823 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:40,969 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 02:43:40,969 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:43:41,237 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 02:43:41,237 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:43:41,237 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [985463202] [2024-11-14 02:43:41,237 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 02:43:41,238 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1820555301] [2024-11-14 02:43:41,238 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1820555301] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:43:41,238 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1936395118] [2024-11-14 02:43:41,243 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2024-11-14 02:43:41,244 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:43:41,244 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:43:41,244 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:43:41,244 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:43:41,845 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 86 for LOIs [2024-11-14 02:43:42,124 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 02:43:43,698 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '875#(and (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 (= (* |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_#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|) (<= |v_ULTIMATE.start_main_#t~post5#1_32| 4) (<= 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|) (<= 1 ~counter~0) (<= 0 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_37|) (<= 0 |v_ULTIMATE.start_main_#t~post5#1_32|))))) (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 (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))) (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|) (<= |v_ULTIMATE.start_main_#t~post5#1_32| 4) (<= 0 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_38|) (<= 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|)))))) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-14 02:43:43,698 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 02:43:43,698 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 02:43:43,698 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 15 [2024-11-14 02:43:43,698 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1547166022] [2024-11-14 02:43:43,698 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 02:43:43,699 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-14 02:43:43,699 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:43:43,700 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-14 02:43:43,700 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=478, Unknown=0, NotChecked=0, Total=552 [2024-11-14 02:43:43,700 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 02:43:43,885 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:43,885 INFO L93 Difference]: Finished difference Result 48 states and 52 transitions. [2024-11-14 02:43:43,885 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-14 02:43:43,886 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 02:43:43,886 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:43,887 INFO L225 Difference]: With dead ends: 48 [2024-11-14 02:43:43,887 INFO L226 Difference]: Without dead ends: 42 [2024-11-14 02:43:43,887 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 35 SyntacticMatches, 4 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 137 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=95, Invalid=607, Unknown=0, NotChecked=0, Total=702 [2024-11-14 02:43:43,888 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 02:43:43,888 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 02:43:43,889 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2024-11-14 02:43:43,902 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 42. [2024-11-14 02:43:43,905 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 02:43:43,905 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 44 transitions. [2024-11-14 02:43:43,906 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 44 transitions. Word has length 21 [2024-11-14 02:43:43,906 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:43,906 INFO L471 AbstractCegarLoop]: Abstraction has 42 states and 44 transitions. [2024-11-14 02:43:43,906 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 02:43:43,906 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 44 transitions. [2024-11-14 02:43:43,907 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-11-14 02:43:43,907 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:43,907 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1] [2024-11-14 02:43:43,927 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-14 02:43:44,107 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:44,108 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:44,108 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:44,108 INFO L85 PathProgramCache]: Analyzing trace with hash 300810268, now seen corresponding path program 2 times [2024-11-14 02:43:44,108 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:44,108 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1674968461] [2024-11-14 02:43:44,108 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:44,108 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:44,128 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:43:44,431 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 02:43:44,431 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:43:44,431 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1674968461] [2024-11-14 02:43:44,431 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1674968461] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 02:43:44,431 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1670673388] [2024-11-14 02:43:44,431 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 02:43:44,432 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:44,432 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:43:44,435 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:43:44,445 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-14 02:43:44,515 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-14 02:43:44,515 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 02:43:44,520 INFO L255 TraceCheckSpWp]: Trace formula consists of 129 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-14 02:43:44,522 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:44,592 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 02:43:44,592 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:43:44,679 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 02:43:44,679 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1670673388] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:43:44,680 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1895084996] [2024-11-14 02:43:44,681 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2024-11-14 02:43:44,681 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:43:44,682 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:43:44,682 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:43:44,682 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:43:45,177 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 77 for LOIs [2024-11-14 02:43:45,294 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 02:43:46,425 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1261#(and (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)) (<= 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|) (<= |v_ULTIMATE.start_main_#t~post5#1_43| 4))))) (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|)))) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-14 02:43:46,425 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 02:43:46,426 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 02:43:46,426 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 8] total 10 [2024-11-14 02:43:46,426 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [902196375] [2024-11-14 02:43:46,426 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 02:43:46,426 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-14 02:43:46,426 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:43:46,427 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-14 02:43:46,427 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=278, Unknown=0, NotChecked=0, Total=342 [2024-11-14 02:43:46,428 INFO L87 Difference]: Start difference. First operand 42 states and 44 transitions. Second operand has 10 states, 10 states have (on average 3.6) internal successors, (36), 10 states have internal predecessors, (36), 5 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-14 02:43:46,531 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:43:46,531 INFO L93 Difference]: Finished difference Result 53 states and 54 transitions. [2024-11-14 02:43:46,531 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-14 02:43:46,531 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.6) internal successors, (36), 10 states have internal predecessors, (36), 5 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) Word has length 39 [2024-11-14 02:43:46,532 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:43:46,533 INFO L225 Difference]: With dead ends: 53 [2024-11-14 02:43:46,533 INFO L226 Difference]: Without dead ends: 48 [2024-11-14 02:43:46,533 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 97 SyntacticMatches, 10 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 172 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=85, Invalid=377, Unknown=0, NotChecked=0, Total=462 [2024-11-14 02:43:46,534 INFO L432 NwaCegarLoop]: 11 mSDtfsCounter, 0 mSDsluCounter, 37 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 02:43:46,535 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 48 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 02:43:46,536 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2024-11-14 02:43:46,545 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2024-11-14 02:43:46,545 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 36 states have (on average 1.0555555555555556) internal successors, (38), 36 states have internal predecessors, (38), 6 states have call successors, (6), 6 states have call predecessors, (6), 5 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-14 02:43:46,546 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 49 transitions. [2024-11-14 02:43:46,546 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 49 transitions. Word has length 39 [2024-11-14 02:43:46,546 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:43:46,546 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 49 transitions. [2024-11-14 02:43:46,546 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.6) internal successors, (36), 10 states have internal predecessors, (36), 5 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-14 02:43:46,547 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 49 transitions. [2024-11-14 02:43:46,547 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2024-11-14 02:43:46,547 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:43:46,547 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1] [2024-11-14 02:43:46,569 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-14 02:43:46,748 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:46,748 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:43:46,748 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:43:46,749 INFO L85 PathProgramCache]: Analyzing trace with hash -987037763, now seen corresponding path program 2 times [2024-11-14 02:43:46,749 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:43:46,749 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1768393341] [2024-11-14 02:43:46,749 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:43:46,749 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:43:46,768 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 02:43:46,769 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1683603218] [2024-11-14 02:43:46,769 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 02:43:46,769 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:43:46,769 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:43:46,772 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:43:46,774 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-14 02:43:46,838 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-14 02:43:46,838 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 02:43:46,839 INFO L255 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-14 02:43:46,841 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:43:47,003 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 02:43:47,003 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:44:22,645 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 02:44:40,698 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 02:44:48,759 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 02:44:58,812 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 02:45:08,868 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 02:45:18,950 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 02:45:24,994 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 02:45:24,995 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:45:24,995 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1768393341] [2024-11-14 02:45:24,995 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 02:45:24,995 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1683603218] [2024-11-14 02:45:24,995 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1683603218] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:45:24,995 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1927050976] [2024-11-14 02:45:24,997 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2024-11-14 02:45:24,997 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:45:24,997 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:45:24,997 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:45:24,997 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:45:25,406 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 86 for LOIs [2024-11-14 02:45:25,518 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 02:45:29,327 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1711#(and (or (exists ((|v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_54| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_68| Int) (|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_55| Int)) (and (= (* |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_55| 4) (+ (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_68| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_68|) (* (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_68| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_68| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_68|) 2) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_68| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_68| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_68| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_68|))) (not (= (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_68| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_68|) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_68| |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_54|))) (exists ((|v_ULTIMATE.start_main_#t~post5#1_52| Int) (|v_ULTIMATE.start_main_~c~0#1_52| Int)) (and (<= 1 |#StackHeapBarrier|) (<= 0 (+ |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_54| 32768)) (<= |v_ULTIMATE.start_main_#t~post5#1_52| 4) (<= 0 |v_ULTIMATE.start_main_#t~post5#1_52|) (<= 1 ~counter~0) (<= |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_54| |v_ULTIMATE.start_main_~c~0#1_52|) (<= 0 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_68|) (<= |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_54| 32767) (<= 0 |v_ULTIMATE.start_main_~c~0#1_52|))))) (exists ((|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_69| Int) (|v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_55| Int) (|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_56| Int) (|v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_61| Int)) (and (exists ((|v_ULTIMATE.start_main_#t~post5#1_52| Int)) (and (<= 0 |v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_61|) (<= 1 |#StackHeapBarrier|) (<= 0 |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_56|) (<= |v_ULTIMATE.start_main_#t~post5#1_52| 4) (<= 0 |v_ULTIMATE.start_main_#t~post5#1_52|) (<= |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_55| 32767) (<= 1 ~counter~0) (<= 0 (+ |v_ULTIMATE.start_main_~k~0#1_BEFORE_CALL_55| 32768)) (<= 0 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_69|))) (not (= (+ (* 2 (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_69| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_69| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_69|)) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_69| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_69|) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_69| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_69| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_69| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_69|)) (* |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_56| 4)))))) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-14 02:45:29,327 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 02:45:29,327 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 02:45:29,327 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13] total 22 [2024-11-14 02:45:29,328 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2131547424] [2024-11-14 02:45:29,328 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 02:45:29,328 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-14 02:45:29,328 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:45:29,329 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-14 02:45:29,329 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=87, Invalid=577, Unknown=10, NotChecked=318, Total=992 [2024-11-14 02:45:29,330 INFO L87 Difference]: Start difference. First operand 48 states and 49 transitions. Second operand has 22 states, 20 states have (on average 2.3) internal successors, (46), 20 states have internal predecessors, (46), 12 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-14 02:45:29,726 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:45:29,727 INFO L93 Difference]: Finished difference Result 55 states and 57 transitions. [2024-11-14 02:45:29,727 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-14 02:45:29,728 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 2.3) internal successors, (46), 20 states have internal predecessors, (46), 12 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Word has length 45 [2024-11-14 02:45:29,728 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:45:29,729 INFO L225 Difference]: With dead ends: 55 [2024-11-14 02:45:29,729 INFO L226 Difference]: Without dead ends: 50 [2024-11-14 02:45:29,730 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 140 GetRequests, 103 SyntacticMatches, 3 SemanticMatches, 34 ConstructedPredicates, 6 IntricatePredicates, 0 DeprecatedPredicates, 109 ImplicationChecksByTransitivity, 29.6s TimeCoverageRelationStatistics Valid=109, Invalid=775, Unknown=10, NotChecked=366, Total=1260 [2024-11-14 02:45:29,730 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 8 mSDsluCounter, 173 mSDsCounter, 0 mSdLazyCounter, 136 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 193 SdHoareTripleChecker+Invalid, 325 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 136 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 180 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 02:45:29,730 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 193 Invalid, 325 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 136 Invalid, 0 Unknown, 180 Unchecked, 0.2s Time] [2024-11-14 02:45:29,731 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2024-11-14 02:45:29,739 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2024-11-14 02:45:29,739 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 37 states have (on average 1.054054054054054) internal successors, (39), 37 states have internal predecessors, (39), 7 states have call successors, (7), 6 states have call predecessors, (7), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-14 02:45:29,740 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 52 transitions. [2024-11-14 02:45:29,740 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 52 transitions. Word has length 45 [2024-11-14 02:45:29,740 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:45:29,741 INFO L471 AbstractCegarLoop]: Abstraction has 50 states and 52 transitions. [2024-11-14 02:45:29,741 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 2.3) internal successors, (46), 20 states have internal predecessors, (46), 12 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-14 02:45:29,741 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 52 transitions. [2024-11-14 02:45:29,742 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2024-11-14 02:45:29,742 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:45:29,742 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1] [2024-11-14 02:45:29,762 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-14 02:45:29,943 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:45:29,943 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:45:29,943 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:45:29,943 INFO L85 PathProgramCache]: Analyzing trace with hash 1429769090, now seen corresponding path program 3 times [2024-11-14 02:45:29,943 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:45:29,943 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1282892688] [2024-11-14 02:45:29,943 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:45:29,944 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:45:29,973 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 02:45:29,978 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [126040765] [2024-11-14 02:45:29,978 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-14 02:45:29,978 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:45:29,978 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:45:29,983 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:45:29,985 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-14 02:45:30,054 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-14 02:45:30,055 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-14 02:45:30,055 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-14 02:45:30,073 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-14 02:45:30,092 INFO L130 FreeRefinementEngine]: Strategy SIFA_TAIPAN found a feasible trace [2024-11-14 02:45:30,092 INFO L325 BasicCegarLoop]: Counterexample is feasible [2024-11-14 02:45:30,093 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-14 02:45:30,115 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-14 02:45:30,295 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:45:30,299 INFO L407 BasicCegarLoop]: Path program histogram: [3, 2, 1, 1, 1, 1] [2024-11-14 02:45:30,325 INFO L173 ceAbstractionStarter]: Computing trace abstraction results [2024-11-14 02:45:30,328 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 14.11 02:45:30 BoogieIcfgContainer [2024-11-14 02:45:30,328 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-14 02:45:30,328 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-14 02:45:30,328 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-14 02:45:30,329 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-14 02:45:30,330 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 02:43:28" (3/4) ... [2024-11-14 02:45:30,330 INFO L136 WitnessPrinter]: Generating witness for reachability counterexample [2024-11-14 02:45:30,385 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/witness.graphml [2024-11-14 02:45:30,386 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-14 02:45:30,386 INFO L158 Benchmark]: Toolchain (without parser) took 122594.02ms. Allocated memory was 142.6MB in the beginning and 377.5MB in the end (delta: 234.9MB). Free memory was 117.8MB in the beginning and 132.2MB in the end (delta: -14.4MB). Peak memory consumption was 214.1MB. Max. memory is 16.1GB. [2024-11-14 02:45:30,387 INFO L158 Benchmark]: CDTParser took 0.44ms. Allocated memory is still 167.8MB. Free memory is still 105.3MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 02:45:30,387 INFO L158 Benchmark]: CACSL2BoogieTranslator took 308.89ms. Allocated memory is still 142.6MB. Free memory was 117.5MB in the beginning and 106.6MB in the end (delta: 10.9MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-14 02:45:30,388 INFO L158 Benchmark]: Boogie Procedure Inliner took 38.00ms. Allocated memory is still 142.6MB. Free memory was 106.6MB in the beginning and 105.5MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 02:45:30,389 INFO L158 Benchmark]: Boogie Preprocessor took 31.23ms. Allocated memory is still 142.6MB. Free memory was 105.5MB in the beginning and 104.8MB in the end (delta: 729.3kB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 02:45:30,389 INFO L158 Benchmark]: RCFGBuilder took 391.20ms. Allocated memory is still 142.6MB. Free memory was 104.8MB in the beginning and 93.7MB in the end (delta: 11.1MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. [2024-11-14 02:45:30,389 INFO L158 Benchmark]: TraceAbstraction took 121757.06ms. Allocated memory was 142.6MB in the beginning and 377.5MB in the end (delta: 234.9MB). Free memory was 93.0MB in the beginning and 133.0MB in the end (delta: -40.0MB). Peak memory consumption was 189.0MB. Max. memory is 16.1GB. [2024-11-14 02:45:30,390 INFO L158 Benchmark]: Witness Printer took 57.24ms. Allocated memory is still 377.5MB. Free memory was 133.0MB in the beginning and 132.2MB in the end (delta: 811.6kB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 02:45:30,392 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.44ms. Allocated memory is still 167.8MB. Free memory is still 105.3MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 308.89ms. Allocated memory is still 142.6MB. Free memory was 117.5MB in the beginning and 106.6MB in the end (delta: 10.9MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 38.00ms. Allocated memory is still 142.6MB. Free memory was 106.6MB in the beginning and 105.5MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 31.23ms. Allocated memory is still 142.6MB. Free memory was 105.5MB in the beginning and 104.8MB in the end (delta: 729.3kB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 391.20ms. Allocated memory is still 142.6MB. Free memory was 104.8MB in the beginning and 93.7MB in the end (delta: 11.1MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. * TraceAbstraction took 121757.06ms. Allocated memory was 142.6MB in the beginning and 377.5MB in the end (delta: 234.9MB). Free memory was 93.0MB in the beginning and 133.0MB in the end (delta: -40.0MB). Peak memory consumption was 189.0MB. Max. memory is 16.1GB. * Witness Printer took 57.24ms. Allocated memory is still 377.5MB. Free memory was 133.0MB in the beginning and 132.2MB in the end (delta: 811.6kB). There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 12]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L17] int counter = 0; [L19] short k; [L20] long long y, x, c; [L21] k = __VERIFIER_nondet_short() [L23] y = 0 [L24] x = 0 [L25] c = 0 VAL [c=0, counter=0, k=6, x=0, y=0] [L27] EXPR counter++ VAL [c=0, counter=1, k=6, x=0, y=0] [L27] COND TRUE counter++<5 [L28] CALL __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [\old(cond)=1, counter=1] [L10] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=1] [L28] RET __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [c=0, counter=1, k=6, x=0, y=0] [L30] COND FALSE !(!(c < k)) [L33] c = c + 1 [L34] y = y + 1 [L35] x = y * y * y + x VAL [c=1, counter=1, k=6, x=1, y=1] [L27] EXPR counter++ VAL [c=1, counter=2, k=6, x=1, y=1] [L27] COND TRUE counter++<5 [L28] CALL __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [\old(cond)=1, counter=2] [L10] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=2] [L28] RET __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [c=1, counter=2, k=6, x=1, y=1] [L30] COND FALSE !(!(c < k)) [L33] c = c + 1 [L34] y = y + 1 [L35] x = y * y * y + x VAL [c=2, counter=2, k=6, x=9, y=2] [L27] EXPR counter++ VAL [c=2, counter=3, k=6, x=9, y=2] [L27] COND TRUE counter++<5 [L28] CALL __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [\old(cond)=1, counter=3] [L10] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=3] [L28] RET __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [c=2, counter=3, k=6, x=9, y=2] [L30] COND FALSE !(!(c < k)) [L33] c = c + 1 [L34] y = y + 1 [L35] x = y * y * y + x VAL [c=3, counter=3, k=6, x=36, y=3] [L27] EXPR counter++ VAL [c=3, counter=4, k=6, x=36, y=3] [L27] COND TRUE counter++<5 [L28] CALL __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [\old(cond)=1, counter=4] [L10] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=4] [L28] RET __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [c=3, counter=4, k=6, x=36, y=3] [L30] COND FALSE !(!(c < k)) [L33] c = c + 1 [L34] y = y + 1 [L35] x = y * y * y + x VAL [c=4, counter=4, k=6, x=100, y=4] [L27] EXPR counter++ VAL [c=4, counter=5, k=6, x=100, y=4] [L27] COND TRUE counter++<5 [L28] CALL __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [\old(cond)=1, counter=5] [L10] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=5] [L28] RET __VERIFIER_assert(4*x - y*y*y*y - 2*y*y*y - y*y == 0) VAL [c=4, counter=5, k=6, x=100, y=4] [L30] COND FALSE !(!(c < k)) [L33] c = c + 1 [L34] y = y + 1 [L35] x = y * y * y + x VAL [c=5, counter=5, k=6, x=225, y=5] [L27] EXPR counter++ VAL [c=5, counter=6, k=6, x=225, y=5] [L27] COND FALSE !(counter++<5) [L37] CALL __VERIFIER_assert(k*y - (y*y) == 0) VAL [\old(cond)=0, counter=6] [L10] COND TRUE !(cond) VAL [\old(cond)=0, counter=6] [L12] reach_error() VAL [\old(cond)=0, counter=6] - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 15 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 121.6s, OverallIterations: 9, TraceHistogramMax: 6, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 1.1s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 63 SdHoareTripleChecker+Valid, 0.5s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 57 mSDsluCounter, 546 SdHoareTripleChecker+Invalid, 0.4s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 180 IncrementalHoareTripleChecker+Unchecked, 439 mSDsCounter, 30 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 358 IncrementalHoareTripleChecker+Invalid, 568 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 30 mSolverCounterUnsat, 107 mSDtfsCounter, 358 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 438 GetRequests, 297 SyntacticMatches, 19 SemanticMatches, 122 ConstructedPredicates, 6 IntricatePredicates, 2 DeprecatedPredicates, 603 ImplicationChecksByTransitivity, 39.4s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=50occurred in iteration=8, InterpolantAutomatonStates: 66, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 8 MinimizatonAttempts, 10 StatesRemovedByMinimization, 2 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.4s SatisfiabilityAnalysisTime, 100.0s InterpolantComputationTime, 391 NumberOfCodeBlocks, 391 NumberOfCodeBlocksAsserted, 25 NumberOfCheckSat, 329 ConstructedInterpolants, 3 QuantifiedInterpolants, 1872 SizeOfPredicates, 15 NumberOfNonLiveVariables, 521 ConjunctsInSsa, 95 ConjunctsInUnsatCore, 15 InterpolantComputations, 3 PerfectInterpolantSequences, 189/418 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2024-11-14 02:45:30,447 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_b7354932-de6c-409b-a2cb-dda660885954/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Writing human readable error path to file UltimateCounterExample.errorpath Result: FALSE