./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound5.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_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/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_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound5.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/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_35e83afa-4b78-46b5-b7a3-648f38291968/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 5f094e7ea34d2025ab25ab51a4a0b06d8f845826c76dbd06e91f3d4a761fa19b --- Real Ultimate output --- This is Ultimate 0.2.3-dev-cf1a783 [2023-11-12 01:02:21,226 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-12 01:02:21,308 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-12 01:02:21,314 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-12 01:02:21,315 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-12 01:02:21,343 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-12 01:02:21,344 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-12 01:02:21,344 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-12 01:02:21,345 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-12 01:02:21,346 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-12 01:02:21,346 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-12 01:02:21,347 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-12 01:02:21,348 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-12 01:02:21,348 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-12 01:02:21,349 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-12 01:02:21,349 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-12 01:02:21,350 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-12 01:02:21,350 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-12 01:02:21,350 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-12 01:02:21,351 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-12 01:02:21,352 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-12 01:02:21,352 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-12 01:02:21,353 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-12 01:02:21,353 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-12 01:02:21,354 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-12 01:02:21,354 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-12 01:02:21,355 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-12 01:02:21,355 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-12 01:02:21,355 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-12 01:02:21,356 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-12 01:02:21,356 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-12 01:02:21,357 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-12 01:02:21,357 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-12 01:02:21,357 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-12 01:02:21,357 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-12 01:02:21,358 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-12 01:02:21,358 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 01:02:21,358 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-12 01:02:21,358 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-12 01:02:21,359 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-12 01:02:21,359 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-12 01:02:21,359 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-12 01:02:21,360 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-12 01:02:21,360 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-12 01:02:21,360 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-12 01:02:21,360 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_35e83afa-4b78-46b5-b7a3-648f38291968/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_35e83afa-4b78-46b5-b7a3-648f38291968/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 -> 5f094e7ea34d2025ab25ab51a4a0b06d8f845826c76dbd06e91f3d4a761fa19b [2023-11-12 01:02:21,609 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-12 01:02:21,646 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-12 01:02:21,649 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-12 01:02:21,651 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-12 01:02:21,651 INFO L274 PluginConnector]: CDTParser initialized [2023-11-12 01:02:21,654 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/../../sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound5.c [2023-11-12 01:02:25,080 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-12 01:02:25,304 INFO L384 CDTParser]: Found 1 translation units. [2023-11-12 01:02:25,305 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound5.c [2023-11-12 01:02:25,313 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/data/a2a998112/f7b96a28b5354b06a0fb6724e7f510de/FLAGd4728bd44 [2023-11-12 01:02:25,329 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/data/a2a998112/f7b96a28b5354b06a0fb6724e7f510de [2023-11-12 01:02:25,332 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-12 01:02:25,334 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-12 01:02:25,335 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-12 01:02:25,335 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-12 01:02:25,341 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-12 01:02:25,342 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 01:02:25" (1/1) ... [2023-11-12 01:02:25,343 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7f44c856 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:02:25, skipping insertion in model container [2023-11-12 01:02:25,343 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 01:02:25" (1/1) ... [2023-11-12 01:02:25,366 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-12 01:02:25,556 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_35e83afa-4b78-46b5-b7a3-648f38291968/sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound5.c[526,539] [2023-11-12 01:02:25,584 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 01:02:25,603 INFO L202 MainTranslator]: Completed pre-run [2023-11-12 01:02:25,621 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_35e83afa-4b78-46b5-b7a3-648f38291968/sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound5.c[526,539] [2023-11-12 01:02:25,641 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 01:02:25,657 INFO L206 MainTranslator]: Completed translation [2023-11-12 01:02:25,658 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:02:25 WrapperNode [2023-11-12 01:02:25,658 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-12 01:02:25,664 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-12 01:02:25,664 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-12 01:02:25,665 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-12 01:02:25,672 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:02:25" (1/1) ... [2023-11-12 01:02:25,681 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:02:25" (1/1) ... [2023-11-12 01:02:25,701 INFO L138 Inliner]: procedures = 14, calls = 22, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 69 [2023-11-12 01:02:25,701 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-12 01:02:25,702 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-12 01:02:25,702 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-12 01:02:25,702 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-12 01:02:25,712 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:02:25" (1/1) ... [2023-11-12 01:02:25,713 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:02:25" (1/1) ... [2023-11-12 01:02:25,727 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:02:25" (1/1) ... [2023-11-12 01:02:25,728 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:02:25" (1/1) ... [2023-11-12 01:02:25,732 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:02:25" (1/1) ... [2023-11-12 01:02:25,744 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:02:25" (1/1) ... [2023-11-12 01:02:25,748 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:02:25" (1/1) ... [2023-11-12 01:02:25,749 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:02:25" (1/1) ... [2023-11-12 01:02:25,751 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-12 01:02:25,758 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-12 01:02:25,759 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-12 01:02:25,759 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-12 01:02:25,760 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:02:25" (1/1) ... [2023-11-12 01:02:25,768 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 01:02:25,784 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:02:25,805 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-12 01:02:25,840 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-12 01:02:25,852 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-12 01:02:25,853 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-12 01:02:25,853 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-12 01:02:25,853 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-12 01:02:25,853 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-11-12 01:02:25,854 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-11-12 01:02:25,931 INFO L236 CfgBuilder]: Building ICFG [2023-11-12 01:02:25,934 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-12 01:02:26,112 INFO L277 CfgBuilder]: Performing block encoding [2023-11-12 01:02:26,149 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-12 01:02:26,149 INFO L302 CfgBuilder]: Removed 2 assume(true) statements. [2023-11-12 01:02:26,152 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 01:02:26 BoogieIcfgContainer [2023-11-12 01:02:26,152 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-12 01:02:26,155 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-12 01:02:26,155 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-12 01:02:26,159 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-12 01:02:26,159 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.11 01:02:25" (1/3) ... [2023-11-12 01:02:26,160 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7d21d07c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 01:02:26, skipping insertion in model container [2023-11-12 01:02:26,160 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 01:02:25" (2/3) ... [2023-11-12 01:02:26,161 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7d21d07c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 01:02:26, skipping insertion in model container [2023-11-12 01:02:26,161 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 01:02:26" (3/3) ... [2023-11-12 01:02:26,162 INFO L112 eAbstractionObserver]: Analyzing ICFG hard2_unwindbound5.c [2023-11-12 01:02:26,185 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-12 01:02:26,185 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-12 01:02:26,228 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-12 01:02:26,234 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;@6af8bf64, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-12 01:02:26,235 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-12 01:02:26,238 INFO L276 IsEmpty]: Start isEmpty. Operand has 22 states, 12 states have (on average 1.6666666666666667) internal successors, (20), 13 states have internal predecessors, (20), 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 01:02:26,245 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-11-12 01:02:26,245 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:02:26,246 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:02:26,246 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:02:26,252 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:02:26,252 INFO L85 PathProgramCache]: Analyzing trace with hash 1291730102, now seen corresponding path program 1 times [2023-11-12 01:02:26,263 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:02:26,263 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1637535696] [2023-11-12 01:02:26,264 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:02:26,264 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:02:26,366 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:02:26,392 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:02:26,392 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1637535696] [2023-11-12 01:02:26,393 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-11-12 01:02:26,393 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1784652949] [2023-11-12 01:02:26,393 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:02:26,394 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:02:26,394 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:02:26,400 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:02:26,424 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-12 01:02:26,520 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:02:26,523 INFO L262 TraceCheckSpWp]: Trace formula consists of 62 conjuncts, 1 conjunts are in the unsatisfiable core [2023-11-12 01:02:26,527 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:02:26,546 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-12 01:02:26,546 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 01:02:26,547 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1784652949] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 01:02:26,547 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 01:02:26,547 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-12 01:02:26,550 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1654608756] [2023-11-12 01:02:26,551 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 01:02:26,555 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-11-12 01:02:26,556 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:02:26,586 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-11-12 01:02:26,587 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-11-12 01:02:26,589 INFO L87 Difference]: Start difference. First operand has 22 states, 12 states have (on average 1.6666666666666667) internal successors, (20), 13 states have internal predecessors, (20), 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 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 01:02:26,623 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:02:26,623 INFO L93 Difference]: Finished difference Result 43 states and 74 transitions. [2023-11-12 01:02:26,625 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-11-12 01:02:26,626 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2023-11-12 01:02:26,626 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:02:26,633 INFO L225 Difference]: With dead ends: 43 [2023-11-12 01:02:26,634 INFO L226 Difference]: Without dead ends: 20 [2023-11-12 01:02:26,637 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-11-12 01:02:26,641 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 3 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 28 SdHoareTripleChecker+Invalid, 3 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 3 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 01:02:26,642 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 28 Invalid, 3 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 3 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 01:02:26,660 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2023-11-12 01:02:26,678 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2023-11-12 01:02:26,680 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 12 states have internal predecessors, (16), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-11-12 01:02:26,681 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 29 transitions. [2023-11-12 01:02:26,683 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 29 transitions. Word has length 7 [2023-11-12 01:02:26,683 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:02:26,683 INFO L495 AbstractCegarLoop]: Abstraction has 20 states and 29 transitions. [2023-11-12 01:02:26,683 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 01:02:26,684 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 29 transitions. [2023-11-12 01:02:26,685 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-11-12 01:02:26,685 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:02:26,685 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:02:26,692 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-12 01:02:26,892 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2023-11-12 01:02:26,894 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:02:26,895 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:02:26,896 INFO L85 PathProgramCache]: Analyzing trace with hash 829671692, now seen corresponding path program 1 times [2023-11-12 01:02:26,896 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:02:26,896 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1432498284] [2023-11-12 01:02:26,897 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:02:26,898 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:02:26,940 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:02:27,184 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-12 01:02:27,185 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:02:27,186 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1432498284] [2023-11-12 01:02:27,187 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1432498284] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 01:02:27,191 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 01:02:27,191 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-11-12 01:02:27,193 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1360250625] [2023-11-12 01:02:27,194 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 01:02:27,195 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 01:02:27,196 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:02:27,197 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 01:02:27,197 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-12 01:02:27,198 INFO L87 Difference]: Start difference. First operand 20 states and 29 transitions. Second operand has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 01:02:27,311 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:02:27,311 INFO L93 Difference]: Finished difference Result 33 states and 46 transitions. [2023-11-12 01:02:27,312 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-12 01:02:27,313 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2023-11-12 01:02:27,313 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:02:27,317 INFO L225 Difference]: With dead ends: 33 [2023-11-12 01:02:27,317 INFO L226 Difference]: Without dead ends: 31 [2023-11-12 01:02:27,318 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-11-12 01:02:27,321 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 13 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 01:02:27,322 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 81 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 01:02:27,325 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2023-11-12 01:02:27,338 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 24. [2023-11-12 01:02:27,338 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 14 states have (on average 1.3571428571428572) internal successors, (19), 15 states have internal predecessors, (19), 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 01:02:27,339 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 32 transitions. [2023-11-12 01:02:27,340 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 32 transitions. Word has length 7 [2023-11-12 01:02:27,340 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:02:27,340 INFO L495 AbstractCegarLoop]: Abstraction has 24 states and 32 transitions. [2023-11-12 01:02:27,340 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 01:02:27,341 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 32 transitions. [2023-11-12 01:02:27,341 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2023-11-12 01:02:27,341 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:02:27,342 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:02:27,342 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-12 01:02:27,342 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:02:27,343 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:02:27,343 INFO L85 PathProgramCache]: Analyzing trace with hash -166824855, now seen corresponding path program 1 times [2023-11-12 01:02:27,343 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:02:27,344 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1261053634] [2023-11-12 01:02:27,344 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:02:27,344 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:02:27,356 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:02:27,372 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:02:27,373 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1261053634] [2023-11-12 01:02:27,373 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-11-12 01:02:27,373 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [169453661] [2023-11-12 01:02:27,373 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:02:27,374 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:02:27,374 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:02:27,375 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:02:27,392 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-12 01:02:27,436 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:02:27,437 INFO L262 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 3 conjunts are in the unsatisfiable core [2023-11-12 01:02:27,439 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:02:27,477 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-12 01:02:27,477 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 01:02:27,478 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [169453661] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 01:02:27,478 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 01:02:27,478 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-12 01:02:27,479 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [9986360] [2023-11-12 01:02:27,479 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 01:02:27,479 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-12 01:02:27,480 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:02:27,480 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-12 01:02:27,480 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-12 01:02:27,481 INFO L87 Difference]: Start difference. First operand 24 states and 32 transitions. Second operand has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 01:02:27,519 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:02:27,520 INFO L93 Difference]: Finished difference Result 39 states and 52 transitions. [2023-11-12 01:02:27,521 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-12 01:02:27,521 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 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 9 [2023-11-12 01:02:27,522 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:02:27,523 INFO L225 Difference]: With dead ends: 39 [2023-11-12 01:02:27,523 INFO L226 Difference]: Without dead ends: 26 [2023-11-12 01:02:27,524 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-12 01:02:27,528 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 0 mSDsluCounter, 48 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 13 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 01:02:27,530 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 73 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 01:02:27,532 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2023-11-12 01:02:27,542 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2023-11-12 01:02:27,544 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 16 states have (on average 1.3125) internal successors, (21), 17 states have internal predecessors, (21), 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 01:02:27,546 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 34 transitions. [2023-11-12 01:02:27,546 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 34 transitions. Word has length 9 [2023-11-12 01:02:27,546 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:02:27,547 INFO L495 AbstractCegarLoop]: Abstraction has 26 states and 34 transitions. [2023-11-12 01:02:27,547 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 01:02:27,547 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 34 transitions. [2023-11-12 01:02:27,548 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2023-11-12 01:02:27,549 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:02:27,549 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:02:27,560 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-12 01:02:27,755 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:02:27,755 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:02:27,757 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:02:27,758 INFO L85 PathProgramCache]: Analyzing trace with hash -439138420, now seen corresponding path program 1 times [2023-11-12 01:02:27,758 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:02:27,758 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [592818011] [2023-11-12 01:02:27,758 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:02:27,759 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:02:27,784 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:02:27,940 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 01:02:27,941 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:02:27,941 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [592818011] [2023-11-12 01:02:27,941 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [592818011] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 01:02:27,941 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 01:02:27,942 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-12 01:02:27,942 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1704056017] [2023-11-12 01:02:27,942 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 01:02:27,943 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 01:02:27,943 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:02:27,944 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 01:02:27,944 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-12 01:02:27,945 INFO L87 Difference]: Start difference. First operand 26 states and 34 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-12 01:02:27,999 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:02:27,999 INFO L93 Difference]: Finished difference Result 39 states and 51 transitions. [2023-11-12 01:02:28,000 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-12 01:02:28,000 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2023-11-12 01:02:28,000 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:02:28,001 INFO L225 Difference]: With dead ends: 39 [2023-11-12 01:02:28,002 INFO L226 Difference]: Without dead ends: 37 [2023-11-12 01:02:28,002 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 01:02:28,003 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 11 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 81 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 01:02:28,004 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 81 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 01:02:28,005 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2023-11-12 01:02:28,011 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 30. [2023-11-12 01:02:28,012 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 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 01:02:28,049 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 37 transitions. [2023-11-12 01:02:28,049 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 37 transitions. Word has length 12 [2023-11-12 01:02:28,050 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:02:28,050 INFO L495 AbstractCegarLoop]: Abstraction has 30 states and 37 transitions. [2023-11-12 01:02:28,050 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-12 01:02:28,051 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 37 transitions. [2023-11-12 01:02:28,051 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2023-11-12 01:02:28,051 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:02:28,052 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:02:28,052 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2023-11-12 01:02:28,055 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:02:28,057 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:02:28,058 INFO L85 PathProgramCache]: Analyzing trace with hash -235147060, now seen corresponding path program 1 times [2023-11-12 01:02:28,059 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:02:28,060 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [85335354] [2023-11-12 01:02:28,060 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:02:28,060 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:02:28,071 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 01:02:28,072 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1292490615] [2023-11-12 01:02:28,072 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:02:28,072 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:02:28,072 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:02:28,073 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:02:28,096 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-12 01:02:28,135 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:02:28,136 INFO L262 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 19 conjunts are in the unsatisfiable core [2023-11-12 01:02:28,139 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:02:28,279 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-11-12 01:02:28,279 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 01:02:28,481 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-11-12 01:02:28,481 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:02:28,481 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [85335354] [2023-11-12 01:02:28,482 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 01:02:28,482 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1292490615] [2023-11-12 01:02:28,482 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1292490615] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 01:02:28,482 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [997492052] [2023-11-12 01:02:28,508 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2023-11-12 01:02:28,509 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 01:02:28,512 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 01:02:28,518 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 01:02:28,518 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 01:02:29,322 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 64 for LOIs [2023-11-12 01:02:29,377 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 01:02:30,176 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [997492052] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 01:02:30,176 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-11-12 01:02:30,176 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [8, 7] total 17 [2023-11-12 01:02:30,177 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1720560970] [2023-11-12 01:02:30,178 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 01:02:30,179 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-11-12 01:02:30,179 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:02:30,181 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-11-12 01:02:30,182 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2023-11-12 01:02:30,183 INFO L87 Difference]: Start difference. First operand 30 states and 37 transitions. Second operand has 7 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 5 states have internal predecessors, (8), 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 01:02:30,361 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:02:30,364 INFO L93 Difference]: Finished difference Result 49 states and 57 transitions. [2023-11-12 01:02:30,365 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-11-12 01:02:30,365 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 5 states have internal predecessors, (8), 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 17 [2023-11-12 01:02:30,365 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:02:30,367 INFO L225 Difference]: With dead ends: 49 [2023-11-12 01:02:30,368 INFO L226 Difference]: Without dead ends: 47 [2023-11-12 01:02:30,369 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 32 SyntacticMatches, 2 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 85 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2023-11-12 01:02:30,370 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 1 mSDsluCounter, 41 mSDsCounter, 0 mSdLazyCounter, 65 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 58 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 65 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 01:02:30,370 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 58 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 65 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 01:02:30,377 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2023-11-12 01:02:30,391 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 45. [2023-11-12 01:02:30,391 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 28 states have (on average 1.1785714285714286) internal successors, (33), 30 states have internal predecessors, (33), 10 states have call successors, (10), 6 states have call predecessors, (10), 6 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2023-11-12 01:02:30,392 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 52 transitions. [2023-11-12 01:02:30,392 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 52 transitions. Word has length 17 [2023-11-12 01:02:30,393 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:02:30,393 INFO L495 AbstractCegarLoop]: Abstraction has 45 states and 52 transitions. [2023-11-12 01:02:30,393 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 5 states have internal predecessors, (8), 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 01:02:30,393 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 52 transitions. [2023-11-12 01:02:30,394 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2023-11-12 01:02:30,394 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:02:30,394 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:02:30,405 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-12 01:02:30,600 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:02:30,600 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:02:30,601 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:02:30,601 INFO L85 PathProgramCache]: Analyzing trace with hash 2012527405, now seen corresponding path program 1 times [2023-11-12 01:02:30,601 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:02:30,601 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2083302035] [2023-11-12 01:02:30,601 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:02:30,601 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:02:30,628 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 01:02:30,631 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [207948632] [2023-11-12 01:02:30,631 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:02:30,632 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:02:30,632 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:02:30,633 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:02:30,656 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-12 01:02:30,696 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:02:30,697 INFO L262 TraceCheckSpWp]: Trace formula consists of 98 conjuncts, 17 conjunts are in the unsatisfiable core [2023-11-12 01:02:30,701 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:02:30,816 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-11-12 01:02:30,816 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 01:02:30,997 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-11-12 01:02:30,997 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:02:30,997 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2083302035] [2023-11-12 01:02:30,998 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 01:02:30,998 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [207948632] [2023-11-12 01:02:30,998 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [207948632] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 01:02:30,998 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2026535298] [2023-11-12 01:02:31,001 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-11-12 01:02:31,002 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 01:02:31,002 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 01:02:31,002 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 01:02:31,003 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 01:02:31,694 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2023-11-12 01:02:31,701 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 01:02:32,836 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [2026535298] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 01:02:32,836 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-11-12 01:02:32,836 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [7, 7] total 19 [2023-11-12 01:02:32,837 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1534457831] [2023-11-12 01:02:32,837 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 01:02:32,838 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-11-12 01:02:32,838 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:02:32,838 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-11-12 01:02:32,839 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=268, Unknown=0, NotChecked=0, Total=342 [2023-11-12 01:02:32,839 INFO L87 Difference]: Start difference. First operand 45 states and 52 transitions. Second operand has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 8 states have internal predecessors, (11), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-11-12 01:02:33,109 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:02:33,109 INFO L93 Difference]: Finished difference Result 70 states and 87 transitions. [2023-11-12 01:02:33,110 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-12 01:02:33,110 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 8 states have internal predecessors, (11), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 25 [2023-11-12 01:02:33,110 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:02:33,111 INFO L225 Difference]: With dead ends: 70 [2023-11-12 01:02:33,111 INFO L226 Difference]: Without dead ends: 46 [2023-11-12 01:02:33,112 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 53 SyntacticMatches, 3 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 110 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=74, Invalid=268, Unknown=0, NotChecked=0, Total=342 [2023-11-12 01:02:33,113 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 1 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 147 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 68 SdHoareTripleChecker+Invalid, 152 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 147 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-12 01:02:33,113 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 68 Invalid, 152 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 147 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-12 01:02:33,114 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2023-11-12 01:02:33,124 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 46. [2023-11-12 01:02:33,124 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 29 states have (on average 1.1724137931034482) internal successors, (34), 30 states have internal predecessors, (34), 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 01:02:33,129 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 53 transitions. [2023-11-12 01:02:33,130 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 53 transitions. Word has length 25 [2023-11-12 01:02:33,131 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:02:33,131 INFO L495 AbstractCegarLoop]: Abstraction has 46 states and 53 transitions. [2023-11-12 01:02:33,131 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 8 states have internal predecessors, (11), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-11-12 01:02:33,132 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 53 transitions. [2023-11-12 01:02:33,132 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2023-11-12 01:02:33,133 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:02:33,133 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:02:33,144 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2023-11-12 01:02:33,340 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:02:33,340 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:02:33,341 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:02:33,341 INFO L85 PathProgramCache]: Analyzing trace with hash 2127759890, now seen corresponding path program 1 times [2023-11-12 01:02:33,341 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:02:33,341 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1716171161] [2023-11-12 01:02:33,341 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:02:33,341 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:02:33,350 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 01:02:33,350 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [772545337] [2023-11-12 01:02:33,350 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:02:33,350 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:02:33,351 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:02:33,352 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:02:33,361 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-12 01:02:33,404 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:02:33,405 INFO L262 TraceCheckSpWp]: Trace formula consists of 107 conjuncts, 5 conjunts are in the unsatisfiable core [2023-11-12 01:02:33,407 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:02:33,458 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-11-12 01:02:33,458 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 01:02:33,510 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-11-12 01:02:33,510 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:02:33,510 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1716171161] [2023-11-12 01:02:33,510 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 01:02:33,510 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [772545337] [2023-11-12 01:02:33,511 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [772545337] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 01:02:33,512 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1403204821] [2023-11-12 01:02:33,515 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-11-12 01:02:33,516 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 01:02:33,516 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 01:02:33,516 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 01:02:33,516 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 01:02:35,570 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2023-11-12 01:02:35,583 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 01:02:36,722 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1198#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 01:02:36,723 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 01:02:36,723 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 01:02:36,723 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5] total 8 [2023-11-12 01:02:36,723 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2022431951] [2023-11-12 01:02:36,723 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 01:02:36,724 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-11-12 01:02:36,724 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:02:36,725 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-11-12 01:02:36,725 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=274, Unknown=0, NotChecked=0, Total=342 [2023-11-12 01:02:36,725 INFO L87 Difference]: Start difference. First operand 46 states and 53 transitions. Second operand has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-11-12 01:02:36,865 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:02:36,865 INFO L93 Difference]: Finished difference Result 109 states and 130 transitions. [2023-11-12 01:02:36,865 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-12 01:02:36,866 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 27 [2023-11-12 01:02:36,866 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:02:36,867 INFO L225 Difference]: With dead ends: 109 [2023-11-12 01:02:36,867 INFO L226 Difference]: Without dead ends: 96 [2023-11-12 01:02:36,868 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 62 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 107 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=88, Invalid=374, Unknown=0, NotChecked=0, Total=462 [2023-11-12 01:02:36,869 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 34 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 01:02:36,869 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 100 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 01:02:36,870 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2023-11-12 01:02:36,889 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 91. [2023-11-12 01:02:36,889 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 58 states have (on average 1.1896551724137931) internal successors, (69), 60 states have internal predecessors, (69), 20 states have call successors, (20), 12 states have call predecessors, (20), 12 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2023-11-12 01:02:36,891 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 107 transitions. [2023-11-12 01:02:36,891 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 107 transitions. Word has length 27 [2023-11-12 01:02:36,891 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:02:36,891 INFO L495 AbstractCegarLoop]: Abstraction has 91 states and 107 transitions. [2023-11-12 01:02:36,892 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-11-12 01:02:36,892 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 107 transitions. [2023-11-12 01:02:36,893 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2023-11-12 01:02:36,893 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:02:36,893 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2023-11-12 01:02:36,908 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-12 01:02:37,100 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:02:37,100 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:02:37,101 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:02:37,101 INFO L85 PathProgramCache]: Analyzing trace with hash 747162997, now seen corresponding path program 1 times [2023-11-12 01:02:37,101 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:02:37,101 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1075468614] [2023-11-12 01:02:37,101 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:02:37,102 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:02:37,110 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 01:02:37,110 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [824204018] [2023-11-12 01:02:37,111 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:02:37,111 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:02:37,111 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:02:37,115 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:02:37,136 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-12 01:02:37,180 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:02:37,181 INFO L262 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 23 conjunts are in the unsatisfiable core [2023-11-12 01:02:37,183 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:02:37,324 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 9 proven. 18 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2023-11-12 01:02:37,325 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 01:02:37,461 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 12 proven. 13 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-11-12 01:02:37,461 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:02:37,461 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1075468614] [2023-11-12 01:02:37,462 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 01:02:37,462 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [824204018] [2023-11-12 01:02:37,462 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [824204018] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 01:02:37,462 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [703422822] [2023-11-12 01:02:37,466 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2023-11-12 01:02:37,466 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 01:02:37,467 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 01:02:37,467 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 01:02:37,467 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 01:02:39,063 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2023-11-12 01:02:39,074 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 01:02:40,035 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1717#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 01:02:40,035 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 01:02:40,035 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 01:02:40,036 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7] total 13 [2023-11-12 01:02:40,036 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [338074812] [2023-11-12 01:02:40,036 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 01:02:40,037 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-11-12 01:02:40,037 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:02:40,038 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-11-12 01:02:40,038 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=83, Invalid=379, Unknown=0, NotChecked=0, Total=462 [2023-11-12 01:02:40,038 INFO L87 Difference]: Start difference. First operand 91 states and 107 transitions. Second operand has 13 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 5 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 5 states have call successors, (9) [2023-11-12 01:02:40,279 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:02:40,280 INFO L93 Difference]: Finished difference Result 131 states and 161 transitions. [2023-11-12 01:02:40,280 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-12 01:02:40,281 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 5 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 5 states have call successors, (9) Word has length 35 [2023-11-12 01:02:40,281 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:02:40,283 INFO L225 Difference]: With dead ends: 131 [2023-11-12 01:02:40,284 INFO L226 Difference]: Without dead ends: 111 [2023-11-12 01:02:40,285 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 83 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 119 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=99, Invalid=453, Unknown=0, NotChecked=0, Total=552 [2023-11-12 01:02:40,285 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 46 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 141 mSolverCounterSat, 32 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 134 SdHoareTripleChecker+Invalid, 173 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 141 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-12 01:02:40,286 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [59 Valid, 134 Invalid, 173 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 141 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-12 01:02:40,287 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2023-11-12 01:02:40,302 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 109. [2023-11-12 01:02:40,302 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 109 states, 69 states have (on average 1.1594202898550725) internal successors, (80), 73 states have internal predecessors, (80), 25 states have call successors, (25), 14 states have call predecessors, (25), 14 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) [2023-11-12 01:02:40,304 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 127 transitions. [2023-11-12 01:02:40,304 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 127 transitions. Word has length 35 [2023-11-12 01:02:40,304 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:02:40,305 INFO L495 AbstractCegarLoop]: Abstraction has 109 states and 127 transitions. [2023-11-12 01:02:40,305 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 5 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 5 states have call successors, (9) [2023-11-12 01:02:40,305 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 127 transitions. [2023-11-12 01:02:40,306 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2023-11-12 01:02:40,306 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:02:40,307 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:02:40,313 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-12 01:02:40,512 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2023-11-12 01:02:40,513 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:02:40,513 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:02:40,513 INFO L85 PathProgramCache]: Analyzing trace with hash 387112662, now seen corresponding path program 1 times [2023-11-12 01:02:40,513 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:02:40,513 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [914430055] [2023-11-12 01:02:40,514 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:02:40,514 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:02:40,528 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 01:02:40,528 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [506925219] [2023-11-12 01:02:40,528 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:02:40,528 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:02:40,529 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:02:40,530 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:02:40,560 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-12 01:02:40,592 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:02:40,593 INFO L262 TraceCheckSpWp]: Trace formula consists of 135 conjuncts, 17 conjunts are in the unsatisfiable core [2023-11-12 01:02:40,595 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:02:40,718 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 11 proven. 16 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2023-11-12 01:02:40,719 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 01:02:40,853 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 14 proven. 16 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2023-11-12 01:02:40,854 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:02:40,854 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [914430055] [2023-11-12 01:02:40,854 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 01:02:40,854 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [506925219] [2023-11-12 01:02:40,854 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [506925219] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 01:02:40,854 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1902566936] [2023-11-12 01:02:40,857 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-11-12 01:02:40,857 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 01:02:40,858 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 01:02:40,858 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 01:02:40,858 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 01:02:42,243 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-12 01:02:42,248 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 01:02:43,277 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2341#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 01:02:43,277 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 01:02:43,278 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 01:02:43,278 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 11 [2023-11-12 01:02:43,278 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1722656605] [2023-11-12 01:02:43,278 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 01:02:43,279 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-11-12 01:02:43,279 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:02:43,279 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-11-12 01:02:43,280 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=109, Invalid=397, Unknown=0, NotChecked=0, Total=506 [2023-11-12 01:02:43,280 INFO L87 Difference]: Start difference. First operand 109 states and 127 transitions. Second operand has 11 states, 11 states have (on average 2.6363636363636362) internal successors, (29), 10 states have internal predecessors, (29), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2023-11-12 01:02:43,434 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:02:43,434 INFO L93 Difference]: Finished difference Result 125 states and 145 transitions. [2023-11-12 01:02:43,435 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-12 01:02:43,435 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.6363636363636362) internal successors, (29), 10 states have internal predecessors, (29), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) Word has length 43 [2023-11-12 01:02:43,435 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:02:43,437 INFO L225 Difference]: With dead ends: 125 [2023-11-12 01:02:43,437 INFO L226 Difference]: Without dead ends: 121 [2023-11-12 01:02:43,438 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 106 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 162 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=125, Invalid=475, Unknown=0, NotChecked=0, Total=600 [2023-11-12 01:02:43,439 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 22 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 98 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 89 SdHoareTripleChecker+Invalid, 115 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 98 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 01:02:43,439 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 89 Invalid, 115 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 98 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 01:02:43,440 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2023-11-12 01:02:43,456 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 117. [2023-11-12 01:02:43,457 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 117 states, 75 states have (on average 1.1466666666666667) internal successors, (86), 78 states have internal predecessors, (86), 26 states have call successors, (26), 16 states have call predecessors, (26), 15 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2023-11-12 01:02:43,458 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 117 states to 117 states and 135 transitions. [2023-11-12 01:02:43,458 INFO L78 Accepts]: Start accepts. Automaton has 117 states and 135 transitions. Word has length 43 [2023-11-12 01:02:43,459 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:02:43,459 INFO L495 AbstractCegarLoop]: Abstraction has 117 states and 135 transitions. [2023-11-12 01:02:43,459 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.6363636363636362) internal successors, (29), 10 states have internal predecessors, (29), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2023-11-12 01:02:43,459 INFO L276 IsEmpty]: Start isEmpty. Operand 117 states and 135 transitions. [2023-11-12 01:02:43,461 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2023-11-12 01:02:43,461 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:02:43,461 INFO L195 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:02:43,472 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-12 01:02:43,668 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2023-11-12 01:02:43,669 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:02:43,669 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:02:43,669 INFO L85 PathProgramCache]: Analyzing trace with hash 1125945480, now seen corresponding path program 1 times [2023-11-12 01:02:43,669 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:02:43,669 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [934950705] [2023-11-12 01:02:43,669 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:02:43,669 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:02:43,676 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 01:02:43,676 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [235465499] [2023-11-12 01:02:43,676 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:02:43,677 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:02:43,677 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:02:43,678 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:02:43,682 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-12 01:02:43,735 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:02:43,737 INFO L262 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 7 conjunts are in the unsatisfiable core [2023-11-12 01:02:43,739 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:02:43,808 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 36 proven. 42 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2023-11-12 01:02:43,808 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 01:02:43,887 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2023-11-12 01:02:43,887 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:02:43,887 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [934950705] [2023-11-12 01:02:43,888 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 01:02:43,888 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [235465499] [2023-11-12 01:02:43,888 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [235465499] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 01:02:43,888 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1871410585] [2023-11-12 01:02:43,891 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-12 01:02:43,891 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 01:02:43,891 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 01:02:43,892 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 01:02:43,892 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 01:02:45,264 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 10 for LOIs [2023-11-12 01:02:45,273 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 01:02:46,348 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2996#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 01:02:46,348 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 01:02:46,348 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 01:02:46,348 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6] total 9 [2023-11-12 01:02:46,348 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1545227218] [2023-11-12 01:02:46,349 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 01:02:46,349 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-11-12 01:02:46,349 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:02:46,350 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-11-12 01:02:46,351 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=79, Invalid=341, Unknown=0, NotChecked=0, Total=420 [2023-11-12 01:02:46,351 INFO L87 Difference]: Start difference. First operand 117 states and 135 transitions. Second operand has 9 states, 9 states have (on average 3.5555555555555554) internal successors, (32), 9 states have internal predecessors, (32), 5 states have call successors, (15), 4 states have call predecessors, (15), 4 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2023-11-12 01:02:46,523 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:02:46,523 INFO L93 Difference]: Finished difference Result 173 states and 196 transitions. [2023-11-12 01:02:46,524 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-12 01:02:46,524 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.5555555555555554) internal successors, (32), 9 states have internal predecessors, (32), 5 states have call successors, (15), 4 states have call predecessors, (15), 4 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) Word has length 48 [2023-11-12 01:02:46,524 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:02:46,526 INFO L225 Difference]: With dead ends: 173 [2023-11-12 01:02:46,526 INFO L226 Difference]: Without dead ends: 151 [2023-11-12 01:02:46,527 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 144 GetRequests, 121 SyntacticMatches, 2 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 142 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=90, Invalid=416, Unknown=0, NotChecked=0, Total=506 [2023-11-12 01:02:46,527 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 33 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 74 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 110 SdHoareTripleChecker+Invalid, 76 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 74 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 01:02:46,528 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 110 Invalid, 76 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 74 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 01:02:46,529 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 151 states. [2023-11-12 01:02:46,550 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 151 to 148. [2023-11-12 01:02:46,550 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 148 states, 96 states have (on average 1.125) internal successors, (108), 100 states have internal predecessors, (108), 31 states have call successors, (31), 20 states have call predecessors, (31), 20 states have return successors, (28), 27 states have call predecessors, (28), 28 states have call successors, (28) [2023-11-12 01:02:46,552 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 167 transitions. [2023-11-12 01:02:46,552 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 167 transitions. Word has length 48 [2023-11-12 01:02:46,552 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:02:46,553 INFO L495 AbstractCegarLoop]: Abstraction has 148 states and 167 transitions. [2023-11-12 01:02:46,553 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.5555555555555554) internal successors, (32), 9 states have internal predecessors, (32), 5 states have call successors, (15), 4 states have call predecessors, (15), 4 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2023-11-12 01:02:46,553 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 167 transitions. [2023-11-12 01:02:46,554 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2023-11-12 01:02:46,555 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:02:46,555 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:02:46,564 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-11-12 01:02:46,760 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-11-12 01:02:46,760 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:02:46,760 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:02:46,760 INFO L85 PathProgramCache]: Analyzing trace with hash -1127123487, now seen corresponding path program 1 times [2023-11-12 01:02:46,761 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:02:46,761 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [863113417] [2023-11-12 01:02:46,761 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:02:46,761 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:02:46,768 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 01:02:46,768 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [304176311] [2023-11-12 01:02:46,768 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:02:46,768 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:02:46,769 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:02:46,770 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:02:46,792 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-11-12 01:02:46,842 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:02:46,844 INFO L262 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 31 conjunts are in the unsatisfiable core [2023-11-12 01:02:46,848 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:02:47,176 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 15 proven. 31 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-11-12 01:02:47,176 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 01:02:50,050 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 15 proven. 31 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-11-12 01:02:50,050 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:02:50,050 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [863113417] [2023-11-12 01:02:50,050 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 01:02:50,050 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [304176311] [2023-11-12 01:02:50,051 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [304176311] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 01:02:50,051 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [294760813] [2023-11-12 01:02:50,053 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2023-11-12 01:02:50,053 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 01:02:50,054 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 01:02:50,054 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 01:02:50,054 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 01:02:52,098 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-11-12 01:02:52,101 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 01:02:53,323 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3815#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 01:02:53,323 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 01:02:53,323 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 01:02:53,324 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2023-11-12 01:02:53,324 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1119876677] [2023-11-12 01:02:53,324 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 01:02:53,325 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-12 01:02:53,325 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:02:53,326 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-12 01:02:53,326 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=98, Invalid=552, Unknown=0, NotChecked=0, Total=650 [2023-11-12 01:02:53,326 INFO L87 Difference]: Start difference. First operand 148 states and 167 transitions. Second operand has 15 states, 15 states have (on average 2.466666666666667) internal successors, (37), 13 states have internal predecessors, (37), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2023-11-12 01:02:58,611 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 01:03:01,426 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 01:03:03,430 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 01:03:03,707 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:03:03,707 INFO L93 Difference]: Finished difference Result 178 states and 197 transitions. [2023-11-12 01:03:03,708 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-11-12 01:03:03,708 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.466666666666667) internal successors, (37), 13 states have internal predecessors, (37), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) Word has length 56 [2023-11-12 01:03:03,709 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:03:03,711 INFO L225 Difference]: With dead ends: 178 [2023-11-12 01:03:03,711 INFO L226 Difference]: Without dead ends: 174 [2023-11-12 01:03:03,712 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 171 GetRequests, 141 SyntacticMatches, 2 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 215 ImplicationChecksByTransitivity, 4.5s TimeCoverageRelationStatistics Valid=138, Invalid=732, Unknown=0, NotChecked=0, Total=870 [2023-11-12 01:03:03,712 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 41 mSDsluCounter, 172 mSDsCounter, 0 mSdLazyCounter, 203 mSolverCounterSat, 41 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 196 SdHoareTripleChecker+Invalid, 247 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 203 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.3s IncrementalHoareTripleChecker+Time [2023-11-12 01:03:03,713 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [44 Valid, 196 Invalid, 247 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 203 Invalid, 3 Unknown, 0 Unchecked, 7.3s Time] [2023-11-12 01:03:03,713 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 174 states. [2023-11-12 01:03:03,761 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 174 to 169. [2023-11-12 01:03:03,761 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 169 states, 112 states have (on average 1.1071428571428572) internal successors, (124), 116 states have internal predecessors, (124), 32 states have call successors, (32), 25 states have call predecessors, (32), 24 states have return successors, (29), 27 states have call predecessors, (29), 29 states have call successors, (29) [2023-11-12 01:03:03,763 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 169 states to 169 states and 185 transitions. [2023-11-12 01:03:03,763 INFO L78 Accepts]: Start accepts. Automaton has 169 states and 185 transitions. Word has length 56 [2023-11-12 01:03:03,763 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:03:03,764 INFO L495 AbstractCegarLoop]: Abstraction has 169 states and 185 transitions. [2023-11-12 01:03:03,764 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.466666666666667) internal successors, (37), 13 states have internal predecessors, (37), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2023-11-12 01:03:03,764 INFO L276 IsEmpty]: Start isEmpty. Operand 169 states and 185 transitions. [2023-11-12 01:03:03,766 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2023-11-12 01:03:03,766 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:03:03,766 INFO L195 NwaCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:03:03,781 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2023-11-12 01:03:03,972 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2023-11-12 01:03:03,972 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:03:03,972 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:03:03,972 INFO L85 PathProgramCache]: Analyzing trace with hash -143001442, now seen corresponding path program 1 times [2023-11-12 01:03:03,973 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:03:03,973 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2110657448] [2023-11-12 01:03:03,973 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:03:03,973 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:03:03,984 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 01:03:03,984 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1116334942] [2023-11-12 01:03:03,985 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:03:03,986 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:03:03,986 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:03:03,987 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:03:03,996 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-11-12 01:03:04,059 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:03:04,060 INFO L262 TraceCheckSpWp]: Trace formula consists of 184 conjuncts, 33 conjunts are in the unsatisfiable core [2023-11-12 01:03:04,065 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:03:04,386 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 19 proven. 39 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2023-11-12 01:03:04,386 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 01:03:05,103 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 19 proven. 39 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2023-11-12 01:03:05,103 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:03:05,103 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2110657448] [2023-11-12 01:03:05,104 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 01:03:05,104 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1116334942] [2023-11-12 01:03:05,104 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1116334942] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 01:03:05,104 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1979421925] [2023-11-12 01:03:05,106 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-11-12 01:03:05,107 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 01:03:05,107 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 01:03:05,107 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 01:03:05,107 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 01:03:06,920 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-11-12 01:03:06,924 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 01:03:08,116 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4740#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 01:03:08,116 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 01:03:08,117 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 01:03:08,117 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2023-11-12 01:03:08,117 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1529443279] [2023-11-12 01:03:08,117 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 01:03:08,118 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-11-12 01:03:08,118 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:03:08,119 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-11-12 01:03:08,119 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=130, Invalid=682, Unknown=0, NotChecked=0, Total=812 [2023-11-12 01:03:08,119 INFO L87 Difference]: Start difference. First operand 169 states and 185 transitions. Second operand has 17 states, 15 states have (on average 2.6) internal successors, (39), 15 states have internal predecessors, (39), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 7 states have call successors, (20) [2023-11-12 01:03:08,975 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:03:08,975 INFO L93 Difference]: Finished difference Result 188 states and 208 transitions. [2023-11-12 01:03:08,975 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-11-12 01:03:08,975 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 2.6) internal successors, (39), 15 states have internal predecessors, (39), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 7 states have call successors, (20) Word has length 67 [2023-11-12 01:03:08,976 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:03:08,977 INFO L225 Difference]: With dead ends: 188 [2023-11-12 01:03:08,977 INFO L226 Difference]: Without dead ends: 161 [2023-11-12 01:03:08,978 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 204 GetRequests, 170 SyntacticMatches, 3 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 301 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=180, Invalid=876, Unknown=0, NotChecked=0, Total=1056 [2023-11-12 01:03:08,979 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 36 mSDsluCounter, 174 mSDsCounter, 0 mSdLazyCounter, 213 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 198 SdHoareTripleChecker+Invalid, 253 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 213 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-12 01:03:08,980 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 198 Invalid, 253 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 213 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-12 01:03:08,980 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 161 states. [2023-11-12 01:03:09,029 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 161 to 148. [2023-11-12 01:03:09,030 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 148 states, 98 states have (on average 1.1224489795918366) internal successors, (110), 100 states have internal predecessors, (110), 28 states have call successors, (28), 22 states have call predecessors, (28), 21 states have return successors, (26), 25 states have call predecessors, (26), 26 states have call successors, (26) [2023-11-12 01:03:09,031 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 164 transitions. [2023-11-12 01:03:09,031 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 164 transitions. Word has length 67 [2023-11-12 01:03:09,032 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:03:09,032 INFO L495 AbstractCegarLoop]: Abstraction has 148 states and 164 transitions. [2023-11-12 01:03:09,032 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 2.6) internal successors, (39), 15 states have internal predecessors, (39), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 7 states have call successors, (20) [2023-11-12 01:03:09,032 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 164 transitions. [2023-11-12 01:03:09,034 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2023-11-12 01:03:09,034 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:03:09,034 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 01:03:09,039 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2023-11-12 01:03:09,237 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2023-11-12 01:03:09,237 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:03:09,237 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:03:09,237 INFO L85 PathProgramCache]: Analyzing trace with hash -319401384, now seen corresponding path program 1 times [2023-11-12 01:03:09,238 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:03:09,238 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [387723580] [2023-11-12 01:03:09,238 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:03:09,238 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:03:09,245 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 01:03:09,245 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1432646058] [2023-11-12 01:03:09,245 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:03:09,245 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:03:09,246 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:03:09,247 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:03:09,276 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-11-12 01:03:09,319 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 01:03:09,321 INFO L262 TraceCheckSpWp]: Trace formula consists of 201 conjuncts, 4 conjunts are in the unsatisfiable core [2023-11-12 01:03:09,327 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:03:09,374 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 84 proven. 0 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2023-11-12 01:03:09,374 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 01:03:09,374 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:03:09,375 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [387723580] [2023-11-12 01:03:09,375 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 01:03:09,375 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1432646058] [2023-11-12 01:03:09,375 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1432646058] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 01:03:09,375 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 01:03:09,375 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-12 01:03:09,376 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [180659926] [2023-11-12 01:03:09,376 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 01:03:09,376 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 01:03:09,376 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:03:09,377 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 01:03:09,377 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2023-11-12 01:03:09,377 INFO L87 Difference]: Start difference. First operand 148 states and 164 transitions. Second operand has 5 states, 5 states have (on average 4.2) internal successors, (21), 5 states have internal predecessors, (21), 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 01:03:09,475 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 01:03:09,476 INFO L93 Difference]: Finished difference Result 163 states and 179 transitions. [2023-11-12 01:03:09,476 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-12 01:03:09,476 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 5 states have internal predecessors, (21), 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 77 [2023-11-12 01:03:09,477 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 01:03:09,478 INFO L225 Difference]: With dead ends: 163 [2023-11-12 01:03:09,478 INFO L226 Difference]: Without dead ends: 143 [2023-11-12 01:03:09,479 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 73 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 01:03:09,479 INFO L413 NwaCegarLoop]: 43 mSDtfsCounter, 12 mSDsluCounter, 32 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 75 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 01:03:09,480 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 75 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 01:03:09,481 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2023-11-12 01:03:09,526 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 140. [2023-11-12 01:03:09,527 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 140 states, 93 states have (on average 1.096774193548387) internal successors, (102), 95 states have internal predecessors, (102), 26 states have call successors, (26), 20 states have call predecessors, (26), 20 states have return successors, (25), 24 states have call predecessors, (25), 25 states have call successors, (25) [2023-11-12 01:03:09,528 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 153 transitions. [2023-11-12 01:03:09,529 INFO L78 Accepts]: Start accepts. Automaton has 140 states and 153 transitions. Word has length 77 [2023-11-12 01:03:09,529 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 01:03:09,529 INFO L495 AbstractCegarLoop]: Abstraction has 140 states and 153 transitions. [2023-11-12 01:03:09,530 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 5 states have internal predecessors, (21), 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 01:03:09,530 INFO L276 IsEmpty]: Start isEmpty. Operand 140 states and 153 transitions. [2023-11-12 01:03:09,531 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2023-11-12 01:03:09,531 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 01:03:09,531 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2023-11-12 01:03:09,545 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2023-11-12 01:03:09,737 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2023-11-12 01:03:09,737 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 01:03:09,737 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 01:03:09,738 INFO L85 PathProgramCache]: Analyzing trace with hash -1379671488, now seen corresponding path program 2 times [2023-11-12 01:03:09,738 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 01:03:09,738 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1026014156] [2023-11-12 01:03:09,738 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 01:03:09,739 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 01:03:09,751 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 01:03:09,751 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [559053239] [2023-11-12 01:03:09,751 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-12 01:03:09,751 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 01:03:09,751 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 01:03:09,755 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 01:03:09,780 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_35e83afa-4b78-46b5-b7a3-648f38291968/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-11-12 01:03:09,817 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-11-12 01:03:09,817 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 01:03:09,819 INFO L262 TraceCheckSpWp]: Trace formula consists of 141 conjuncts, 31 conjunts are in the unsatisfiable core [2023-11-12 01:03:09,821 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 01:03:10,089 INFO L134 CoverageAnalysis]: Checked inductivity of 310 backedges. 41 proven. 38 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-11-12 01:03:10,089 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 01:03:12,378 INFO L134 CoverageAnalysis]: Checked inductivity of 310 backedges. 41 proven. 32 refuted. 0 times theorem prover too weak. 237 trivial. 0 not checked. [2023-11-12 01:03:12,379 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 01:03:12,379 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1026014156] [2023-11-12 01:03:12,379 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 01:03:12,379 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [559053239] [2023-11-12 01:03:12,380 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [559053239] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 01:03:12,380 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1598445461] [2023-11-12 01:03:12,382 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2023-11-12 01:03:12,382 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 01:03:12,383 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 01:03:12,383 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 01:03:12,383 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 01:03:13,863 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-11-12 01:03:13,866 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 01:03:14,980 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '6383#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 01:03:14,980 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 01:03:14,980 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 01:03:14,981 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 17 [2023-11-12 01:03:14,981 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2045947690] [2023-11-12 01:03:14,981 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 01:03:14,982 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-11-12 01:03:14,982 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 01:03:14,983 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-11-12 01:03:14,983 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=118, Invalid=638, Unknown=0, NotChecked=0, Total=756 [2023-11-12 01:03:14,983 INFO L87 Difference]: Start difference. First operand 140 states and 153 transitions. Second operand has 17 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 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)