./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/ps5-ll_unwindbound20.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version a0165632 Calling Ultimate with: /usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/ps5-ll_unwindbound20.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje --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 e51b21c2da790a7136d7ad701fd2bec1367e3ae6dd3a60c613fa7cfa4db22905 --- Real Ultimate output --- This is Ultimate 0.2.5-dev-a016563 [2024-11-09 01:15:24,981 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 01:15:25,101 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/config/svcomp-Reach-32bit-Taipan_Default.epf [2024-11-09 01:15:25,110 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 01:15:25,111 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 01:15:25,145 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 01:15:25,146 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 01:15:25,146 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 01:15:25,147 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-09 01:15:25,148 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-09 01:15:25,148 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-09 01:15:25,149 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-09 01:15:25,149 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-09 01:15:25,150 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-09 01:15:25,150 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-09 01:15:25,151 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-09 01:15:25,151 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-09 01:15:25,152 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-09 01:15:25,153 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-09 01:15:25,153 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-09 01:15:25,154 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-09 01:15:25,154 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-09 01:15:25,155 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 01:15:25,156 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-09 01:15:25,156 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 01:15:25,157 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 01:15:25,157 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 01:15:25,158 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 01:15:25,158 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-09 01:15:25,159 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-09 01:15:25,159 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-09 01:15:25,160 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 01:15:25,160 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 01:15:25,161 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 01:15:25,172 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 01:15:25,173 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-09 01:15:25,173 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-09 01:15:25,174 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-09 01:15:25,175 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-09 01:15:25,175 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 01:15:25,176 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-09 01:15:25,176 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-09 01:15:25,177 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-09 01:15:25,177 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-09 01:15:25,178 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-09 01:15:25,178 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-09 01:15:25,179 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-09 01:15:25,179 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release 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_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje 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 -> e51b21c2da790a7136d7ad701fd2bec1367e3ae6dd3a60c613fa7cfa4db22905 [2024-11-09 01:15:25,573 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 01:15:25,605 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 01:15:25,610 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 01:15:25,613 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 01:15:25,614 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 01:15:25,616 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/../../sv-benchmarks/c/nla-digbench-scaling/ps5-ll_unwindbound20.c Unable to find full path for "g++" [2024-11-09 01:15:28,144 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 01:15:28,384 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 01:15:28,384 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/sv-benchmarks/c/nla-digbench-scaling/ps5-ll_unwindbound20.c [2024-11-09 01:15:28,394 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/data/d6b0f9f46/5339fa2764ad49f5963df07d8cbc7f89/FLAG62301ad84 [2024-11-09 01:15:28,415 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/data/d6b0f9f46/5339fa2764ad49f5963df07d8cbc7f89 [2024-11-09 01:15:28,418 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 01:15:28,420 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 01:15:28,422 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 01:15:28,422 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 01:15:28,430 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 01:15:28,431 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 01:15:28" (1/1) ... [2024-11-09 01:15:28,433 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3aa2f5c5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:15:28, skipping insertion in model container [2024-11-09 01:15:28,433 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 01:15:28" (1/1) ... [2024-11-09 01:15:28,463 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 01:15:28,694 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_a268191a-6df6-4f13-a380-93da71d1d4a7/sv-benchmarks/c/nla-digbench-scaling/ps5-ll_unwindbound20.c[458,471] [2024-11-09 01:15:28,721 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 01:15:28,733 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 01:15:28,749 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_a268191a-6df6-4f13-a380-93da71d1d4a7/sv-benchmarks/c/nla-digbench-scaling/ps5-ll_unwindbound20.c[458,471] [2024-11-09 01:15:28,759 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 01:15:28,787 INFO L204 MainTranslator]: Completed translation [2024-11-09 01:15:28,788 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:15:28 WrapperNode [2024-11-09 01:15:28,788 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 01:15:28,789 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 01:15:28,789 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 01:15:28,789 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 01:15:28,800 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:15:28" (1/1) ... [2024-11-09 01:15:28,809 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:15:28" (1/1) ... [2024-11-09 01:15:28,831 INFO L138 Inliner]: procedures = 14, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 42 [2024-11-09 01:15:28,831 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 01:15:28,832 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 01:15:28,833 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 01:15:28,833 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 01:15:28,844 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:15:28" (1/1) ... [2024-11-09 01:15:28,845 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:15:28" (1/1) ... [2024-11-09 01:15:28,846 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:15:28" (1/1) ... [2024-11-09 01:15:28,847 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:15:28" (1/1) ... [2024-11-09 01:15:28,851 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:15:28" (1/1) ... [2024-11-09 01:15:28,856 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:15:28" (1/1) ... [2024-11-09 01:15:28,858 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:15:28" (1/1) ... [2024-11-09 01:15:28,859 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:15:28" (1/1) ... [2024-11-09 01:15:28,861 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 01:15:28,862 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-09 01:15:28,863 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-09 01:15:28,863 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-09 01:15:28,864 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:15:28" (1/1) ... [2024-11-09 01:15:28,872 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-09 01:15:28,887 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:15:28,900 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-09 01:15:28,903 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-09 01:15:28,936 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 01:15:28,936 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-09 01:15:28,936 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 01:15:28,936 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 01:15:28,937 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-09 01:15:28,937 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-09 01:15:29,040 INFO L238 CfgBuilder]: Building ICFG [2024-11-09 01:15:29,043 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 01:15:29,199 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-09 01:15:29,199 INFO L287 CfgBuilder]: Performing block encoding [2024-11-09 01:15:29,246 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 01:15:29,247 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-09 01:15:29,247 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 01:15:29 BoogieIcfgContainer [2024-11-09 01:15:29,247 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-09 01:15:29,250 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-09 01:15:29,250 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-09 01:15:29,255 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-09 01:15:29,255 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.11 01:15:28" (1/3) ... [2024-11-09 01:15:29,256 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@51796779 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 01:15:29, skipping insertion in model container [2024-11-09 01:15:29,256 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:15:28" (2/3) ... [2024-11-09 01:15:29,257 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@51796779 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 01:15:29, skipping insertion in model container [2024-11-09 01:15:29,257 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 01:15:29" (3/3) ... [2024-11-09 01:15:29,259 INFO L112 eAbstractionObserver]: Analyzing ICFG ps5-ll_unwindbound20.c [2024-11-09 01:15:29,281 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-09 01:15:29,281 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-09 01:15:29,354 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-09 01:15:29,363 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;@271f64b, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-09 01:15:29,364 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-09 01:15:29,369 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-09 01:15:29,377 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2024-11-09 01:15:29,377 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:15:29,378 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2024-11-09 01:15:29,379 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:15:29,385 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:15:29,386 INFO L85 PathProgramCache]: Analyzing trace with hash -1778785576, now seen corresponding path program 1 times [2024-11-09 01:15:29,398 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:15:29,401 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [87634795] [2024-11-09 01:15:29,402 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:15:29,402 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:15:29,523 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:15:29,574 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-09 01:15:29,574 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:15:29,575 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [87634795] [2024-11-09 01:15:29,576 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [87634795] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 01:15:29,576 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 01:15:29,576 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-09 01:15:29,578 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1767881232] [2024-11-09 01:15:29,579 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 01:15:29,583 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-09 01:15:29,584 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:15:29,610 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-09 01:15:29,611 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-09 01:15:29,614 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-09 01:15:29,645 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:15:29,645 INFO L93 Difference]: Finished difference Result 29 states and 42 transitions. [2024-11-09 01:15:29,647 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-09 01:15:29,648 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-09 01:15:29,649 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:15:29,657 INFO L225 Difference]: With dead ends: 29 [2024-11-09 01:15:29,658 INFO L226 Difference]: Without dead ends: 13 [2024-11-09 01:15:29,661 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-09 01:15:29,667 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-09 01:15:29,668 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-09 01:15:29,689 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 13 states. [2024-11-09 01:15:29,709 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 13 to 13. [2024-11-09 01:15:29,711 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-09 01:15:29,712 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 16 transitions. [2024-11-09 01:15:29,715 INFO L78 Accepts]: Start accepts. Automaton has 13 states and 16 transitions. Word has length 6 [2024-11-09 01:15:29,716 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:15:29,716 INFO L471 AbstractCegarLoop]: Abstraction has 13 states and 16 transitions. [2024-11-09 01:15:29,717 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-09 01:15:29,718 INFO L276 IsEmpty]: Start isEmpty. Operand 13 states and 16 transitions. [2024-11-09 01:15:29,719 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-09 01:15:29,719 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:15:29,719 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:15:29,720 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-09 01:15:29,720 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:15:29,721 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:15:29,724 INFO L85 PathProgramCache]: Analyzing trace with hash 291798255, now seen corresponding path program 1 times [2024-11-09 01:15:29,725 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:15:29,725 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [277621722] [2024-11-09 01:15:29,725 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:15:29,726 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:15:29,751 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:15:29,834 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-09 01:15:29,834 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:15:29,834 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [277621722] [2024-11-09 01:15:29,835 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [277621722] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 01:15:29,835 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 01:15:29,835 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-09 01:15:29,836 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1100380558] [2024-11-09 01:15:29,836 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 01:15:29,837 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-09 01:15:29,838 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:15:29,838 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-09 01:15:29,839 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-09 01:15:29,839 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-09 01:15:29,867 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:15:29,867 INFO L93 Difference]: Finished difference Result 23 states and 27 transitions. [2024-11-09 01:15:29,871 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-09 01:15:29,871 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-09 01:15:29,872 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:15:29,872 INFO L225 Difference]: With dead ends: 23 [2024-11-09 01:15:29,873 INFO L226 Difference]: Without dead ends: 15 [2024-11-09 01:15:29,874 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-09 01:15:29,876 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-09 01:15:29,880 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-09 01:15:29,881 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2024-11-09 01:15:29,885 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2024-11-09 01:15:29,888 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-09 01:15:29,889 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 18 transitions. [2024-11-09 01:15:29,890 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 18 transitions. Word has length 7 [2024-11-09 01:15:29,890 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:15:29,890 INFO L471 AbstractCegarLoop]: Abstraction has 15 states and 18 transitions. [2024-11-09 01:15:29,890 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-09 01:15:29,891 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 18 transitions. [2024-11-09 01:15:29,891 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-09 01:15:29,892 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:15:29,892 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:15:29,893 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-09 01:15:29,893 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:15:29,897 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:15:29,897 INFO L85 PathProgramCache]: Analyzing trace with hash 293585715, now seen corresponding path program 1 times [2024-11-09 01:15:29,898 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:15:29,899 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1324939093] [2024-11-09 01:15:29,900 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:15:29,900 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:15:29,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 01:15:29,934 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [154671780] [2024-11-09 01:15:29,934 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:15:29,935 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:15:29,935 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:15:29,937 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:15:29,940 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-09 01:15:30,005 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:15:30,008 INFO L255 TraceCheckSpWp]: Trace formula consists of 46 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 01:15:30,015 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:15:30,185 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-09 01:15:30,186 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 01:15:30,186 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:15:30,186 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1324939093] [2024-11-09 01:15:30,187 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 01:15:30,187 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [154671780] [2024-11-09 01:15:30,188 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [154671780] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 01:15:30,188 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 01:15:30,188 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-09 01:15:30,191 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [427132573] [2024-11-09 01:15:30,191 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 01:15:30,191 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 01:15:30,192 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:15:30,198 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 01:15:30,198 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 01:15:30,199 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-09 01:15:30,330 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:15:30,330 INFO L93 Difference]: Finished difference Result 25 states and 30 transitions. [2024-11-09 01:15:30,331 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 01:15:30,331 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-09 01:15:30,332 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:15:30,332 INFO L225 Difference]: With dead ends: 25 [2024-11-09 01:15:30,332 INFO L226 Difference]: Without dead ends: 21 [2024-11-09 01:15:30,335 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 01:15:30,336 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-09 01:15:30,337 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-09 01:15:30,338 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2024-11-09 01:15:30,352 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2024-11-09 01:15:30,353 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-09 01:15:30,355 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 24 transitions. [2024-11-09 01:15:30,355 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 24 transitions. Word has length 7 [2024-11-09 01:15:30,356 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:15:30,356 INFO L471 AbstractCegarLoop]: Abstraction has 21 states and 24 transitions. [2024-11-09 01:15:30,356 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-09 01:15:30,356 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 24 transitions. [2024-11-09 01:15:30,357 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-09 01:15:30,357 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:15:30,357 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:15:30,380 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-11-09 01:15:30,558 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:15:30,559 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:15:30,559 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:15:30,560 INFO L85 PathProgramCache]: Analyzing trace with hash 782645461, now seen corresponding path program 1 times [2024-11-09 01:15:30,560 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:15:30,560 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1484411104] [2024-11-09 01:15:30,561 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:15:30,561 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:15:30,597 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:15:30,728 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-09 01:15:30,728 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:15:30,729 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1484411104] [2024-11-09 01:15:30,729 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1484411104] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 01:15:30,729 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [232824022] [2024-11-09 01:15:30,729 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:15:30,730 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:15:30,730 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:15:30,732 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:15:30,734 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-09 01:15:30,825 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:15:30,826 INFO L255 TraceCheckSpWp]: Trace formula consists of 67 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-09 01:15:30,829 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:15:30,891 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-09 01:15:30,891 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 01:15:30,973 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-09 01:15:30,973 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [232824022] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 01:15:30,973 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [100873665] [2024-11-09 01:15:31,005 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2024-11-09 01:15:31,006 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 01:15:31,011 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 01:15:31,018 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 01:15:31,019 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 01:15:32,235 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 64 for LOIs [2024-11-09 01:15:32,422 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 01:15:36,390 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '327#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (or (and (exists ((|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_9| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| Int)) (and (<= 0 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9|) (<= 0 |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_9|) (not (= (+ (* (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9|) 6) (* (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9|) 15) (* (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9|) 10)) (+ (* |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_9| 30) |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9|))))) (<= ~counter~0 20)) (and (exists ((|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| Int) (|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_8| Int)) (and (<= 0 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|) (<= 0 |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_8|) (not (= (+ |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| (* |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_8| 30)) (+ (* 15 (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|)) (* (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|) 10) (* 6 (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|))))))) (<= 21 ~counter~0))))' at error location [2024-11-09 01:15:36,391 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 01:15:36,391 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 01:15:36,391 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4, 5] total 8 [2024-11-09 01:15:36,392 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [109298602] [2024-11-09 01:15:36,392 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 01:15:36,392 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-09 01:15:36,393 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:15:36,394 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-09 01:15:36,395 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=226, Unknown=0, NotChecked=0, Total=272 [2024-11-09 01:15:36,395 INFO L87 Difference]: Start difference. First operand 21 states and 24 transitions. Second operand has 8 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 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-09 01:15:36,529 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:15:36,530 INFO L93 Difference]: Finished difference Result 55 states and 65 transitions. [2024-11-09 01:15:36,531 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-09 01:15:36,531 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 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-09 01:15:36,531 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:15:36,532 INFO L225 Difference]: With dead ends: 55 [2024-11-09 01:15:36,533 INFO L226 Difference]: Without dead ends: 47 [2024-11-09 01:15:36,533 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 86 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=66, Invalid=314, Unknown=0, NotChecked=0, Total=380 [2024-11-09 01:15:36,535 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 23 mSDsluCounter, 44 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 57 SdHoareTripleChecker+Invalid, 29 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 01:15:36,535 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 57 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 01:15:36,536 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-11-09 01:15:36,544 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 43. [2024-11-09 01:15:36,544 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-09 01:15:36,546 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 52 transitions. [2024-11-09 01:15:36,546 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 52 transitions. Word has length 15 [2024-11-09 01:15:36,546 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:15:36,547 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 52 transitions. [2024-11-09 01:15:36,547 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 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-09 01:15:36,547 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 52 transitions. [2024-11-09 01:15:36,548 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-09 01:15:36,548 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:15:36,548 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:15:36,574 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-09 01:15:36,749 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:15:36,749 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:15:36,750 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:15:36,750 INFO L85 PathProgramCache]: Analyzing trace with hash 784432921, now seen corresponding path program 1 times [2024-11-09 01:15:36,750 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:15:36,751 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [901407878] [2024-11-09 01:15:36,751 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:15:36,751 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:15:36,778 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 01:15:36,779 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1272444276] [2024-11-09 01:15:36,779 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:15:36,780 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:15:36,780 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:15:36,782 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:15:36,787 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-09 01:15:36,839 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:15:36,840 INFO L255 TraceCheckSpWp]: Trace formula consists of 67 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 01:15:36,842 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:15:36,919 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 01:15:36,920 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 01:15:37,002 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-09 01:15:37,003 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:15:37,003 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [901407878] [2024-11-09 01:15:37,004 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 01:15:37,004 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1272444276] [2024-11-09 01:15:37,004 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1272444276] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-09 01:15:37,004 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-09 01:15:37,005 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-09 01:15:37,005 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [681303939] [2024-11-09 01:15:37,005 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 01:15:37,006 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 01:15:37,006 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:15:37,009 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 01:15:37,009 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-09 01:15:37,010 INFO L87 Difference]: Start difference. First operand 43 states and 52 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 01:15:37,080 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:15:37,080 INFO L93 Difference]: Finished difference Result 57 states and 65 transitions. [2024-11-09 01:15:37,083 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 01:15:37,083 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 15 [2024-11-09 01:15:37,083 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:15:37,084 INFO L225 Difference]: With dead ends: 57 [2024-11-09 01:15:37,084 INFO L226 Difference]: Without dead ends: 49 [2024-11-09 01:15:37,085 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 21 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-09 01:15:37,086 INFO L432 NwaCegarLoop]: 10 mSDtfsCounter, 5 mSDsluCounter, 23 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 33 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 01:15:37,086 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 33 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 01:15:37,091 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2024-11-09 01:15:37,109 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 43. [2024-11-09 01:15:37,110 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 30 states have (on average 1.1333333333333333) internal successors, (34), 32 states have internal predecessors, (34), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-09 01:15:37,111 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 49 transitions. [2024-11-09 01:15:37,111 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 49 transitions. Word has length 15 [2024-11-09 01:15:37,111 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:15:37,112 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 49 transitions. [2024-11-09 01:15:37,112 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 01:15:37,112 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 49 transitions. [2024-11-09 01:15:37,113 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2024-11-09 01:15:37,113 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:15:37,113 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:15:37,135 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-09 01:15:37,313 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:15:37,314 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:15:37,314 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:15:37,314 INFO L85 PathProgramCache]: Analyzing trace with hash 780138349, now seen corresponding path program 1 times [2024-11-09 01:15:37,314 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:15:37,314 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1334107517] [2024-11-09 01:15:37,315 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:15:37,315 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:15:37,378 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 01:15:37,383 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1826166437] [2024-11-09 01:15:37,386 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:15:37,387 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:15:37,387 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:15:37,389 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:15:37,393 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-09 01:15:37,460 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:15:37,464 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-09 01:15:37,466 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:15:37,601 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-09 01:15:37,602 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 01:15:37,759 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-09 01:15:37,759 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:15:37,760 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1334107517] [2024-11-09 01:15:37,760 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 01:15:37,760 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1826166437] [2024-11-09 01:15:37,760 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1826166437] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 01:15:37,760 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2065158383] [2024-11-09 01:15:37,763 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2024-11-09 01:15:37,764 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 01:15:37,764 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 01:15:37,764 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 01:15:37,765 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 01:15:38,429 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2024-11-09 01:15:38,436 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 01:15:38,775 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '894#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (<= ~counter~0 20))' at error location [2024-11-09 01:15:38,775 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 01:15:38,775 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 01:15:38,775 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2024-11-09 01:15:38,776 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [653681755] [2024-11-09 01:15:38,776 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 01:15:38,776 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-09 01:15:38,776 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:15:38,777 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-09 01:15:38,777 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=289, Unknown=0, NotChecked=0, Total=342 [2024-11-09 01:15:38,778 INFO L87 Difference]: Start difference. First operand 43 states and 49 transitions. Second operand has 10 states, 8 states have (on average 2.5) internal successors, (20), 9 states have internal predecessors, (20), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-09 01:15:38,948 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:15:38,948 INFO L93 Difference]: Finished difference Result 52 states and 60 transitions. [2024-11-09 01:15:38,948 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-09 01:15:38,949 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.5) internal successors, (20), 9 states have internal predecessors, (20), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 26 [2024-11-09 01:15:38,949 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:15:38,950 INFO L225 Difference]: With dead ends: 52 [2024-11-09 01:15:38,950 INFO L226 Difference]: Without dead ends: 43 [2024-11-09 01:15:38,951 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 57 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 64 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=68, Invalid=394, Unknown=0, NotChecked=0, Total=462 [2024-11-09 01:15:38,952 INFO L432 NwaCegarLoop]: 17 mSDtfsCounter, 1 mSDsluCounter, 82 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 99 SdHoareTripleChecker+Invalid, 53 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 01:15:38,952 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 99 Invalid, 53 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 01:15:38,957 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-11-09 01:15:38,980 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2024-11-09 01:15:38,982 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 31 states have (on average 1.064516129032258) internal successors, (33), 31 states have internal predecessors, (33), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-09 01:15:38,982 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 46 transitions. [2024-11-09 01:15:38,983 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 46 transitions. Word has length 26 [2024-11-09 01:15:38,983 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:15:38,983 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 46 transitions. [2024-11-09 01:15:38,984 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.5) internal successors, (20), 9 states have internal predecessors, (20), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-09 01:15:38,984 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 46 transitions. [2024-11-09 01:15:38,985 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2024-11-09 01:15:38,985 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:15:38,985 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 5, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:15:39,011 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-09 01:15:39,190 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2024-11-09 01:15:39,190 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:15:39,190 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:15:39,191 INFO L85 PathProgramCache]: Analyzing trace with hash 2136345052, now seen corresponding path program 1 times [2024-11-09 01:15:39,191 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:15:39,191 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [840956343] [2024-11-09 01:15:39,191 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:15:39,191 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:15:39,217 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:15:39,540 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 10 proven. 32 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-09 01:15:39,541 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:15:39,541 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [840956343] [2024-11-09 01:15:39,541 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [840956343] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 01:15:39,541 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1482412415] [2024-11-09 01:15:39,541 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:15:39,542 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:15:39,542 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:15:39,543 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:15:39,545 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-09 01:15:39,612 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:15:39,615 INFO L255 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 01:15:39,617 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:15:39,703 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 24 proven. 56 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-09 01:15:39,704 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 01:15:39,868 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 10 proven. 32 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-09 01:15:39,871 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1482412415] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 01:15:39,871 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1152476696] [2024-11-09 01:15:39,873 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2024-11-09 01:15:39,874 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 01:15:39,875 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 01:15:39,875 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 01:15:39,876 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 01:15:40,416 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2024-11-09 01:15:40,428 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 01:15:40,799 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1324#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 01:15:40,800 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 01:15:40,800 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 01:15:40,800 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 8] total 14 [2024-11-09 01:15:40,800 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [81357334] [2024-11-09 01:15:40,800 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 01:15:40,801 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-09 01:15:40,801 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:15:40,802 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-09 01:15:40,803 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=106, Invalid=446, Unknown=0, NotChecked=0, Total=552 [2024-11-09 01:15:40,803 INFO L87 Difference]: Start difference. First operand 43 states and 46 transitions. Second operand has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (14), 9 states have call predecessors, (14), 9 states have call successors, (14) [2024-11-09 01:15:41,182 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:15:41,182 INFO L93 Difference]: Finished difference Result 129 states and 141 transitions. [2024-11-09 01:15:41,183 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-09 01:15:41,183 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (14), 9 states have call predecessors, (14), 9 states have call successors, (14) Word has length 44 [2024-11-09 01:15:41,184 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:15:41,185 INFO L225 Difference]: With dead ends: 129 [2024-11-09 01:15:41,185 INFO L226 Difference]: Without dead ends: 119 [2024-11-09 01:15:41,186 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 147 GetRequests, 116 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 272 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=219, Invalid=837, Unknown=0, NotChecked=0, Total=1056 [2024-11-09 01:15:41,189 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 77 mSDsluCounter, 92 mSDsCounter, 0 mSdLazyCounter, 67 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 77 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 84 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 67 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 01:15:41,190 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [77 Valid, 105 Invalid, 84 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 67 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 01:15:41,191 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2024-11-09 01:15:41,222 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 94. [2024-11-09 01:15:41,222 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 66 states have (on average 1.106060606060606) internal successors, (73), 71 states have internal predecessors, (73), 17 states have call successors, (17), 11 states have call predecessors, (17), 10 states have return successors, (16), 11 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-09 01:15:41,227 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 106 transitions. [2024-11-09 01:15:41,227 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 106 transitions. Word has length 44 [2024-11-09 01:15:41,228 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:15:41,228 INFO L471 AbstractCegarLoop]: Abstraction has 94 states and 106 transitions. [2024-11-09 01:15:41,228 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (14), 9 states have call predecessors, (14), 9 states have call successors, (14) [2024-11-09 01:15:41,228 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 106 transitions. [2024-11-09 01:15:41,229 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2024-11-09 01:15:41,229 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:15:41,230 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:15:41,251 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-09 01:15:41,433 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:15:41,437 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:15:41,437 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:15:41,437 INFO L85 PathProgramCache]: Analyzing trace with hash 319030395, now seen corresponding path program 2 times [2024-11-09 01:15:41,437 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:15:41,438 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1502894395] [2024-11-09 01:15:41,438 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:15:41,438 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:15:41,533 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 01:15:41,538 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [217661563] [2024-11-09 01:15:41,539 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 01:15:41,539 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:15:41,542 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:15:41,544 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:15:41,545 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-09 01:15:41,817 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-09 01:15:41,817 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 01:15:41,818 INFO L255 TraceCheckSpWp]: Trace formula consists of 149 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-09 01:15:41,821 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:15:42,066 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 20 proven. 47 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-09 01:15:42,066 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 01:15:46,247 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| |c_ULTIMATE.start_main_~y~0#1| 15) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 10) (* |c_ULTIMATE.start_main_~y~0#1| 29) (* |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| |c_ULTIMATE.start_main_~y~0#1| 6)) 30) 0))) is different from false [2024-11-09 01:16:06,353 WARN L873 $PredicateComparison]: unable to prove that (or (not (= |c___VERIFIER_assert_#in~cond| 0)) (forall ((|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| Int) (|v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_43| Int)) (or (= (+ |v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_43| (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_43|)) (+ |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57|))) (= (mod (+ (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| 15) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| 6) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| 10) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| 29)) 30) 0)))) is different from true [2024-11-09 01:16:24,421 WARN L873 $PredicateComparison]: unable to prove that (or (not (= |c___VERIFIER_assert_#in~cond| 0)) (forall ((|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| Int) (|v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_43| Int)) (or (= (+ |v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_43| (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_43|)) (+ |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57|))) (= (mod (+ (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| 15) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| 6) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| 10) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_57| 29)) 30) 0))) (= c___VERIFIER_assert_~cond 0)) is different from true [2024-11-09 01:16:32,484 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| |c_ULTIMATE.start_main_~y~0#1| 15) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 10) (* |c_ULTIMATE.start_main_~y~0#1| 29) (* |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| |c_ULTIMATE.start_main_~y~0#1| 6)) 30) 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-09 01:16:44,574 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| |c_ULTIMATE.start_main_~y~0#1| 15) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 10) (* |c_ULTIMATE.start_main_~y~0#1| 29) (* |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| |c_ULTIMATE.start_main_~y~0#1| 6)) 30) 0))) is different from false [2024-11-09 01:16:56,573 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| |c_ULTIMATE.start_main_~y~0#1| 15) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 10) (* |c_ULTIMATE.start_main_~y~0#1| 29) (* |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| |c_ULTIMATE.start_main_~y~0#1| 6)) 30) 0))) is different from false [2024-11-09 01:17:02,806 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 20 proven. 1 refuted. 6 times theorem prover too weak. 45 trivial. 40 not checked. [2024-11-09 01:17:02,806 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:17:02,806 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1502894395] [2024-11-09 01:17:02,806 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 01:17:02,806 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [217661563] [2024-11-09 01:17:02,807 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [217661563] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 01:17:02,807 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [246040970] [2024-11-09 01:17:02,815 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2024-11-09 01:17:02,815 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 01:17:02,815 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 01:17:02,816 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 01:17:02,816 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 01:17:03,353 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2024-11-09 01:17:03,367 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 01:17:03,778 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2004#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (<= ~counter~0 20))' at error location [2024-11-09 01:17:03,779 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 01:17:03,779 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 01:17:03,779 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13] total 22 [2024-11-09 01:17:03,779 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [569925995] [2024-11-09 01:17:03,779 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 01:17:03,780 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-09 01:17:03,780 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:17:03,780 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-09 01:17:03,781 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=534, Unknown=6, NotChecked=306, Total=930 [2024-11-09 01:17:03,781 INFO L87 Difference]: Start difference. First operand 94 states and 106 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, (14), 3 states have call predecessors, (14), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-09 01:17:04,217 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:17:04,218 INFO L93 Difference]: Finished difference Result 100 states and 111 transitions. [2024-11-09 01:17:04,218 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-09 01:17:04,218 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, (14), 3 states have call predecessors, (14), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Word has length 50 [2024-11-09 01:17:04,219 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:17:04,221 INFO L225 Difference]: With dead ends: 100 [2024-11-09 01:17:04,221 INFO L226 Difference]: Without dead ends: 91 [2024-11-09 01:17:04,222 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 158 GetRequests, 119 SyntacticMatches, 4 SemanticMatches, 35 ConstructedPredicates, 6 IntricatePredicates, 0 DeprecatedPredicates, 142 ImplicationChecksByTransitivity, 12.8s TimeCoverageRelationStatistics Valid=120, Invalid=828, Unknown=6, NotChecked=378, Total=1332 [2024-11-09 01:17:04,223 INFO L432 NwaCegarLoop]: 21 mSDtfsCounter, 5 mSDsluCounter, 215 mSDsCounter, 0 mSdLazyCounter, 184 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 236 SdHoareTripleChecker+Invalid, 460 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 184 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 271 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 01:17:04,224 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 236 Invalid, 460 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 184 Invalid, 0 Unknown, 271 Unchecked, 0.2s Time] [2024-11-09 01:17:04,224 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2024-11-09 01:17:04,244 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 91. [2024-11-09 01:17:04,244 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 66 states have (on average 1.0606060606060606) internal successors, (70), 68 states have internal predecessors, (70), 14 states have call successors, (14), 11 states have call predecessors, (14), 10 states have return successors, (13), 11 states have call predecessors, (13), 13 states have call successors, (13) [2024-11-09 01:17:04,245 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 97 transitions. [2024-11-09 01:17:04,246 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 97 transitions. Word has length 50 [2024-11-09 01:17:04,246 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:17:04,246 INFO L471 AbstractCegarLoop]: Abstraction has 91 states and 97 transitions. [2024-11-09 01:17:04,246 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, (14), 3 states have call predecessors, (14), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-09 01:17:04,247 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 97 transitions. [2024-11-09 01:17:04,248 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2024-11-09 01:17:04,248 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:17:04,249 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 8, 8, 8, 8, 7, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:17:04,266 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-09 01:17:04,449 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:17:04,449 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:17:04,450 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:17:04,450 INFO L85 PathProgramCache]: Analyzing trace with hash 1511344009, now seen corresponding path program 3 times [2024-11-09 01:17:04,450 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:17:04,450 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1306560124] [2024-11-09 01:17:04,450 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:17:04,450 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:17:04,553 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 01:17:04,555 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1478501870] [2024-11-09 01:17:04,559 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-09 01:17:04,560 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:17:04,560 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:17:04,562 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:17:04,568 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-09 01:17:04,667 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-09 01:17:04,667 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 01:17:04,669 INFO L255 TraceCheckSpWp]: Trace formula consists of 212 conjuncts, 36 conjuncts are in the unsatisfiable core [2024-11-09 01:17:04,672 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:17:04,948 INFO L134 CoverageAnalysis]: Checked inductivity of 274 backedges. 18 proven. 112 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2024-11-09 01:17:04,948 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 01:17:05,512 INFO L134 CoverageAnalysis]: Checked inductivity of 274 backedges. 18 proven. 112 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2024-11-09 01:17:05,513 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:17:05,513 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1306560124] [2024-11-09 01:17:05,513 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 01:17:05,513 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1478501870] [2024-11-09 01:17:05,513 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1478501870] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 01:17:05,513 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1082169290] [2024-11-09 01:17:05,515 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2024-11-09 01:17:05,515 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 01:17:05,515 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 01:17:05,515 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 01:17:05,515 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 01:17:05,889 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2024-11-09 01:17:05,899 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 01:17:06,594 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2778#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (<= ~counter~0 20))' at error location [2024-11-09 01:17:06,594 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 01:17:06,594 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 01:17:06,594 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 22 [2024-11-09 01:17:06,594 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1517733167] [2024-11-09 01:17:06,595 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 01:17:06,595 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-09 01:17:06,595 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:17:06,596 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-09 01:17:06,597 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=125, Invalid=805, Unknown=0, NotChecked=0, Total=930 [2024-11-09 01:17:06,597 INFO L87 Difference]: Start difference. First operand 91 states and 97 transitions. Second operand has 22 states, 20 states have (on average 2.8) internal successors, (56), 21 states have internal predecessors, (56), 18 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2024-11-09 01:17:07,106 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:17:07,107 INFO L93 Difference]: Finished difference Result 98 states and 104 transitions. [2024-11-09 01:17:07,107 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-09 01:17:07,107 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 2.8) internal successors, (56), 21 states have internal predecessors, (56), 18 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) Word has length 74 [2024-11-09 01:17:07,108 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:17:07,109 INFO L225 Difference]: With dead ends: 98 [2024-11-09 01:17:07,109 INFO L226 Difference]: Without dead ends: 89 [2024-11-09 01:17:07,110 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 229 GetRequests, 189 SyntacticMatches, 2 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 199 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=224, Invalid=1336, Unknown=0, NotChecked=0, Total=1560 [2024-11-09 01:17:07,111 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 9 mSDsluCounter, 330 mSDsCounter, 0 mSdLazyCounter, 202 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 374 SdHoareTripleChecker+Invalid, 213 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 202 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-09 01:17:07,111 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 374 Invalid, 213 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 202 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-09 01:17:07,112 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2024-11-09 01:17:07,133 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 89. [2024-11-09 01:17:07,133 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 66 states have (on average 1.0151515151515151) internal successors, (67), 66 states have internal predecessors, (67), 12 states have call successors, (12), 11 states have call predecessors, (12), 10 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-09 01:17:07,138 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 90 transitions. [2024-11-09 01:17:07,138 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 90 transitions. Word has length 74 [2024-11-09 01:17:07,139 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:17:07,139 INFO L471 AbstractCegarLoop]: Abstraction has 89 states and 90 transitions. [2024-11-09 01:17:07,139 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 2.8) internal successors, (56), 21 states have internal predecessors, (56), 18 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2024-11-09 01:17:07,139 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 90 transitions. [2024-11-09 01:17:07,140 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2024-11-09 01:17:07,141 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:17:07,141 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 11, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:17:07,159 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-11-09 01:17:07,345 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2024-11-09 01:17:07,345 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:17:07,345 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:17:07,345 INFO L85 PathProgramCache]: Analyzing trace with hash -1931867400, now seen corresponding path program 2 times [2024-11-09 01:17:07,346 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:17:07,346 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1233900548] [2024-11-09 01:17:07,346 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:17:07,346 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:17:07,380 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:17:07,890 INFO L134 CoverageAnalysis]: Checked inductivity of 442 backedges. 22 proven. 200 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-09 01:17:07,890 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:17:07,891 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1233900548] [2024-11-09 01:17:07,891 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1233900548] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 01:17:07,891 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [195049237] [2024-11-09 01:17:07,891 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 01:17:07,891 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:17:07,892 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:17:07,893 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:17:07,895 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-09 01:17:15,965 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2024-11-09 01:17:15,965 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 01:17:15,967 INFO L255 TraceCheckSpWp]: Trace formula consists of 265 conjuncts, 23 conjuncts are in the unsatisfiable core [2024-11-09 01:17:15,969 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:17:16,094 INFO L134 CoverageAnalysis]: Checked inductivity of 442 backedges. 60 proven. 380 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-09 01:17:16,094 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 01:17:16,402 INFO L134 CoverageAnalysis]: Checked inductivity of 442 backedges. 22 proven. 200 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-09 01:17:16,402 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [195049237] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 01:17:16,402 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [748092830] [2024-11-09 01:17:16,404 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2024-11-09 01:17:16,404 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 01:17:16,404 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 01:17:16,405 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 01:17:16,405 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 01:17:16,709 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2024-11-09 01:17:16,715 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 01:17:16,996 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3656#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 01:17:16,996 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 01:17:16,996 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 01:17:16,997 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13, 14] total 24 [2024-11-09 01:17:16,997 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1478662875] [2024-11-09 01:17:16,997 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 01:17:16,998 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-11-09 01:17:16,998 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:17:16,999 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-09 01:17:16,999 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=271, Invalid=851, Unknown=0, NotChecked=0, Total=1122 [2024-11-09 01:17:17,000 INFO L87 Difference]: Start difference. First operand 89 states and 90 transitions. Second operand has 24 states, 24 states have (on average 4.208333333333333) internal successors, (101), 24 states have internal predecessors, (101), 20 states have call successors, (32), 12 states have call predecessors, (32), 12 states have return successors, (31), 20 states have call predecessors, (31), 20 states have call successors, (31) [2024-11-09 01:17:17,556 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:17:17,556 INFO L93 Difference]: Finished difference Result 179 states and 189 transitions. [2024-11-09 01:17:17,556 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2024-11-09 01:17:17,557 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 4.208333333333333) internal successors, (101), 24 states have internal predecessors, (101), 20 states have call successors, (32), 12 states have call predecessors, (32), 12 states have return successors, (31), 20 states have call predecessors, (31), 20 states have call successors, (31) Word has length 92 [2024-11-09 01:17:17,557 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:17:17,558 INFO L225 Difference]: With dead ends: 179 [2024-11-09 01:17:17,559 INFO L226 Difference]: Without dead ends: 169 [2024-11-09 01:17:17,560 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 307 GetRequests, 254 SyntacticMatches, 2 SemanticMatches, 51 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 674 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=700, Invalid=2056, Unknown=0, NotChecked=0, Total=2756 [2024-11-09 01:17:17,561 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 81 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 89 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 81 SdHoareTripleChecker+Valid, 122 SdHoareTripleChecker+Invalid, 104 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 89 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 01:17:17,561 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [81 Valid, 122 Invalid, 104 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 89 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 01:17:17,562 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states. [2024-11-09 01:17:17,595 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 169. [2024-11-09 01:17:17,596 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 169 states, 126 states have (on average 1.007936507936508) internal successors, (127), 126 states have internal predecessors, (127), 22 states have call successors, (22), 21 states have call predecessors, (22), 20 states have return successors, (21), 21 states have call predecessors, (21), 21 states have call successors, (21) [2024-11-09 01:17:17,597 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 169 states to 169 states and 170 transitions. [2024-11-09 01:17:17,597 INFO L78 Accepts]: Start accepts. Automaton has 169 states and 170 transitions. Word has length 92 [2024-11-09 01:17:17,598 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:17:17,599 INFO L471 AbstractCegarLoop]: Abstraction has 169 states and 170 transitions. [2024-11-09 01:17:17,599 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 4.208333333333333) internal successors, (101), 24 states have internal predecessors, (101), 20 states have call successors, (32), 12 states have call predecessors, (32), 12 states have return successors, (31), 20 states have call predecessors, (31), 20 states have call successors, (31) [2024-11-09 01:17:17,599 INFO L276 IsEmpty]: Start isEmpty. Operand 169 states and 170 transitions. [2024-11-09 01:17:17,603 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 173 [2024-11-09 01:17:17,604 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:17:17,604 INFO L215 NwaCegarLoop]: trace histogram [22, 21, 21, 21, 20, 20, 20, 20, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:17:17,641 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-09 01:17:17,804 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-09 01:17:17,805 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:17:17,805 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:17:17,805 INFO L85 PathProgramCache]: Analyzing trace with hash -602237060, now seen corresponding path program 3 times [2024-11-09 01:17:17,805 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:17:17,805 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [333357140] [2024-11-09 01:17:17,805 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:17:17,806 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:17:18,166 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 01:17:18,169 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1397123577] [2024-11-09 01:17:18,169 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-09 01:17:18,169 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:17:18,170 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:17:18,171 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:17:18,173 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a268191a-6df6-4f13-a380-93da71d1d4a7/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process