./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound50.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_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/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_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound50.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/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_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/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 0bcbcb4a55258889434b8bf703da9ec6fb29d07a2fbacad968a5ab15e005b314 --- Real Ultimate output --- This is Ultimate 0.2.3-dev-cf1a783 [2023-11-12 00:48:37,682 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-12 00:48:37,812 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-12 00:48:37,823 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-12 00:48:37,824 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-12 00:48:37,866 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-12 00:48:37,867 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-12 00:48:37,868 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-12 00:48:37,869 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-12 00:48:37,874 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-12 00:48:37,875 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-12 00:48:37,876 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-12 00:48:37,877 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-12 00:48:37,878 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-12 00:48:37,879 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-12 00:48:37,879 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-12 00:48:37,880 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-12 00:48:37,880 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-12 00:48:37,881 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-12 00:48:37,881 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-12 00:48:37,882 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-12 00:48:37,882 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-12 00:48:37,884 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-12 00:48:37,884 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-12 00:48:37,885 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-12 00:48:37,885 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-12 00:48:37,885 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-12 00:48:37,886 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-12 00:48:37,886 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-12 00:48:37,887 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-12 00:48:37,888 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-12 00:48:37,888 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-12 00:48:37,889 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-12 00:48:37,889 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-12 00:48:37,889 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-12 00:48:37,889 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-12 00:48:37,890 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 00:48:37,890 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-12 00:48:37,890 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-12 00:48:37,890 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-12 00:48:37,891 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-12 00:48:37,891 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-12 00:48:37,891 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-12 00:48:37,891 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-12 00:48:37,892 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-12 00:48:37,892 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_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/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_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/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 -> 0bcbcb4a55258889434b8bf703da9ec6fb29d07a2fbacad968a5ab15e005b314 [2023-11-12 00:48:38,174 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-12 00:48:38,195 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-12 00:48:38,198 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-12 00:48:38,199 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-12 00:48:38,199 INFO L274 PluginConnector]: CDTParser initialized [2023-11-12 00:48:38,201 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/../../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound50.c [2023-11-12 00:48:41,264 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-12 00:48:41,467 INFO L384 CDTParser]: Found 1 translation units. [2023-11-12 00:48:41,469 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound50.c [2023-11-12 00:48:41,479 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/data/d7e93dce3/2bf24e8e35284b0cab1a83c4e11c725d/FLAG505c139a6 [2023-11-12 00:48:41,497 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/data/d7e93dce3/2bf24e8e35284b0cab1a83c4e11c725d [2023-11-12 00:48:41,504 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-12 00:48:41,506 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-12 00:48:41,511 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-12 00:48:41,511 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-12 00:48:41,517 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-12 00:48:41,518 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 12:48:41" (1/1) ... [2023-11-12 00:48:41,519 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@149e2b96 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:48:41, skipping insertion in model container [2023-11-12 00:48:41,519 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 12:48:41" (1/1) ... [2023-11-12 00:48:41,549 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-12 00:48:41,735 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_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound50.c[588,601] [2023-11-12 00:48:41,780 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 00:48:41,800 INFO L202 MainTranslator]: Completed pre-run [2023-11-12 00:48:41,816 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_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound50.c[588,601] [2023-11-12 00:48:41,840 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 00:48:41,856 INFO L206 MainTranslator]: Completed translation [2023-11-12 00:48:41,856 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:48:41 WrapperNode [2023-11-12 00:48:41,856 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-12 00:48:41,858 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-12 00:48:41,858 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-12 00:48:41,858 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-12 00:48:41,866 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:48:41" (1/1) ... [2023-11-12 00:48:41,873 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:48:41" (1/1) ... [2023-11-12 00:48:41,912 INFO L138 Inliner]: procedures = 14, calls = 19, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 48 [2023-11-12 00:48:41,912 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-12 00:48:41,913 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-12 00:48:41,914 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-12 00:48:41,914 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-12 00:48:41,923 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:48:41" (1/1) ... [2023-11-12 00:48:41,924 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:48:41" (1/1) ... [2023-11-12 00:48:41,938 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:48:41" (1/1) ... [2023-11-12 00:48:41,939 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:48:41" (1/1) ... [2023-11-12 00:48:41,942 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:48:41" (1/1) ... [2023-11-12 00:48:41,945 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:48:41" (1/1) ... [2023-11-12 00:48:41,947 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:48:41" (1/1) ... [2023-11-12 00:48:41,948 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:48:41" (1/1) ... [2023-11-12 00:48:41,950 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-12 00:48:41,951 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-12 00:48:41,951 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-12 00:48:41,952 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-12 00:48:41,953 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:48:41" (1/1) ... [2023-11-12 00:48:41,961 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 00:48:41,979 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:48:41,994 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-12 00:48:42,035 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-12 00:48:42,046 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-12 00:48:42,046 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-12 00:48:42,046 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-12 00:48:42,047 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-12 00:48:42,047 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-11-12 00:48:42,047 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-11-12 00:48:42,126 INFO L236 CfgBuilder]: Building ICFG [2023-11-12 00:48:42,129 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-12 00:48:42,380 INFO L277 CfgBuilder]: Performing block encoding [2023-11-12 00:48:42,420 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-12 00:48:42,421 INFO L302 CfgBuilder]: Removed 1 assume(true) statements. [2023-11-12 00:48:42,423 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 12:48:42 BoogieIcfgContainer [2023-11-12 00:48:42,423 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-12 00:48:42,427 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-12 00:48:42,427 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-12 00:48:42,430 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-12 00:48:42,431 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.11 12:48:41" (1/3) ... [2023-11-12 00:48:42,431 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6c0340d7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 12:48:42, skipping insertion in model container [2023-11-12 00:48:42,432 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:48:41" (2/3) ... [2023-11-12 00:48:42,432 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6c0340d7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 12:48:42, skipping insertion in model container [2023-11-12 00:48:42,432 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 12:48:42" (3/3) ... [2023-11-12 00:48:42,434 INFO L112 eAbstractionObserver]: Analyzing ICFG cohencu-ll_valuebound50.c [2023-11-12 00:48:42,455 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-12 00:48:42,455 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-12 00:48:42,505 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-12 00:48:42,512 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;@59fc0bbd, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-12 00:48:42,512 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-12 00:48:42,521 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 00:48:42,529 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2023-11-12 00:48:42,530 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:48:42,530 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2023-11-12 00:48:42,531 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:48:42,540 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:48:42,540 INFO L85 PathProgramCache]: Analyzing trace with hash -1070258279, now seen corresponding path program 1 times [2023-11-12 00:48:42,553 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:48:42,554 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1912681093] [2023-11-12 00:48:42,554 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:48:42,554 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:48:42,699 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:48:43,150 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 00:48:43,151 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:48:43,151 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1912681093] [2023-11-12 00:48:43,153 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1912681093] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:48:43,153 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:48:43,154 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-11-12 00:48:43,155 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [670023042] [2023-11-12 00:48:43,156 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:48:43,161 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:48:43,162 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:48:43,203 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:48:43,204 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-12 00:48:43,206 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 00:48:43,404 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:48:43,404 INFO L93 Difference]: Finished difference Result 47 states and 82 transitions. [2023-11-12 00:48:43,405 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-12 00:48:43,407 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 00:48:43,407 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:48:43,420 INFO L225 Difference]: With dead ends: 47 [2023-11-12 00:48:43,420 INFO L226 Difference]: Without dead ends: 24 [2023-11-12 00:48:43,426 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 00:48:43,431 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 00:48:43,433 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 00:48:43,457 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2023-11-12 00:48:43,496 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2023-11-12 00:48:43,500 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 00:48:43,503 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 33 transitions. [2023-11-12 00:48:43,505 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 33 transitions. Word has length 6 [2023-11-12 00:48:43,506 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:48:43,506 INFO L495 AbstractCegarLoop]: Abstraction has 24 states and 33 transitions. [2023-11-12 00:48:43,507 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 00:48:43,507 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 33 transitions. [2023-11-12 00:48:43,510 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2023-11-12 00:48:43,510 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:48:43,510 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:48:43,511 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-12 00:48:43,511 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:48:43,512 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:48:43,513 INFO L85 PathProgramCache]: Analyzing trace with hash -1088770990, now seen corresponding path program 1 times [2023-11-12 00:48:43,513 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:48:43,513 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [502520893] [2023-11-12 00:48:43,513 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:48:43,514 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:48:43,553 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:48:43,554 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1331107676] [2023-11-12 00:48:43,554 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:48:43,555 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:48:43,555 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:48:43,559 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:48:43,569 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-12 00:48:43,621 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:48:43,628 INFO L262 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 17 conjunts are in the unsatisfiable core [2023-11-12 00:48:43,633 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:48:43,820 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 00:48:43,820 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:48:44,007 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 00:48:44,007 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:48:44,008 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [502520893] [2023-11-12 00:48:44,008 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:48:44,008 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1331107676] [2023-11-12 00:48:44,009 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1331107676] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:48:44,009 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1014878462] [2023-11-12 00:48:44,028 INFO L159 IcfgInterpreter]: Started Sifa with 10 locations of interest [2023-11-12 00:48:44,029 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:48:44,032 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:48:44,038 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:48:44,039 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:48:44,541 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 72 for LOIs [2023-11-12 00:48:44,873 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:48:45,452 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [1014878462] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:48:45,453 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:48:45,453 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [8, 7] total 15 [2023-11-12 00:48:45,454 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [161360877] [2023-11-12 00:48:45,454 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:48:45,455 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:48:45,456 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:48:45,457 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:48:45,457 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=158, Unknown=0, NotChecked=0, Total=210 [2023-11-12 00:48:45,457 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 00:48:45,684 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:48:45,684 INFO L93 Difference]: Finished difference Result 55 states and 72 transitions. [2023-11-12 00:48:45,685 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-12 00:48:45,685 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 00:48:45,685 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:48:45,686 INFO L225 Difference]: With dead ends: 55 [2023-11-12 00:48:45,686 INFO L226 Difference]: Without dead ends: 39 [2023-11-12 00:48:45,687 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 00:48:45,689 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 00:48:45,690 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 00:48:45,691 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2023-11-12 00:48:45,713 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2023-11-12 00:48:45,714 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 00:48:45,718 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 51 transitions. [2023-11-12 00:48:45,719 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 51 transitions. Word has length 11 [2023-11-12 00:48:45,719 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:48:45,720 INFO L495 AbstractCegarLoop]: Abstraction has 39 states and 51 transitions. [2023-11-12 00:48:45,720 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 00:48:45,721 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 51 transitions. [2023-11-12 00:48:45,722 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2023-11-12 00:48:45,723 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:48:45,723 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 00:48:45,734 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-12 00:48:45,929 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:48:45,930 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:48:45,930 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:48:45,930 INFO L85 PathProgramCache]: Analyzing trace with hash -700920967, now seen corresponding path program 1 times [2023-11-12 00:48:45,931 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:48:45,931 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [927907951] [2023-11-12 00:48:45,931 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:48:45,931 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:48:45,948 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:48:45,955 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1602085895] [2023-11-12 00:48:45,958 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:48:45,958 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:48:45,959 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:48:45,961 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:48:45,980 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-12 00:48:46,040 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:48:46,042 INFO L262 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 21 conjunts are in the unsatisfiable core [2023-11-12 00:48:46,047 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:48:46,192 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 00:48:46,192 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:48:46,381 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 00:48:46,382 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:48:46,382 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [927907951] [2023-11-12 00:48:46,382 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:48:46,382 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1602085895] [2023-11-12 00:48:46,383 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1602085895] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:48:46,383 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [819156392] [2023-11-12 00:48:46,387 INFO L159 IcfgInterpreter]: Started Sifa with 14 locations of interest [2023-11-12 00:48:46,388 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:48:46,388 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:48:46,389 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:48:46,389 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:48:47,922 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 00:48:47,928 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:48:48,242 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 00:48:48,242 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:48:48,243 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:48:48,243 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2023-11-12 00:48:48,243 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1964116675] [2023-11-12 00:48:48,243 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:48:48,244 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-11-12 00:48:48,244 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:48:48,245 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-11-12 00:48:48,245 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=275, Unknown=0, NotChecked=0, Total=342 [2023-11-12 00:48:48,246 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 00:48:50,783 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.08s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-12 00:48:50,810 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:48:50,810 INFO L93 Difference]: Finished difference Result 62 states and 83 transitions. [2023-11-12 00:48:50,811 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-12 00:48:50,811 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 00:48:50,812 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:48:50,813 INFO L225 Difference]: With dead ends: 62 [2023-11-12 00:48:50,813 INFO L226 Difference]: Without dead ends: 60 [2023-11-12 00:48:50,814 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 00:48:50,815 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 22 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 134 mSolverCounterSat, 73 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 101 SdHoareTripleChecker+Invalid, 208 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 73 IncrementalHoareTripleChecker+Valid, 134 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.5s IncrementalHoareTripleChecker+Time [2023-11-12 00:48:50,816 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 101 Invalid, 208 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [73 Valid, 134 Invalid, 1 Unknown, 0 Unchecked, 2.5s Time] [2023-11-12 00:48:50,816 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2023-11-12 00:48:50,839 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 47. [2023-11-12 00:48:50,839 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 00:48:50,840 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 57 transitions. [2023-11-12 00:48:50,841 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 57 transitions. Word has length 38 [2023-11-12 00:48:50,841 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:48:50,842 INFO L495 AbstractCegarLoop]: Abstraction has 47 states and 57 transitions. [2023-11-12 00:48:50,842 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 00:48:50,842 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 57 transitions. [2023-11-12 00:48:50,843 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2023-11-12 00:48:50,844 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:48:50,844 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 00:48:50,857 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2023-11-12 00:48:51,053 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:48:51,054 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:48:51,054 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:48:51,054 INFO L85 PathProgramCache]: Analyzing trace with hash -1757443022, now seen corresponding path program 2 times [2023-11-12 00:48:51,055 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:48:51,055 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1647351245] [2023-11-12 00:48:51,055 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:48:51,055 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:48:51,081 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:48:51,081 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [819677067] [2023-11-12 00:48:51,083 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-12 00:48:51,084 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:48:51,084 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:48:51,085 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:48:51,104 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-12 00:48:51,195 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-11-12 00:48:51,196 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 00:48:51,197 INFO L262 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 16 conjunts are in the unsatisfiable core [2023-11-12 00:48:51,200 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:48:51,322 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 00:48:51,323 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:48:51,427 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 00:48:51,428 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:48:51,428 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1647351245] [2023-11-12 00:48:51,428 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:48:51,428 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [819677067] [2023-11-12 00:48:51,428 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [819677067] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:48:51,429 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [155873930] [2023-11-12 00:48:51,431 INFO L159 IcfgInterpreter]: Started Sifa with 14 locations of interest [2023-11-12 00:48:51,432 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:48:51,432 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:48:51,433 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:48:51,433 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:48:52,738 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 00:48:52,748 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:48:52,998 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 00:48:52,999 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:48:52,999 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:48:52,999 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2023-11-12 00:48:52,999 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1685578501] [2023-11-12 00:48:52,999 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:48:53,000 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-11-12 00:48:53,000 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:48:53,001 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-11-12 00:48:53,001 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=193, Unknown=0, NotChecked=0, Total=240 [2023-11-12 00:48:53,002 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 00:48:53,187 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:48:53,187 INFO L93 Difference]: Finished difference Result 74 states and 92 transitions. [2023-11-12 00:48:53,188 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-11-12 00:48:53,188 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 00:48:53,189 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:48:53,190 INFO L225 Difference]: With dead ends: 74 [2023-11-12 00:48:53,191 INFO L226 Difference]: Without dead ends: 72 [2023-11-12 00:48:53,191 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 00:48:53,193 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 00:48:53,193 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 00:48:53,195 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2023-11-12 00:48:53,222 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 63. [2023-11-12 00:48:53,222 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 00:48:53,224 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 73 transitions. [2023-11-12 00:48:53,224 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 73 transitions. Word has length 43 [2023-11-12 00:48:53,225 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:48:53,225 INFO L495 AbstractCegarLoop]: Abstraction has 63 states and 73 transitions. [2023-11-12 00:48:53,225 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 00:48:53,226 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 73 transitions. [2023-11-12 00:48:53,227 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2023-11-12 00:48:53,228 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:48:53,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 00:48:53,240 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-12 00:48:53,434 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:48:53,435 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:48:53,435 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:48:53,436 INFO L85 PathProgramCache]: Analyzing trace with hash 1748922073, now seen corresponding path program 3 times [2023-11-12 00:48:53,436 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:48:53,441 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [380695410] [2023-11-12 00:48:53,441 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:48:53,442 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:48:53,453 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:48:53,464 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [126227610] [2023-11-12 00:48:53,464 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-12 00:48:53,464 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:48:53,465 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:48:53,466 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:48:53,481 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-12 00:48:53,561 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-12 00:48:53,561 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 00:48:53,563 INFO L262 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 27 conjunts are in the unsatisfiable core [2023-11-12 00:48:53,566 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:48:53,735 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 00:48:53,736 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:48:54,176 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 00:48:54,177 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:48:54,177 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [380695410] [2023-11-12 00:48:54,177 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:48:54,178 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [126227610] [2023-11-12 00:48:54,178 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [126227610] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:48:54,178 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [912888655] [2023-11-12 00:48:54,181 INFO L159 IcfgInterpreter]: Started Sifa with 14 locations of interest [2023-11-12 00:48:54,181 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:48:54,182 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:48:54,182 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:48:54,182 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:48:55,355 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 00:48:55,360 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:48:55,673 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 00:48:55,674 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:48:55,674 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:48:55,674 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2023-11-12 00:48:55,674 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2084580744] [2023-11-12 00:48:55,674 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:48:55,675 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-11-12 00:48:55,675 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:48:55,676 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-11-12 00:48:55,677 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=275, Unknown=0, NotChecked=0, Total=342 [2023-11-12 00:48:55,677 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 00:48:56,124 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:48:56,124 INFO L93 Difference]: Finished difference Result 82 states and 98 transitions. [2023-11-12 00:48:56,125 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-12 00:48:56,125 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 00:48:56,126 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:48:56,127 INFO L225 Difference]: With dead ends: 82 [2023-11-12 00:48:56,127 INFO L226 Difference]: Without dead ends: 74 [2023-11-12 00:48:56,128 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 123 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 118 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=91, Invalid=371, Unknown=0, NotChecked=0, Total=462 [2023-11-12 00:48:56,129 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 20 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 161 mSolverCounterSat, 50 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s 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 00:48:56,130 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 00:48:56,131 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2023-11-12 00:48:56,177 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 68. [2023-11-12 00:48:56,180 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 00:48:56,181 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 73 transitions. [2023-11-12 00:48:56,181 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 73 transitions. Word has length 48 [2023-11-12 00:48:56,184 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:48:56,185 INFO L495 AbstractCegarLoop]: Abstraction has 68 states and 73 transitions. [2023-11-12 00:48:56,185 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 00:48:56,185 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 73 transitions. [2023-11-12 00:48:56,190 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2023-11-12 00:48:56,190 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:48:56,191 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 00:48:56,208 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-12 00:48:56,398 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:48:56,398 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:48:56,399 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:48:56,399 INFO L85 PathProgramCache]: Analyzing trace with hash -2025080784, now seen corresponding path program 1 times [2023-11-12 00:48:56,400 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:48:56,400 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [499274978] [2023-11-12 00:48:56,400 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:48:56,400 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:48:56,425 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:48:56,426 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [685731182] [2023-11-12 00:48:56,426 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:48:56,426 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:48:56,426 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:48:56,428 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:48:56,452 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-12 00:48:56,517 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:48:56,520 INFO L262 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 26 conjunts are in the unsatisfiable core [2023-11-12 00:48:56,524 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:48:56,871 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 00:48:56,872 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:49:01,858 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 00:49:01,859 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:49:01,859 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [499274978] [2023-11-12 00:49:01,859 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:49:01,859 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [685731182] [2023-11-12 00:49:01,859 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [685731182] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:49:01,860 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1029777430] [2023-11-12 00:49:01,863 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-11-12 00:49:01,863 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:49:01,863 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:49:01,864 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:49:01,864 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:49:03,022 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 00:49:03,029 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:49:04,666 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 00:49:04,667 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:49:04,667 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:49:04,667 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2023-11-12 00:49:04,667 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1076593044] [2023-11-12 00:49:04,667 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:49:04,670 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-12 00:49:04,670 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:49:04,671 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-12 00:49:04,672 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=346, Unknown=0, NotChecked=0, Total=420 [2023-11-12 00:49:04,672 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 00:49:07,420 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:49:07,421 INFO L93 Difference]: Finished difference Result 84 states and 92 transitions. [2023-11-12 00:49:07,421 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-12 00:49:07,421 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 00:49:07,422 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:49:07,423 INFO L225 Difference]: With dead ends: 84 [2023-11-12 00:49:07,423 INFO L226 Difference]: Without dead ends: 82 [2023-11-12 00:49:07,424 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 193 GetRequests, 169 SyntacticMatches, 2 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 135 ImplicationChecksByTransitivity, 5.5s TimeCoverageRelationStatistics Valid=96, Invalid=456, Unknown=0, NotChecked=0, Total=552 [2023-11-12 00:49:07,425 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 18 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 141 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.7s 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.8s IncrementalHoareTripleChecker+Time [2023-11-12 00:49:07,428 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.8s Time] [2023-11-12 00:49:07,429 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2023-11-12 00:49:07,459 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 81. [2023-11-12 00:49:07,460 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 00:49:07,461 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 89 transitions. [2023-11-12 00:49:07,461 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 89 transitions. Word has length 64 [2023-11-12 00:49:07,462 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:49:07,462 INFO L495 AbstractCegarLoop]: Abstraction has 81 states and 89 transitions. [2023-11-12 00:49:07,463 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 00:49:07,463 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 89 transitions. [2023-11-12 00:49:07,464 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2023-11-12 00:49:07,465 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:49:07,465 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 00:49:07,471 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2023-11-12 00:49:07,671 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:49:07,671 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:49:07,672 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:49:07,672 INFO L85 PathProgramCache]: Analyzing trace with hash -1309118309, now seen corresponding path program 1 times [2023-11-12 00:49:07,672 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:49:07,672 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [717818305] [2023-11-12 00:49:07,672 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:49:07,672 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:49:07,683 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:49:07,683 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1433761926] [2023-11-12 00:49:07,684 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:49:07,684 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:49:07,684 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:49:07,685 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:49:07,686 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-12 00:49:07,756 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:49:07,758 INFO L262 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 24 conjunts are in the unsatisfiable core [2023-11-12 00:49:07,761 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:49:08,037 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 00:49:08,037 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:49:08,412 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 00:49:08,412 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:49:08,413 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [717818305] [2023-11-12 00:49:08,413 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:49:08,413 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1433761926] [2023-11-12 00:49:08,413 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1433761926] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:49:08,413 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2015596065] [2023-11-12 00:49:08,417 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-12 00:49:08,418 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:49:08,418 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:49:08,418 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:49:08,419 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:49:09,443 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 00:49:09,448 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:49:09,709 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 00:49:09,709 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:49:09,709 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:49:09,710 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2023-11-12 00:49:09,710 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [267108804] [2023-11-12 00:49:09,710 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:49:09,711 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-12 00:49:09,711 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:49:09,712 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-12 00:49:09,712 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=346, Unknown=0, NotChecked=0, Total=420 [2023-11-12 00:49:09,713 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 00:49:10,051 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:49:10,051 INFO L93 Difference]: Finished difference Result 92 states and 98 transitions. [2023-11-12 00:49:10,052 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-12 00:49:10,052 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 00:49:10,053 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:49:10,054 INFO L225 Difference]: With dead ends: 92 [2023-11-12 00:49:10,054 INFO L226 Difference]: Without dead ends: 79 [2023-11-12 00:49:10,054 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 208 GetRequests, 184 SyntacticMatches, 2 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 135 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=96, Invalid=456, Unknown=0, NotChecked=0, Total=552 [2023-11-12 00:49:10,055 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 00:49:10,056 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 00:49:10,056 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2023-11-12 00:49:10,091 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 79. [2023-11-12 00:49:10,092 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 00:49:10,095 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 84 transitions. [2023-11-12 00:49:10,095 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 84 transitions. Word has length 69 [2023-11-12 00:49:10,095 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:49:10,096 INFO L495 AbstractCegarLoop]: Abstraction has 79 states and 84 transitions. [2023-11-12 00:49:10,096 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 00:49:10,096 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 84 transitions. [2023-11-12 00:49:10,100 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2023-11-12 00:49:10,102 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:49:10,103 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 00:49:10,122 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-12 00:49:10,318 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:49:10,318 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:49:10,318 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:49:10,318 INFO L85 PathProgramCache]: Analyzing trace with hash 33509209, now seen corresponding path program 4 times [2023-11-12 00:49:10,318 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:49:10,318 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [181921016] [2023-11-12 00:49:10,318 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:49:10,319 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:49:10,327 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:49:10,327 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [228820353] [2023-11-12 00:49:10,327 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-11-12 00:49:10,327 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:49:10,328 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:49:10,329 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:49:10,352 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-12 00:49:10,400 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:49:10,402 INFO L262 TraceCheckSpWp]: Trace formula consists of 170 conjuncts, 36 conjunts are in the unsatisfiable core [2023-11-12 00:49:10,405 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:49:10,642 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 00:49:10,642 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:49:11,062 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 00:49:11,063 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:49:11,063 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [181921016] [2023-11-12 00:49:11,063 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:49:11,063 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [228820353] [2023-11-12 00:49:11,063 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [228820353] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:49:11,063 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [807392847] [2023-11-12 00:49:11,071 INFO L159 IcfgInterpreter]: Started Sifa with 14 locations of interest [2023-11-12 00:49:11,072 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:49:11,072 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:49:11,072 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:49:11,073 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:49:12,221 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 00:49:12,227 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:49:12,499 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 00:49:12,499 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:49:12,500 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:49:12,500 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2023-11-12 00:49:12,500 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1278684009] [2023-11-12 00:49:12,500 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:49:12,500 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-11-12 00:49:12,501 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:49:12,501 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-11-12 00:49:12,502 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=418, Unknown=0, NotChecked=0, Total=506 [2023-11-12 00:49:12,502 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 00:49:14,994 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.05s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-12 00:49:17,765 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.64s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-12 00:49:17,784 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:49:17,784 INFO L93 Difference]: Finished difference Result 110 states and 130 transitions. [2023-11-12 00:49:17,784 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-11-12 00:49:17,785 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 00:49:17,785 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:49:17,788 INFO L225 Difference]: With dead ends: 110 [2023-11-12 00:49:17,788 INFO L226 Difference]: Without dead ends: 108 [2023-11-12 00:49:17,789 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 216 GetRequests, 184 SyntacticMatches, 3 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 244 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=170, Invalid=760, Unknown=0, NotChecked=0, Total=930 [2023-11-12 00:49:17,790 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 27 mSDsluCounter, 179 mSDsCounter, 0 mSdLazyCounter, 175 mSolverCounterSat, 53 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 202 SdHoareTripleChecker+Invalid, 230 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 175 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:49:17,790 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 202 Invalid, 230 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 175 Invalid, 2 Unknown, 0 Unchecked, 5.0s Time] [2023-11-12 00:49:17,791 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states. [2023-11-12 00:49:17,827 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 87. [2023-11-12 00:49:17,827 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 00:49:17,828 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 90 transitions. [2023-11-12 00:49:17,828 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 90 transitions. Word has length 70 [2023-11-12 00:49:17,829 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:49:17,829 INFO L495 AbstractCegarLoop]: Abstraction has 87 states and 90 transitions. [2023-11-12 00:49:17,829 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 00:49:17,829 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 90 transitions. [2023-11-12 00:49:17,831 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2023-11-12 00:49:17,831 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:49:17,831 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 00:49:17,837 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-12 00:49:18,037 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:49:18,037 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:49:18,038 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:49:18,038 INFO L85 PathProgramCache]: Analyzing trace with hash -176995479, now seen corresponding path program 2 times [2023-11-12 00:49:18,038 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:49:18,038 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [176925537] [2023-11-12 00:49:18,038 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:49:18,039 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:49:18,075 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:49:18,076 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1063194931] [2023-11-12 00:49:18,076 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-12 00:49:18,076 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:49:18,076 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:49:18,097 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:49:18,132 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-12 00:49:18,185 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-11-12 00:49:18,185 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 00:49:18,187 INFO L262 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 39 conjunts are in the unsatisfiable core [2023-11-12 00:49:18,191 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:49:18,501 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 00:49:18,502 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:49:20,820 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 00:49:20,820 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:49:20,820 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [176925537] [2023-11-12 00:49:20,820 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:49:20,820 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1063194931] [2023-11-12 00:49:20,821 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1063194931] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:49:20,821 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1930094144] [2023-11-12 00:49:20,823 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-11-12 00:49:20,823 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:49:20,823 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:49:20,823 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:49:20,824 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:49:21,699 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 00:49:21,704 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:49:22,350 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4407#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:49:22,350 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:49:22,350 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:49:22,350 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 16 [2023-11-12 00:49:22,350 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1227594399] [2023-11-12 00:49:22,350 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:49:22,351 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2023-11-12 00:49:22,351 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:49:22,352 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2023-11-12 00:49:22,352 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=381, Unknown=0, NotChecked=0, Total=462 [2023-11-12 00:49:22,353 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 00:49:22,813 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:49:22,813 INFO L93 Difference]: Finished difference Result 111 states and 119 transitions. [2023-11-12 00:49:22,814 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-11-12 00:49:22,814 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 00:49:22,815 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:49:22,816 INFO L225 Difference]: With dead ends: 111 [2023-11-12 00:49:22,816 INFO L226 Difference]: Without dead ends: 107 [2023-11-12 00:49:22,817 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 274 GetRequests, 248 SyntacticMatches, 3 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 169 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=101, Invalid=499, Unknown=0, NotChecked=0, Total=600 [2023-11-12 00:49:22,818 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 16 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 190 mSolverCounterSat, 33 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 223 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 190 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-12 00:49:22,818 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 123 Invalid, 223 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 190 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-12 00:49:22,819 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 107 states. [2023-11-12 00:49:22,873 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 107 to 105. [2023-11-12 00:49:22,874 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 00:49:22,875 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 112 transitions. [2023-11-12 00:49:22,875 INFO L78 Accepts]: Start accepts. Automaton has 105 states and 112 transitions. Word has length 91 [2023-11-12 00:49:22,876 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:49:22,876 INFO L495 AbstractCegarLoop]: Abstraction has 105 states and 112 transitions. [2023-11-12 00:49:22,876 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 00:49:22,876 INFO L276 IsEmpty]: Start isEmpty. Operand 105 states and 112 transitions. [2023-11-12 00:49:22,878 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2023-11-12 00:49:22,878 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:49:22,878 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 00:49:22,884 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-11-12 00:49:23,084 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:49:23,084 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:49:23,085 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:49:23,085 INFO L85 PathProgramCache]: Analyzing trace with hash -1760296702, now seen corresponding path program 2 times [2023-11-12 00:49:23,085 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:49:23,085 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [501654159] [2023-11-12 00:49:23,085 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:49:23,085 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:49:23,097 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:49:23,098 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [109263613] [2023-11-12 00:49:23,098 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-12 00:49:23,098 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:49:23,098 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:49:23,100 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:49:23,120 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-11-12 00:49:23,173 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-11-12 00:49:23,174 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 00:49:23,176 INFO L262 TraceCheckSpWp]: Trace formula consists of 107 conjuncts, 44 conjunts are in the unsatisfiable core [2023-11-12 00:49:23,180 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:49:23,639 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 00:49:23,639 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:49:25,276 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 00:49:25,277 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:49:25,277 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [501654159] [2023-11-12 00:49:25,277 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:49:25,277 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [109263613] [2023-11-12 00:49:25,277 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [109263613] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:49:25,277 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2091232046] [2023-11-12 00:49:25,279 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-12 00:49:25,280 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:49:25,280 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:49:25,280 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:49:25,280 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:49:26,053 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 00:49:26,057 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:49:26,584 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5317#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:49:26,584 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:49:26,584 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:49:26,584 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10] total 18 [2023-11-12 00:49:26,584 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [579252817] [2023-11-12 00:49:26,585 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:49:26,586 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2023-11-12 00:49:26,586 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:49:26,587 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2023-11-12 00:49:26,588 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=98, Invalid=454, Unknown=0, NotChecked=0, Total=552 [2023-11-12 00:49:26,588 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 00:49:32,946 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:49:32,947 INFO L93 Difference]: Finished difference Result 151 states and 174 transitions. [2023-11-12 00:49:32,949 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2023-11-12 00:49:32,949 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 00:49:32,949 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:49:32,951 INFO L225 Difference]: With dead ends: 151 [2023-11-12 00:49:32,951 INFO L226 Difference]: Without dead ends: 137 [2023-11-12 00:49:32,952 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 294 GetRequests, 261 SyntacticMatches, 3 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 248 ImplicationChecksByTransitivity, 6.7s TimeCoverageRelationStatistics Valid=190, Invalid=802, Unknown=0, NotChecked=0, Total=992 [2023-11-12 00:49:32,953 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 20 mSDsluCounter, 149 mSDsCounter, 0 mSdLazyCounter, 275 mSolverCounterSat, 56 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 172 SdHoareTripleChecker+Invalid, 331 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 56 IncrementalHoareTripleChecker+Valid, 275 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2023-11-12 00:49:32,953 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 172 Invalid, 331 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [56 Valid, 275 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2023-11-12 00:49:32,954 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 137 states. [2023-11-12 00:49:33,032 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 137 to 137. [2023-11-12 00:49:33,032 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 00:49:33,033 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 137 states to 137 states and 154 transitions. [2023-11-12 00:49:33,034 INFO L78 Accepts]: Start accepts. Automaton has 137 states and 154 transitions. Word has length 96 [2023-11-12 00:49:33,034 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:49:33,034 INFO L495 AbstractCegarLoop]: Abstraction has 137 states and 154 transitions. [2023-11-12 00:49:33,035 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 00:49:33,035 INFO L276 IsEmpty]: Start isEmpty. Operand 137 states and 154 transitions. [2023-11-12 00:49:33,038 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 205 [2023-11-12 00:49:33,038 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:49:33,038 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 00:49:33,043 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-11-12 00:49:33,238 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-11-12 00:49:33,239 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:49:33,239 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:49:33,239 INFO L85 PathProgramCache]: Analyzing trace with hash -2082635326, now seen corresponding path program 3 times [2023-11-12 00:49:33,240 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:49:33,240 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1375273962] [2023-11-12 00:49:33,240 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:49:33,240 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:49:33,256 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:49:33,257 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [469153207] [2023-11-12 00:49:33,257 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-12 00:49:33,257 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:49:33,257 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:49:33,258 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:49:33,262 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_a59c37cc-afba-4bf8-beb1-50fd04d4e00f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-11-12 00:49:35,576 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-12 00:49:35,576 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 00:49:35,580 INFO L262 TraceCheckSpWp]: Trace formula consists of 346 conjuncts, 88 conjunts are in the unsatisfiable core [2023-11-12 00:49:35,586 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:49:36,297 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 00:49:36,298 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:49:37,139 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 00:49:37,140 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:49:37,140 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1375273962] [2023-11-12 00:49:37,140 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:49:37,140 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [469153207] [2023-11-12 00:49:37,140 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [469153207] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:49:37,140 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [181821658] [2023-11-12 00:49:37,143 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-12 00:49:37,143 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:49:37,143 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:49:37,144 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:49:37,144 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs