./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound100.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 30e01a73 Calling Ultimate with: /usr/lib/jvm/java-11-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound100.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire --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 c55d57654781cf0634666e1c7d4e43dff0d9410f4306aded3e4e446e1f9e88d1 --- Real Ultimate output --- This is Ultimate 0.2.3-dev-30e01a7 [2023-11-23 21:15:45,695 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-23 21:15:45,771 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-23 21:15:45,776 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-23 21:15:45,777 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-23 21:15:45,804 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-23 21:15:45,805 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-23 21:15:45,806 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-23 21:15:45,807 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-23 21:15:45,807 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-23 21:15:45,808 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-23 21:15:45,808 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-23 21:15:45,809 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-23 21:15:45,809 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-23 21:15:45,810 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-23 21:15:45,810 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-23 21:15:45,811 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-23 21:15:45,811 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-23 21:15:45,812 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-23 21:15:45,812 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-23 21:15:45,813 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-23 21:15:45,814 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-23 21:15:45,814 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-23 21:15:45,815 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-23 21:15:45,815 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-23 21:15:45,816 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-23 21:15:45,816 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-23 21:15:45,816 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-23 21:15:45,817 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-23 21:15:45,817 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-23 21:15:45,818 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-23 21:15:45,818 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-23 21:15:45,818 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-23 21:15:45,819 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-23 21:15:45,819 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-23 21:15:45,819 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-11-23 21:15:45,819 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-23 21:15:45,820 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-23 21:15:45,820 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-23 21:15:45,820 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-23 21:15:45,820 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-23 21:15:45,821 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-23 21:15:45,821 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-23 21:15:45,821 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-11-23 21:15:45,821 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-23 21:15:45,822 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-23 21:15:45,822 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-23 21:15:45,822 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_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/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_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire 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 -> c55d57654781cf0634666e1c7d4e43dff0d9410f4306aded3e4e446e1f9e88d1 [2023-11-23 21:15:46,072 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-23 21:15:46,105 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-23 21:15:46,107 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-23 21:15:46,109 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-23 21:15:46,110 INFO L274 PluginConnector]: CDTParser initialized [2023-11-23 21:15:46,111 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/../../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound100.c [2023-11-23 21:15:49,283 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-23 21:15:49,509 INFO L384 CDTParser]: Found 1 translation units. [2023-11-23 21:15:49,510 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound100.c [2023-11-23 21:15:49,520 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/data/85c1144f3/4c76a9e61474486db423be033ecb0402/FLAG12522dd9d [2023-11-23 21:15:49,538 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/data/85c1144f3/4c76a9e61474486db423be033ecb0402 [2023-11-23 21:15:49,541 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-23 21:15:49,542 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-23 21:15:49,544 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-23 21:15:49,544 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-23 21:15:49,556 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-23 21:15:49,558 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.11 09:15:49" (1/1) ... [2023-11-23 21:15:49,559 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3a0cb7ba and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:15:49, skipping insertion in model container [2023-11-23 21:15:49,560 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.11 09:15:49" (1/1) ... [2023-11-23 21:15:49,589 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-23 21:15:49,791 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_066adabc-420a-4623-9dcb-7c86229d9e2a/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound100.c[588,601] [2023-11-23 21:15:49,822 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-23 21:15:49,832 INFO L202 MainTranslator]: Completed pre-run [2023-11-23 21:15:49,842 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_066adabc-420a-4623-9dcb-7c86229d9e2a/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound100.c[588,601] [2023-11-23 21:15:49,854 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-23 21:15:49,869 INFO L206 MainTranslator]: Completed translation [2023-11-23 21:15:49,870 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:15:49 WrapperNode [2023-11-23 21:15:49,870 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-23 21:15:49,871 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-23 21:15:49,871 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-23 21:15:49,872 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-23 21:15:49,880 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:15:49" (1/1) ... [2023-11-23 21:15:49,887 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:15:49" (1/1) ... [2023-11-23 21:15:49,907 INFO L138 Inliner]: procedures = 14, calls = 18, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 49 [2023-11-23 21:15:49,908 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-23 21:15:49,909 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-23 21:15:49,909 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-23 21:15:49,909 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-23 21:15:49,918 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:15:49" (1/1) ... [2023-11-23 21:15:49,918 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:15:49" (1/1) ... [2023-11-23 21:15:49,920 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:15:49" (1/1) ... [2023-11-23 21:15:49,921 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:15:49" (1/1) ... [2023-11-23 21:15:49,924 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:15:49" (1/1) ... [2023-11-23 21:15:49,928 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:15:49" (1/1) ... [2023-11-23 21:15:49,929 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:15:49" (1/1) ... [2023-11-23 21:15:49,930 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:15:49" (1/1) ... [2023-11-23 21:15:49,932 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-23 21:15:49,933 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-23 21:15:49,933 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-23 21:15:49,933 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-23 21:15:49,934 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:15:49" (1/1) ... [2023-11-23 21:15:49,952 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-23 21:15:49,963 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:15:49,980 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-23 21:15:49,990 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-23 21:15:50,015 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-23 21:15:50,016 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-23 21:15:50,016 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-23 21:15:50,016 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-23 21:15:50,016 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-11-23 21:15:50,016 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-11-23 21:15:50,073 INFO L241 CfgBuilder]: Building ICFG [2023-11-23 21:15:50,076 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-23 21:15:50,273 INFO L282 CfgBuilder]: Performing block encoding [2023-11-23 21:15:50,302 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-23 21:15:50,303 INFO L309 CfgBuilder]: Removed 1 assume(true) statements. [2023-11-23 21:15:50,304 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.11 09:15:50 BoogieIcfgContainer [2023-11-23 21:15:50,305 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-23 21:15:50,307 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-23 21:15:50,308 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-23 21:15:50,317 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-23 21:15:50,318 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 23.11 09:15:49" (1/3) ... [2023-11-23 21:15:50,320 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@53066517 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.11 09:15:50, skipping insertion in model container [2023-11-23 21:15:50,320 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 09:15:49" (2/3) ... [2023-11-23 21:15:50,321 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@53066517 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.11 09:15:50, skipping insertion in model container [2023-11-23 21:15:50,322 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.11 09:15:50" (3/3) ... [2023-11-23 21:15:50,323 INFO L112 eAbstractionObserver]: Analyzing ICFG cohencu-ll_unwindbound100.c [2023-11-23 21:15:50,341 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-23 21:15:50,342 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-23 21:15:50,393 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-23 21:15:50,399 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;@68a48caf, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-23 21:15:50,400 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-23 21:15:50,403 INFO L276 IsEmpty]: Start isEmpty. Operand has 23 states, 9 states have (on average 1.5555555555555556) internal successors, (14), 10 states have internal predecessors, (14), 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-23 21:15:50,409 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2023-11-23 21:15:50,409 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:15:50,409 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2023-11-23 21:15:50,410 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 21:15:50,414 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:15:50,415 INFO L85 PathProgramCache]: Analyzing trace with hash -1379524608, now seen corresponding path program 1 times [2023-11-23 21:15:50,422 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:15:50,423 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1848744292] [2023-11-23 21:15:50,423 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:15:50,423 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:15:50,546 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:15:50,613 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-23 21:15:50,614 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:15:50,615 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1848744292] [2023-11-23 21:15:50,616 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1848744292] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 21:15:50,616 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 21:15:50,617 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-23 21:15:50,618 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1255755975] [2023-11-23 21:15:50,619 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 21:15:50,623 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-11-23 21:15:50,625 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:15:50,666 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-11-23 21:15:50,667 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-11-23 21:15:50,670 INFO L87 Difference]: Start difference. First operand has 23 states, 9 states have (on average 1.5555555555555556) internal successors, (14), 10 states have internal predecessors, (14), 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 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:15:50,726 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:15:50,727 INFO L93 Difference]: Finished difference Result 45 states and 82 transitions. [2023-11-23 21:15:50,730 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-11-23 21:15:50,732 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 6 [2023-11-23 21:15:50,732 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:15:50,740 INFO L225 Difference]: With dead ends: 45 [2023-11-23 21:15:50,740 INFO L226 Difference]: Without dead ends: 21 [2023-11-23 21:15:50,745 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-11-23 21:15:50,750 INFO L413 NwaCegarLoop]: 32 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 32 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-23 21:15:50,752 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 32 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-23 21:15:50,771 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2023-11-23 21:15:50,799 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2023-11-23 21:15:50,801 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 8 states have (on average 1.375) internal successors, (11), 9 states have internal predecessors, (11), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2023-11-23 21:15:50,803 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 32 transitions. [2023-11-23 21:15:50,805 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 32 transitions. Word has length 6 [2023-11-23 21:15:50,805 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:15:50,806 INFO L495 AbstractCegarLoop]: Abstraction has 21 states and 32 transitions. [2023-11-23 21:15:50,806 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:15:50,806 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 32 transitions. [2023-11-23 21:15:50,808 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-11-23 21:15:50,809 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:15:50,809 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:15:50,809 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-23 21:15:50,810 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 21:15:50,810 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:15:50,811 INFO L85 PathProgramCache]: Analyzing trace with hash -345068235, now seen corresponding path program 1 times [2023-11-23 21:15:50,811 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:15:50,826 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [117852927] [2023-11-23 21:15:50,826 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:15:50,827 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:15:50,854 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:15:51,010 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-23 21:15:51,010 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:15:51,011 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [117852927] [2023-11-23 21:15:51,011 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [117852927] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 21:15:51,011 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 21:15:51,011 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-23 21:15:51,012 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1986794374] [2023-11-23 21:15:51,012 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 21:15:51,013 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-23 21:15:51,013 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:15:51,014 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-23 21:15:51,014 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-23 21:15:51,015 INFO L87 Difference]: Start difference. First operand 21 states and 32 transitions. Second operand has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:15:51,040 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:15:51,040 INFO L93 Difference]: Finished difference Result 35 states and 51 transitions. [2023-11-23 21:15:51,040 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-23 21:15:51,041 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2023-11-23 21:15:51,041 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:15:51,042 INFO L225 Difference]: With dead ends: 35 [2023-11-23 21:15:51,042 INFO L226 Difference]: Without dead ends: 23 [2023-11-23 21:15:51,043 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-23 21:15:51,044 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 0 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 86 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-23 21:15:51,045 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 86 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-23 21:15:51,046 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2023-11-23 21:15:51,051 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2023-11-23 21:15:51,052 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2023-11-23 21:15:51,053 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 34 transitions. [2023-11-23 21:15:51,057 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 34 transitions. Word has length 7 [2023-11-23 21:15:51,057 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:15:51,058 INFO L495 AbstractCegarLoop]: Abstraction has 23 states and 34 transitions. [2023-11-23 21:15:51,058 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:15:51,058 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 34 transitions. [2023-11-23 21:15:51,059 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-11-23 21:15:51,059 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:15:51,059 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:15:51,059 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-23 21:15:51,059 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 21:15:51,060 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:15:51,060 INFO L85 PathProgramCache]: Analyzing trace with hash -343519103, now seen corresponding path program 1 times [2023-11-23 21:15:51,060 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:15:51,061 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [226518977] [2023-11-23 21:15:51,061 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:15:51,061 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:15:51,082 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:15:51,308 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-23 21:15:51,309 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:15:51,309 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [226518977] [2023-11-23 21:15:51,310 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [226518977] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 21:15:51,310 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 21:15:51,310 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-11-23 21:15:51,310 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1353344853] [2023-11-23 21:15:51,310 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 21:15:51,311 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-23 21:15:51,311 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:15:51,312 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-23 21:15:51,312 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-23 21:15:51,312 INFO L87 Difference]: Start difference. First operand 23 states and 34 transitions. Second operand has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:15:51,431 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:15:51,431 INFO L93 Difference]: Finished difference Result 29 states and 39 transitions. [2023-11-23 21:15:51,431 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-23 21:15:51,432 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2023-11-23 21:15:51,432 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:15:51,433 INFO L225 Difference]: With dead ends: 29 [2023-11-23 21:15:51,433 INFO L226 Difference]: Without dead ends: 27 [2023-11-23 21:15:51,433 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-23 21:15:51,435 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 8 mSDsluCounter, 52 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 77 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-23 21:15:51,436 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 77 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-23 21:15:51,437 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2023-11-23 21:15:51,449 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2023-11-23 21:15:51,449 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 14 states have internal predecessors, (16), 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-23 21:15:51,451 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 37 transitions. [2023-11-23 21:15:51,451 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 37 transitions. Word has length 7 [2023-11-23 21:15:51,452 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:15:51,452 INFO L495 AbstractCegarLoop]: Abstraction has 27 states and 37 transitions. [2023-11-23 21:15:51,452 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-23 21:15:51,452 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 37 transitions. [2023-11-23 21:15:51,453 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2023-11-23 21:15:51,453 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:15:51,453 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:15:51,453 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2023-11-23 21:15:51,454 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 21:15:51,454 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:15:51,454 INFO L85 PathProgramCache]: Analyzing trace with hash -875596316, now seen corresponding path program 1 times [2023-11-23 21:15:51,455 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:15:51,455 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [346144869] [2023-11-23 21:15:51,455 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:15:51,455 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:15:51,468 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 21:15:51,468 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [512006139] [2023-11-23 21:15:51,468 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:15:51,469 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:15:51,469 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:15:51,476 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:15:51,511 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-23 21:15:51,585 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:15:51,588 INFO L262 TraceCheckSpWp]: Trace formula consists of 56 conjuncts, 7 conjunts are in the unsatisfiable core [2023-11-23 21:15:51,593 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:15:51,723 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-23 21:15:51,723 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-23 21:15:51,723 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:15:51,723 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [346144869] [2023-11-23 21:15:51,724 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 21:15:51,724 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [512006139] [2023-11-23 21:15:51,724 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [512006139] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 21:15:51,724 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 21:15:51,724 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-23 21:15:51,725 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1721119536] [2023-11-23 21:15:51,725 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 21:15:51,725 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-23 21:15:51,726 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:15:51,727 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-23 21:15:51,727 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-23 21:15:51,727 INFO L87 Difference]: Start difference. First operand 27 states and 37 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-23 21:15:51,841 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:15:51,841 INFO L93 Difference]: Finished difference Result 45 states and 65 transitions. [2023-11-23 21:15:51,842 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-23 21:15:51,843 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2023-11-23 21:15:51,844 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:15:51,847 INFO L225 Difference]: With dead ends: 45 [2023-11-23 21:15:51,847 INFO L226 Difference]: Without dead ends: 43 [2023-11-23 21:15:51,848 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 8 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-23 21:15:51,855 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 6 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 106 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-23 21:15:51,856 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 106 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-23 21:15:51,857 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2023-11-23 21:15:51,883 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 33. [2023-11-23 21:15:51,884 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 16 states have (on average 1.1875) internal successors, (19), 18 states have internal predecessors, (19), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) [2023-11-23 21:15:51,892 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 44 transitions. [2023-11-23 21:15:51,892 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 44 transitions. Word has length 12 [2023-11-23 21:15:51,892 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:15:51,892 INFO L495 AbstractCegarLoop]: Abstraction has 33 states and 44 transitions. [2023-11-23 21:15:51,893 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-23 21:15:51,893 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 44 transitions. [2023-11-23 21:15:51,893 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2023-11-23 21:15:51,893 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:15:51,894 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:15:51,926 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-23 21:15:52,115 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:15:52,116 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 21:15:52,116 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:15:52,116 INFO L85 PathProgramCache]: Analyzing trace with hash 2105691681, now seen corresponding path program 1 times [2023-11-23 21:15:52,116 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:15:52,117 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1778958305] [2023-11-23 21:15:52,117 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:15:52,117 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:15:52,131 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 21:15:52,132 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [589363616] [2023-11-23 21:15:52,132 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:15:52,133 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:15:52,133 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:15:52,134 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:15:52,150 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-23 21:15:52,189 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:15:52,190 INFO L262 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 7 conjunts are in the unsatisfiable core [2023-11-23 21:15:52,191 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:15:52,294 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-11-23 21:15:52,294 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-23 21:15:52,294 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:15:52,294 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1778958305] [2023-11-23 21:15:52,295 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 21:15:52,295 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [589363616] [2023-11-23 21:15:52,295 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [589363616] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 21:15:52,295 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 21:15:52,295 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-23 21:15:52,296 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [958935112] [2023-11-23 21:15:52,296 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 21:15:52,296 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-23 21:15:52,296 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:15:52,297 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-23 21:15:52,297 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-23 21:15:52,297 INFO L87 Difference]: Start difference. First operand 33 states and 44 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-11-23 21:15:52,422 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:15:52,422 INFO L93 Difference]: Finished difference Result 49 states and 68 transitions. [2023-11-23 21:15:52,422 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-23 21:15:52,423 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2023-11-23 21:15:52,423 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:15:52,424 INFO L225 Difference]: With dead ends: 49 [2023-11-23 21:15:52,424 INFO L226 Difference]: Without dead ends: 47 [2023-11-23 21:15:52,425 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 13 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-23 21:15:52,426 INFO L413 NwaCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-23 21:15:52,426 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 115 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-23 21:15:52,427 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2023-11-23 21:15:52,442 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 43. [2023-11-23 21:15:52,442 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 20 states have (on average 1.2) internal successors, (24), 22 states have internal predecessors, (24), 18 states have call successors, (18), 4 states have call predecessors, (18), 4 states have return successors, (17), 16 states have call predecessors, (17), 17 states have call successors, (17) [2023-11-23 21:15:52,444 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 59 transitions. [2023-11-23 21:15:52,444 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 59 transitions. Word has length 17 [2023-11-23 21:15:52,444 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:15:52,444 INFO L495 AbstractCegarLoop]: Abstraction has 43 states and 59 transitions. [2023-11-23 21:15:52,444 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-11-23 21:15:52,445 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 59 transitions. [2023-11-23 21:15:52,445 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2023-11-23 21:15:52,445 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:15:52,446 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:15:52,470 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-23 21:15:52,670 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:15:52,670 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 21:15:52,671 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:15:52,671 INFO L85 PathProgramCache]: Analyzing trace with hash 168504260, now seen corresponding path program 1 times [2023-11-23 21:15:52,671 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:15:52,671 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [325457699] [2023-11-23 21:15:52,672 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:15:52,672 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:15:52,682 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 21:15:52,687 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1488034510] [2023-11-23 21:15:52,687 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:15:52,688 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:15:52,688 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:15:52,691 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:15:52,706 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-23 21:15:52,754 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:15:52,755 INFO L262 TraceCheckSpWp]: Trace formula consists of 74 conjuncts, 9 conjunts are in the unsatisfiable core [2023-11-23 21:15:52,758 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:15:52,884 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-11-23 21:15:52,885 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-23 21:15:52,885 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:15:52,885 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [325457699] [2023-11-23 21:15:52,885 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 21:15:52,885 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1488034510] [2023-11-23 21:15:52,886 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1488034510] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 21:15:52,886 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 21:15:52,886 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-23 21:15:52,887 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [99599923] [2023-11-23 21:15:52,888 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 21:15:52,888 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-23 21:15:52,888 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:15:52,889 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-23 21:15:52,889 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-23 21:15:52,889 INFO L87 Difference]: Start difference. First operand 43 states and 59 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-11-23 21:15:52,999 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:15:52,999 INFO L93 Difference]: Finished difference Result 57 states and 74 transitions. [2023-11-23 21:15:52,999 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-23 21:15:53,000 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 22 [2023-11-23 21:15:53,000 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:15:53,001 INFO L225 Difference]: With dead ends: 57 [2023-11-23 21:15:53,001 INFO L226 Difference]: Without dead ends: 45 [2023-11-23 21:15:53,002 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 18 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-23 21:15:53,003 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 6 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 107 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-23 21:15:53,004 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 107 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-23 21:15:53,007 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2023-11-23 21:15:53,033 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2023-11-23 21:15:53,033 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 23 states have (on average 1.1304347826086956) internal successors, (26), 24 states have internal predecessors, (26), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2023-11-23 21:15:53,034 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 57 transitions. [2023-11-23 21:15:53,035 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 57 transitions. Word has length 22 [2023-11-23 21:15:53,035 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:15:53,035 INFO L495 AbstractCegarLoop]: Abstraction has 45 states and 57 transitions. [2023-11-23 21:15:53,035 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-11-23 21:15:53,036 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 57 transitions. [2023-11-23 21:15:53,037 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2023-11-23 21:15:53,037 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:15:53,037 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:15:53,063 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-23 21:15:53,258 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2023-11-23 21:15:53,259 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 21:15:53,259 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:15:53,259 INFO L85 PathProgramCache]: Analyzing trace with hash 1666200982, now seen corresponding path program 1 times [2023-11-23 21:15:53,259 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:15:53,259 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1322312840] [2023-11-23 21:15:53,260 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:15:53,260 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:15:53,273 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 21:15:53,273 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1663157209] [2023-11-23 21:15:53,273 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:15:53,274 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:15:53,274 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:15:53,275 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:15:53,302 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-23 21:15:53,348 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:15:53,349 INFO L262 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 5 conjunts are in the unsatisfiable core [2023-11-23 21:15:53,352 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:15:53,433 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 30 proven. 2 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2023-11-23 21:15:53,434 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:15:53,536 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 12 proven. 2 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2023-11-23 21:15:53,536 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:15:53,536 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1322312840] [2023-11-23 21:15:53,536 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 21:15:53,537 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1663157209] [2023-11-23 21:15:53,537 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1663157209] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:15:53,537 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [930161665] [2023-11-23 21:15:53,561 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-23 21:15:53,561 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:15:53,566 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-23 21:15:53,572 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-23 21:15:53,572 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-23 21:15:55,989 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-23 21:15:55,995 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-23 21:15:56,415 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1152#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-23 21:15:56,415 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-23 21:15:56,415 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 21:15:56,416 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5] total 8 [2023-11-23 21:15:56,417 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [861439814] [2023-11-23 21:15:56,417 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 21:15:56,418 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-11-23 21:15:56,418 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:15:56,418 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-11-23 21:15:56,419 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=181, Unknown=0, NotChecked=0, Total=240 [2023-11-23 21:15:56,420 INFO L87 Difference]: Start difference. First operand 45 states and 57 transitions. Second operand has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2023-11-23 21:15:56,641 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:15:56,641 INFO L93 Difference]: Finished difference Result 115 states and 150 transitions. [2023-11-23 21:15:56,642 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-23 21:15:56,642 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 40 [2023-11-23 21:15:56,644 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:15:56,648 INFO L225 Difference]: With dead ends: 115 [2023-11-23 21:15:56,648 INFO L226 Difference]: Without dead ends: 99 [2023-11-23 21:15:56,652 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 103 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 102 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=82, Invalid=260, Unknown=0, NotChecked=0, Total=342 [2023-11-23 21:15:56,653 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 57 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 71 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 88 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 71 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-23 21:15:56,653 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [57 Valid, 132 Invalid, 88 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 71 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-23 21:15:56,655 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2023-11-23 21:15:56,694 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 95. [2023-11-23 21:15:56,696 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 95 states, 46 states have (on average 1.1521739130434783) internal successors, (53), 49 states have internal predecessors, (53), 38 states have call successors, (38), 10 states have call predecessors, (38), 10 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2023-11-23 21:15:56,701 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 126 transitions. [2023-11-23 21:15:56,701 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 126 transitions. Word has length 40 [2023-11-23 21:15:56,702 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:15:56,702 INFO L495 AbstractCegarLoop]: Abstraction has 95 states and 126 transitions. [2023-11-23 21:15:56,703 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2023-11-23 21:15:56,704 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 126 transitions. [2023-11-23 21:15:56,707 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2023-11-23 21:15:56,707 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:15:56,707 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:15:56,733 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-23 21:15:56,920 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2023-11-23 21:15:56,920 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 21:15:56,921 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:15:56,921 INFO L85 PathProgramCache]: Analyzing trace with hash -2136650998, now seen corresponding path program 1 times [2023-11-23 21:15:56,921 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:15:56,921 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1898991196] [2023-11-23 21:15:56,921 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:15:56,921 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:15:56,932 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 21:15:56,932 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [348694811] [2023-11-23 21:15:56,933 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:15:56,933 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:15:56,933 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:15:56,934 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:15:56,954 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-23 21:15:57,001 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:15:57,002 INFO L262 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 23 conjunts are in the unsatisfiable core [2023-11-23 21:15:57,009 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:15:57,153 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 11 proven. 20 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2023-11-23 21:15:57,153 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:15:57,324 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 14 proven. 17 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2023-11-23 21:15:57,325 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:15:57,325 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1898991196] [2023-11-23 21:15:57,325 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 21:15:57,325 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [348694811] [2023-11-23 21:15:57,326 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [348694811] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:15:57,326 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [714176989] [2023-11-23 21:15:57,329 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-11-23 21:15:57,329 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:15:57,329 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-23 21:15:57,330 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-23 21:15:57,330 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-23 21:15:58,918 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-23 21:15:58,925 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-23 21:15:59,449 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1737#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-23 21:15:59,449 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-23 21:15:59,449 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 21:15:59,449 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2023-11-23 21:15:59,450 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1524079183] [2023-11-23 21:15:59,450 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 21:15:59,450 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-11-23 21:15:59,450 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:15:59,451 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-11-23 21:15:59,451 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=338, Unknown=0, NotChecked=0, Total=420 [2023-11-23 21:15:59,452 INFO L87 Difference]: Start difference. First operand 95 states and 126 transitions. Second operand has 13 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 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-23 21:15:59,769 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:15:59,769 INFO L93 Difference]: Finished difference Result 113 states and 142 transitions. [2023-11-23 21:15:59,770 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-23 21:15:59,770 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 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 40 [2023-11-23 21:15:59,771 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:15:59,773 INFO L225 Difference]: With dead ends: 113 [2023-11-23 21:15:59,773 INFO L226 Difference]: Without dead ends: 111 [2023-11-23 21:15:59,773 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 122 GetRequests, 97 SyntacticMatches, 2 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 168 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=114, Invalid=486, Unknown=0, NotChecked=0, Total=600 [2023-11-23 21:15:59,775 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 25 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 200 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 253 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 200 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-23 21:15:59,776 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 129 Invalid, 253 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 200 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-23 21:15:59,777 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2023-11-23 21:15:59,818 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 111. [2023-11-23 21:15:59,819 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 111 states, 58 states have (on average 1.1206896551724137) internal successors, (65), 61 states have internal predecessors, (65), 38 states have call successors, (38), 14 states have call predecessors, (38), 14 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2023-11-23 21:15:59,820 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 138 transitions. [2023-11-23 21:15:59,821 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 138 transitions. Word has length 40 [2023-11-23 21:15:59,822 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:15:59,823 INFO L495 AbstractCegarLoop]: Abstraction has 111 states and 138 transitions. [2023-11-23 21:15:59,823 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 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-23 21:15:59,823 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 138 transitions. [2023-11-23 21:15:59,824 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2023-11-23 21:15:59,824 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:15:59,825 INFO L195 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:15:59,850 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-23 21:16:00,046 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2023-11-23 21:16:00,046 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 21:16:00,046 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:16:00,047 INFO L85 PathProgramCache]: Analyzing trace with hash 1054982331, now seen corresponding path program 2 times [2023-11-23 21:16:00,047 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:16:00,047 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [748454642] [2023-11-23 21:16:00,047 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:16:00,047 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:16:00,057 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 21:16:00,063 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [326671109] [2023-11-23 21:16:00,063 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-23 21:16:00,064 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:16:00,064 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:16:00,065 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:16:00,082 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-23 21:16:00,114 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-11-23 21:16:00,114 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 21:16:00,115 INFO L262 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 16 conjunts are in the unsatisfiable core [2023-11-23 21:16:00,120 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:16:00,210 INFO L134 CoverageAnalysis]: Checked inductivity of 103 backedges. 14 proven. 5 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2023-11-23 21:16:00,211 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:16:00,303 INFO L134 CoverageAnalysis]: Checked inductivity of 103 backedges. 14 proven. 5 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2023-11-23 21:16:00,303 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:16:00,304 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [748454642] [2023-11-23 21:16:00,304 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 21:16:00,304 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [326671109] [2023-11-23 21:16:00,304 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [326671109] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:16:00,304 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [633312509] [2023-11-23 21:16:00,307 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-11-23 21:16:00,308 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:16:00,308 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-23 21:16:00,308 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-23 21:16:00,308 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-23 21:16:01,764 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-23 21:16:01,769 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-23 21:16:02,223 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2365#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-23 21:16:02,223 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-23 21:16:02,223 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 21:16:02,224 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2023-11-23 21:16:02,224 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1482855221] [2023-11-23 21:16:02,224 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 21:16:02,225 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-11-23 21:16:02,225 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:16:02,226 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-11-23 21:16:02,226 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=246, Unknown=0, NotChecked=0, Total=306 [2023-11-23 21:16:02,226 INFO L87 Difference]: Start difference. First operand 111 states and 138 transitions. Second operand has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 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-23 21:16:02,391 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:16:02,391 INFO L93 Difference]: Finished difference Result 117 states and 143 transitions. [2023-11-23 21:16:02,391 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-11-23 21:16:02,392 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 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 45 [2023-11-23 21:16:02,393 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:16:02,396 INFO L225 Difference]: With dead ends: 117 [2023-11-23 21:16:02,396 INFO L226 Difference]: Without dead ends: 115 [2023-11-23 21:16:02,397 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 115 SyntacticMatches, 2 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 91 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=66, Invalid=276, Unknown=0, NotChecked=0, Total=342 [2023-11-23 21:16:02,400 INFO L413 NwaCegarLoop]: 39 mSDtfsCounter, 8 mSDsluCounter, 173 mSDsCounter, 0 mSdLazyCounter, 97 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 212 SdHoareTripleChecker+Invalid, 108 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 97 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-23 21:16:02,401 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 212 Invalid, 108 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 97 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-23 21:16:02,402 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states. [2023-11-23 21:16:02,434 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 115. [2023-11-23 21:16:02,435 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 115 states, 61 states have (on average 1.1147540983606556) internal successors, (68), 64 states have internal predecessors, (68), 38 states have call successors, (38), 15 states have call predecessors, (38), 15 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2023-11-23 21:16:02,439 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 115 states to 115 states and 141 transitions. [2023-11-23 21:16:02,439 INFO L78 Accepts]: Start accepts. Automaton has 115 states and 141 transitions. Word has length 45 [2023-11-23 21:16:02,440 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:16:02,440 INFO L495 AbstractCegarLoop]: Abstraction has 115 states and 141 transitions. [2023-11-23 21:16:02,440 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 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-23 21:16:02,440 INFO L276 IsEmpty]: Start isEmpty. Operand 115 states and 141 transitions. [2023-11-23 21:16:02,447 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2023-11-23 21:16:02,447 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:16:02,447 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:16:02,478 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-23 21:16:02,670 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:16:02,671 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 21:16:02,671 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:16:02,671 INFO L85 PathProgramCache]: Analyzing trace with hash -615691926, now seen corresponding path program 3 times [2023-11-23 21:16:02,671 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:16:02,671 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1065380615] [2023-11-23 21:16:02,671 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:16:02,671 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:16:02,680 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 21:16:02,680 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [603771597] [2023-11-23 21:16:02,681 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-23 21:16:02,681 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:16:02,681 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:16:02,682 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:16:02,710 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-23 21:16:02,748 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-23 21:16:02,748 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 21:16:02,749 INFO L262 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 19 conjunts are in the unsatisfiable core [2023-11-23 21:16:02,752 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:16:02,876 INFO L134 CoverageAnalysis]: Checked inductivity of 134 backedges. 16 proven. 6 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2023-11-23 21:16:02,877 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:16:02,982 INFO L134 CoverageAnalysis]: Checked inductivity of 134 backedges. 16 proven. 6 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2023-11-23 21:16:02,983 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:16:02,983 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1065380615] [2023-11-23 21:16:02,983 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 21:16:02,983 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [603771597] [2023-11-23 21:16:02,983 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [603771597] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:16:02,984 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1880546349] [2023-11-23 21:16:02,986 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-11-23 21:16:02,986 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:16:02,987 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-23 21:16:02,987 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-23 21:16:02,987 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-23 21:16:04,383 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-23 21:16:04,391 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-23 21:16:04,799 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3025#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-23 21:16:04,799 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-23 21:16:04,799 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 21:16:04,799 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2023-11-23 21:16:04,799 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1457804622] [2023-11-23 21:16:04,799 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 21:16:04,800 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-11-23 21:16:04,800 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:16:04,801 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-11-23 21:16:04,801 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=187, Unknown=0, NotChecked=0, Total=240 [2023-11-23 21:16:04,802 INFO L87 Difference]: Start difference. First operand 115 states and 141 transitions. Second operand has 8 states, 8 states have (on average 2.25) internal successors, (18), 7 states have internal predecessors, (18), 4 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2023-11-23 21:16:05,060 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:16:05,060 INFO L93 Difference]: Finished difference Result 141 states and 163 transitions. [2023-11-23 21:16:05,061 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-11-23 21:16:05,061 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.25) internal successors, (18), 7 states have internal predecessors, (18), 4 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) Word has length 50 [2023-11-23 21:16:05,061 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:16:05,062 INFO L225 Difference]: With dead ends: 141 [2023-11-23 21:16:05,062 INFO L226 Difference]: Without dead ends: 130 [2023-11-23 21:16:05,063 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 150 GetRequests, 130 SyntacticMatches, 4 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 73 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=66, Invalid=240, Unknown=0, NotChecked=0, Total=306 [2023-11-23 21:16:05,064 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 12 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 79 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 117 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 79 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-23 21:16:05,064 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 141 Invalid, 117 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 79 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-23 21:16:05,065 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2023-11-23 21:16:05,100 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 130. [2023-11-23 21:16:05,100 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 130 states, 79 states have (on average 1.0886075949367089) internal successors, (86), 82 states have internal predecessors, (86), 29 states have call successors, (29), 21 states have call predecessors, (29), 21 states have return successors, (26), 26 states have call predecessors, (26), 26 states have call successors, (26) [2023-11-23 21:16:05,103 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 130 states to 130 states and 141 transitions. [2023-11-23 21:16:05,104 INFO L78 Accepts]: Start accepts. Automaton has 130 states and 141 transitions. Word has length 50 [2023-11-23 21:16:05,106 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:16:05,106 INFO L495 AbstractCegarLoop]: Abstraction has 130 states and 141 transitions. [2023-11-23 21:16:05,107 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.25) internal successors, (18), 7 states have internal predecessors, (18), 4 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2023-11-23 21:16:05,107 INFO L276 IsEmpty]: Start isEmpty. Operand 130 states and 141 transitions. [2023-11-23 21:16:05,109 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2023-11-23 21:16:05,109 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:16:05,109 INFO L195 NwaCegarLoop]: trace histogram [12, 11, 11, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:16:05,130 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-23 21:16:05,318 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:16:05,318 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 21:16:05,319 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:16:05,319 INFO L85 PathProgramCache]: Analyzing trace with hash -1733391679, now seen corresponding path program 1 times [2023-11-23 21:16:05,319 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:16:05,319 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1906529836] [2023-11-23 21:16:05,319 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:16:05,319 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:16:05,328 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 21:16:05,328 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1957165744] [2023-11-23 21:16:05,328 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:16:05,328 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:16:05,329 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:16:05,330 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:16:05,338 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-23 21:16:05,397 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:16:05,399 INFO L262 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 29 conjunts are in the unsatisfiable core [2023-11-23 21:16:05,402 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:16:05,768 INFO L134 CoverageAnalysis]: Checked inductivity of 250 backedges. 21 proven. 39 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2023-11-23 21:16:05,768 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:16:06,112 INFO L134 CoverageAnalysis]: Checked inductivity of 250 backedges. 24 proven. 36 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2023-11-23 21:16:06,112 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:16:06,112 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1906529836] [2023-11-23 21:16:06,112 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 21:16:06,112 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1957165744] [2023-11-23 21:16:06,113 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1957165744] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:16:06,113 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1263339268] [2023-11-23 21:16:06,115 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-23 21:16:06,115 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:16:06,116 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-23 21:16:06,116 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-23 21:16:06,116 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-23 21:16:07,462 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-23 21:16:07,467 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-23 21:16:08,032 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3831#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-23 21:16:08,032 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-23 21:16:08,034 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 21:16:08,034 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 14 [2023-11-23 21:16:08,035 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1836426007] [2023-11-23 21:16:08,035 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 21:16:08,036 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-11-23 21:16:08,036 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:16:08,036 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-11-23 21:16:08,037 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=377, Unknown=0, NotChecked=0, Total=462 [2023-11-23 21:16:08,037 INFO L87 Difference]: Start difference. First operand 130 states and 141 transitions. Second operand has 14 states, 12 states have (on average 2.25) internal successors, (27), 12 states have internal predecessors, (27), 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-23 21:16:08,361 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:16:08,361 INFO L93 Difference]: Finished difference Result 146 states and 158 transitions. [2023-11-23 21:16:08,362 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-11-23 21:16:08,362 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 2.25) internal successors, (27), 12 states have internal predecessors, (27), 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 66 [2023-11-23 21:16:08,362 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:16:08,365 INFO L225 Difference]: With dead ends: 146 [2023-11-23 21:16:08,365 INFO L226 Difference]: Without dead ends: 142 [2023-11-23 21:16:08,366 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 202 GetRequests, 175 SyntacticMatches, 2 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 184 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=129, Invalid=573, Unknown=0, NotChecked=0, Total=702 [2023-11-23 21:16:08,366 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 22 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 131 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 108 SdHoareTripleChecker+Invalid, 165 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 131 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-23 21:16:08,367 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 108 Invalid, 165 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 131 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-23 21:16:08,367 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2023-11-23 21:16:08,403 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 142. [2023-11-23 21:16:08,404 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 142 states, 87 states have (on average 1.0689655172413792) internal successors, (93), 90 states have internal predecessors, (93), 31 states have call successors, (31), 24 states have call predecessors, (31), 23 states have return successors, (28), 27 states have call predecessors, (28), 28 states have call successors, (28) [2023-11-23 21:16:08,404 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 152 transitions. [2023-11-23 21:16:08,405 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 152 transitions. Word has length 66 [2023-11-23 21:16:08,405 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:16:08,405 INFO L495 AbstractCegarLoop]: Abstraction has 142 states and 152 transitions. [2023-11-23 21:16:08,405 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 2.25) internal successors, (27), 12 states have internal predecessors, (27), 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-23 21:16:08,406 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 152 transitions. [2023-11-23 21:16:08,406 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2023-11-23 21:16:08,406 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:16:08,407 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:16:08,422 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-11-23 21:16:08,614 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:16:08,614 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 21:16:08,615 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:16:08,615 INFO L85 PathProgramCache]: Analyzing trace with hash 2124427812, now seen corresponding path program 1 times [2023-11-23 21:16:08,615 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:16:08,615 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2079558239] [2023-11-23 21:16:08,615 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:16:08,615 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:16:08,623 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 21:16:08,624 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1133272628] [2023-11-23 21:16:08,624 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:16:08,624 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:16:08,624 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:16:08,625 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:16:08,627 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-11-23 21:16:08,691 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:16:08,692 INFO L262 TraceCheckSpWp]: Trace formula consists of 170 conjuncts, 27 conjunts are in the unsatisfiable core [2023-11-23 21:16:08,695 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:16:09,020 INFO L134 CoverageAnalysis]: Checked inductivity of 296 backedges. 23 proven. 42 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-11-23 21:16:09,020 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:16:09,385 INFO L134 CoverageAnalysis]: Checked inductivity of 296 backedges. 23 proven. 42 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-11-23 21:16:09,385 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:16:09,385 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2079558239] [2023-11-23 21:16:09,385 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 21:16:09,385 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1133272628] [2023-11-23 21:16:09,385 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1133272628] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:16:09,385 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1791769962] [2023-11-23 21:16:09,388 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2023-11-23 21:16:09,388 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:16:09,388 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-23 21:16:09,388 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-23 21:16:09,389 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-23 21:16:10,417 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-23 21:16:10,421 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-23 21:16:10,866 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4693#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-23 21:16:10,866 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-23 21:16:10,866 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 21:16:10,866 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2023-11-23 21:16:10,867 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [902863277] [2023-11-23 21:16:10,867 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 21:16:10,867 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-23 21:16:10,867 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:16:10,868 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-23 21:16:10,868 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=412, Unknown=0, NotChecked=0, Total=506 [2023-11-23 21:16:10,869 INFO L87 Difference]: Start difference. First operand 142 states and 152 transitions. Second operand has 15 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 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-23 21:16:12,353 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:16:12,354 INFO L93 Difference]: Finished difference Result 162 states and 179 transitions. [2023-11-23 21:16:12,354 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-11-23 21:16:12,354 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 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 71 [2023-11-23 21:16:12,355 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:16:12,356 INFO L225 Difference]: With dead ends: 162 [2023-11-23 21:16:12,356 INFO L226 Difference]: Without dead ends: 133 [2023-11-23 21:16:12,357 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 217 GetRequests, 188 SyntacticMatches, 2 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 221 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=154, Invalid=658, Unknown=0, NotChecked=0, Total=812 [2023-11-23 21:16:12,357 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 16 mSDsluCounter, 190 mSDsCounter, 0 mSdLazyCounter, 263 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 210 SdHoareTripleChecker+Invalid, 285 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 263 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2023-11-23 21:16:12,358 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 210 Invalid, 285 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 263 Invalid, 0 Unknown, 0 Unchecked, 1.3s Time] [2023-11-23 21:16:12,359 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 133 states. [2023-11-23 21:16:12,396 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 133 to 132. [2023-11-23 21:16:12,397 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 132 states, 80 states have (on average 1.05) internal successors, (84), 82 states have internal predecessors, (84), 30 states have call successors, (30), 21 states have call predecessors, (30), 21 states have return successors, (29), 28 states have call predecessors, (29), 29 states have call successors, (29) [2023-11-23 21:16:12,398 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 132 states to 132 states and 143 transitions. [2023-11-23 21:16:12,398 INFO L78 Accepts]: Start accepts. Automaton has 132 states and 143 transitions. Word has length 71 [2023-11-23 21:16:12,398 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:16:12,399 INFO L495 AbstractCegarLoop]: Abstraction has 132 states and 143 transitions. [2023-11-23 21:16:12,399 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 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-23 21:16:12,399 INFO L276 IsEmpty]: Start isEmpty. Operand 132 states and 143 transitions. [2023-11-23 21:16:12,400 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2023-11-23 21:16:12,400 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:16:12,400 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1] [2023-11-23 21:16:12,418 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-11-23 21:16:12,600 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:16:12,601 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 21:16:12,601 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:16:12,601 INFO L85 PathProgramCache]: Analyzing trace with hash -1181636523, now seen corresponding path program 4 times [2023-11-23 21:16:12,601 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:16:12,601 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [60805340] [2023-11-23 21:16:12,601 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:16:12,602 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:16:12,610 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 21:16:12,610 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [161515518] [2023-11-23 21:16:12,610 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-11-23 21:16:12,610 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:16:12,611 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:16:12,612 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:16:12,619 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-11-23 21:16:12,679 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:16:12,680 INFO L262 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 31 conjunts are in the unsatisfiable core [2023-11-23 21:16:12,683 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:16:12,877 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 23 proven. 52 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-11-23 21:16:12,877 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:16:13,138 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 23 proven. 52 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-11-23 21:16:13,139 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:16:13,139 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [60805340] [2023-11-23 21:16:13,139 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 21:16:13,139 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [161515518] [2023-11-23 21:16:13,139 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [161515518] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:16:13,139 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [273394752] [2023-11-23 21:16:13,142 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-11-23 21:16:13,142 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:16:13,142 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-23 21:16:13,143 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-23 21:16:13,143 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-23 21:16:14,268 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-23 21:16:14,273 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-23 21:16:14,754 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5581#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-23 21:16:14,754 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-23 21:16:14,755 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 21:16:14,755 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2023-11-23 21:16:14,755 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1798394210] [2023-11-23 21:16:14,755 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 21:16:14,755 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-23 21:16:14,756 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:16:14,756 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-23 21:16:14,757 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=415, Unknown=0, NotChecked=0, Total=506 [2023-11-23 21:16:14,757 INFO L87 Difference]: Start difference. First operand 132 states and 143 transitions. Second operand has 15 states, 15 states have (on average 2.066666666666667) internal successors, (31), 13 states have internal predecessors, (31), 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-23 21:16:17,032 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-23 21:16:17,136 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:16:17,137 INFO L93 Difference]: Finished difference Result 138 states and 148 transitions. [2023-11-23 21:16:17,137 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-23 21:16:17,138 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.066666666666667) internal successors, (31), 13 states have internal predecessors, (31), 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 73 [2023-11-23 21:16:17,138 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:16:17,139 INFO L225 Difference]: With dead ends: 138 [2023-11-23 21:16:17,139 INFO L226 Difference]: Without dead ends: 136 [2023-11-23 21:16:17,140 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 223 GetRequests, 194 SyntacticMatches, 3 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 219 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=133, Invalid=623, Unknown=0, NotChecked=0, Total=756 [2023-11-23 21:16:17,141 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 28 mSDsluCounter, 152 mSDsCounter, 0 mSdLazyCounter, 224 mSolverCounterSat, 44 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 179 SdHoareTripleChecker+Invalid, 269 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 224 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.2s IncrementalHoareTripleChecker+Time [2023-11-23 21:16:17,142 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 179 Invalid, 269 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 224 Invalid, 1 Unknown, 0 Unchecked, 2.2s Time] [2023-11-23 21:16:17,142 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2023-11-23 21:16:17,192 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 136. [2023-11-23 21:16:17,192 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 136 states, 83 states have (on average 1.036144578313253) internal successors, (86), 85 states have internal predecessors, (86), 30 states have call successors, (30), 22 states have call predecessors, (30), 22 states have return successors, (29), 28 states have call predecessors, (29), 29 states have call successors, (29) [2023-11-23 21:16:17,194 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 136 states to 136 states and 145 transitions. [2023-11-23 21:16:17,194 INFO L78 Accepts]: Start accepts. Automaton has 136 states and 145 transitions. Word has length 73 [2023-11-23 21:16:17,194 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:16:17,195 INFO L495 AbstractCegarLoop]: Abstraction has 136 states and 145 transitions. [2023-11-23 21:16:17,195 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.066666666666667) internal successors, (31), 13 states have internal predecessors, (31), 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-23 21:16:17,195 INFO L276 IsEmpty]: Start isEmpty. Operand 136 states and 145 transitions. [2023-11-23 21:16:17,196 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 125 [2023-11-23 21:16:17,196 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:16:17,197 INFO L195 NwaCegarLoop]: trace histogram [22, 21, 21, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:16:17,223 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2023-11-23 21:16:17,410 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2023-11-23 21:16:17,410 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 21:16:17,411 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:16:17,411 INFO L85 PathProgramCache]: Analyzing trace with hash -1753860344, now seen corresponding path program 2 times [2023-11-23 21:16:17,411 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:16:17,411 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [704832610] [2023-11-23 21:16:17,411 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:16:17,411 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:16:17,420 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 21:16:17,420 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1310806034] [2023-11-23 21:16:17,421 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-23 21:16:17,421 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:16:17,421 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:16:17,422 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:16:17,427 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-11-23 21:16:17,564 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2023-11-23 21:16:17,565 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 21:16:17,567 INFO L262 TraceCheckSpWp]: Trace formula consists of 265 conjuncts, 11 conjunts are in the unsatisfiable core [2023-11-23 21:16:17,571 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:16:17,740 INFO L134 CoverageAnalysis]: Checked inductivity of 938 backedges. 120 proven. 656 refuted. 0 times theorem prover too weak. 162 trivial. 0 not checked. [2023-11-23 21:16:17,740 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:16:17,880 INFO L134 CoverageAnalysis]: Checked inductivity of 938 backedges. 42 proven. 56 refuted. 0 times theorem prover too weak. 840 trivial. 0 not checked. [2023-11-23 21:16:17,881 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:16:17,881 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [704832610] [2023-11-23 21:16:17,881 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 21:16:17,881 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1310806034] [2023-11-23 21:16:17,881 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1310806034] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:16:17,881 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1282362336] [2023-11-23 21:16:17,883 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-23 21:16:17,884 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:16:17,884 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-23 21:16:17,884 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-23 21:16:17,884 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-23 21:16:18,914 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-23 21:16:18,919 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-23 21:16:19,350 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '6740#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-23 21:16:19,350 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-23 21:16:19,350 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 21:16:19,351 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8] total 14 [2023-11-23 21:16:19,351 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [926726373] [2023-11-23 21:16:19,351 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 21:16:19,352 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-11-23 21:16:19,352 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:16:19,352 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-11-23 21:16:19,353 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=128, Invalid=334, Unknown=0, NotChecked=0, Total=462 [2023-11-23 21:16:19,353 INFO L87 Difference]: Start difference. First operand 136 states and 145 transitions. Second operand has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (43), 6 states have call predecessors, (43), 6 states have return successors, (42), 9 states have call predecessors, (42), 9 states have call successors, (42) [2023-11-23 21:16:19,836 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:16:19,837 INFO L93 Difference]: Finished difference Result 376 states and 391 transitions. [2023-11-23 21:16:19,837 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2023-11-23 21:16:19,837 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (43), 6 states have call predecessors, (43), 6 states have return successors, (42), 9 states have call predecessors, (42), 9 states have call successors, (42) Word has length 124 [2023-11-23 21:16:19,838 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:16:19,840 INFO L225 Difference]: With dead ends: 376 [2023-11-23 21:16:19,840 INFO L226 Difference]: Without dead ends: 353 [2023-11-23 21:16:19,841 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 379 GetRequests, 346 SyntacticMatches, 4 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 351 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=250, Invalid=680, Unknown=0, NotChecked=0, Total=930 [2023-11-23 21:16:19,842 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 99 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 153 mSolverCounterSat, 21 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 99 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 174 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 153 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-23 21:16:19,842 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [99 Valid, 129 Invalid, 174 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 153 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-23 21:16:19,843 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 353 states. [2023-11-23 21:16:19,962 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 353 to 311. [2023-11-23 21:16:19,963 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 311 states, 195 states have (on average 1.041025641025641) internal successors, (203), 201 states have internal predecessors, (203), 62 states have call successors, (62), 54 states have call predecessors, (62), 53 states have return successors, (60), 55 states have call predecessors, (60), 60 states have call successors, (60) [2023-11-23 21:16:19,965 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 311 states to 311 states and 325 transitions. [2023-11-23 21:16:19,965 INFO L78 Accepts]: Start accepts. Automaton has 311 states and 325 transitions. Word has length 124 [2023-11-23 21:16:19,966 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:16:19,966 INFO L495 AbstractCegarLoop]: Abstraction has 311 states and 325 transitions. [2023-11-23 21:16:19,966 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (43), 6 states have call predecessors, (43), 6 states have return successors, (42), 9 states have call predecessors, (42), 9 states have call successors, (42) [2023-11-23 21:16:19,966 INFO L276 IsEmpty]: Start isEmpty. Operand 311 states and 325 transitions. [2023-11-23 21:16:19,968 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 156 [2023-11-23 21:16:19,968 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:16:19,968 INFO L195 NwaCegarLoop]: trace histogram [28, 27, 27, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:16:19,989 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2023-11-23 21:16:20,181 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2023-11-23 21:16:20,181 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 21:16:20,182 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:16:20,182 INFO L85 PathProgramCache]: Analyzing trace with hash 460751474, now seen corresponding path program 2 times [2023-11-23 21:16:20,182 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:16:20,182 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [151213251] [2023-11-23 21:16:20,182 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:16:20,182 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:16:20,193 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 21:16:20,194 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1536991212] [2023-11-23 21:16:20,194 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-23 21:16:20,194 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:16:20,194 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:16:20,195 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:16:20,200 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-11-23 21:16:20,296 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2023-11-23 21:16:20,296 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 21:16:20,298 INFO L262 TraceCheckSpWp]: Trace formula consists of 171 conjuncts, 42 conjunts are in the unsatisfiable core [2023-11-23 21:16:20,302 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:16:21,250 INFO L134 CoverageAnalysis]: Checked inductivity of 1538 backedges. 341 proven. 46 refuted. 0 times theorem prover too weak. 1151 trivial. 0 not checked. [2023-11-23 21:16:21,250 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:16:21,965 INFO L134 CoverageAnalysis]: Checked inductivity of 1538 backedges. 215 proven. 24 refuted. 0 times theorem prover too weak. 1299 trivial. 0 not checked. [2023-11-23 21:16:21,965 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:16:21,965 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [151213251] [2023-11-23 21:16:21,965 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 21:16:21,966 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1536991212] [2023-11-23 21:16:21,966 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1536991212] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:16:21,966 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [173650468] [2023-11-23 21:16:21,968 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2023-11-23 21:16:21,968 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:16:21,969 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-23 21:16:21,969 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-23 21:16:21,969 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-23 21:16:23,128 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-23 21:16:23,133 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-23 21:16:23,883 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '8669#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-23 21:16:23,883 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-23 21:16:23,883 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 21:16:23,884 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 17 [2023-11-23 21:16:23,884 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [674280303] [2023-11-23 21:16:23,884 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 21:16:23,885 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-11-23 21:16:23,885 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:16:23,886 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-11-23 21:16:23,886 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=110, Invalid=490, Unknown=0, NotChecked=0, Total=600 [2023-11-23 21:16:23,886 INFO L87 Difference]: Start difference. First operand 311 states and 325 transitions. Second operand has 17 states, 13 states have (on average 2.4615384615384617) internal successors, (32), 13 states have internal predecessors, (32), 9 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (31), 8 states have call predecessors, (31), 9 states have call successors, (31) [2023-11-23 21:16:25,231 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:16:25,231 INFO L93 Difference]: Finished difference Result 318 states and 331 transitions. [2023-11-23 21:16:25,231 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-23 21:16:25,232 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 13 states have (on average 2.4615384615384617) internal successors, (32), 13 states have internal predecessors, (32), 9 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (31), 8 states have call predecessors, (31), 9 states have call successors, (31) Word has length 155 [2023-11-23 21:16:25,232 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:16:25,234 INFO L225 Difference]: With dead ends: 318 [2023-11-23 21:16:25,234 INFO L226 Difference]: Without dead ends: 292 [2023-11-23 21:16:25,235 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 467 GetRequests, 434 SyntacticMatches, 6 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 302 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=150, Invalid=662, Unknown=0, NotChecked=0, Total=812 [2023-11-23 21:16:25,235 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 18 mSDsluCounter, 160 mSDsCounter, 0 mSdLazyCounter, 165 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 182 SdHoareTripleChecker+Invalid, 188 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 165 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2023-11-23 21:16:25,236 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 182 Invalid, 188 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 165 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2023-11-23 21:16:25,236 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 292 states. [2023-11-23 21:16:25,336 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 292 to 292. [2023-11-23 21:16:25,337 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 292 states, 187 states have (on average 1.0106951871657754) internal successors, (189), 188 states have internal predecessors, (189), 53 states have call successors, (53), 51 states have call predecessors, (53), 51 states have return successors, (52), 52 states have call predecessors, (52), 52 states have call successors, (52) [2023-11-23 21:16:25,338 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 292 states to 292 states and 294 transitions. [2023-11-23 21:16:25,339 INFO L78 Accepts]: Start accepts. Automaton has 292 states and 294 transitions. Word has length 155 [2023-11-23 21:16:25,339 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:16:25,339 INFO L495 AbstractCegarLoop]: Abstraction has 292 states and 294 transitions. [2023-11-23 21:16:25,339 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 13 states have (on average 2.4615384615384617) internal successors, (32), 13 states have internal predecessors, (32), 9 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (31), 8 states have call predecessors, (31), 9 states have call successors, (31) [2023-11-23 21:16:25,340 INFO L276 IsEmpty]: Start isEmpty. Operand 292 states and 294 transitions. [2023-11-23 21:16:25,343 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 293 [2023-11-23 21:16:25,344 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:16:25,344 INFO L195 NwaCegarLoop]: trace histogram [52, 51, 51, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:16:25,349 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2023-11-23 21:16:25,549 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2023-11-23 21:16:25,549 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 21:16:25,550 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:16:25,550 INFO L85 PathProgramCache]: Analyzing trace with hash -141720852, now seen corresponding path program 3 times [2023-11-23 21:16:25,550 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:16:25,550 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [486078851] [2023-11-23 21:16:25,550 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:16:25,551 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:16:25,569 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 21:16:25,570 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [577091627] [2023-11-23 21:16:25,570 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-23 21:16:25,570 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:16:25,570 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:16:25,571 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:16:25,589 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-11-23 21:16:25,715 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-23 21:16:25,715 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 21:16:25,718 INFO L262 TraceCheckSpWp]: Trace formula consists of 646 conjuncts, 23 conjunts are in the unsatisfiable core [2023-11-23 21:16:25,726 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:16:26,127 INFO L134 CoverageAnalysis]: Checked inductivity of 5582 backedges. 300 proven. 4880 refuted. 0 times theorem prover too weak. 402 trivial. 0 not checked. [2023-11-23 21:16:26,128 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:16:26,589 INFO L134 CoverageAnalysis]: Checked inductivity of 5582 backedges. 102 proven. 380 refuted. 0 times theorem prover too weak. 5100 trivial. 0 not checked. [2023-11-23 21:16:26,589 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:16:26,590 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [486078851] [2023-11-23 21:16:26,590 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 21:16:26,590 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [577091627] [2023-11-23 21:16:26,590 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [577091627] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:16:26,590 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [662778421] [2023-11-23 21:16:26,596 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-23 21:16:26,596 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:16:26,597 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-23 21:16:26,598 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-23 21:16:26,598 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-23 21:16:27,887 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-23 21:16:27,893 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-23 21:16:28,422 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '11311#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-23 21:16:28,423 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-23 21:16:28,423 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 21:16:28,423 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 14] total 26 [2023-11-23 21:16:28,423 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [290787362] [2023-11-23 21:16:28,424 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 21:16:28,425 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2023-11-23 21:16:28,425 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:16:28,426 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2023-11-23 21:16:28,427 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=374, Invalid=748, Unknown=0, NotChecked=0, Total=1122 [2023-11-23 21:16:28,427 INFO L87 Difference]: Start difference. First operand 292 states and 294 transitions. Second operand has 26 states, 26 states have (on average 4.0) internal successors, (104), 26 states have internal predecessors, (104), 21 states have call successors, (103), 12 states have call predecessors, (103), 12 states have return successors, (102), 21 states have call predecessors, (102), 21 states have call successors, (102) [2023-11-23 21:16:29,550 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:16:29,550 INFO L93 Difference]: Finished difference Result 641 states and 655 transitions. [2023-11-23 21:16:29,551 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2023-11-23 21:16:29,551 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 4.0) internal successors, (104), 26 states have internal predecessors, (104), 21 states have call successors, (103), 12 states have call predecessors, (103), 12 states have return successors, (102), 21 states have call predecessors, (102), 21 states have call successors, (102) Word has length 292 [2023-11-23 21:16:29,552 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:16:29,556 INFO L225 Difference]: With dead ends: 641 [2023-11-23 21:16:29,556 INFO L226 Difference]: Without dead ends: 628 [2023-11-23 21:16:29,558 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 895 GetRequests, 832 SyntacticMatches, 10 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1200 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=910, Invalid=2060, Unknown=0, NotChecked=0, Total=2970 [2023-11-23 21:16:29,558 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 137 mSDsluCounter, 156 mSDsCounter, 0 mSdLazyCounter, 265 mSolverCounterSat, 71 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 137 SdHoareTripleChecker+Valid, 178 SdHoareTripleChecker+Invalid, 336 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 71 IncrementalHoareTripleChecker+Valid, 265 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-23 21:16:29,559 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [137 Valid, 178 Invalid, 336 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [71 Valid, 265 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-23 21:16:29,560 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 628 states. [2023-11-23 21:16:29,789 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 628 to 628. [2023-11-23 21:16:29,791 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 628 states, 403 states have (on average 1.0049627791563276) internal successors, (405), 404 states have internal predecessors, (405), 113 states have call successors, (113), 111 states have call predecessors, (113), 111 states have return successors, (112), 112 states have call predecessors, (112), 112 states have call successors, (112) [2023-11-23 21:16:29,794 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 628 states to 628 states and 630 transitions. [2023-11-23 21:16:29,795 INFO L78 Accepts]: Start accepts. Automaton has 628 states and 630 transitions. Word has length 292 [2023-11-23 21:16:29,795 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:16:29,796 INFO L495 AbstractCegarLoop]: Abstraction has 628 states and 630 transitions. [2023-11-23 21:16:29,796 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 4.0) internal successors, (104), 26 states have internal predecessors, (104), 21 states have call successors, (103), 12 states have call predecessors, (103), 12 states have return successors, (102), 21 states have call predecessors, (102), 21 states have call successors, (102) [2023-11-23 21:16:29,796 INFO L276 IsEmpty]: Start isEmpty. Operand 628 states and 630 transitions. [2023-11-23 21:16:29,812 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 629 [2023-11-23 21:16:29,813 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:16:29,813 INFO L195 NwaCegarLoop]: trace histogram [112, 111, 111, 23, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:16:29,838 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2023-11-23 21:16:30,034 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2023-11-23 21:16:30,034 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 21:16:30,034 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:16:30,034 INFO L85 PathProgramCache]: Analyzing trace with hash -1785250124, now seen corresponding path program 4 times [2023-11-23 21:16:30,034 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:16:30,034 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1379917824] [2023-11-23 21:16:30,035 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:16:30,035 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:16:30,069 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 21:16:30,069 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2112055446] [2023-11-23 21:16:30,069 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-11-23 21:16:30,070 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:16:30,070 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:16:30,071 INFO L229 MonitoredProcess]: Starting monitored process 15 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:16:30,100 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2023-11-23 21:16:30,348 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 21:16:30,356 INFO L262 TraceCheckSpWp]: Trace formula consists of 1354 conjuncts, 47 conjunts are in the unsatisfiable core [2023-11-23 21:16:30,379 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 21:16:31,415 INFO L134 CoverageAnalysis]: Checked inductivity of 26534 backedges. 660 proven. 24992 refuted. 0 times theorem prover too weak. 882 trivial. 0 not checked. [2023-11-23 21:16:31,416 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 21:16:32,762 INFO L134 CoverageAnalysis]: Checked inductivity of 26534 backedges. 222 proven. 1892 refuted. 0 times theorem prover too weak. 24420 trivial. 0 not checked. [2023-11-23 21:16:32,765 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-23 21:16:32,766 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1379917824] [2023-11-23 21:16:32,766 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-23 21:16:32,766 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2112055446] [2023-11-23 21:16:32,766 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2112055446] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 21:16:32,766 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1744655100] [2023-11-23 21:16:32,768 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-23 21:16:32,769 INFO L166 IcfgInterpreter]: Building call graph [2023-11-23 21:16:32,770 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-23 21:16:32,770 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-23 21:16:32,770 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-23 21:16:34,039 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-23 21:16:34,044 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-23 21:16:35,035 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '16941#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-23 21:16:35,036 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-23 21:16:35,036 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 21:16:35,036 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 26] total 50 [2023-11-23 21:16:35,036 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2094838531] [2023-11-23 21:16:35,036 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 21:16:35,039 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 50 states [2023-11-23 21:16:35,039 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-23 21:16:35,042 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2023-11-23 21:16:35,043 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1298, Invalid=2008, Unknown=0, NotChecked=0, Total=3306 [2023-11-23 21:16:35,043 INFO L87 Difference]: Start difference. First operand 628 states and 630 transitions. Second operand has 50 states, 50 states have (on average 4.24) internal successors, (212), 50 states have internal predecessors, (212), 45 states have call successors, (223), 24 states have call predecessors, (223), 24 states have return successors, (222), 45 states have call predecessors, (222), 45 states have call successors, (222) [2023-11-23 21:16:38,142 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 21:16:38,143 INFO L93 Difference]: Finished difference Result 1313 states and 1339 transitions. [2023-11-23 21:16:38,143 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 94 states. [2023-11-23 21:16:38,144 INFO L78 Accepts]: Start accepts. Automaton has has 50 states, 50 states have (on average 4.24) internal successors, (212), 50 states have internal predecessors, (212), 45 states have call successors, (223), 24 states have call predecessors, (223), 24 states have return successors, (222), 45 states have call predecessors, (222), 45 states have call successors, (222) Word has length 628 [2023-11-23 21:16:38,146 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 21:16:38,153 INFO L225 Difference]: With dead ends: 1313 [2023-11-23 21:16:38,153 INFO L226 Difference]: Without dead ends: 1300 [2023-11-23 21:16:38,157 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 1927 GetRequests, 1804 SyntacticMatches, 22 SemanticMatches, 101 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4302 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=3526, Invalid=6980, Unknown=0, NotChecked=0, Total=10506 [2023-11-23 21:16:38,158 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 302 mSDsluCounter, 276 mSDsCounter, 0 mSdLazyCounter, 553 mSolverCounterSat, 186 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 302 SdHoareTripleChecker+Valid, 298 SdHoareTripleChecker+Invalid, 739 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 186 IncrementalHoareTripleChecker+Valid, 553 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2023-11-23 21:16:38,159 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [302 Valid, 298 Invalid, 739 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [186 Valid, 553 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2023-11-23 21:16:38,161 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1300 states. [2023-11-23 21:16:38,644 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1300 to 1300. [2023-11-23 21:16:38,647 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1300 states, 835 states have (on average 1.0023952095808384) internal successors, (837), 836 states have internal predecessors, (837), 233 states have call successors, (233), 231 states have call predecessors, (233), 231 states have return successors, (232), 232 states have call predecessors, (232), 232 states have call successors, (232) [2023-11-23 21:16:38,653 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1300 states to 1300 states and 1302 transitions. [2023-11-23 21:16:38,654 INFO L78 Accepts]: Start accepts. Automaton has 1300 states and 1302 transitions. Word has length 628 [2023-11-23 21:16:38,655 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 21:16:38,655 INFO L495 AbstractCegarLoop]: Abstraction has 1300 states and 1302 transitions. [2023-11-23 21:16:38,656 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 50 states, 50 states have (on average 4.24) internal successors, (212), 50 states have internal predecessors, (212), 45 states have call successors, (223), 24 states have call predecessors, (223), 24 states have return successors, (222), 45 states have call predecessors, (222), 45 states have call successors, (222) [2023-11-23 21:16:38,656 INFO L276 IsEmpty]: Start isEmpty. Operand 1300 states and 1302 transitions. [2023-11-23 21:16:38,737 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1301 [2023-11-23 21:16:38,737 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 21:16:38,738 INFO L195 NwaCegarLoop]: trace histogram [232, 231, 231, 47, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 21:16:38,761 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2023-11-23 21:16:38,954 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2023-11-23 21:16:38,954 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 21:16:38,955 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 21:16:38,955 INFO L85 PathProgramCache]: Analyzing trace with hash -997767612, now seen corresponding path program 5 times [2023-11-23 21:16:38,955 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-23 21:16:38,955 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1098141794] [2023-11-23 21:16:38,955 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 21:16:38,955 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 21:16:39,020 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-23 21:16:39,021 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [487189960] [2023-11-23 21:16:39,021 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-23 21:16:39,021 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 21:16:39,021 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 [2023-11-23 21:16:39,022 INFO L229 MonitoredProcess]: Starting monitored process 16 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-23 21:16:39,042 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_066adabc-420a-4623-9dcb-7c86229d9e2a/bin/utaipan-verify-mE87zJ7Ire/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process