./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound5.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version cf1a7837 Calling Ultimate with: /usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound5.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash a077c1334c11d8329da2d0c58ca917b2036581fa7e949d1d304e3346ec54a811 --- Real Ultimate output --- This is Ultimate 0.2.3-dev-cf1a783 [2023-11-12 00:14:09,561 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-12 00:14:09,635 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-12 00:14:09,644 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-12 00:14:09,648 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-12 00:14:09,688 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-12 00:14:09,689 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-12 00:14:09,689 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-12 00:14:09,691 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-12 00:14:09,696 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-12 00:14:09,696 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-12 00:14:09,697 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-12 00:14:09,698 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-12 00:14:09,699 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-12 00:14:09,700 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-12 00:14:09,700 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-12 00:14:09,701 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-12 00:14:09,701 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-12 00:14:09,702 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-12 00:14:09,703 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-12 00:14:09,703 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-12 00:14:09,704 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-12 00:14:09,705 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-12 00:14:09,705 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-12 00:14:09,705 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-12 00:14:09,706 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-12 00:14:09,706 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-12 00:14:09,707 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-12 00:14:09,707 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-12 00:14:09,708 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-12 00:14:09,709 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-12 00:14:09,709 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-12 00:14:09,710 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-12 00:14:09,710 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-12 00:14:09,710 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-12 00:14:09,711 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-12 00:14:09,711 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 00:14:09,711 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-12 00:14:09,712 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-12 00:14:09,712 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-12 00:14:09,712 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-12 00:14:09,713 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-12 00:14:09,713 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-12 00:14:09,714 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-12 00:14:09,715 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-12 00:14:09,715 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_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Taipan Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> a077c1334c11d8329da2d0c58ca917b2036581fa7e949d1d304e3346ec54a811 [2023-11-12 00:14:10,042 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-12 00:14:10,076 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-12 00:14:10,079 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-12 00:14:10,080 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-12 00:14:10,081 INFO L274 PluginConnector]: CDTParser initialized [2023-11-12 00:14:10,084 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/../../sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound5.c [2023-11-12 00:14:13,383 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-12 00:14:13,564 INFO L384 CDTParser]: Found 1 translation units. [2023-11-12 00:14:13,564 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound5.c [2023-11-12 00:14:13,572 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/data/1bac60291/3f0eda4069f747b2a0a520ba4bbd4dcd/FLAG96dd130cb [2023-11-12 00:14:13,587 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/data/1bac60291/3f0eda4069f747b2a0a520ba4bbd4dcd [2023-11-12 00:14:13,590 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-12 00:14:13,591 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-12 00:14:13,593 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-12 00:14:13,593 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-12 00:14:13,598 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-12 00:14:13,599 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 12:14:13" (1/1) ... [2023-11-12 00:14:13,600 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7ef13a29 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:14:13, skipping insertion in model container [2023-11-12 00:14:13,601 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 12:14:13" (1/1) ... [2023-11-12 00:14:13,626 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-12 00:14:13,799 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_9f6b4b80-2f46-41f8-9641-55e25691172f/sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound5.c[526,539] [2023-11-12 00:14:13,825 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 00:14:13,841 INFO L202 MainTranslator]: Completed pre-run [2023-11-12 00:14:13,856 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_9f6b4b80-2f46-41f8-9641-55e25691172f/sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound5.c[526,539] [2023-11-12 00:14:13,862 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 00:14:13,878 INFO L206 MainTranslator]: Completed translation [2023-11-12 00:14:13,878 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:14:13 WrapperNode [2023-11-12 00:14:13,879 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-12 00:14:13,880 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-12 00:14:13,880 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-12 00:14:13,880 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-12 00:14:13,888 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:14:13" (1/1) ... [2023-11-12 00:14:13,896 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:14:13" (1/1) ... [2023-11-12 00:14:13,914 INFO L138 Inliner]: procedures = 14, calls = 23, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 64 [2023-11-12 00:14:13,914 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-12 00:14:13,915 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-12 00:14:13,915 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-12 00:14:13,915 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-12 00:14:13,924 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:14:13" (1/1) ... [2023-11-12 00:14:13,924 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:14:13" (1/1) ... [2023-11-12 00:14:13,926 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:14:13" (1/1) ... [2023-11-12 00:14:13,926 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:14:13" (1/1) ... [2023-11-12 00:14:13,930 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:14:13" (1/1) ... [2023-11-12 00:14:13,934 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:14:13" (1/1) ... [2023-11-12 00:14:13,935 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:14:13" (1/1) ... [2023-11-12 00:14:13,936 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:14:13" (1/1) ... [2023-11-12 00:14:13,940 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-12 00:14:13,941 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-12 00:14:13,941 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-12 00:14:13,941 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-12 00:14:13,942 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:14:13" (1/1) ... [2023-11-12 00:14:13,948 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 00:14:13,965 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:14:13,981 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-12 00:14:13,999 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-12 00:14:14,028 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-12 00:14:14,028 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-12 00:14:14,028 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-12 00:14:14,028 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-12 00:14:14,029 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-11-12 00:14:14,029 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-11-12 00:14:14,092 INFO L236 CfgBuilder]: Building ICFG [2023-11-12 00:14:14,094 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-12 00:14:14,255 INFO L277 CfgBuilder]: Performing block encoding [2023-11-12 00:14:14,330 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-12 00:14:14,330 INFO L302 CfgBuilder]: Removed 2 assume(true) statements. [2023-11-12 00:14:14,332 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 12:14:14 BoogieIcfgContainer [2023-11-12 00:14:14,333 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-12 00:14:14,335 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-12 00:14:14,335 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-12 00:14:14,338 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-12 00:14:14,339 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.11 12:14:13" (1/3) ... [2023-11-12 00:14:14,340 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5eec912 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 12:14:14, skipping insertion in model container [2023-11-12 00:14:14,340 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:14:13" (2/3) ... [2023-11-12 00:14:14,340 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5eec912 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 12:14:14, skipping insertion in model container [2023-11-12 00:14:14,340 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 12:14:14" (3/3) ... [2023-11-12 00:14:14,342 INFO L112 eAbstractionObserver]: Analyzing ICFG hard2_valuebound5.c [2023-11-12 00:14:14,362 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-12 00:14:14,362 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-12 00:14:14,408 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-12 00:14:14,416 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;@122fd6a2, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-12 00:14:14,417 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-12 00:14:14,423 INFO L276 IsEmpty]: Start isEmpty. Operand has 20 states, 10 states have (on average 1.6) internal successors, (16), 11 states have internal predecessors, (16), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2023-11-12 00:14:14,429 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2023-11-12 00:14:14,430 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:14:14,430 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2023-11-12 00:14:14,431 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:14:14,436 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:14:14,437 INFO L85 PathProgramCache]: Analyzing trace with hash -697525204, now seen corresponding path program 1 times [2023-11-12 00:14:14,447 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:14:14,448 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [28038121] [2023-11-12 00:14:14,448 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:14:14,449 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:14:14,566 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:14:14,764 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-12 00:14:14,764 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:14:14,765 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [28038121] [2023-11-12 00:14:14,766 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [28038121] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:14:14,766 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:14:14,766 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-11-12 00:14:14,768 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2065473073] [2023-11-12 00:14:14,769 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:14:14,774 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:14:14,774 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:14:14,826 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:14:14,829 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-12 00:14:14,833 INFO L87 Difference]: Start difference. First operand has 20 states, 10 states have (on average 1.6) internal successors, (16), 11 states have internal predecessors, (16), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 5 states, 5 states have (on average 1.0) internal successors, (5), 3 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 00:14:14,937 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:14:14,938 INFO L93 Difference]: Finished difference Result 50 states and 87 transitions. [2023-11-12 00:14:14,940 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-12 00:14:14,941 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.0) internal successors, (5), 3 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 6 [2023-11-12 00:14:14,941 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:14:14,963 INFO L225 Difference]: With dead ends: 50 [2023-11-12 00:14:14,963 INFO L226 Difference]: Without dead ends: 28 [2023-11-12 00:14:14,973 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-11-12 00:14:14,977 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 10 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 71 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:14:14,979 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 71 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 00:14:15,012 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2023-11-12 00:14:15,033 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 22. [2023-11-12 00:14:15,035 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-11-12 00:14:15,036 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 28 transitions. [2023-11-12 00:14:15,038 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 28 transitions. Word has length 6 [2023-11-12 00:14:15,038 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:14:15,038 INFO L495 AbstractCegarLoop]: Abstraction has 22 states and 28 transitions. [2023-11-12 00:14:15,039 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.0) internal successors, (5), 3 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 00:14:15,039 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 28 transitions. [2023-11-12 00:14:15,040 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2023-11-12 00:14:15,040 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:14:15,041 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:14:15,041 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-12 00:14:15,041 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:14:15,042 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:14:15,042 INFO L85 PathProgramCache]: Analyzing trace with hash -515229903, now seen corresponding path program 1 times [2023-11-12 00:14:15,043 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:14:15,043 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [144539503] [2023-11-12 00:14:15,043 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:14:15,044 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:14:15,062 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:14:15,221 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-12 00:14:15,222 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:14:15,222 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [144539503] [2023-11-12 00:14:15,222 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [144539503] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:14:15,223 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:14:15,223 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-12 00:14:15,223 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1726922488] [2023-11-12 00:14:15,223 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:14:15,225 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:14:15,225 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:14:15,226 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:14:15,227 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-12 00:14:15,227 INFO L87 Difference]: Start difference. First operand 22 states and 28 transitions. Second operand has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 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-12 00:14:15,290 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:14:15,291 INFO L93 Difference]: Finished difference Result 34 states and 43 transitions. [2023-11-12 00:14:15,291 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-12 00:14:15,292 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 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 11 [2023-11-12 00:14:15,292 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:14:15,293 INFO L225 Difference]: With dead ends: 34 [2023-11-12 00:14:15,293 INFO L226 Difference]: Without dead ends: 32 [2023-11-12 00:14:15,294 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-11-12 00:14:15,296 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 8 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 67 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:14:15,297 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 67 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 00:14:15,298 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2023-11-12 00:14:15,305 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 26. [2023-11-12 00:14:15,305 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-11-12 00:14:15,306 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 31 transitions. [2023-11-12 00:14:15,307 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 31 transitions. Word has length 11 [2023-11-12 00:14:15,307 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:14:15,307 INFO L495 AbstractCegarLoop]: Abstraction has 26 states and 31 transitions. [2023-11-12 00:14:15,308 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 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-12 00:14:15,308 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 31 transitions. [2023-11-12 00:14:15,309 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2023-11-12 00:14:15,309 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:14:15,309 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:14:15,310 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-12 00:14:15,310 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:14:15,311 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:14:15,311 INFO L85 PathProgramCache]: Analyzing trace with hash -1604661492, now seen corresponding path program 1 times [2023-11-12 00:14:15,311 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:14:15,312 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1037356501] [2023-11-12 00:14:15,312 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:14:15,312 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:14:15,329 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:14:15,330 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [807947796] [2023-11-12 00:14:15,330 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:14:15,330 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:14:15,331 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:14:15,334 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:14:15,356 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-12 00:14:15,444 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:14:15,448 INFO L262 TraceCheckSpWp]: Trace formula consists of 78 conjuncts, 19 conjunts are in the unsatisfiable core [2023-11-12 00:14:15,454 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:14:15,709 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-11-12 00:14:15,710 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:14:15,921 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-11-12 00:14:15,921 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:14:15,921 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1037356501] [2023-11-12 00:14:15,922 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:14:15,922 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [807947796] [2023-11-12 00:14:15,928 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [807947796] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:14:15,929 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [634058897] [2023-11-12 00:14:15,956 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2023-11-12 00:14:15,957 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:14:15,960 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:14:15,966 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:14:15,966 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:14:16,633 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 62 for LOIs [2023-11-12 00:14:16,686 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:14:17,082 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [634058897] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:14:17,084 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:14:17,084 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [8, 7] total 15 [2023-11-12 00:14:17,085 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1292321712] [2023-11-12 00:14:17,091 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:14:17,092 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:14:17,093 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:14:17,094 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:14:17,095 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=158, Unknown=0, NotChecked=0, Total=210 [2023-11-12 00:14:17,095 INFO L87 Difference]: Start difference. First operand 26 states and 31 transitions. Second operand has 5 states, 5 states have (on average 1.4) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (3), 1 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-12 00:14:17,282 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:14:17,282 INFO L93 Difference]: Finished difference Result 61 states and 75 transitions. [2023-11-12 00:14:17,283 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-12 00:14:17,283 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (3), 1 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 16 [2023-11-12 00:14:17,283 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:14:17,285 INFO L225 Difference]: With dead ends: 61 [2023-11-12 00:14:17,286 INFO L226 Difference]: Without dead ends: 43 [2023-11-12 00:14:17,288 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 31 SyntacticMatches, 2 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 61 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=52, Invalid=158, Unknown=0, NotChecked=0, Total=210 [2023-11-12 00:14:17,291 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 3 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 52 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 29 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 52 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 00:14:17,292 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 29 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 52 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 00:14:17,294 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2023-11-12 00:14:17,318 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2023-11-12 00:14:17,319 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 26 states have (on average 1.1153846153846154) internal successors, (29), 27 states have internal predecessors, (29), 10 states have call successors, (10), 6 states have call predecessors, (10), 6 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-11-12 00:14:17,325 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 48 transitions. [2023-11-12 00:14:17,325 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 48 transitions. Word has length 16 [2023-11-12 00:14:17,326 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:14:17,326 INFO L495 AbstractCegarLoop]: Abstraction has 43 states and 48 transitions. [2023-11-12 00:14:17,326 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (3), 1 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-12 00:14:17,326 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 48 transitions. [2023-11-12 00:14:17,328 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2023-11-12 00:14:17,328 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:14:17,329 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2023-11-12 00:14:17,339 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2023-11-12 00:14:17,535 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:14:17,536 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:14:17,536 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:14:17,537 INFO L85 PathProgramCache]: Analyzing trace with hash 1042343919, now seen corresponding path program 1 times [2023-11-12 00:14:17,537 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:14:17,538 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [801914662] [2023-11-12 00:14:17,539 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:14:17,539 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:14:17,562 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:14:17,571 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [886086283] [2023-11-12 00:14:17,574 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:14:17,574 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:14:17,575 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:14:17,576 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:14:17,603 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-12 00:14:17,645 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:14:17,646 INFO L262 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 23 conjunts are in the unsatisfiable core [2023-11-12 00:14:17,656 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:14:17,829 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 12 proven. 14 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2023-11-12 00:14:17,829 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:14:17,996 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 15 proven. 10 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2023-11-12 00:14:18,000 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:14:18,000 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [801914662] [2023-11-12 00:14:18,001 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:14:18,001 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [886086283] [2023-11-12 00:14:18,001 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [886086283] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:14:18,001 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1040412150] [2023-11-12 00:14:18,004 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2023-11-12 00:14:18,004 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:14:18,005 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:14:18,005 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:14:18,005 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:14:19,569 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 00:14:19,575 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:14:20,123 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '698#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:14:20,123 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:14:20,123 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:14:20,123 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7] total 13 [2023-11-12 00:14:20,123 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1909872780] [2023-11-12 00:14:20,124 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:14:20,124 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-11-12 00:14:20,124 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:14:20,125 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-11-12 00:14:20,126 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=79, Invalid=341, Unknown=0, NotChecked=0, Total=420 [2023-11-12 00:14:20,126 INFO L87 Difference]: Start difference. First operand 43 states and 48 transitions. Second operand has 13 states, 13 states have (on average 1.6153846153846154) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) [2023-11-12 00:14:20,381 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:14:20,381 INFO L93 Difference]: Finished difference Result 77 states and 98 transitions. [2023-11-12 00:14:20,382 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-12 00:14:20,382 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 1.6153846153846154) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) Word has length 33 [2023-11-12 00:14:20,382 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:14:20,385 INFO L225 Difference]: With dead ends: 77 [2023-11-12 00:14:20,385 INFO L226 Difference]: Without dead ends: 64 [2023-11-12 00:14:20,386 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 103 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=95, Invalid=411, Unknown=0, NotChecked=0, Total=506 [2023-11-12 00:14:20,387 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 25 mSDsluCounter, 54 mSDsCounter, 0 mSdLazyCounter, 155 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 74 SdHoareTripleChecker+Invalid, 182 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 155 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-12 00:14:20,387 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 74 Invalid, 182 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 155 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-12 00:14:20,388 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2023-11-12 00:14:20,403 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 64. [2023-11-12 00:14:20,403 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 36 states have (on average 1.1111111111111112) internal successors, (40), 39 states have internal predecessors, (40), 20 states have call successors, (20), 7 states have call predecessors, (20), 7 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) [2023-11-12 00:14:20,405 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 78 transitions. [2023-11-12 00:14:20,405 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 78 transitions. Word has length 33 [2023-11-12 00:14:20,406 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:14:20,406 INFO L495 AbstractCegarLoop]: Abstraction has 64 states and 78 transitions. [2023-11-12 00:14:20,406 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 1.6153846153846154) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) [2023-11-12 00:14:20,406 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 78 transitions. [2023-11-12 00:14:20,407 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2023-11-12 00:14:20,408 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:14:20,408 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:14:20,419 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-12 00:14:20,613 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:14:20,614 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:14:20,615 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:14:20,615 INFO L85 PathProgramCache]: Analyzing trace with hash -1798480357, now seen corresponding path program 1 times [2023-11-12 00:14:20,615 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:14:20,615 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2001673257] [2023-11-12 00:14:20,615 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:14:20,616 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:14:20,640 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:14:20,644 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1817823755] [2023-11-12 00:14:20,644 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:14:20,645 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:14:20,645 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:14:20,646 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:14:20,659 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-12 00:14:20,713 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:14:20,714 INFO L262 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 17 conjunts are in the unsatisfiable core [2023-11-12 00:14:20,721 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:14:20,825 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 14 proven. 13 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2023-11-12 00:14:20,825 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:14:20,940 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 17 proven. 13 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2023-11-12 00:14:20,940 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:14:20,941 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2001673257] [2023-11-12 00:14:20,941 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:14:20,941 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1817823755] [2023-11-12 00:14:20,941 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1817823755] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:14:20,941 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [493971816] [2023-11-12 00:14:20,944 INFO L159 IcfgInterpreter]: Started Sifa with 14 locations of interest [2023-11-12 00:14:20,944 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:14:20,945 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:14:20,945 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:14:20,945 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:14:22,406 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 00:14:22,412 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:14:22,953 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1171#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:14:22,953 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:14:22,953 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:14:22,953 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 11 [2023-11-12 00:14:22,953 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [666091579] [2023-11-12 00:14:22,953 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:14:22,954 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-11-12 00:14:22,954 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:14:22,955 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-11-12 00:14:22,955 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=295, Unknown=0, NotChecked=0, Total=380 [2023-11-12 00:14:22,955 INFO L87 Difference]: Start difference. First operand 64 states and 78 transitions. Second operand has 11 states, 11 states have (on average 2.1818181818181817) internal successors, (24), 10 states have internal predecessors, (24), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2023-11-12 00:14:23,093 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:14:23,095 INFO L93 Difference]: Finished difference Result 73 states and 88 transitions. [2023-11-12 00:14:23,095 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-11-12 00:14:23,096 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.1818181818181817) internal successors, (24), 10 states have internal predecessors, (24), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 40 [2023-11-12 00:14:23,096 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:14:23,099 INFO L225 Difference]: With dead ends: 73 [2023-11-12 00:14:23,099 INFO L226 Difference]: Without dead ends: 71 [2023-11-12 00:14:23,100 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 100 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 117 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=101, Invalid=361, Unknown=0, NotChecked=0, Total=462 [2023-11-12 00:14:23,101 INFO L413 NwaCegarLoop]: 14 mSDtfsCounter, 18 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 71 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 70 SdHoareTripleChecker+Invalid, 85 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 71 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 00:14:23,101 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 70 Invalid, 85 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 71 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 00:14:23,102 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2023-11-12 00:14:23,122 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 70. [2023-11-12 00:14:23,125 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 70 states, 40 states have (on average 1.125) internal successors, (45), 43 states have internal predecessors, (45), 21 states have call successors, (21), 8 states have call predecessors, (21), 8 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2023-11-12 00:14:23,128 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 85 transitions. [2023-11-12 00:14:23,128 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 85 transitions. Word has length 40 [2023-11-12 00:14:23,129 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:14:23,129 INFO L495 AbstractCegarLoop]: Abstraction has 70 states and 85 transitions. [2023-11-12 00:14:23,131 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.1818181818181817) internal successors, (24), 10 states have internal predecessors, (24), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2023-11-12 00:14:23,131 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 85 transitions. [2023-11-12 00:14:23,135 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2023-11-12 00:14:23,135 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:14:23,136 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:14:23,145 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2023-11-12 00:14:23,340 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:14:23,341 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:14:23,341 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:14:23,341 INFO L85 PathProgramCache]: Analyzing trace with hash -1731990838, now seen corresponding path program 1 times [2023-11-12 00:14:23,341 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:14:23,342 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [196054930] [2023-11-12 00:14:23,342 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:14:23,342 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:14:23,351 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:14:23,351 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1518408523] [2023-11-12 00:14:23,351 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:14:23,351 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:14:23,352 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:14:23,353 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:14:23,360 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-12 00:14:23,431 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:14:23,432 INFO L262 TraceCheckSpWp]: Trace formula consists of 147 conjuncts, 31 conjunts are in the unsatisfiable core [2023-11-12 00:14:23,435 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:14:23,698 INFO L134 CoverageAnalysis]: Checked inductivity of 135 backedges. 18 proven. 26 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-11-12 00:14:23,698 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:14:26,348 INFO L134 CoverageAnalysis]: Checked inductivity of 135 backedges. 18 proven. 26 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-11-12 00:14:26,348 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:14:26,348 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [196054930] [2023-11-12 00:14:26,348 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:14:26,348 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1518408523] [2023-11-12 00:14:26,348 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1518408523] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:14:26,349 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [314407397] [2023-11-12 00:14:26,351 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-11-12 00:14:26,351 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:14:26,351 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:14:26,352 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:14:26,352 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:14:27,967 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-11-12 00:14:27,974 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:14:28,581 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1721#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:14:28,581 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:14:28,581 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:14:28,581 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2023-11-12 00:14:28,582 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [442986293] [2023-11-12 00:14:28,582 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:14:28,582 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-12 00:14:28,582 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:14:28,583 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-12 00:14:28,583 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=87, Invalid=419, Unknown=0, NotChecked=0, Total=506 [2023-11-12 00:14:28,584 INFO L87 Difference]: Start difference. First operand 70 states and 85 transitions. Second operand has 15 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 13 states have internal predecessors, (29), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2023-11-12 00:14:29,734 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:14:29,734 INFO L93 Difference]: Finished difference Result 96 states and 108 transitions. [2023-11-12 00:14:29,735 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-11-12 00:14:29,735 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 13 states have internal predecessors, (29), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) Word has length 52 [2023-11-12 00:14:29,736 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:14:29,737 INFO L225 Difference]: With dead ends: 96 [2023-11-12 00:14:29,737 INFO L226 Difference]: Without dead ends: 94 [2023-11-12 00:14:29,738 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 159 GetRequests, 132 SyntacticMatches, 2 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 150 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=125, Invalid=577, Unknown=0, NotChecked=0, Total=702 [2023-11-12 00:14:29,739 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 29 mSDsluCounter, 165 mSDsCounter, 0 mSdLazyCounter, 199 mSolverCounterSat, 45 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 184 SdHoareTripleChecker+Invalid, 244 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 45 IncrementalHoareTripleChecker+Valid, 199 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2023-11-12 00:14:29,739 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 184 Invalid, 244 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [45 Valid, 199 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2023-11-12 00:14:29,740 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 94 states. [2023-11-12 00:14:29,771 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 94 to 92. [2023-11-12 00:14:29,771 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 56 states have (on average 1.0892857142857142) internal successors, (61), 60 states have internal predecessors, (61), 22 states have call successors, (22), 13 states have call predecessors, (22), 13 states have return successors, (20), 18 states have call predecessors, (20), 20 states have call successors, (20) [2023-11-12 00:14:29,773 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 103 transitions. [2023-11-12 00:14:29,773 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 103 transitions. Word has length 52 [2023-11-12 00:14:29,773 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:14:29,774 INFO L495 AbstractCegarLoop]: Abstraction has 92 states and 103 transitions. [2023-11-12 00:14:29,774 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 13 states have internal predecessors, (29), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2023-11-12 00:14:29,774 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 103 transitions. [2023-11-12 00:14:29,775 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2023-11-12 00:14:29,776 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:14:29,776 INFO L195 NwaCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:14:29,782 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2023-11-12 00:14:29,981 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2023-11-12 00:14:29,981 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:14:29,982 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:14:29,982 INFO L85 PathProgramCache]: Analyzing trace with hash -1143375622, now seen corresponding path program 1 times [2023-11-12 00:14:29,982 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:14:29,982 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1574896596] [2023-11-12 00:14:29,983 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:14:29,983 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:14:29,993 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:14:29,994 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [952509326] [2023-11-12 00:14:29,994 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:14:29,994 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:14:29,994 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:14:29,996 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:14:30,015 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-12 00:14:30,061 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:14:30,063 INFO L262 TraceCheckSpWp]: Trace formula consists of 167 conjuncts, 33 conjunts are in the unsatisfiable core [2023-11-12 00:14:30,067 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:14:30,393 INFO L134 CoverageAnalysis]: Checked inductivity of 209 backedges. 22 proven. 34 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2023-11-12 00:14:30,393 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:14:31,208 INFO L134 CoverageAnalysis]: Checked inductivity of 209 backedges. 22 proven. 34 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2023-11-12 00:14:31,208 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:14:31,209 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1574896596] [2023-11-12 00:14:31,210 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:14:31,210 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [952509326] [2023-11-12 00:14:31,210 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [952509326] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:14:31,210 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [251777763] [2023-11-12 00:14:31,215 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-12 00:14:31,215 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:14:31,216 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:14:31,216 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:14:31,216 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:14:32,727 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-11-12 00:14:32,731 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:14:33,317 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2403#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:14:33,317 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:14:33,317 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:14:33,317 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2023-11-12 00:14:33,317 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [972937987] [2023-11-12 00:14:33,318 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:14:33,318 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-11-12 00:14:33,318 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:14:33,319 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-11-12 00:14:33,320 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=118, Invalid=532, Unknown=0, NotChecked=0, Total=650 [2023-11-12 00:14:33,320 INFO L87 Difference]: Start difference. First operand 92 states and 103 transitions. Second operand has 17 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2023-11-12 00:14:33,974 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:14:33,974 INFO L93 Difference]: Finished difference Result 114 states and 133 transitions. [2023-11-12 00:14:33,975 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-11-12 00:14:33,975 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) Word has length 63 [2023-11-12 00:14:33,976 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:14:33,977 INFO L225 Difference]: With dead ends: 114 [2023-11-12 00:14:33,977 INFO L226 Difference]: Without dead ends: 99 [2023-11-12 00:14:33,978 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 191 GetRequests, 161 SyntacticMatches, 3 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 221 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=153, Invalid=659, Unknown=0, NotChecked=0, Total=812 [2023-11-12 00:14:33,979 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 26 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 183 mSolverCounterSat, 44 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 227 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 183 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-12 00:14:33,979 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 124 Invalid, 227 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 183 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-12 00:14:33,980 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2023-11-12 00:14:34,011 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 85. [2023-11-12 00:14:34,011 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 85 states, 53 states have (on average 1.0943396226415094) internal successors, (58), 55 states have internal predecessors, (58), 18 states have call successors, (18), 13 states have call predecessors, (18), 13 states have return successors, (17), 16 states have call predecessors, (17), 17 states have call successors, (17) [2023-11-12 00:14:34,012 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 85 states to 85 states and 93 transitions. [2023-11-12 00:14:34,012 INFO L78 Accepts]: Start accepts. Automaton has 85 states and 93 transitions. Word has length 63 [2023-11-12 00:14:34,013 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:14:34,013 INFO L495 AbstractCegarLoop]: Abstraction has 85 states and 93 transitions. [2023-11-12 00:14:34,013 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2023-11-12 00:14:34,013 INFO L276 IsEmpty]: Start isEmpty. Operand 85 states and 93 transitions. [2023-11-12 00:14:34,015 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2023-11-12 00:14:34,015 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:14:34,015 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:14:34,023 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-12 00:14:34,221 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2023-11-12 00:14:34,221 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:14:34,221 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:14:34,222 INFO L85 PathProgramCache]: Analyzing trace with hash 2113244439, now seen corresponding path program 1 times [2023-11-12 00:14:34,222 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:14:34,222 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [470485462] [2023-11-12 00:14:34,222 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:14:34,222 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:14:34,231 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:14:34,231 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [286379496] [2023-11-12 00:14:34,231 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:14:34,232 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:14:34,232 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:14:34,238 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:14:34,240 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-12 00:14:34,293 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:14:34,294 INFO L262 TraceCheckSpWp]: Trace formula consists of 184 conjuncts, 4 conjunts are in the unsatisfiable core [2023-11-12 00:14:34,296 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:14:34,347 INFO L134 CoverageAnalysis]: Checked inductivity of 303 backedges. 81 proven. 0 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2023-11-12 00:14:34,349 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 00:14:34,350 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:14:34,350 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [470485462] [2023-11-12 00:14:34,350 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:14:34,350 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [286379496] [2023-11-12 00:14:34,350 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [286379496] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:14:34,351 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:14:34,351 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-12 00:14:34,351 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1105696106] [2023-11-12 00:14:34,351 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:14:34,352 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:14:34,353 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:14:34,353 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:14:34,353 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2023-11-12 00:14:34,354 INFO L87 Difference]: Start difference. First operand 85 states and 93 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-11-12 00:14:34,423 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:14:34,423 INFO L93 Difference]: Finished difference Result 92 states and 99 transitions. [2023-11-12 00:14:34,423 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-12 00:14:34,424 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 73 [2023-11-12 00:14:34,427 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:14:34,431 INFO L225 Difference]: With dead ends: 92 [2023-11-12 00:14:34,431 INFO L226 Difference]: Without dead ends: 80 [2023-11-12 00:14:34,432 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2023-11-12 00:14:34,434 INFO L413 NwaCegarLoop]: 35 mSDtfsCounter, 3 mSDsluCounter, 40 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 75 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:14:34,434 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 75 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 00:14:34,435 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2023-11-12 00:14:34,460 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 80. [2023-11-12 00:14:34,460 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 80 states, 50 states have (on average 1.06) internal successors, (53), 51 states have internal predecessors, (53), 17 states have call successors, (17), 12 states have call predecessors, (17), 12 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2023-11-12 00:14:34,462 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 86 transitions. [2023-11-12 00:14:34,463 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 86 transitions. Word has length 73 [2023-11-12 00:14:34,463 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:14:34,464 INFO L495 AbstractCegarLoop]: Abstraction has 80 states and 86 transitions. [2023-11-12 00:14:34,464 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-11-12 00:14:34,464 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 86 transitions. [2023-11-12 00:14:34,468 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2023-11-12 00:14:34,469 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:14:34,469 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2023-11-12 00:14:34,475 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-12 00:14:34,675 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2023-11-12 00:14:34,675 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:14:34,676 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:14:34,676 INFO L85 PathProgramCache]: Analyzing trace with hash 1241228560, now seen corresponding path program 2 times [2023-11-12 00:14:34,676 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:14:34,676 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [479307373] [2023-11-12 00:14:34,676 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:14:34,676 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:14:34,685 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:14:34,685 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [654500225] [2023-11-12 00:14:34,685 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-12 00:14:34,685 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:14:34,685 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:14:34,690 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:14:34,707 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-12 00:14:34,756 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-11-12 00:14:34,756 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 00:14:34,758 INFO L262 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 31 conjunts are in the unsatisfiable core [2023-11-12 00:14:34,761 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:14:35,006 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 41 proven. 34 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-11-12 00:14:35,006 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:14:36,949 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 41 proven. 29 refuted. 0 times theorem prover too weak. 236 trivial. 0 not checked. [2023-11-12 00:14:36,949 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:14:36,949 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [479307373] [2023-11-12 00:14:36,949 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:14:36,949 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [654500225] [2023-11-12 00:14:36,950 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [654500225] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:14:36,950 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2032545980] [2023-11-12 00:14:36,952 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-11-12 00:14:36,952 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:14:36,953 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:14:36,953 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:14:36,953 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:14:38,253 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-11-12 00:14:38,256 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:14:38,870 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3631#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:14:38,870 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:14:38,870 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:14:38,870 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 17 [2023-11-12 00:14:38,870 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2121561536] [2023-11-12 00:14:38,871 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:14:38,871 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-11-12 00:14:38,871 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:14:38,872 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-11-12 00:14:38,872 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=107, Invalid=493, Unknown=0, NotChecked=0, Total=600 [2023-11-12 00:14:38,872 INFO L87 Difference]: Start difference. First operand 80 states and 86 transitions. Second operand has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 16 states have internal predecessors, (32), 9 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) [2023-11-12 00:14:43,680 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-12 00:14:46,158 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.96s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-12 00:14:46,178 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:14:46,178 INFO L93 Difference]: Finished difference Result 112 states and 130 transitions. [2023-11-12 00:14:46,179 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-11-12 00:14:46,179 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 16 states have internal predecessors, (32), 9 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) Word has length 74 [2023-11-12 00:14:46,180 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:14:46,181 INFO L225 Difference]: With dead ends: 112 [2023-11-12 00:14:46,181 INFO L226 Difference]: Without dead ends: 110 [2023-11-12 00:14:46,182 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 223 GetRequests, 195 SyntacticMatches, 3 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 179 ImplicationChecksByTransitivity, 3.7s TimeCoverageRelationStatistics Valid=130, Invalid=572, Unknown=0, NotChecked=0, Total=702 [2023-11-12 00:14:46,183 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 24 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 213 mSolverCounterSat, 37 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 125 SdHoareTripleChecker+Invalid, 251 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 213 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.7s IncrementalHoareTripleChecker+Time [2023-11-12 00:14:46,183 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [32 Valid, 125 Invalid, 251 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 213 Invalid, 1 Unknown, 0 Unchecked, 4.7s Time] [2023-11-12 00:14:46,184 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2023-11-12 00:14:46,223 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 108. [2023-11-12 00:14:46,224 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 108 states, 65 states have (on average 1.0769230769230769) internal successors, (70), 67 states have internal predecessors, (70), 28 states have call successors, (28), 14 states have call predecessors, (28), 14 states have return successors, (27), 26 states have call predecessors, (27), 27 states have call successors, (27) [2023-11-12 00:14:46,225 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 108 states to 108 states and 125 transitions. [2023-11-12 00:14:46,226 INFO L78 Accepts]: Start accepts. Automaton has 108 states and 125 transitions. Word has length 74 [2023-11-12 00:14:46,226 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:14:46,226 INFO L495 AbstractCegarLoop]: Abstraction has 108 states and 125 transitions. [2023-11-12 00:14:46,227 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 16 states have internal predecessors, (32), 9 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) [2023-11-12 00:14:46,227 INFO L276 IsEmpty]: Start isEmpty. Operand 108 states and 125 transitions. [2023-11-12 00:14:46,228 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2023-11-12 00:14:46,229 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:14:46,229 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1] [2023-11-12 00:14:46,235 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-12 00:14:46,431 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:14:46,431 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:14:46,432 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:14:46,432 INFO L85 PathProgramCache]: Analyzing trace with hash 1175687132, now seen corresponding path program 3 times [2023-11-12 00:14:46,432 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:14:46,432 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1630052613] [2023-11-12 00:14:46,432 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:14:46,432 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:14:46,441 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:14:46,442 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1560584493] [2023-11-12 00:14:46,442 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-12 00:14:46,442 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:14:46,442 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:14:46,443 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:14:46,459 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9f6b4b80-2f46-41f8-9641-55e25691172f/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-12 00:14:46,537 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-12 00:14:46,537 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 00:14:46,538 INFO L262 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 51 conjunts are in the unsatisfiable core [2023-11-12 00:14:46,542 INFO L285 TraceCheckSpWp]: Computing forward predicates...