./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/ps6-ll_unwindbound10.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 9bd2c7ff 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_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/ps6-ll_unwindbound10.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ --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 ebfcdae9f2d92c4e39230ecf30ad4ac0897188e9aff6dcbde95509d87ea826ad --- Real Ultimate output --- This is Ultimate 0.2.3-dev-9bd2c7f [2023-11-19 05:24:43,804 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-19 05:24:43,922 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-19 05:24:43,926 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-19 05:24:43,927 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-19 05:24:43,967 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-19 05:24:43,968 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-19 05:24:43,969 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-19 05:24:43,970 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-19 05:24:43,975 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-19 05:24:43,975 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-19 05:24:43,977 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-19 05:24:43,977 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-19 05:24:43,979 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-19 05:24:43,979 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-19 05:24:43,980 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-19 05:24:43,980 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-19 05:24:43,980 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-19 05:24:43,981 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-19 05:24:43,981 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-19 05:24:43,982 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-19 05:24:43,982 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-19 05:24:43,983 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-19 05:24:43,984 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-19 05:24:43,984 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-19 05:24:43,985 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-19 05:24:43,985 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-19 05:24:43,985 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-19 05:24:43,986 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-19 05:24:43,986 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-19 05:24:43,988 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-19 05:24:44,001 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-19 05:24:44,002 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-19 05:24:44,002 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-19 05:24:44,002 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-19 05:24:44,003 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-19 05:24:44,003 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-19 05:24:44,003 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-19 05:24:44,004 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-19 05:24:44,004 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-19 05:24:44,004 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-19 05:24:44,005 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-19 05:24:44,005 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-19 05:24:44,005 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-19 05:24:44,006 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-19 05:24:44,006 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_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/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_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ 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 -> ebfcdae9f2d92c4e39230ecf30ad4ac0897188e9aff6dcbde95509d87ea826ad [2023-11-19 05:24:44,309 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-19 05:24:44,343 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-19 05:24:44,346 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-19 05:24:44,347 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-19 05:24:44,348 INFO L274 PluginConnector]: CDTParser initialized [2023-11-19 05:24:44,352 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/../../sv-benchmarks/c/nla-digbench-scaling/ps6-ll_unwindbound10.c [2023-11-19 05:24:47,392 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-19 05:24:47,633 INFO L384 CDTParser]: Found 1 translation units. [2023-11-19 05:24:47,634 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/sv-benchmarks/c/nla-digbench-scaling/ps6-ll_unwindbound10.c [2023-11-19 05:24:47,642 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/data/e517c4bad/91f883c7e1184cd9bb4c35d9d857a964/FLAGa03b124e1 [2023-11-19 05:24:47,658 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/data/e517c4bad/91f883c7e1184cd9bb4c35d9d857a964 [2023-11-19 05:24:47,661 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-19 05:24:47,662 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-19 05:24:47,664 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-19 05:24:47,664 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-19 05:24:47,670 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-19 05:24:47,671 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 05:24:47" (1/1) ... [2023-11-19 05:24:47,672 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@45af2ae1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:24:47, skipping insertion in model container [2023-11-19 05:24:47,672 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 05:24:47" (1/1) ... [2023-11-19 05:24:47,695 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-19 05:24:47,859 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_39736793-42af-45a6-a7f1-e7203db5d8c5/sv-benchmarks/c/nla-digbench-scaling/ps6-ll_unwindbound10.c[458,471] [2023-11-19 05:24:47,879 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-19 05:24:47,889 INFO L202 MainTranslator]: Completed pre-run [2023-11-19 05:24:47,901 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_39736793-42af-45a6-a7f1-e7203db5d8c5/sv-benchmarks/c/nla-digbench-scaling/ps6-ll_unwindbound10.c[458,471] [2023-11-19 05:24:47,913 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-19 05:24:47,928 INFO L206 MainTranslator]: Completed translation [2023-11-19 05:24:47,928 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:24:47 WrapperNode [2023-11-19 05:24:47,928 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-19 05:24:47,930 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-19 05:24:47,930 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-19 05:24:47,930 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-19 05:24:47,936 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:24:47" (1/1) ... [2023-11-19 05:24:47,942 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:24:47" (1/1) ... [2023-11-19 05:24:47,958 INFO L138 Inliner]: procedures = 14, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 43 [2023-11-19 05:24:47,959 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-19 05:24:47,959 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-19 05:24:47,960 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-19 05:24:47,960 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-19 05:24:47,968 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:24:47" (1/1) ... [2023-11-19 05:24:47,968 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:24:47" (1/1) ... [2023-11-19 05:24:47,969 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:24:47" (1/1) ... [2023-11-19 05:24:47,970 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:24:47" (1/1) ... [2023-11-19 05:24:47,973 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:24:47" (1/1) ... [2023-11-19 05:24:47,976 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:24:47" (1/1) ... [2023-11-19 05:24:47,978 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:24:47" (1/1) ... [2023-11-19 05:24:47,979 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:24:47" (1/1) ... [2023-11-19 05:24:47,980 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-19 05:24:47,982 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-19 05:24:47,982 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-19 05:24:47,982 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-19 05:24:47,983 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:24:47" (1/1) ... [2023-11-19 05:24:48,008 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-19 05:24:48,021 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:24:48,037 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-19 05:24:48,055 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-19 05:24:48,080 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-19 05:24:48,080 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-19 05:24:48,081 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-19 05:24:48,081 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-19 05:24:48,081 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-11-19 05:24:48,081 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-11-19 05:24:48,168 INFO L236 CfgBuilder]: Building ICFG [2023-11-19 05:24:48,170 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-19 05:24:48,334 INFO L277 CfgBuilder]: Performing block encoding [2023-11-19 05:24:48,372 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-19 05:24:48,372 INFO L302 CfgBuilder]: Removed 1 assume(true) statements. [2023-11-19 05:24:48,377 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 05:24:48 BoogieIcfgContainer [2023-11-19 05:24:48,377 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-19 05:24:48,380 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-19 05:24:48,380 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-19 05:24:48,383 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-19 05:24:48,384 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.11 05:24:47" (1/3) ... [2023-11-19 05:24:48,384 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5fdc5ed4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 05:24:48, skipping insertion in model container [2023-11-19 05:24:48,385 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 05:24:47" (2/3) ... [2023-11-19 05:24:48,385 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5fdc5ed4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 05:24:48, skipping insertion in model container [2023-11-19 05:24:48,385 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 05:24:48" (3/3) ... [2023-11-19 05:24:48,387 INFO L112 eAbstractionObserver]: Analyzing ICFG ps6-ll_unwindbound10.c [2023-11-19 05:24:48,408 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-19 05:24:48,408 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-19 05:24:48,454 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-19 05:24:48,461 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;@2a095626, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-19 05:24:48,461 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-19 05:24:48,465 INFO L276 IsEmpty]: Start isEmpty. Operand has 15 states, 9 states have (on average 1.5555555555555556) internal successors, (14), 10 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2023-11-19 05:24:48,471 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2023-11-19 05:24:48,472 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:24:48,472 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2023-11-19 05:24:48,473 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:24:48,478 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:24:48,479 INFO L85 PathProgramCache]: Analyzing trace with hash -1749202120, now seen corresponding path program 1 times [2023-11-19 05:24:48,490 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:24:48,490 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1794981427] [2023-11-19 05:24:48,490 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:24:48,491 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:24:48,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:24:48,600 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:24:48,601 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1794981427] [2023-11-19 05:24:48,601 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-11-19 05:24:48,601 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [364641724] [2023-11-19 05:24:48,602 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:24:48,602 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:24:48,602 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:24:48,603 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:24:48,605 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-19 05:24:48,660 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:24:48,662 INFO L262 TraceCheckSpWp]: Trace formula consists of 42 conjuncts, 1 conjunts are in the unsatisfiable core [2023-11-19 05:24:48,666 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:24:48,683 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-19 05:24:48,684 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-19 05:24:48,684 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [364641724] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 05:24:48,684 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 05:24:48,685 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-19 05:24:48,686 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1778102757] [2023-11-19 05:24:48,687 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 05:24:48,691 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-11-19 05:24:48,692 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:24:48,720 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-11-19 05:24:48,721 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-11-19 05:24:48,723 INFO L87 Difference]: Start difference. First operand has 15 states, 9 states have (on average 1.5555555555555556) internal successors, (14), 10 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-19 05:24:48,751 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:24:48,751 INFO L93 Difference]: Finished difference Result 29 states and 42 transitions. [2023-11-19 05:24:48,752 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-11-19 05:24:48,754 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 6 [2023-11-19 05:24:48,754 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:24:48,761 INFO L225 Difference]: With dead ends: 29 [2023-11-19 05:24:48,762 INFO L226 Difference]: Without dead ends: 13 [2023-11-19 05:24:48,765 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 5 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-19 05:24:48,769 INFO L413 NwaCegarLoop]: 16 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 16 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-19 05:24:48,770 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 16 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-19 05:24:48,789 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 13 states. [2023-11-19 05:24:48,805 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 13 to 13. [2023-11-19 05:24:48,806 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 13 states, 8 states have (on average 1.375) internal successors, (11), 9 states have internal predecessors, (11), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-19 05:24:48,807 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 16 transitions. [2023-11-19 05:24:48,809 INFO L78 Accepts]: Start accepts. Automaton has 13 states and 16 transitions. Word has length 6 [2023-11-19 05:24:48,809 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:24:48,810 INFO L495 AbstractCegarLoop]: Abstraction has 13 states and 16 transitions. [2023-11-19 05:24:48,810 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-19 05:24:48,810 INFO L276 IsEmpty]: Start isEmpty. Operand 13 states and 16 transitions. [2023-11-19 05:24:48,811 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-11-19 05:24:48,811 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:24:48,811 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:24:48,837 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-19 05:24:49,028 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2023-11-19 05:24:49,028 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:24:49,029 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:24:49,029 INFO L85 PathProgramCache]: Analyzing trace with hash 1208885392, now seen corresponding path program 1 times [2023-11-19 05:24:49,030 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:24:49,030 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1333790246] [2023-11-19 05:24:49,030 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:24:49,031 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:24:49,050 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:24:49,070 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:24:49,070 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1333790246] [2023-11-19 05:24:49,070 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-11-19 05:24:49,070 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [948334033] [2023-11-19 05:24:49,071 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:24:49,071 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:24:49,071 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:24:49,072 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:24:49,081 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-19 05:24:49,156 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:24:49,157 INFO L262 TraceCheckSpWp]: Trace formula consists of 46 conjuncts, 3 conjunts are in the unsatisfiable core [2023-11-19 05:24:49,158 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:24:49,215 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-19 05:24:49,215 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-19 05:24:49,216 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [948334033] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 05:24:49,216 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 05:24:49,216 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-19 05:24:49,217 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [3403916] [2023-11-19 05:24:49,217 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 05:24:49,218 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-19 05:24:49,218 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:24:49,218 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-19 05:24:49,219 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-19 05:24:49,219 INFO L87 Difference]: Start difference. First operand 13 states and 16 transitions. Second operand has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-19 05:24:49,238 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:24:49,239 INFO L93 Difference]: Finished difference Result 23 states and 27 transitions. [2023-11-19 05:24:49,239 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-19 05:24:49,240 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2023-11-19 05:24:49,240 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:24:49,240 INFO L225 Difference]: With dead ends: 23 [2023-11-19 05:24:49,241 INFO L226 Difference]: Without dead ends: 15 [2023-11-19 05:24:49,241 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 4 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-19 05:24:49,243 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 0 mSDsluCounter, 25 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 38 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-19 05:24:49,244 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 38 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-19 05:24:49,245 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2023-11-19 05:24:49,249 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2023-11-19 05:24:49,250 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 15 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-19 05:24:49,251 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 18 transitions. [2023-11-19 05:24:49,251 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 18 transitions. Word has length 7 [2023-11-19 05:24:49,251 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:24:49,251 INFO L495 AbstractCegarLoop]: Abstraction has 15 states and 18 transitions. [2023-11-19 05:24:49,252 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-19 05:24:49,252 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 18 transitions. [2023-11-19 05:24:49,252 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-11-19 05:24:49,252 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:24:49,253 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:24:49,281 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-19 05:24:49,480 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:24:49,481 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:24:49,482 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:24:49,482 INFO L85 PathProgramCache]: Analyzing trace with hash 1210672852, now seen corresponding path program 1 times [2023-11-19 05:24:49,482 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:24:49,482 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [859611249] [2023-11-19 05:24:49,483 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:24:49,483 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:24:49,500 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:24:49,501 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [778187677] [2023-11-19 05:24:49,501 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:24:49,501 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:24:49,502 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:24:49,503 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:24:49,508 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-19 05:24:49,558 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:24:49,559 INFO L262 TraceCheckSpWp]: Trace formula consists of 46 conjuncts, 7 conjunts are in the unsatisfiable core [2023-11-19 05:24:49,561 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:24:49,615 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-19 05:24:49,615 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-19 05:24:49,615 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:24:49,615 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [859611249] [2023-11-19 05:24:49,616 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-19 05:24:49,616 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [778187677] [2023-11-19 05:24:49,616 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [778187677] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-19 05:24:49,616 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-19 05:24:49,616 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-11-19 05:24:49,617 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1856633688] [2023-11-19 05:24:49,617 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 05:24:49,617 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-19 05:24:49,617 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:24:49,618 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-19 05:24:49,618 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-19 05:24:49,619 INFO L87 Difference]: Start difference. First operand 15 states and 18 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-19 05:24:49,698 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:24:49,698 INFO L93 Difference]: Finished difference Result 25 states and 30 transitions. [2023-11-19 05:24:49,699 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-19 05:24:49,699 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-19 05:24:49,699 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:24:49,700 INFO L225 Difference]: With dead ends: 25 [2023-11-19 05:24:49,700 INFO L226 Difference]: Without dead ends: 21 [2023-11-19 05:24:49,701 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 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-19 05:24:49,702 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 6 mSDsluCounter, 33 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 05:24:49,704 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 45 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 05:24:49,705 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2023-11-19 05:24:49,711 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2023-11-19 05:24:49,711 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 15 states have internal predecessors, (17), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2023-11-19 05:24:49,712 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 24 transitions. [2023-11-19 05:24:49,712 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 24 transitions. Word has length 7 [2023-11-19 05:24:49,713 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:24:49,713 INFO L495 AbstractCegarLoop]: Abstraction has 21 states and 24 transitions. [2023-11-19 05:24:49,713 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-19 05:24:49,713 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 24 transitions. [2023-11-19 05:24:49,714 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2023-11-19 05:24:49,714 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:24:49,714 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:24:49,744 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-19 05:24:49,936 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:24:49,936 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:24:49,937 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:24:49,937 INFO L85 PathProgramCache]: Analyzing trace with hash 479296502, now seen corresponding path program 1 times [2023-11-19 05:24:49,937 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:24:49,937 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1054361648] [2023-11-19 05:24:49,937 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:24:49,938 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:24:49,954 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:24:49,959 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [808689419] [2023-11-19 05:24:49,959 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:24:49,959 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:24:49,960 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:24:49,963 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:24:49,980 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-19 05:24:50,015 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:24:50,016 INFO L262 TraceCheckSpWp]: Trace formula consists of 67 conjuncts, 5 conjunts are in the unsatisfiable core [2023-11-19 05:24:50,018 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:24:50,055 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:24:50,055 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:24:50,110 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:24:50,111 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:24:50,113 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1054361648] [2023-11-19 05:24:50,113 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-19 05:24:50,114 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [808689419] [2023-11-19 05:24:50,114 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [808689419] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:24:50,114 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [627972298] [2023-11-19 05:24:50,140 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2023-11-19 05:24:50,140 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:24:50,145 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-19 05:24:50,152 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-19 05:24:50,153 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-19 05:24:51,374 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 66 for LOIs [2023-11-19 05:24:51,608 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-19 05:24:55,260 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '348#(and (<= 1 |#StackHeapBarrier|) (or (and (<= ~counter~0 10) (exists ((|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_9| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| Int)) (and (<= 0 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9|) (<= 0 |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_9|) (not (= (+ (* (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9|) 2) (* 5 (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9|)) (* (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9|) 6)) (+ (* |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_9| 12) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_9|))))))) (and (<= 11 ~counter~0) (exists ((|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| Int) (|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_8| Int)) (and (<= 0 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|) (not (= (+ (* |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_8| 12) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|)) (+ (* (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|) 2) (* 6 (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|)) (* 5 (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_8|))))) (<= 0 |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_8|))))) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-19 05:24:55,260 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-19 05:24:55,260 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-19 05:24:55,261 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5] total 8 [2023-11-19 05:24:55,261 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [850227362] [2023-11-19 05:24:55,261 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-19 05:24:55,262 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-11-19 05:24:55,262 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:24:55,263 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-11-19 05:24:55,264 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=224, Unknown=1, NotChecked=0, Total=272 [2023-11-19 05:24:55,265 INFO L87 Difference]: Start difference. First operand 21 states and 24 transitions. Second operand has 8 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-19 05:24:55,399 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:24:55,399 INFO L93 Difference]: Finished difference Result 55 states and 65 transitions. [2023-11-19 05:24:55,399 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-19 05:24:55,400 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 15 [2023-11-19 05:24:55,400 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:24:55,402 INFO L225 Difference]: With dead ends: 55 [2023-11-19 05:24:55,407 INFO L226 Difference]: Without dead ends: 47 [2023-11-19 05:24:55,409 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 84 ImplicationChecksByTransitivity, 3.7s TimeCoverageRelationStatistics Valid=67, Invalid=312, Unknown=1, NotChecked=0, Total=380 [2023-11-19 05:24:55,411 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 29 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 69 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 05:24:55,411 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 69 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 05:24:55,412 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2023-11-19 05:24:55,420 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 43. [2023-11-19 05:24:55,421 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 28 states have (on average 1.25) internal successors, (35), 31 states have internal predecessors, (35), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2023-11-19 05:24:55,422 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 52 transitions. [2023-11-19 05:24:55,423 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 52 transitions. Word has length 15 [2023-11-19 05:24:55,423 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:24:55,423 INFO L495 AbstractCegarLoop]: Abstraction has 43 states and 52 transitions. [2023-11-19 05:24:55,423 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-19 05:24:55,424 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 52 transitions. [2023-11-19 05:24:55,424 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2023-11-19 05:24:55,424 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:24:55,425 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:24:55,452 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-19 05:24:55,638 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:24:55,638 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:24:55,639 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:24:55,639 INFO L85 PathProgramCache]: Analyzing trace with hash 481083962, now seen corresponding path program 1 times [2023-11-19 05:24:55,639 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:24:55,639 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1984819597] [2023-11-19 05:24:55,639 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:24:55,640 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:24:55,653 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:24:55,654 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [391745970] [2023-11-19 05:24:55,654 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:24:55,654 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:24:55,654 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:24:55,661 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:24:55,669 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-19 05:24:55,720 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:24:55,721 INFO L262 TraceCheckSpWp]: Trace formula consists of 67 conjuncts, 11 conjunts are in the unsatisfiable core [2023-11-19 05:24:55,725 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:24:55,792 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-19 05:24:55,793 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:24:55,860 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2023-11-19 05:24:55,861 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:24:55,861 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1984819597] [2023-11-19 05:24:55,861 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-19 05:24:55,861 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [391745970] [2023-11-19 05:24:55,862 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [391745970] provided 1 perfect and 1 imperfect interpolant sequences [2023-11-19 05:24:55,862 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-19 05:24:55,862 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2023-11-19 05:24:55,862 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [317276567] [2023-11-19 05:24:55,862 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-19 05:24:55,863 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-19 05:24:55,863 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:24:55,864 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-19 05:24:55,864 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2023-11-19 05:24:55,864 INFO L87 Difference]: Start difference. First operand 43 states and 52 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 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-19 05:24:55,916 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:24:55,916 INFO L93 Difference]: Finished difference Result 57 states and 65 transitions. [2023-11-19 05:24:55,917 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-19 05:24:55,917 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 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 15 [2023-11-19 05:24:55,917 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:24:55,918 INFO L225 Difference]: With dead ends: 57 [2023-11-19 05:24:55,918 INFO L226 Difference]: Without dead ends: 49 [2023-11-19 05:24:55,919 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 21 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2023-11-19 05:24:55,920 INFO L413 NwaCegarLoop]: 10 mSDtfsCounter, 7 mSDsluCounter, 23 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 33 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-19 05:24:55,920 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 33 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-19 05:24:55,921 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2023-11-19 05:24:55,936 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 43. [2023-11-19 05:24:55,936 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 30 states have (on average 1.1333333333333333) internal successors, (34), 32 states have internal predecessors, (34), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) [2023-11-19 05:24:55,938 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 49 transitions. [2023-11-19 05:24:55,938 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 49 transitions. Word has length 15 [2023-11-19 05:24:55,938 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:24:55,938 INFO L495 AbstractCegarLoop]: Abstraction has 43 states and 49 transitions. [2023-11-19 05:24:55,938 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 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-19 05:24:55,939 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 49 transitions. [2023-11-19 05:24:55,940 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2023-11-19 05:24:55,940 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:24:55,940 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:24:55,966 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-19 05:24:56,160 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:24:56,160 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:24:56,161 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:24:56,161 INFO L85 PathProgramCache]: Analyzing trace with hash 669026573, now seen corresponding path program 1 times [2023-11-19 05:24:56,161 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:24:56,161 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1871566736] [2023-11-19 05:24:56,161 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:24:56,161 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:24:56,178 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:24:56,180 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1062981192] [2023-11-19 05:24:56,180 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:24:56,181 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:24:56,181 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:24:56,182 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:24:56,199 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-19 05:24:56,234 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:24:56,236 INFO L262 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjunts are in the unsatisfiable core [2023-11-19 05:24:56,238 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:24:56,321 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-11-19 05:24:56,321 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:24:56,421 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-11-19 05:24:56,421 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:24:56,421 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1871566736] [2023-11-19 05:24:56,421 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-19 05:24:56,422 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1062981192] [2023-11-19 05:24:56,422 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1062981192] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:24:56,422 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [497262829] [2023-11-19 05:24:56,424 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2023-11-19 05:24:56,425 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:24:56,425 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-19 05:24:56,425 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-19 05:24:56,425 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-19 05:24:57,097 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2023-11-19 05:24:57,104 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-19 05:24:57,421 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '895#(and (<= ~counter~0 10) (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-19 05:24:57,421 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-19 05:24:57,421 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-19 05:24:57,421 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2023-11-19 05:24:57,421 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1433239566] [2023-11-19 05:24:57,422 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-19 05:24:57,422 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-11-19 05:24:57,422 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:24:57,423 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-11-19 05:24:57,423 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=285, Unknown=0, NotChecked=0, Total=342 [2023-11-19 05:24:57,423 INFO L87 Difference]: Start difference. First operand 43 states and 49 transitions. Second operand has 10 states, 8 states have (on average 2.5) internal successors, (20), 9 states have internal predecessors, (20), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-11-19 05:24:57,601 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:24:57,601 INFO L93 Difference]: Finished difference Result 53 states and 61 transitions. [2023-11-19 05:24:57,602 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-11-19 05:24:57,602 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.5) internal successors, (20), 9 states have internal predecessors, (20), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 26 [2023-11-19 05:24:57,602 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:24:57,603 INFO L225 Difference]: With dead ends: 53 [2023-11-19 05:24:57,603 INFO L226 Difference]: Without dead ends: 43 [2023-11-19 05:24:57,604 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 57 SyntacticMatches, 2 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 85 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=89, Invalid=463, Unknown=0, NotChecked=0, Total=552 [2023-11-19 05:24:57,605 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 4 mSDsluCounter, 63 mSDsCounter, 0 mSdLazyCounter, 49 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 80 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 49 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 05:24:57,605 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 80 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 49 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 05:24:57,606 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2023-11-19 05:24:57,619 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2023-11-19 05:24:57,620 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 31 states have (on average 1.064516129032258) internal successors, (33), 31 states have internal predecessors, (33), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-11-19 05:24:57,621 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 46 transitions. [2023-11-19 05:24:57,621 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 46 transitions. Word has length 26 [2023-11-19 05:24:57,621 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:24:57,621 INFO L495 AbstractCegarLoop]: Abstraction has 43 states and 46 transitions. [2023-11-19 05:24:57,622 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.5) internal successors, (20), 9 states have internal predecessors, (20), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-11-19 05:24:57,622 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 46 transitions. [2023-11-19 05:24:57,623 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2023-11-19 05:24:57,623 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:24:57,623 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 5, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:24:57,651 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-19 05:24:57,839 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:24:57,840 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:24:57,840 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:24:57,840 INFO L85 PathProgramCache]: Analyzing trace with hash -783657828, now seen corresponding path program 1 times [2023-11-19 05:24:57,840 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:24:57,840 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1760120858] [2023-11-19 05:24:57,841 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:24:57,841 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:24:57,855 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:24:57,855 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1239601786] [2023-11-19 05:24:57,856 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:24:57,856 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:24:57,856 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:24:57,857 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:24:57,859 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-19 05:24:57,928 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-19 05:24:57,929 INFO L262 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 11 conjunts are in the unsatisfiable core [2023-11-19 05:24:57,934 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:24:58,021 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 24 proven. 56 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-11-19 05:24:58,022 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:24:58,138 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 10 proven. 32 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2023-11-19 05:24:58,138 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:24:58,138 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1760120858] [2023-11-19 05:24:58,138 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-19 05:24:58,138 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1239601786] [2023-11-19 05:24:58,139 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1239601786] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:24:58,139 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1640141499] [2023-11-19 05:24:58,142 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2023-11-19 05:24:58,142 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:24:58,142 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-19 05:24:58,143 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-19 05:24:58,143 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-19 05:24:58,764 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-19 05:24:58,770 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-19 05:24:59,046 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1323#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-19 05:24:59,047 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-19 05:24:59,047 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-19 05:24:59,047 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8] total 14 [2023-11-19 05:24:59,047 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [997627491] [2023-11-19 05:24:59,047 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-19 05:24:59,048 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-11-19 05:24:59,048 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:24:59,050 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-11-19 05:24:59,050 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=444, Unknown=0, NotChecked=0, Total=552 [2023-11-19 05:24:59,050 INFO L87 Difference]: Start difference. First operand 43 states and 46 transitions. Second operand has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (11), 6 states have call predecessors, (11), 6 states have return successors, (10), 9 states have call predecessors, (10), 9 states have call successors, (10) [2023-11-19 05:24:59,366 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:24:59,366 INFO L93 Difference]: Finished difference Result 129 states and 141 transitions. [2023-11-19 05:24:59,366 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2023-11-19 05:24:59,367 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (11), 6 states have call predecessors, (11), 6 states have return successors, (10), 9 states have call predecessors, (10), 9 states have call successors, (10) Word has length 44 [2023-11-19 05:24:59,367 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:24:59,369 INFO L225 Difference]: With dead ends: 129 [2023-11-19 05:24:59,369 INFO L226 Difference]: Without dead ends: 119 [2023-11-19 05:24:59,370 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 108 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 279 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=221, Invalid=835, Unknown=0, NotChecked=0, Total=1056 [2023-11-19 05:24:59,371 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 77 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 64 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 77 SdHoareTripleChecker+Valid, 93 SdHoareTripleChecker+Invalid, 81 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 64 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-19 05:24:59,371 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [77 Valid, 93 Invalid, 81 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 64 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-19 05:24:59,372 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2023-11-19 05:24:59,399 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 94. [2023-11-19 05:24:59,400 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 66 states have (on average 1.106060606060606) internal successors, (73), 71 states have internal predecessors, (73), 17 states have call successors, (17), 11 states have call predecessors, (17), 10 states have return successors, (16), 11 states have call predecessors, (16), 16 states have call successors, (16) [2023-11-19 05:24:59,401 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 106 transitions. [2023-11-19 05:24:59,401 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 106 transitions. Word has length 44 [2023-11-19 05:24:59,402 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:24:59,402 INFO L495 AbstractCegarLoop]: Abstraction has 94 states and 106 transitions. [2023-11-19 05:24:59,402 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (11), 6 states have call predecessors, (11), 6 states have return successors, (10), 9 states have call predecessors, (10), 9 states have call successors, (10) [2023-11-19 05:24:59,402 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 106 transitions. [2023-11-19 05:24:59,404 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2023-11-19 05:24:59,404 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:24:59,404 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:24:59,430 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-19 05:24:59,623 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2023-11-19 05:24:59,624 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:24:59,624 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:24:59,624 INFO L85 PathProgramCache]: Analyzing trace with hash 1502128027, now seen corresponding path program 2 times [2023-11-19 05:24:59,624 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:24:59,624 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [740245896] [2023-11-19 05:24:59,624 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:24:59,624 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:24:59,636 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:24:59,637 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [452779593] [2023-11-19 05:24:59,637 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-19 05:24:59,637 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:24:59,637 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:24:59,638 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:24:59,684 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-19 05:24:59,730 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2023-11-19 05:24:59,730 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-19 05:24:59,732 INFO L262 TraceCheckSpWp]: Trace formula consists of 149 conjuncts, 43 conjunts are in the unsatisfiable core [2023-11-19 05:24:59,736 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-19 05:24:59,974 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 25 proven. 51 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2023-11-19 05:24:59,975 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-19 05:25:04,414 WARN L854 $PredicateComparison]: unable to prove that (let ((.cse0 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1|))) (or (not (= 0 (mod (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 10) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 7) .cse0 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 6)) 12))) (= (+ .cse0 (* |c_ULTIMATE.start_main_~y~0#1| 2)) (+ (* |c_ULTIMATE.start_main_~c~0#1| 2) (* |c_ULTIMATE.start_main_~c~0#1| |c_ULTIMATE.start_main_~y~0#1|))))) is different from false [2023-11-19 05:25:12,545 WARN L854 $PredicateComparison]: unable to prove that (let ((.cse0 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1|))) (or (= (+ (* |c_ULTIMATE.start_main_~c~0#1| 3) (* |c_ULTIMATE.start_main_~c~0#1| |c_ULTIMATE.start_main_~y~0#1|)) (+ .cse0 (* |c_ULTIMATE.start_main_~y~0#1| 3))) (not (= 0 (mod (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 10) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 7) .cse0 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 6)) 12))))) is different from false [2023-11-19 05:25:22,654 WARN L854 $PredicateComparison]: unable to prove that (let ((.cse0 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1|))) (or (= (+ (* |c_ULTIMATE.start_main_~c~0#1| |c_ULTIMATE.start_main_~y~0#1|) (* |c_ULTIMATE.start_main_~c~0#1| 4)) (+ .cse0 (* |c_ULTIMATE.start_main_~y~0#1| 4))) (not (= 0 (mod (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 10) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 7) .cse0 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 6)) 12))))) is different from false [2023-11-19 05:25:28,729 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 23 proven. 10 refuted. 0 times theorem prover too weak. 45 trivial. 34 not checked. [2023-11-19 05:25:28,729 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-19 05:25:28,729 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [740245896] [2023-11-19 05:25:28,729 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-19 05:25:28,729 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [452779593] [2023-11-19 05:25:28,729 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [452779593] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-19 05:25:28,730 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1792208501] [2023-11-19 05:25:28,732 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2023-11-19 05:25:28,732 INFO L166 IcfgInterpreter]: Building call graph [2023-11-19 05:25:28,732 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-19 05:25:28,732 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-19 05:25:28,733 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-19 05:25:29,333 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2023-11-19 05:25:29,340 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-19 05:25:29,734 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1984#(and (<= ~counter~0 10) (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-19 05:25:29,734 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-19 05:25:29,735 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-19 05:25:29,735 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13] total 24 [2023-11-19 05:25:29,735 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1859775966] [2023-11-19 05:25:29,735 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-19 05:25:29,736 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2023-11-19 05:25:29,736 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-19 05:25:29,736 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2023-11-19 05:25:29,737 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=116, Invalid=763, Unknown=3, NotChecked=174, Total=1056 [2023-11-19 05:25:29,737 INFO L87 Difference]: Start difference. First operand 94 states and 106 transitions. Second operand has 24 states, 22 states have (on average 2.0454545454545454) internal successors, (45), 19 states have internal predecessors, (45), 12 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2023-11-19 05:25:30,376 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-19 05:25:30,376 INFO L93 Difference]: Finished difference Result 101 states and 113 transitions. [2023-11-19 05:25:30,376 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-11-19 05:25:30,377 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 22 states have (on average 2.0454545454545454) internal successors, (45), 19 states have internal predecessors, (45), 12 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Word has length 50 [2023-11-19 05:25:30,377 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-19 05:25:30,378 INFO L225 Difference]: With dead ends: 101 [2023-11-19 05:25:30,378 INFO L226 Difference]: Without dead ends: 89 [2023-11-19 05:25:30,380 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 160 GetRequests, 117 SyntacticMatches, 1 SemanticMatches, 42 ConstructedPredicates, 3 IntricatePredicates, 0 DeprecatedPredicates, 315 ImplicationChecksByTransitivity, 7.1s TimeCoverageRelationStatistics Valid=218, Invalid=1431, Unknown=3, NotChecked=240, Total=1892 [2023-11-19 05:25:30,381 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 36 mSDsluCounter, 189 mSDsCounter, 0 mSdLazyCounter, 178 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 211 SdHoareTripleChecker+Invalid, 318 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 178 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 112 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-19 05:25:30,381 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 211 Invalid, 318 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 178 Invalid, 0 Unknown, 112 Unchecked, 0.3s Time] [2023-11-19 05:25:30,382 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2023-11-19 05:25:30,407 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 89. [2023-11-19 05:25:30,407 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 66 states have (on average 1.0151515151515151) internal successors, (67), 66 states have internal predecessors, (67), 12 states have call successors, (12), 11 states have call predecessors, (12), 10 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2023-11-19 05:25:30,408 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 90 transitions. [2023-11-19 05:25:30,408 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 90 transitions. Word has length 50 [2023-11-19 05:25:30,409 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-19 05:25:30,409 INFO L495 AbstractCegarLoop]: Abstraction has 89 states and 90 transitions. [2023-11-19 05:25:30,409 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 22 states have (on average 2.0454545454545454) internal successors, (45), 19 states have internal predecessors, (45), 12 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2023-11-19 05:25:30,410 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 90 transitions. [2023-11-19 05:25:30,414 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2023-11-19 05:25:30,415 INFO L187 NwaCegarLoop]: Found error trace [2023-11-19 05:25:30,415 INFO L195 NwaCegarLoop]: trace histogram [12, 11, 11, 11, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1] [2023-11-19 05:25:30,436 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-11-19 05:25:30,635 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2023-11-19 05:25:30,636 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-19 05:25:30,636 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-19 05:25:30,636 INFO L85 PathProgramCache]: Analyzing trace with hash 1775712440, now seen corresponding path program 2 times [2023-11-19 05:25:30,637 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-19 05:25:30,637 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [582563684] [2023-11-19 05:25:30,637 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-19 05:25:30,637 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-19 05:25:30,666 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-19 05:25:30,668 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [368387581] [2023-11-19 05:25:30,669 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-19 05:25:30,669 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-19 05:25:30,669 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 [2023-11-19 05:25:30,670 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-19 05:25:30,687 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_39736793-42af-45a6-a7f1-e7203db5d8c5/bin/utaipan-verify-t7M7D8N6sZ/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process