./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound20.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version cf1a7837 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_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound20.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX --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 d3c61dee0c4c48de96844df391dc470a843cae078bb175116ed4a6b789669168 --- Real Ultimate output --- This is Ultimate 0.2.3-dev-cf1a783 [2023-11-12 01:03:28,665 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-12 01:03:28,762 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-12 01:03:28,766 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-12 01:03:28,767 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-12 01:03:28,793 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-12 01:03:28,794 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-12 01:03:28,794 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-12 01:03:28,795 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-12 01:03:28,796 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-12 01:03:28,796 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-12 01:03:28,797 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-12 01:03:28,798 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-12 01:03:28,798 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-12 01:03:28,799 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-12 01:03:28,799 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-12 01:03:28,800 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-12 01:03:28,800 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-12 01:03:28,801 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-12 01:03:28,802 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-12 01:03:28,802 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-12 01:03:28,807 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-12 01:03:28,808 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-12 01:03:28,808 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-12 01:03:28,809 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-12 01:03:28,809 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-12 01:03:28,810 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-12 01:03:28,810 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-12 01:03:28,810 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-12 01:03:28,811 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-12 01:03:28,811 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-12 01:03:28,812 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-12 01:03:28,812 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-12 01:03:28,813 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-12 01:03:28,813 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-12 01:03:28,813 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-12 01:03:28,814 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 01:03:28,814 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-12 01:03:28,815 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-12 01:03:28,815 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-12 01:03:28,816 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-12 01:03:28,822 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-12 01:03:28,823 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-12 01:03:28,823 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-12 01:03:28,823 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-12 01:03:28,824 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_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/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_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX 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 -> d3c61dee0c4c48de96844df391dc470a843cae078bb175116ed4a6b789669168 [2023-11-12 01:03:29,172 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-12 01:03:29,195 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-12 01:03:29,198 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-12 01:03:29,199 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-12 01:03:29,200 INFO L274 PluginConnector]: CDTParser initialized [2023-11-12 01:03:29,201 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/../../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound20.c [2023-11-12 01:03:32,367 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-12 01:03:32,654 INFO L384 CDTParser]: Found 1 translation units. [2023-11-12 01:03:32,655 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound20.c [2023-11-12 01:03:32,664 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/data/91dc839f3/5f828b89bd994f35a51c50b796dd1bd6/FLAG322cd10d9 [2023-11-12 01:03:32,679 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/data/91dc839f3/5f828b89bd994f35a51c50b796dd1bd6 [2023-11-12 01:03:32,682 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-12 01:03:32,684 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-12 01:03:32,685 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-12 01:03:32,686 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-12 01:03:32,692 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-12 01:03:32,695 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 01:03:32" (1/1) ... [2023-11-12 01:03:32,697 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@73bd001c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:32, skipping insertion in model container [2023-11-12 01:03:32,697 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 01:03:32" (1/1) ... [2023-11-12 01:03:32,722 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-12 01:03:32,926 WARN L240 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_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound20.c[588,601] [2023-11-12 01:03:32,970 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 01:03:32,985 INFO L202 MainTranslator]: Completed pre-run [2023-11-12 01:03:33,001 WARN L240 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_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound20.c[588,601] [2023-11-12 01:03:33,025 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 01:03:33,044 INFO L206 MainTranslator]: Completed translation [2023-11-12 01:03:33,044 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:33 WrapperNode [2023-11-12 01:03:33,045 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-12 01:03:33,046 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-12 01:03:33,046 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-12 01:03:33,046 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-12 01:03:33,054 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:33" (1/1) ... [2023-11-12 01:03:33,076 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:33" (1/1) ... [2023-11-12 01:03:33,106 INFO L138 Inliner]: procedures = 14, calls = 19, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 48 [2023-11-12 01:03:33,106 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-12 01:03:33,107 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-12 01:03:33,107 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-12 01:03:33,107 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-12 01:03:33,116 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:33" (1/1) ... [2023-11-12 01:03:33,117 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:33" (1/1) ... [2023-11-12 01:03:33,120 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:33" (1/1) ... [2023-11-12 01:03:33,121 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:33" (1/1) ... [2023-11-12 01:03:33,136 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:33" (1/1) ... [2023-11-12 01:03:33,140 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:33" (1/1) ... [2023-11-12 01:03:33,141 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:33" (1/1) ... [2023-11-12 01:03:33,142 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:33" (1/1) ... [2023-11-12 01:03:33,144 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-12 01:03:33,145 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-12 01:03:33,145 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-12 01:03:33,145 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-12 01:03:33,146 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:33" (1/1) ... [2023-11-12 01:03:33,152 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 01:03:33,164 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:03:33,179 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-12 01:03:33,212 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-12 01:03:33,225 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-12 01:03:33,225 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-12 01:03:33,225 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-12 01:03:33,225 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-12 01:03:33,226 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-11-12 01:03:33,226 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-11-12 01:03:33,305 INFO L236 CfgBuilder]: Building ICFG [2023-11-12 01:03:33,308 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-12 01:03:33,492 INFO L277 CfgBuilder]: Performing block encoding [2023-11-12 01:03:33,543 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-12 01:03:33,544 INFO L302 CfgBuilder]: Removed 1 assume(true) statements. [2023-11-12 01:03:33,547 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 01:03:33 BoogieIcfgContainer [2023-11-12 01:03:33,547 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-12 01:03:33,550 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-12 01:03:33,550 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-12 01:03:33,554 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-12 01:03:33,554 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.11 01:03:32" (1/3) ... [2023-11-12 01:03:33,555 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4d02d828 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 01:03:33, skipping insertion in model container [2023-11-12 01:03:33,555 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:03:33" (2/3) ... [2023-11-12 01:03:33,556 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4d02d828 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 01:03:33, skipping insertion in model container [2023-11-12 01:03:33,556 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 01:03:33" (3/3) ... [2023-11-12 01:03:33,558 INFO L112 eAbstractionObserver]: Analyzing ICFG cohencu-ll_valuebound20.c [2023-11-12 01:03:33,578 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-12 01:03:33,578 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-12 01:03:33,636 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-12 01:03:33,644 INFO L357 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, mHoare=true, 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;@6c2495c0, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-12 01:03:33,644 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-12 01:03:33,648 INFO L276 IsEmpty]: Start isEmpty. Operand has 22 states, 8 states have (on average 1.5) internal successors, (12), 9 states have internal predecessors, (12), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2023-11-12 01:03:33,656 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2023-11-12 01:03:33,657 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:03:33,657 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2023-11-12 01:03:33,658 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:03:33,664 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:03:33,665 INFO L85 PathProgramCache]: Analyzing trace with hash -1070258279, now seen corresponding path program 1 times [2023-11-12 01:03:33,675 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:03:33,676 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [615077339] [2023-11-12 01:03:33,677 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:03:33,678 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:03:33,791 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:03:34,166 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-12 01:03:34,167 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:03:34,167 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [615077339] [2023-11-12 01:03:34,168 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [615077339] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 01:03:34,168 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 01:03:34,169 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-11-12 01:03:34,170 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [868809495] [2023-11-12 01:03:34,171 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 01:03:34,175 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 01:03:34,175 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:03:34,221 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 01:03:34,221 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-12 01:03:34,224 INFO L87 Difference]: Start difference. First operand has 22 states, 8 states have (on average 1.5) internal successors, (12), 9 states have internal predecessors, (12), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 5 states, 5 states have (on average 1.0) internal successors, (5), 3 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) [2023-11-12 01:03:34,339 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:03:34,339 INFO L93 Difference]: Finished difference Result 47 states and 82 transitions. [2023-11-12 01:03:34,341 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-12 01:03:34,342 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.0) internal successors, (5), 3 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 [2023-11-12 01:03:34,342 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:03:34,350 INFO L225 Difference]: With dead ends: 47 [2023-11-12 01:03:34,350 INFO L226 Difference]: Without dead ends: 24 [2023-11-12 01:03:34,354 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-11-12 01:03:34,358 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 7 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 74 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 01:03:34,359 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 74 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 01:03:34,376 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2023-11-12 01:03:34,401 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2023-11-12 01:03:34,403 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 10 states have (on average 1.2) internal successors, (12), 11 states have internal predecessors, (12), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2023-11-12 01:03:34,405 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 33 transitions. [2023-11-12 01:03:34,406 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 33 transitions. Word has length 6 [2023-11-12 01:03:34,407 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:03:34,407 INFO L495 AbstractCegarLoop]: Abstraction has 24 states and 33 transitions. [2023-11-12 01:03:34,407 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.0) internal successors, (5), 3 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) [2023-11-12 01:03:34,407 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 33 transitions. [2023-11-12 01:03:34,409 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2023-11-12 01:03:34,409 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:03:34,409 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:03:34,409 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-12 01:03:34,410 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:03:34,410 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:03:34,411 INFO L85 PathProgramCache]: Analyzing trace with hash -1088770990, now seen corresponding path program 1 times [2023-11-12 01:03:34,411 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:03:34,411 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1885836351] [2023-11-12 01:03:34,411 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:03:34,412 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:03:34,426 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 01:03:34,427 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [216361923] [2023-11-12 01:03:34,427 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:03:34,427 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:03:34,427 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:03:34,432 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:03:34,464 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-12 01:03:34,522 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:03:34,524 INFO L262 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 17 conjunts are in the unsatisfiable core [2023-11-12 01:03:34,530 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:03:34,708 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-12 01:03:34,710 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 01:03:34,935 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-12 01:03:34,936 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:03:34,937 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1885836351] [2023-11-12 01:03:34,937 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 01:03:34,938 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [216361923] [2023-11-12 01:03:34,939 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [216361923] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 01:03:34,940 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [247995580] [2023-11-12 01:03:34,971 INFO L159 IcfgInterpreter]: Started Sifa with 10 locations of interest [2023-11-12 01:03:34,972 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 01:03:34,975 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 01:03:34,981 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 01:03:34,982 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 01:03:35,506 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 72 for LOIs [2023-11-12 01:03:35,811 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 01:03:36,381 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [247995580] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 01:03:36,381 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-11-12 01:03:36,382 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [8, 7] total 15 [2023-11-12 01:03:36,383 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1412646092] [2023-11-12 01:03:36,384 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 01:03:36,385 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 01:03:36,385 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:03:36,387 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 01:03:36,387 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=158, Unknown=0, NotChecked=0, Total=210 [2023-11-12 01:03:36,388 INFO L87 Difference]: Start difference. First operand 24 states and 33 transitions. Second operand has 5 states, 5 states have (on average 1.4) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-12 01:03:36,660 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:03:36,660 INFO L93 Difference]: Finished difference Result 55 states and 72 transitions. [2023-11-12 01:03:36,660 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-12 01:03:36,661 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (2), 1 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 11 [2023-11-12 01:03:36,661 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:03:36,662 INFO L225 Difference]: With dead ends: 55 [2023-11-12 01:03:36,662 INFO L226 Difference]: Without dead ends: 39 [2023-11-12 01:03:36,663 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 17 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 50 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=52, Invalid=158, Unknown=0, NotChecked=0, Total=210 [2023-11-12 01:03:36,665 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 0 mSDsluCounter, 40 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 61 SdHoareTripleChecker+Invalid, 62 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-12 01:03:36,665 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 61 Invalid, 62 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-12 01:03:36,667 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2023-11-12 01:03:36,700 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2023-11-12 01:03:36,701 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 18 states have (on average 1.1111111111111112) internal successors, (20), 19 states have internal predecessors, (20), 16 states have call successors, (16), 4 states have call predecessors, (16), 4 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2023-11-12 01:03:36,703 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 51 transitions. [2023-11-12 01:03:36,703 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 51 transitions. Word has length 11 [2023-11-12 01:03:36,703 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:03:36,704 INFO L495 AbstractCegarLoop]: Abstraction has 39 states and 51 transitions. [2023-11-12 01:03:36,704 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-12 01:03:36,704 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 51 transitions. [2023-11-12 01:03:36,705 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2023-11-12 01:03:36,706 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:03:36,706 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:03:36,720 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-12 01:03:36,912 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:03:36,912 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:03:36,912 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:03:36,913 INFO L85 PathProgramCache]: Analyzing trace with hash -700920967, now seen corresponding path program 1 times [2023-11-12 01:03:36,913 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:03:36,913 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [964463099] [2023-11-12 01:03:36,913 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:03:36,913 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:03:36,932 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 01:03:36,933 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [466584757] [2023-11-12 01:03:36,933 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:03:36,933 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:03:36,933 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:03:36,935 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:03:36,945 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-12 01:03:37,020 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:03:37,022 INFO L262 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 21 conjunts are in the unsatisfiable core [2023-11-12 01:03:37,027 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:03:37,145 INFO L134 CoverageAnalysis]: Checked inductivity of 75 backedges. 11 proven. 19 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2023-11-12 01:03:37,146 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 01:03:37,338 INFO L134 CoverageAnalysis]: Checked inductivity of 75 backedges. 13 proven. 17 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2023-11-12 01:03:37,339 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:03:37,339 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [964463099] [2023-11-12 01:03:37,339 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 01:03:37,339 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [466584757] [2023-11-12 01:03:37,339 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [466584757] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 01:03:37,340 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [950029337] [2023-11-12 01:03:37,343 INFO L159 IcfgInterpreter]: Started Sifa with 14 locations of interest [2023-11-12 01:03:37,344 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 01:03:37,344 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 01:03:37,345 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 01:03:37,345 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 01:03:38,962 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 01:03:38,968 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 01:03:39,297 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '600#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 01:03:39,297 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 01:03:39,298 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 01:03:39,298 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2023-11-12 01:03:39,298 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1533402518] [2023-11-12 01:03:39,298 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 01:03:39,299 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-11-12 01:03:39,299 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:03:39,300 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-11-12 01:03:39,300 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=275, Unknown=0, NotChecked=0, Total=342 [2023-11-12 01:03:39,301 INFO L87 Difference]: Start difference. First operand 39 states and 51 transitions. Second operand has 13 states, 13 states have (on average 1.6153846153846154) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2023-11-12 01:03:39,829 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:03:39,830 INFO L93 Difference]: Finished difference Result 62 states and 83 transitions. [2023-11-12 01:03:39,830 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-12 01:03:39,831 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 1.6153846153846154) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) Word has length 38 [2023-11-12 01:03:39,831 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:03:39,832 INFO L225 Difference]: With dead ends: 62 [2023-11-12 01:03:39,833 INFO L226 Difference]: Without dead ends: 60 [2023-11-12 01:03:39,833 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 93 SyntacticMatches, 2 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 128 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=97, Invalid=409, Unknown=0, NotChecked=0, Total=506 [2023-11-12 01:03:39,834 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 22 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 135 mSolverCounterSat, 73 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 101 SdHoareTripleChecker+Invalid, 208 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 73 IncrementalHoareTripleChecker+Valid, 135 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-12 01:03:39,835 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 101 Invalid, 208 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [73 Valid, 135 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-12 01:03:39,836 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2023-11-12 01:03:39,865 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 47. [2023-11-12 01:03:39,866 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 24 states have (on average 1.0833333333333333) internal successors, (26), 25 states have internal predecessors, (26), 16 states have call successors, (16), 6 states have call predecessors, (16), 6 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2023-11-12 01:03:39,873 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 57 transitions. [2023-11-12 01:03:39,873 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 57 transitions. Word has length 38 [2023-11-12 01:03:39,874 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:03:39,875 INFO L495 AbstractCegarLoop]: Abstraction has 47 states and 57 transitions. [2023-11-12 01:03:39,875 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 1.6153846153846154) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2023-11-12 01:03:39,875 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 57 transitions. [2023-11-12 01:03:39,877 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2023-11-12 01:03:39,877 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:03:39,877 INFO L195 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:03:39,888 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-12 01:03:40,083 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:03:40,084 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:03:40,084 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:03:40,084 INFO L85 PathProgramCache]: Analyzing trace with hash -1757443022, now seen corresponding path program 2 times [2023-11-12 01:03:40,084 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:03:40,085 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1898557981] [2023-11-12 01:03:40,085 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:03:40,085 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:03:40,106 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 01:03:40,111 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [151119310] [2023-11-12 01:03:40,111 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-12 01:03:40,111 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:03:40,112 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:03:40,114 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:03:40,119 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-12 01:03:40,172 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-11-12 01:03:40,173 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 01:03:40,174 INFO L262 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 16 conjunts are in the unsatisfiable core [2023-11-12 01:03:40,180 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:03:40,273 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 14 proven. 4 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2023-11-12 01:03:40,273 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 01:03:40,367 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 14 proven. 4 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2023-11-12 01:03:40,367 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:03:40,367 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1898557981] [2023-11-12 01:03:40,368 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 01:03:40,369 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [151119310] [2023-11-12 01:03:40,369 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [151119310] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 01:03:40,369 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1026106073] [2023-11-12 01:03:40,374 INFO L159 IcfgInterpreter]: Started Sifa with 14 locations of interest [2023-11-12 01:03:40,374 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 01:03:40,375 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 01:03:40,375 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 01:03:40,375 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 01:03:41,664 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 01:03:41,686 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 01:03:41,960 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1045#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 01:03:41,960 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 01:03:41,961 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 01:03:41,961 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2023-11-12 01:03:41,961 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [668531287] [2023-11-12 01:03:41,961 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 01:03:41,962 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-11-12 01:03:41,962 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:03:41,963 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-11-12 01:03:41,963 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=193, Unknown=0, NotChecked=0, Total=240 [2023-11-12 01:03:41,963 INFO L87 Difference]: Start difference. First operand 47 states and 57 transitions. Second operand has 10 states, 10 states have (on average 1.6) internal successors, (16), 8 states have internal predecessors, (16), 4 states have call successors, (16), 3 states have call predecessors, (16), 1 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2023-11-12 01:03:42,162 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:03:42,162 INFO L93 Difference]: Finished difference Result 74 states and 92 transitions. [2023-11-12 01:03:42,163 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-11-12 01:03:42,163 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 1.6) internal successors, (16), 8 states have internal predecessors, (16), 4 states have call successors, (16), 3 states have call predecessors, (16), 1 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 43 [2023-11-12 01:03:42,164 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:03:42,165 INFO L225 Difference]: With dead ends: 74 [2023-11-12 01:03:42,166 INFO L226 Difference]: Without dead ends: 72 [2023-11-12 01:03:42,167 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 128 GetRequests, 111 SyntacticMatches, 2 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 67 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=53, Invalid=219, Unknown=0, NotChecked=0, Total=272 [2023-11-12 01:03:42,172 INFO L413 NwaCegarLoop]: 36 mSDtfsCounter, 11 mSDsluCounter, 161 mSDsCounter, 0 mSdLazyCounter, 90 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 197 SdHoareTripleChecker+Invalid, 102 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 90 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 01:03:42,173 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 197 Invalid, 102 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 90 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 01:03:42,177 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2023-11-12 01:03:42,215 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 63. [2023-11-12 01:03:42,215 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 34 states have (on average 1.0588235294117647) internal successors, (36), 36 states have internal predecessors, (36), 19 states have call successors, (19), 9 states have call predecessors, (19), 9 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) [2023-11-12 01:03:42,219 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 73 transitions. [2023-11-12 01:03:42,220 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 73 transitions. Word has length 43 [2023-11-12 01:03:42,220 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:03:42,220 INFO L495 AbstractCegarLoop]: Abstraction has 63 states and 73 transitions. [2023-11-12 01:03:42,221 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 1.6) internal successors, (16), 8 states have internal predecessors, (16), 4 states have call successors, (16), 3 states have call predecessors, (16), 1 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2023-11-12 01:03:42,221 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 73 transitions. [2023-11-12 01:03:42,224 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2023-11-12 01:03:42,228 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:03:42,228 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:03:42,239 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-12 01:03:42,434 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:03:42,434 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:03:42,435 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:03:42,435 INFO L85 PathProgramCache]: Analyzing trace with hash 1748922073, now seen corresponding path program 3 times [2023-11-12 01:03:42,435 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:03:42,436 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [120486358] [2023-11-12 01:03:42,436 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:03:42,436 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:03:42,450 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 01:03:42,450 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1950009277] [2023-11-12 01:03:42,451 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-12 01:03:42,451 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:03:42,451 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:03:42,457 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:03:42,480 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-12 01:03:42,537 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-12 01:03:42,537 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 01:03:42,539 INFO L262 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 27 conjunts are in the unsatisfiable core [2023-11-12 01:03:42,542 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:03:42,691 INFO L134 CoverageAnalysis]: Checked inductivity of 133 backedges. 21 proven. 21 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-11-12 01:03:42,691 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 01:03:43,279 INFO L134 CoverageAnalysis]: Checked inductivity of 133 backedges. 21 proven. 21 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-11-12 01:03:43,279 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:03:43,279 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [120486358] [2023-11-12 01:03:43,280 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 01:03:43,280 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1950009277] [2023-11-12 01:03:43,280 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1950009277] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 01:03:43,280 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1162739710] [2023-11-12 01:03:43,283 INFO L159 IcfgInterpreter]: Started Sifa with 14 locations of interest [2023-11-12 01:03:43,283 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 01:03:43,283 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 01:03:43,284 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 01:03:43,284 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 01:03:44,460 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 01:03:44,467 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 01:03:44,737 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1555#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 01:03:44,738 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 01:03:44,738 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 01:03:44,738 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2023-11-12 01:03:44,738 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1607926969] [2023-11-12 01:03:44,738 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 01:03:44,739 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-11-12 01:03:44,739 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:03:44,740 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-11-12 01:03:44,740 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=275, Unknown=0, NotChecked=0, Total=342 [2023-11-12 01:03:44,741 INFO L87 Difference]: Start difference. First operand 63 states and 73 transitions. Second operand has 13 states, 13 states have (on average 1.6153846153846154) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2023-11-12 01:03:45,335 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:03:45,336 INFO L93 Difference]: Finished difference Result 82 states and 98 transitions. [2023-11-12 01:03:45,336 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-12 01:03:45,336 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 1.6153846153846154) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) Word has length 48 [2023-11-12 01:03:45,337 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:03:45,338 INFO L225 Difference]: With dead ends: 82 [2023-11-12 01:03:45,338 INFO L226 Difference]: Without dead ends: 74 [2023-11-12 01:03:45,339 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 123 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 118 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=91, Invalid=371, Unknown=0, NotChecked=0, Total=462 [2023-11-12 01:03:45,340 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 20 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 161 mSolverCounterSat, 50 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 110 SdHoareTripleChecker+Invalid, 211 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 50 IncrementalHoareTripleChecker+Valid, 161 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-12 01:03:45,340 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 110 Invalid, 211 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [50 Valid, 161 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-12 01:03:45,341 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2023-11-12 01:03:45,365 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 68. [2023-11-12 01:03:45,366 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 40 states have (on average 1.05) internal successors, (42), 42 states have internal predecessors, (42), 16 states have call successors, (16), 11 states have call predecessors, (16), 11 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) [2023-11-12 01:03:45,367 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 73 transitions. [2023-11-12 01:03:45,367 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 73 transitions. Word has length 48 [2023-11-12 01:03:45,367 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:03:45,368 INFO L495 AbstractCegarLoop]: Abstraction has 68 states and 73 transitions. [2023-11-12 01:03:45,368 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 1.6153846153846154) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2023-11-12 01:03:45,368 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 73 transitions. [2023-11-12 01:03:45,369 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2023-11-12 01:03:45,369 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:03:45,369 INFO L195 NwaCegarLoop]: trace histogram [12, 11, 11, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:03:45,385 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-12 01:03:45,580 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:03:45,581 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:03:45,581 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:03:45,581 INFO L85 PathProgramCache]: Analyzing trace with hash -2025080784, now seen corresponding path program 1 times [2023-11-12 01:03:45,581 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:03:45,582 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2029877532] [2023-11-12 01:03:45,582 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:03:45,582 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:03:45,591 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 01:03:45,592 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1665572855] [2023-11-12 01:03:45,592 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:03:45,592 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:03:45,592 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:03:45,593 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:03:45,612 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-12 01:03:45,667 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:03:45,669 INFO L262 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 26 conjunts are in the unsatisfiable core [2023-11-12 01:03:45,672 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:03:45,929 INFO L134 CoverageAnalysis]: Checked inductivity of 249 backedges. 21 proven. 38 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2023-11-12 01:03:45,930 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 01:03:48,204 INFO L134 CoverageAnalysis]: Checked inductivity of 249 backedges. 21 proven. 38 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2023-11-12 01:03:48,204 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:03:48,204 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2029877532] [2023-11-12 01:03:48,205 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 01:03:48,205 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1665572855] [2023-11-12 01:03:48,205 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1665572855] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 01:03:48,205 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [681488198] [2023-11-12 01:03:48,207 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-11-12 01:03:48,208 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 01:03:48,208 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 01:03:48,208 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 01:03:48,208 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 01:03:49,273 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 01:03:49,278 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 01:03:49,829 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2181#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 01:03:49,829 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 01:03:49,829 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 01:03:49,829 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2023-11-12 01:03:49,829 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1061471544] [2023-11-12 01:03:49,829 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 01:03:49,830 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-12 01:03:49,830 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:03:49,831 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-12 01:03:49,831 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=346, Unknown=0, NotChecked=0, Total=420 [2023-11-12 01:03:49,832 INFO L87 Difference]: Start difference. First operand 68 states and 73 transitions. Second operand has 15 states, 13 states have (on average 1.7692307692307692) internal successors, (23), 13 states have internal predecessors, (23), 7 states have call successors, (24), 3 states have call predecessors, (24), 2 states have return successors, (22), 6 states have call predecessors, (22), 7 states have call successors, (22) [2023-11-12 01:03:51,297 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:03:51,297 INFO L93 Difference]: Finished difference Result 84 states and 92 transitions. [2023-11-12 01:03:51,298 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-12 01:03:51,298 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 1.7692307692307692) internal successors, (23), 13 states have internal predecessors, (23), 7 states have call successors, (24), 3 states have call predecessors, (24), 2 states have return successors, (22), 6 states have call predecessors, (22), 7 states have call successors, (22) Word has length 64 [2023-11-12 01:03:51,299 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:03:51,300 INFO L225 Difference]: With dead ends: 84 [2023-11-12 01:03:51,300 INFO L226 Difference]: Without dead ends: 82 [2023-11-12 01:03:51,300 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 193 GetRequests, 169 SyntacticMatches, 2 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 135 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=96, Invalid=456, Unknown=0, NotChecked=0, Total=552 [2023-11-12 01:03:51,301 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 18 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 141 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 165 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 141 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2023-11-12 01:03:51,301 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 105 Invalid, 165 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 141 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2023-11-12 01:03:51,302 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2023-11-12 01:03:51,328 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 81. [2023-11-12 01:03:51,329 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 81 states, 47 states have (on average 1.0638297872340425) internal successors, (50), 49 states have internal predecessors, (50), 20 states have call successors, (20), 13 states have call predecessors, (20), 13 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2023-11-12 01:03:51,330 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 89 transitions. [2023-11-12 01:03:51,330 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 89 transitions. Word has length 64 [2023-11-12 01:03:51,330 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:03:51,330 INFO L495 AbstractCegarLoop]: Abstraction has 81 states and 89 transitions. [2023-11-12 01:03:51,331 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 1.7692307692307692) internal successors, (23), 13 states have internal predecessors, (23), 7 states have call successors, (24), 3 states have call predecessors, (24), 2 states have return successors, (22), 6 states have call predecessors, (22), 7 states have call successors, (22) [2023-11-12 01:03:51,331 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 89 transitions. [2023-11-12 01:03:51,332 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2023-11-12 01:03:51,333 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:03:51,333 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:03:51,345 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2023-11-12 01:03:51,538 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:03:51,539 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:03:51,539 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:03:51,539 INFO L85 PathProgramCache]: Analyzing trace with hash -1309118309, now seen corresponding path program 1 times [2023-11-12 01:03:51,539 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:03:51,540 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1490163554] [2023-11-12 01:03:51,540 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:03:51,540 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:03:51,552 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 01:03:51,555 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2063752463] [2023-11-12 01:03:51,555 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:03:51,560 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:03:51,560 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:03:51,561 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:03:51,564 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-12 01:03:51,622 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:03:51,623 INFO L262 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 26 conjunts are in the unsatisfiable core [2023-11-12 01:03:51,627 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:03:51,882 INFO L134 CoverageAnalysis]: Checked inductivity of 295 backedges. 23 proven. 41 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-11-12 01:03:51,883 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 01:03:52,175 INFO L134 CoverageAnalysis]: Checked inductivity of 295 backedges. 23 proven. 41 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-11-12 01:03:52,175 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:03:52,175 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1490163554] [2023-11-12 01:03:52,175 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 01:03:52,176 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2063752463] [2023-11-12 01:03:52,176 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2063752463] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 01:03:52,176 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1060369707] [2023-11-12 01:03:52,179 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-12 01:03:52,179 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 01:03:52,179 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 01:03:52,180 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 01:03:52,180 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 01:03:53,162 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 01:03:53,167 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 01:03:53,421 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2854#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 01:03:53,421 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 01:03:53,421 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 01:03:53,422 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2023-11-12 01:03:53,422 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1649827655] [2023-11-12 01:03:53,422 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 01:03:53,423 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-12 01:03:53,423 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:03:53,424 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-12 01:03:53,424 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=346, Unknown=0, NotChecked=0, Total=420 [2023-11-12 01:03:53,424 INFO L87 Difference]: Start difference. First operand 81 states and 89 transitions. Second operand has 15 states, 13 states have (on average 1.7692307692307692) internal successors, (23), 13 states have internal predecessors, (23), 7 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 6 states have call predecessors, (24), 7 states have call successors, (24) [2023-11-12 01:03:53,770 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:03:53,770 INFO L93 Difference]: Finished difference Result 92 states and 98 transitions. [2023-11-12 01:03:53,771 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-12 01:03:53,771 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 1.7692307692307692) internal successors, (23), 13 states have internal predecessors, (23), 7 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 6 states have call predecessors, (24), 7 states have call successors, (24) Word has length 69 [2023-11-12 01:03:53,771 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:03:53,772 INFO L225 Difference]: With dead ends: 92 [2023-11-12 01:03:53,773 INFO L226 Difference]: Without dead ends: 79 [2023-11-12 01:03:53,773 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 208 GetRequests, 184 SyntacticMatches, 2 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 135 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=96, Invalid=456, Unknown=0, NotChecked=0, Total=552 [2023-11-12 01:03:53,774 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 13 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 218 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 226 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 218 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-12 01:03:53,775 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 111 Invalid, 226 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 218 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-12 01:03:53,776 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2023-11-12 01:03:53,801 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 79. [2023-11-12 01:03:53,801 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 47 states have (on average 1.0425531914893618) internal successors, (49), 48 states have internal predecessors, (49), 18 states have call successors, (18), 13 states have call predecessors, (18), 13 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2023-11-12 01:03:53,802 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 84 transitions. [2023-11-12 01:03:53,802 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 84 transitions. Word has length 69 [2023-11-12 01:03:53,803 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:03:53,803 INFO L495 AbstractCegarLoop]: Abstraction has 79 states and 84 transitions. [2023-11-12 01:03:53,803 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 1.7692307692307692) internal successors, (23), 13 states have internal predecessors, (23), 7 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 6 states have call predecessors, (24), 7 states have call successors, (24) [2023-11-12 01:03:53,803 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 84 transitions. [2023-11-12 01:03:53,805 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2023-11-12 01:03:53,805 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:03:53,805 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1] [2023-11-12 01:03:53,810 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-12 01:03:54,007 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:03:54,007 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:03:54,008 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:03:54,008 INFO L85 PathProgramCache]: Analyzing trace with hash 33509209, now seen corresponding path program 4 times [2023-11-12 01:03:54,008 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:03:54,008 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1637318834] [2023-11-12 01:03:54,008 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:03:54,009 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:03:54,019 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 01:03:54,020 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1067148764] [2023-11-12 01:03:54,020 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-11-12 01:03:54,020 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:03:54,020 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:03:54,021 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:03:54,027 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-12 01:03:54,094 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:03:54,095 INFO L262 TraceCheckSpWp]: Trace formula consists of 170 conjuncts, 36 conjunts are in the unsatisfiable core [2023-11-12 01:03:54,099 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:03:54,308 INFO L134 CoverageAnalysis]: Checked inductivity of 303 backedges. 52 proven. 47 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2023-11-12 01:03:54,309 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 01:03:54,696 INFO L134 CoverageAnalysis]: Checked inductivity of 303 backedges. 52 proven. 47 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2023-11-12 01:03:54,696 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:03:54,696 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1637318834] [2023-11-12 01:03:54,696 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 01:03:54,697 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1067148764] [2023-11-12 01:03:54,697 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1067148764] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 01:03:54,697 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [215928596] [2023-11-12 01:03:54,703 INFO L159 IcfgInterpreter]: Started Sifa with 14 locations of interest [2023-11-12 01:03:54,703 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 01:03:54,703 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 01:03:54,704 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 01:03:54,704 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 01:03:55,667 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 01:03:55,671 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 01:03:55,977 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3541#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 01:03:55,977 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 01:03:55,977 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 01:03:55,977 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2023-11-12 01:03:55,977 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1520784364] [2023-11-12 01:03:55,978 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 01:03:55,978 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-11-12 01:03:55,978 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:03:55,979 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-11-12 01:03:55,979 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=418, Unknown=0, NotChecked=0, Total=506 [2023-11-12 01:03:55,979 INFO L87 Difference]: Start difference. First operand 79 states and 84 transitions. Second operand has 17 states, 15 states have (on average 1.6666666666666667) internal successors, (25), 13 states have internal predecessors, (25), 9 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 8 states have call predecessors, (24), 7 states have call successors, (24) [2023-11-12 01:03:58,579 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.12s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-12 01:04:00,350 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.60s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-12 01:04:00,441 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:04:00,442 INFO L93 Difference]: Finished difference Result 110 states and 130 transitions. [2023-11-12 01:04:00,442 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-11-12 01:04:00,443 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 1.6666666666666667) internal successors, (25), 13 states have internal predecessors, (25), 9 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 8 states have call predecessors, (24), 7 states have call successors, (24) Word has length 70 [2023-11-12 01:04:00,443 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:04:00,446 INFO L225 Difference]: With dead ends: 110 [2023-11-12 01:04:00,446 INFO L226 Difference]: Without dead ends: 108 [2023-11-12 01:04:00,447 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 218 GetRequests, 184 SyntacticMatches, 3 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 279 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=195, Invalid=861, Unknown=0, NotChecked=0, Total=1056 [2023-11-12 01:04:00,448 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 27 mSDsluCounter, 179 mSDsCounter, 0 mSdLazyCounter, 175 mSolverCounterSat, 53 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 202 SdHoareTripleChecker+Invalid, 229 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 175 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.0s IncrementalHoareTripleChecker+Time [2023-11-12 01:04:00,449 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 202 Invalid, 229 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 175 Invalid, 1 Unknown, 0 Unchecked, 4.0s Time] [2023-11-12 01:04:00,449 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states. [2023-11-12 01:04:00,479 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 87. [2023-11-12 01:04:00,480 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 87 states, 53 states have (on average 1.0377358490566038) internal successors, (55), 54 states have internal predecessors, (55), 18 states have call successors, (18), 15 states have call predecessors, (18), 15 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2023-11-12 01:04:00,481 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 90 transitions. [2023-11-12 01:04:00,481 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 90 transitions. Word has length 70 [2023-11-12 01:04:00,481 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:04:00,482 INFO L495 AbstractCegarLoop]: Abstraction has 87 states and 90 transitions. [2023-11-12 01:04:00,482 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 1.6666666666666667) internal successors, (25), 13 states have internal predecessors, (25), 9 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 8 states have call predecessors, (24), 7 states have call successors, (24) [2023-11-12 01:04:00,482 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 90 transitions. [2023-11-12 01:04:00,484 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2023-11-12 01:04:00,484 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:04:00,484 INFO L195 NwaCegarLoop]: trace histogram [17, 16, 16, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:04:00,492 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-12 01:04:00,690 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:00,690 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:04:00,691 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:04:00,691 INFO L85 PathProgramCache]: Analyzing trace with hash -176995479, now seen corresponding path program 2 times [2023-11-12 01:04:00,691 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:04:00,691 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1539725640] [2023-11-12 01:04:00,691 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:00,691 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:04:00,701 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 01:04:00,702 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [200714436] [2023-11-12 01:04:00,702 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-12 01:04:00,702 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:00,702 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:04:00,703 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:04:00,740 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-12 01:04:00,790 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-11-12 01:04:00,790 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 01:04:00,791 INFO L262 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 39 conjunts are in the unsatisfiable core [2023-11-12 01:04:00,794 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:04:01,074 INFO L134 CoverageAnalysis]: Checked inductivity of 533 backedges. 76 proven. 22 refuted. 0 times theorem prover too weak. 435 trivial. 0 not checked. [2023-11-12 01:04:01,074 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 01:04:03,121 INFO L134 CoverageAnalysis]: Checked inductivity of 533 backedges. 90 proven. 1 refuted. 0 times theorem prover too weak. 442 trivial. 0 not checked. [2023-11-12 01:04:03,122 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:04:03,122 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1539725640] [2023-11-12 01:04:03,122 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 01:04:03,122 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [200714436] [2023-11-12 01:04:03,122 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [200714436] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 01:04:03,122 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2021718867] [2023-11-12 01:04:03,125 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-11-12 01:04:03,125 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 01:04:03,125 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 01:04:03,125 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 01:04:03,126 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 01:04:04,009 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 01:04:04,013 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 01:04:04,689 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4411#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 01:04:04,689 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 01:04:04,690 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 01:04:04,690 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 16 [2023-11-12 01:04:04,690 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2147090230] [2023-11-12 01:04:04,690 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 01:04:04,691 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2023-11-12 01:04:04,691 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:04:04,692 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2023-11-12 01:04:04,692 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=381, Unknown=0, NotChecked=0, Total=462 [2023-11-12 01:04:04,693 INFO L87 Difference]: Start difference. First operand 87 states and 90 transitions. Second operand has 16 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 13 states have internal predecessors, (26), 9 states have call successors, (29), 3 states have call predecessors, (29), 2 states have return successors, (27), 7 states have call predecessors, (27), 7 states have call successors, (27) [2023-11-12 01:04:06,039 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:04:06,039 INFO L93 Difference]: Finished difference Result 111 states and 119 transitions. [2023-11-12 01:04:06,040 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-11-12 01:04:06,040 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 13 states have internal predecessors, (26), 9 states have call successors, (29), 3 states have call predecessors, (29), 2 states have return successors, (27), 7 states have call predecessors, (27), 7 states have call successors, (27) Word has length 91 [2023-11-12 01:04:06,040 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:04:06,042 INFO L225 Difference]: With dead ends: 111 [2023-11-12 01:04:06,042 INFO L226 Difference]: Without dead ends: 107 [2023-11-12 01:04:06,043 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 274 GetRequests, 248 SyntacticMatches, 3 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 169 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=101, Invalid=499, Unknown=0, NotChecked=0, Total=600 [2023-11-12 01:04:06,044 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 14 mSDsluCounter, 127 mSDsCounter, 0 mSdLazyCounter, 265 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 150 SdHoareTripleChecker+Invalid, 283 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 265 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2023-11-12 01:04:06,044 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 150 Invalid, 283 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 265 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2023-11-12 01:04:06,045 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 107 states. [2023-11-12 01:04:06,105 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 107 to 105. [2023-11-12 01:04:06,106 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 105 states, 63 states have (on average 1.0317460317460319) internal successors, (65), 64 states have internal predecessors, (65), 24 states have call successors, (24), 18 states have call predecessors, (24), 17 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2023-11-12 01:04:06,107 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 112 transitions. [2023-11-12 01:04:06,107 INFO L78 Accepts]: Start accepts. Automaton has 105 states and 112 transitions. Word has length 91 [2023-11-12 01:04:06,107 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:04:06,108 INFO L495 AbstractCegarLoop]: Abstraction has 105 states and 112 transitions. [2023-11-12 01:04:06,108 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 12 states have (on average 2.1666666666666665) internal successors, (26), 13 states have internal predecessors, (26), 9 states have call successors, (29), 3 states have call predecessors, (29), 2 states have return successors, (27), 7 states have call predecessors, (27), 7 states have call successors, (27) [2023-11-12 01:04:06,108 INFO L276 IsEmpty]: Start isEmpty. Operand 105 states and 112 transitions. [2023-11-12 01:04:06,110 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2023-11-12 01:04:06,110 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:04:06,110 INFO L195 NwaCegarLoop]: trace histogram [18, 17, 17, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:04:06,125 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-11-12 01:04:06,316 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:06,317 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:04:06,317 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:04:06,317 INFO L85 PathProgramCache]: Analyzing trace with hash -1760296702, now seen corresponding path program 2 times [2023-11-12 01:04:06,317 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:04:06,317 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [291674391] [2023-11-12 01:04:06,317 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:06,318 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:04:06,330 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 01:04:06,330 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1766774252] [2023-11-12 01:04:06,340 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-12 01:04:06,340 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:06,340 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:04:06,341 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:04:06,364 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-11-12 01:04:06,413 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-11-12 01:04:06,413 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 01:04:06,414 INFO L262 TraceCheckSpWp]: Trace formula consists of 107 conjuncts, 44 conjunts are in the unsatisfiable core [2023-11-12 01:04:06,418 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:04:06,823 INFO L134 CoverageAnalysis]: Checked inductivity of 599 backedges. 107 proven. 38 refuted. 0 times theorem prover too weak. 454 trivial. 0 not checked. [2023-11-12 01:04:06,823 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 01:04:09,640 INFO L134 CoverageAnalysis]: Checked inductivity of 599 backedges. 107 proven. 38 refuted. 0 times theorem prover too weak. 454 trivial. 0 not checked. [2023-11-12 01:04:09,641 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:04:09,641 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [291674391] [2023-11-12 01:04:09,641 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 01:04:09,641 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1766774252] [2023-11-12 01:04:09,641 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1766774252] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 01:04:09,641 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1818947861] [2023-11-12 01:04:09,643 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-12 01:04:09,644 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 01:04:09,644 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 01:04:09,644 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 01:04:09,645 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 01:04:10,606 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 01:04:10,610 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 01:04:11,249 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5321#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 01:04:11,250 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 01:04:11,250 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 01:04:11,250 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10] total 18 [2023-11-12 01:04:11,250 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2037420096] [2023-11-12 01:04:11,250 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 01:04:11,251 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2023-11-12 01:04:11,251 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:04:11,252 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2023-11-12 01:04:11,252 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=98, Invalid=454, Unknown=0, NotChecked=0, Total=552 [2023-11-12 01:04:11,252 INFO L87 Difference]: Start difference. First operand 105 states and 112 transitions. Second operand has 18 states, 16 states have (on average 1.6875) internal successors, (27), 15 states have internal predecessors, (27), 10 states have call successors, (36), 3 states have call predecessors, (36), 2 states have return successors, (34), 8 states have call predecessors, (34), 8 states have call successors, (34) [2023-11-12 01:04:21,069 WARN L293 SmtUtils]: Spent 7.70s on a formula simplification that was a NOOP. DAG size: 55 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-11-12 01:04:21,838 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:04:21,838 INFO L93 Difference]: Finished difference Result 151 states and 174 transitions. [2023-11-12 01:04:21,839 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2023-11-12 01:04:21,839 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 16 states have (on average 1.6875) internal successors, (27), 15 states have internal predecessors, (27), 10 states have call successors, (36), 3 states have call predecessors, (36), 2 states have return successors, (34), 8 states have call predecessors, (34), 8 states have call successors, (34) Word has length 96 [2023-11-12 01:04:21,840 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:04:21,841 INFO L225 Difference]: With dead ends: 151 [2023-11-12 01:04:21,841 INFO L226 Difference]: Without dead ends: 137 [2023-11-12 01:04:21,842 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 294 GetRequests, 261 SyntacticMatches, 3 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 248 ImplicationChecksByTransitivity, 10.6s TimeCoverageRelationStatistics Valid=190, Invalid=802, Unknown=0, NotChecked=0, Total=992 [2023-11-12 01:04:21,843 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 17 mSDsluCounter, 155 mSDsCounter, 0 mSdLazyCounter, 329 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 178 SdHoareTripleChecker+Invalid, 369 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 329 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2023-11-12 01:04:21,843 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 178 Invalid, 369 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 329 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2023-11-12 01:04:21,844 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 137 states. [2023-11-12 01:04:21,911 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 137 to 137. [2023-11-12 01:04:21,911 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 137 states, 78 states have (on average 1.0128205128205128) internal successors, (79), 78 states have internal predecessors, (79), 38 states have call successors, (38), 21 states have call predecessors, (38), 20 states have return successors, (37), 37 states have call predecessors, (37), 37 states have call successors, (37) [2023-11-12 01:04:21,912 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 137 states to 137 states and 154 transitions. [2023-11-12 01:04:21,912 INFO L78 Accepts]: Start accepts. Automaton has 137 states and 154 transitions. Word has length 96 [2023-11-12 01:04:21,913 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:04:21,913 INFO L495 AbstractCegarLoop]: Abstraction has 137 states and 154 transitions. [2023-11-12 01:04:21,913 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 16 states have (on average 1.6875) internal successors, (27), 15 states have internal predecessors, (27), 10 states have call successors, (36), 3 states have call predecessors, (36), 2 states have return successors, (34), 8 states have call predecessors, (34), 8 states have call successors, (34) [2023-11-12 01:04:21,913 INFO L276 IsEmpty]: Start isEmpty. Operand 137 states and 154 transitions. [2023-11-12 01:04:21,916 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 205 [2023-11-12 01:04:21,917 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:04:21,917 INFO L195 NwaCegarLoop]: trace histogram [38, 37, 37, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:04:21,924 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-11-12 01:04:22,122 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-11-12 01:04:22,122 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:04:22,122 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:04:22,123 INFO L85 PathProgramCache]: Analyzing trace with hash -2082635326, now seen corresponding path program 3 times [2023-11-12 01:04:22,123 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:04:22,123 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [712956406] [2023-11-12 01:04:22,123 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:04:22,123 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:04:22,137 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 01:04:22,137 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1330156755] [2023-11-12 01:04:22,137 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-12 01:04:22,137 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:04:22,138 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:04:22,139 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:04:22,153 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_e5efa9d5-9a65-4d71-9166-4e2344f2fa39/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-11-12 01:04:24,023 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-12 01:04:24,023 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 01:04:24,027 INFO L262 TraceCheckSpWp]: Trace formula consists of 346 conjuncts, 88 conjunts are in the unsatisfiable core [2023-11-12 01:04:24,033 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:04:24,926 INFO L134 CoverageAnalysis]: Checked inductivity of 2885 backedges. 460 proven. 430 refuted. 0 times theorem prover too weak. 1995 trivial. 0 not checked. [2023-11-12 01:04:24,927 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 01:04:26,004 INFO L134 CoverageAnalysis]: Checked inductivity of 2885 backedges. 310 proven. 36 refuted. 0 times theorem prover too weak. 2539 trivial. 0 not checked. [2023-11-12 01:04:26,005 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:04:26,005 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [712956406] [2023-11-12 01:04:26,005 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 01:04:26,005 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1330156755] [2023-11-12 01:04:26,006 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1330156755] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 01:04:26,007 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1085485777] [2023-11-12 01:04:26,010 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-12 01:04:26,011 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 01:04:26,011 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 01:04:26,011 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 01:04:26,012 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 01:04:27,025 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 01:04:27,033 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 01:04:27,837 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '7009#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 01:04:27,837 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 01:04:27,837 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 01:04:27,837 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 9] total 20 [2023-11-12 01:04:27,837 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1054202446] [2023-11-12 01:04:27,838 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 01:04:27,838 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2023-11-12 01:04:27,838 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:04:27,839 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2023-11-12 01:04:27,840 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=109, Invalid=541, Unknown=0, NotChecked=0, Total=650 [2023-11-12 01:04:27,840 INFO L87 Difference]: Start difference. First operand 137 states and 154 transitions. Second operand has 20 states, 15 states have (on average 1.8666666666666667) internal successors, (28), 14 states have internal predecessors, (28), 13 states have call successors, (39), 3 states have call predecessors, (39), 2 states have return successors, (41), 11 states have call predecessors, (41), 13 states have call successors, (41)