./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench/hard2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version cf1a7837 Calling Ultimate with: /usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench/hard2.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 966f2b433cfe84d90040e5149c3cdda56fb59546e621a76bee869282a92c61d4 --- Real Ultimate output --- This is Ultimate 0.2.3-dev-cf1a783 [2023-11-12 00:43:16,159 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-12 00:43:16,285 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-12 00:43:16,298 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-12 00:43:16,299 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-12 00:43:16,339 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-12 00:43:16,340 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-12 00:43:16,340 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-12 00:43:16,342 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-12 00:43:16,347 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-12 00:43:16,347 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-12 00:43:16,348 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-12 00:43:16,348 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-12 00:43:16,350 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-12 00:43:16,351 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-12 00:43:16,351 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-12 00:43:16,351 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-12 00:43:16,352 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-12 00:43:16,352 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-12 00:43:16,353 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-12 00:43:16,353 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-12 00:43:16,354 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-12 00:43:16,355 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-12 00:43:16,356 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-12 00:43:16,356 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-12 00:43:16,357 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-12 00:43:16,357 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-12 00:43:16,357 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-12 00:43:16,358 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-12 00:43:16,358 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-12 00:43:16,360 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-12 00:43:16,360 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-12 00:43:16,360 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-12 00:43:16,361 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-12 00:43:16,361 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-12 00:43:16,361 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-12 00:43:16,362 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 00:43:16,362 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-12 00:43:16,362 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-12 00:43:16,362 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-12 00:43:16,363 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-12 00:43:16,363 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-12 00:43:16,363 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-12 00:43:16,364 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-12 00:43:16,364 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-12 00:43:16,365 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_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Taipan Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 966f2b433cfe84d90040e5149c3cdda56fb59546e621a76bee869282a92c61d4 [2023-11-12 00:43:16,657 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-12 00:43:16,693 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-12 00:43:16,696 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-12 00:43:16,697 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-12 00:43:16,698 INFO L274 PluginConnector]: CDTParser initialized [2023-11-12 00:43:16,700 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/../../sv-benchmarks/c/nla-digbench/hard2.c [2023-11-12 00:43:19,902 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-12 00:43:20,128 INFO L384 CDTParser]: Found 1 translation units. [2023-11-12 00:43:20,129 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/sv-benchmarks/c/nla-digbench/hard2.c [2023-11-12 00:43:20,142 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/data/24e49a466/ae1398b158a641afb1b763c656d95429/FLAG73d175927 [2023-11-12 00:43:20,156 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/data/24e49a466/ae1398b158a641afb1b763c656d95429 [2023-11-12 00:43:20,159 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-12 00:43:20,160 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-12 00:43:20,162 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-12 00:43:20,162 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-12 00:43:20,168 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-12 00:43:20,169 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 12:43:20" (1/1) ... [2023-11-12 00:43:20,170 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@38d3bdb5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:43:20, skipping insertion in model container [2023-11-12 00:43:20,170 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 12:43:20" (1/1) ... [2023-11-12 00:43:20,193 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-12 00:43:20,368 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_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/sv-benchmarks/c/nla-digbench/hard2.c[526,539] [2023-11-12 00:43:20,385 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 00:43:20,394 INFO L202 MainTranslator]: Completed pre-run [2023-11-12 00:43:20,408 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_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/sv-benchmarks/c/nla-digbench/hard2.c[526,539] [2023-11-12 00:43:20,422 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 00:43:20,437 INFO L206 MainTranslator]: Completed translation [2023-11-12 00:43:20,437 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:43:20 WrapperNode [2023-11-12 00:43:20,437 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-12 00:43:20,439 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-12 00:43:20,439 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-12 00:43:20,439 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-12 00:43:20,447 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:43:20" (1/1) ... [2023-11-12 00:43:20,459 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:43:20" (1/1) ... [2023-11-12 00:43:20,477 INFO L138 Inliner]: procedures = 14, calls = 22, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 60 [2023-11-12 00:43:20,477 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-12 00:43:20,478 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-12 00:43:20,478 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-12 00:43:20,478 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-12 00:43:20,488 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:43:20" (1/1) ... [2023-11-12 00:43:20,489 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:43:20" (1/1) ... [2023-11-12 00:43:20,496 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:43:20" (1/1) ... [2023-11-12 00:43:20,497 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:43:20" (1/1) ... [2023-11-12 00:43:20,500 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:43:20" (1/1) ... [2023-11-12 00:43:20,509 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:43:20" (1/1) ... [2023-11-12 00:43:20,510 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:43:20" (1/1) ... [2023-11-12 00:43:20,511 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:43:20" (1/1) ... [2023-11-12 00:43:20,513 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-12 00:43:20,514 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-12 00:43:20,514 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-12 00:43:20,514 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-12 00:43:20,515 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:43:20" (1/1) ... [2023-11-12 00:43:20,522 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 00:43:20,538 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:43:20,552 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-12 00:43:20,578 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-12 00:43:20,595 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-12 00:43:20,595 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-12 00:43:20,595 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-12 00:43:20,596 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-12 00:43:20,596 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-11-12 00:43:20,596 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-11-12 00:43:20,659 INFO L236 CfgBuilder]: Building ICFG [2023-11-12 00:43:20,661 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-12 00:43:20,820 INFO L277 CfgBuilder]: Performing block encoding [2023-11-12 00:43:20,891 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-12 00:43:20,891 INFO L302 CfgBuilder]: Removed 2 assume(true) statements. [2023-11-12 00:43:20,894 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 12:43:20 BoogieIcfgContainer [2023-11-12 00:43:20,894 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-12 00:43:20,908 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-12 00:43:20,908 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-12 00:43:20,912 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-12 00:43:20,912 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.11 12:43:20" (1/3) ... [2023-11-12 00:43:20,913 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@11a19bce and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 12:43:20, skipping insertion in model container [2023-11-12 00:43:20,914 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:43:20" (2/3) ... [2023-11-12 00:43:20,914 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@11a19bce and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 12:43:20, skipping insertion in model container [2023-11-12 00:43:20,914 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 12:43:20" (3/3) ... [2023-11-12 00:43:20,916 INFO L112 eAbstractionObserver]: Analyzing ICFG hard2.c [2023-11-12 00:43:20,937 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-12 00:43:20,938 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-12 00:43:20,983 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-12 00:43:20,990 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;@62976f63, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-12 00:43:20,990 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-12 00:43:20,994 INFO L276 IsEmpty]: Start isEmpty. Operand has 20 states, 10 states have (on average 1.6) internal successors, (16), 11 states have internal predecessors, (16), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2023-11-12 00:43:21,010 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2023-11-12 00:43:21,010 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:43:21,010 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2023-11-12 00:43:21,011 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:43:21,015 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:43:21,016 INFO L85 PathProgramCache]: Analyzing trace with hash -1133642604, now seen corresponding path program 1 times [2023-11-12 00:43:21,023 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:43:21,023 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [612786878] [2023-11-12 00:43:21,024 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:43:21,024 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:43:21,117 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:43:21,348 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-12 00:43:21,349 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:43:21,349 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [612786878] [2023-11-12 00:43:21,350 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [612786878] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:43:21,350 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:43:21,350 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-11-12 00:43:21,352 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1892562336] [2023-11-12 00:43:21,353 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:43:21,357 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:43:21,357 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:43:21,403 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:43:21,404 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-12 00:43:21,406 INFO L87 Difference]: Start difference. First operand has 20 states, 10 states have (on average 1.6) internal successors, (16), 11 states have internal predecessors, (16), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 5 states, 5 states have (on average 1.0) internal successors, (5), 3 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 00:43:21,506 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:43:21,506 INFO L93 Difference]: Finished difference Result 50 states and 87 transitions. [2023-11-12 00:43:21,508 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-12 00:43:21,509 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.0) internal successors, (5), 3 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 6 [2023-11-12 00:43:21,510 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:43:21,518 INFO L225 Difference]: With dead ends: 50 [2023-11-12 00:43:21,518 INFO L226 Difference]: Without dead ends: 28 [2023-11-12 00:43:21,521 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-11-12 00:43:21,526 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 10 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 71 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:43:21,527 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 71 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 00:43:21,545 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2023-11-12 00:43:21,569 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 22. [2023-11-12 00:43:21,570 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-11-12 00:43:21,574 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 28 transitions. [2023-11-12 00:43:21,576 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 28 transitions. Word has length 6 [2023-11-12 00:43:21,576 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:43:21,577 INFO L495 AbstractCegarLoop]: Abstraction has 22 states and 28 transitions. [2023-11-12 00:43:21,577 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.0) internal successors, (5), 3 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 00:43:21,577 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 28 transitions. [2023-11-12 00:43:21,579 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2023-11-12 00:43:21,579 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:43:21,579 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:43:21,580 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-12 00:43:21,580 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:43:21,581 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:43:21,581 INFO L85 PathProgramCache]: Analyzing trace with hash 372697474, now seen corresponding path program 1 times [2023-11-12 00:43:21,582 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:43:21,582 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [67524282] [2023-11-12 00:43:21,582 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:43:21,583 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:43:21,615 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:43:21,776 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-12 00:43:21,777 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:43:21,777 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [67524282] [2023-11-12 00:43:21,777 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [67524282] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:43:21,778 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:43:21,778 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-12 00:43:21,778 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2144060016] [2023-11-12 00:43:21,778 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:43:21,780 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:43:21,780 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:43:21,781 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:43:21,781 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-12 00:43:21,782 INFO L87 Difference]: Start difference. First operand 22 states and 28 transitions. Second operand has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-12 00:43:21,835 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:43:21,835 INFO L93 Difference]: Finished difference Result 34 states and 43 transitions. [2023-11-12 00:43:21,836 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-12 00:43:21,836 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2023-11-12 00:43:21,836 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:43:21,837 INFO L225 Difference]: With dead ends: 34 [2023-11-12 00:43:21,838 INFO L226 Difference]: Without dead ends: 32 [2023-11-12 00:43:21,838 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-11-12 00:43:21,840 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 8 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 67 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:43:21,841 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 67 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 00:43:21,842 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2023-11-12 00:43:21,852 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 26. [2023-11-12 00:43:21,852 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-11-12 00:43:21,856 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 31 transitions. [2023-11-12 00:43:21,856 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 31 transitions. Word has length 11 [2023-11-12 00:43:21,857 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:43:21,857 INFO L495 AbstractCegarLoop]: Abstraction has 26 states and 31 transitions. [2023-11-12 00:43:21,858 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-12 00:43:21,858 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 31 transitions. [2023-11-12 00:43:21,858 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2023-11-12 00:43:21,859 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:43:21,859 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:43:21,860 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-12 00:43:21,860 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:43:21,861 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:43:21,861 INFO L85 PathProgramCache]: Analyzing trace with hash -413140716, now seen corresponding path program 1 times [2023-11-12 00:43:21,861 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:43:21,862 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [926009476] [2023-11-12 00:43:21,862 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:43:21,862 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:43:21,878 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:43:21,879 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1599476172] [2023-11-12 00:43:21,879 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:43:21,880 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:43:21,880 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:43:21,886 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:43:21,902 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-12 00:43:21,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:43:21,966 INFO L262 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 19 conjunts are in the unsatisfiable core [2023-11-12 00:43:21,973 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:43:22,208 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-11-12 00:43:22,210 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:43:22,417 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-11-12 00:43:22,418 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:43:22,418 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [926009476] [2023-11-12 00:43:22,418 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:43:22,419 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1599476172] [2023-11-12 00:43:22,424 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1599476172] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:43:22,424 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1704035197] [2023-11-12 00:43:22,451 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2023-11-12 00:43:22,452 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:43:22,461 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:43:22,468 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:43:22,469 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:43:23,184 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 62 for LOIs [2023-11-12 00:43:23,236 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:43:23,637 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [1704035197] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:43:23,638 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:43:23,638 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [8, 7] total 15 [2023-11-12 00:43:23,639 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [350685491] [2023-11-12 00:43:23,639 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:43:23,640 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:43:23,640 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:43:23,640 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:43:23,641 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=158, Unknown=0, NotChecked=0, Total=210 [2023-11-12 00:43:23,641 INFO L87 Difference]: Start difference. First operand 26 states and 31 transitions. Second operand has 5 states, 5 states have (on average 1.4) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-11-12 00:43:23,791 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:43:23,791 INFO L93 Difference]: Finished difference Result 61 states and 75 transitions. [2023-11-12 00:43:23,791 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-12 00:43:23,792 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 16 [2023-11-12 00:43:23,792 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:43:23,793 INFO L225 Difference]: With dead ends: 61 [2023-11-12 00:43:23,793 INFO L226 Difference]: Without dead ends: 43 [2023-11-12 00:43:23,794 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 31 SyntacticMatches, 2 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 61 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=52, Invalid=158, Unknown=0, NotChecked=0, Total=210 [2023-11-12 00:43:23,796 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 3 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 52 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 29 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 52 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 00:43:23,796 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 29 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 52 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 00:43:23,798 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2023-11-12 00:43:23,810 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2023-11-12 00:43:23,810 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 26 states have (on average 1.1153846153846154) internal successors, (29), 27 states have internal predecessors, (29), 10 states have call successors, (10), 6 states have call predecessors, (10), 6 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-11-12 00:43:23,811 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 48 transitions. [2023-11-12 00:43:23,812 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 48 transitions. Word has length 16 [2023-11-12 00:43:23,812 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:43:23,812 INFO L495 AbstractCegarLoop]: Abstraction has 43 states and 48 transitions. [2023-11-12 00:43:23,812 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-11-12 00:43:23,813 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 48 transitions. [2023-11-12 00:43:23,814 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2023-11-12 00:43:23,814 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:43:23,814 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2023-11-12 00:43:23,823 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-12 00:43:24,020 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2023-11-12 00:43:24,020 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:43:24,021 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:43:24,021 INFO L85 PathProgramCache]: Analyzing trace with hash 1951602144, now seen corresponding path program 1 times [2023-11-12 00:43:24,021 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:43:24,021 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [464803498] [2023-11-12 00:43:24,022 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:43:24,022 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:43:24,042 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:43:24,048 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [308762562] [2023-11-12 00:43:24,048 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:43:24,048 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:43:24,049 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:43:24,050 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:43:24,074 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-12 00:43:24,122 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:43:24,124 INFO L262 TraceCheckSpWp]: Trace formula consists of 110 conjuncts, 23 conjunts are in the unsatisfiable core [2023-11-12 00:43:24,128 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:43:24,279 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 9 proven. 17 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2023-11-12 00:43:24,280 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:43:24,429 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 11 proven. 13 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2023-11-12 00:43:24,429 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:43:24,429 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [464803498] [2023-11-12 00:43:24,430 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:43:24,430 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [308762562] [2023-11-12 00:43:24,430 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [308762562] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:43:24,430 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [184238211] [2023-11-12 00:43:24,433 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2023-11-12 00:43:24,433 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:43:24,434 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:43:24,434 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:43:24,434 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:43:26,793 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-11-12 00:43:26,797 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:43:27,334 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '698#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:43:27,334 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:43:27,335 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:43:27,335 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7] total 13 [2023-11-12 00:43:27,335 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1363187723] [2023-11-12 00:43:27,335 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:43:27,336 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-11-12 00:43:27,336 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:43:27,337 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-11-12 00:43:27,337 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=247, Unknown=0, NotChecked=0, Total=306 [2023-11-12 00:43:27,337 INFO L87 Difference]: Start difference. First operand 43 states and 48 transitions. Second operand has 13 states, 13 states have (on average 1.6153846153846154) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 5 states have call successors, (9) [2023-11-12 00:43:27,542 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:43:27,543 INFO L93 Difference]: Finished difference Result 77 states and 98 transitions. [2023-11-12 00:43:27,543 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-12 00:43:27,543 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 1.6153846153846154) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 5 states have call successors, (9) Word has length 33 [2023-11-12 00:43:27,544 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:43:27,547 INFO L225 Difference]: With dead ends: 77 [2023-11-12 00:43:27,548 INFO L226 Difference]: Without dead ends: 64 [2023-11-12 00:43:27,548 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 81 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 62 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=68, Invalid=274, Unknown=0, NotChecked=0, Total=342 [2023-11-12 00:43:27,552 INFO L413 NwaCegarLoop]: 18 mSDtfsCounter, 26 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 114 mSolverCounterSat, 21 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 135 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 114 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-12 00:43:27,553 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 91 Invalid, 135 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 114 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-12 00:43:27,556 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2023-11-12 00:43:27,580 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 64. [2023-11-12 00:43:27,581 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 36 states have (on average 1.1111111111111112) internal successors, (40), 39 states have internal predecessors, (40), 20 states have call successors, (20), 7 states have call predecessors, (20), 7 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) [2023-11-12 00:43:27,583 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 78 transitions. [2023-11-12 00:43:27,584 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 78 transitions. Word has length 33 [2023-11-12 00:43:27,584 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:43:27,584 INFO L495 AbstractCegarLoop]: Abstraction has 64 states and 78 transitions. [2023-11-12 00:43:27,585 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 1.6153846153846154) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 5 states have call successors, (9) [2023-11-12 00:43:27,585 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 78 transitions. [2023-11-12 00:43:27,586 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2023-11-12 00:43:27,587 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:43:27,587 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:43:27,599 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-12 00:43:27,793 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2023-11-12 00:43:27,794 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:43:27,794 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:43:27,795 INFO L85 PathProgramCache]: Analyzing trace with hash 1133925795, now seen corresponding path program 1 times [2023-11-12 00:43:27,795 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:43:27,795 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1760961718] [2023-11-12 00:43:27,795 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:43:27,795 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:43:27,805 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:43:27,805 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1426729794] [2023-11-12 00:43:27,805 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:43:27,806 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:43:27,806 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:43:27,807 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:43:27,830 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-12 00:43:27,874 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:43:27,875 INFO L262 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 17 conjunts are in the unsatisfiable core [2023-11-12 00:43:27,880 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:43:27,998 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 11 proven. 16 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2023-11-12 00:43:27,998 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:43:28,168 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 13 proven. 16 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2023-11-12 00:43:28,172 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:43:28,173 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1760961718] [2023-11-12 00:43:28,173 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:43:28,173 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1426729794] [2023-11-12 00:43:28,173 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1426729794] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:43:28,173 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [914902586] [2023-11-12 00:43:28,178 INFO L159 IcfgInterpreter]: Started Sifa with 14 locations of interest [2023-11-12 00:43:28,178 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:43:28,179 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:43:28,179 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:43:28,186 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:43:30,474 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-11-12 00:43:30,478 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:43:30,982 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1167#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:43:30,982 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:43:30,982 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:43:30,982 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 11 [2023-11-12 00:43:30,982 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1820119779] [2023-11-12 00:43:30,982 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:43:30,983 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-11-12 00:43:30,983 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:43:30,984 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-11-12 00:43:30,984 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=222, Unknown=0, NotChecked=0, Total=272 [2023-11-12 00:43:30,984 INFO L87 Difference]: Start difference. First operand 64 states and 78 transitions. Second operand has 11 states, 11 states have (on average 2.1818181818181817) internal successors, (24), 10 states have internal predecessors, (24), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2023-11-12 00:43:31,116 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:43:31,116 INFO L93 Difference]: Finished difference Result 73 states and 88 transitions. [2023-11-12 00:43:31,117 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-11-12 00:43:31,117 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.1818181818181817) internal successors, (24), 10 states have internal predecessors, (24), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) Word has length 40 [2023-11-12 00:43:31,119 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:43:31,121 INFO L225 Difference]: With dead ends: 73 [2023-11-12 00:43:31,122 INFO L226 Difference]: Without dead ends: 71 [2023-11-12 00:43:31,122 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 103 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=59, Invalid=247, Unknown=0, NotChecked=0, Total=306 [2023-11-12 00:43:31,123 INFO L413 NwaCegarLoop]: 14 mSDtfsCounter, 19 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 78 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 72 SdHoareTripleChecker+Invalid, 86 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 78 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 00:43:31,123 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [24 Valid, 72 Invalid, 86 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 78 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 00:43:31,124 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2023-11-12 00:43:31,148 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 70. [2023-11-12 00:43:31,148 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 70 states, 40 states have (on average 1.125) internal successors, (45), 43 states have internal predecessors, (45), 21 states have call successors, (21), 8 states have call predecessors, (21), 8 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2023-11-12 00:43:31,150 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 85 transitions. [2023-11-12 00:43:31,150 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 85 transitions. Word has length 40 [2023-11-12 00:43:31,150 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:43:31,151 INFO L495 AbstractCegarLoop]: Abstraction has 70 states and 85 transitions. [2023-11-12 00:43:31,151 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.1818181818181817) internal successors, (24), 10 states have internal predecessors, (24), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2023-11-12 00:43:31,151 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 85 transitions. [2023-11-12 00:43:31,153 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2023-11-12 00:43:31,153 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:43:31,153 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:43:31,164 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-12 00:43:31,359 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:43:31,360 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:43:31,360 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:43:31,360 INFO L85 PathProgramCache]: Analyzing trace with hash 581212434, now seen corresponding path program 1 times [2023-11-12 00:43:31,360 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:43:31,361 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [401496783] [2023-11-12 00:43:31,361 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:43:31,361 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:43:31,370 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:43:31,371 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [288250336] [2023-11-12 00:43:31,371 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:43:31,371 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:43:31,371 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:43:31,372 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:43:31,388 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-12 00:43:31,449 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:43:31,451 INFO L262 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 31 conjunts are in the unsatisfiable core [2023-11-12 00:43:31,454 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:43:31,727 INFO L134 CoverageAnalysis]: Checked inductivity of 135 backedges. 15 proven. 29 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-11-12 00:43:31,727 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:43:34,252 INFO L134 CoverageAnalysis]: Checked inductivity of 135 backedges. 15 proven. 29 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-11-12 00:43:34,253 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:43:34,253 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [401496783] [2023-11-12 00:43:34,253 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:43:34,253 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [288250336] [2023-11-12 00:43:34,253 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [288250336] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:43:34,253 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1016848460] [2023-11-12 00:43:34,259 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-11-12 00:43:34,259 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:43:34,260 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:43:34,260 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:43:34,260 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:43:36,643 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-11-12 00:43:36,647 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:43:37,260 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1713#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:43:37,260 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:43:37,260 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:43:37,261 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2023-11-12 00:43:37,261 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1301933798] [2023-11-12 00:43:37,261 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:43:37,261 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-12 00:43:37,261 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:43:37,262 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-12 00:43:37,263 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=390, Unknown=0, NotChecked=0, Total=462 [2023-11-12 00:43:37,263 INFO L87 Difference]: Start difference. First operand 70 states and 85 transitions. Second operand has 15 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 13 states have internal predecessors, (29), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2023-11-12 00:43:42,463 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-12 00:43:44,466 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-12 00:43:46,841 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-12 00:43:46,906 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:43:46,906 INFO L93 Difference]: Finished difference Result 96 states and 108 transitions. [2023-11-12 00:43:46,906 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-11-12 00:43:46,907 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 13 states have internal predecessors, (29), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) Word has length 52 [2023-11-12 00:43:46,907 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:43:46,908 INFO L225 Difference]: With dead ends: 96 [2023-11-12 00:43:46,908 INFO L226 Difference]: Without dead ends: 94 [2023-11-12 00:43:46,909 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 160 GetRequests, 133 SyntacticMatches, 2 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 128 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=116, Invalid=586, Unknown=0, NotChecked=0, Total=702 [2023-11-12 00:43:46,910 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 29 mSDsluCounter, 121 mSDsCounter, 0 mSdLazyCounter, 194 mSolverCounterSat, 44 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 140 SdHoareTripleChecker+Invalid, 241 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 194 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 6.7s IncrementalHoareTripleChecker+Time [2023-11-12 00:43:46,911 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 140 Invalid, 241 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 194 Invalid, 3 Unknown, 0 Unchecked, 6.7s Time] [2023-11-12 00:43:46,911 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 94 states. [2023-11-12 00:43:46,943 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 94 to 92. [2023-11-12 00:43:46,943 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 56 states have (on average 1.0892857142857142) internal successors, (61), 60 states have internal predecessors, (61), 22 states have call successors, (22), 13 states have call predecessors, (22), 13 states have return successors, (20), 18 states have call predecessors, (20), 20 states have call successors, (20) [2023-11-12 00:43:46,944 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 103 transitions. [2023-11-12 00:43:46,945 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 103 transitions. Word has length 52 [2023-11-12 00:43:46,945 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:43:46,945 INFO L495 AbstractCegarLoop]: Abstraction has 92 states and 103 transitions. [2023-11-12 00:43:46,946 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 13 states have internal predecessors, (29), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2023-11-12 00:43:46,946 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 103 transitions. [2023-11-12 00:43:46,947 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2023-11-12 00:43:46,948 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:43:46,948 INFO L195 NwaCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:43:46,959 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-12 00:43:47,159 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2023-11-12 00:43:47,160 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:43:47,160 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:43:47,160 INFO L85 PathProgramCache]: Analyzing trace with hash 174642699, now seen corresponding path program 1 times [2023-11-12 00:43:47,160 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:43:47,161 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [771504754] [2023-11-12 00:43:47,161 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:43:47,161 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:43:47,170 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:43:47,170 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [945966682] [2023-11-12 00:43:47,170 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:43:47,171 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:43:47,171 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:43:47,172 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:43:47,183 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-12 00:43:47,234 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:43:47,236 INFO L262 TraceCheckSpWp]: Trace formula consists of 166 conjuncts, 33 conjunts are in the unsatisfiable core [2023-11-12 00:43:47,239 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:43:47,582 INFO L134 CoverageAnalysis]: Checked inductivity of 209 backedges. 19 proven. 37 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2023-11-12 00:43:47,584 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:43:48,281 INFO L134 CoverageAnalysis]: Checked inductivity of 209 backedges. 19 proven. 37 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2023-11-12 00:43:48,282 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:43:48,282 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [771504754] [2023-11-12 00:43:48,282 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:43:48,282 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [945966682] [2023-11-12 00:43:48,283 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [945966682] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:43:48,283 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [656107348] [2023-11-12 00:43:48,285 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-12 00:43:48,286 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:43:48,286 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:43:48,286 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:43:48,286 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:43:50,099 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-11-12 00:43:50,103 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:43:50,702 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2396#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:43:50,702 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:43:50,702 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:43:50,702 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2023-11-12 00:43:50,702 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1825765076] [2023-11-12 00:43:50,703 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:43:50,703 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-11-12 00:43:50,703 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:43:50,704 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-11-12 00:43:50,706 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=99, Invalid=501, Unknown=0, NotChecked=0, Total=600 [2023-11-12 00:43:50,706 INFO L87 Difference]: Start difference. First operand 92 states and 103 transitions. Second operand has 17 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 7 states have call successors, (20) [2023-11-12 00:43:51,303 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:43:51,303 INFO L93 Difference]: Finished difference Result 114 states and 133 transitions. [2023-11-12 00:43:51,304 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-11-12 00:43:51,305 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 7 states have call successors, (20) Word has length 63 [2023-11-12 00:43:51,306 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:43:51,307 INFO L225 Difference]: With dead ends: 114 [2023-11-12 00:43:51,307 INFO L226 Difference]: Without dead ends: 99 [2023-11-12 00:43:51,308 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 192 GetRequests, 162 SyntacticMatches, 3 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 189 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=137, Invalid=675, Unknown=0, NotChecked=0, Total=812 [2023-11-12 00:43:51,309 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 27 mSDsluCounter, 109 mSDsCounter, 0 mSdLazyCounter, 212 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 128 SdHoareTripleChecker+Invalid, 249 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 212 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-11-12 00:43:51,310 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 128 Invalid, 249 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 212 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-11-12 00:43:51,310 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2023-11-12 00:43:51,346 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 85. [2023-11-12 00:43:51,347 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 85 states, 53 states have (on average 1.0943396226415094) internal successors, (58), 55 states have internal predecessors, (58), 18 states have call successors, (18), 13 states have call predecessors, (18), 13 states have return successors, (17), 16 states have call predecessors, (17), 17 states have call successors, (17) [2023-11-12 00:43:51,348 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 85 states to 85 states and 93 transitions. [2023-11-12 00:43:51,348 INFO L78 Accepts]: Start accepts. Automaton has 85 states and 93 transitions. Word has length 63 [2023-11-12 00:43:51,348 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:43:51,349 INFO L495 AbstractCegarLoop]: Abstraction has 85 states and 93 transitions. [2023-11-12 00:43:51,349 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 7 states have call successors, (20) [2023-11-12 00:43:51,349 INFO L276 IsEmpty]: Start isEmpty. Operand 85 states and 93 transitions. [2023-11-12 00:43:51,350 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2023-11-12 00:43:51,351 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:43:51,351 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:43:51,357 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2023-11-12 00:43:51,556 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2023-11-12 00:43:51,556 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:43:51,557 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:43:51,557 INFO L85 PathProgramCache]: Analyzing trace with hash 204977288, now seen corresponding path program 1 times [2023-11-12 00:43:51,557 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:43:51,557 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [968441728] [2023-11-12 00:43:51,557 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:43:51,557 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:43:51,565 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:43:51,565 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [707115110] [2023-11-12 00:43:51,565 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:43:51,565 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:43:51,566 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:43:51,567 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:43:51,580 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-12 00:43:51,634 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:43:51,635 INFO L262 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 4 conjunts are in the unsatisfiable core [2023-11-12 00:43:51,638 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:43:51,693 INFO L134 CoverageAnalysis]: Checked inductivity of 303 backedges. 81 proven. 0 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2023-11-12 00:43:51,693 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 00:43:51,693 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:43:51,693 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [968441728] [2023-11-12 00:43:51,694 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:43:51,694 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [707115110] [2023-11-12 00:43:51,694 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [707115110] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:43:51,694 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:43:51,694 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-12 00:43:51,694 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [764120414] [2023-11-12 00:43:51,695 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:43:51,695 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:43:51,695 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:43:51,696 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:43:51,696 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2023-11-12 00:43:51,696 INFO L87 Difference]: Start difference. First operand 85 states and 93 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-11-12 00:43:51,762 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:43:51,763 INFO L93 Difference]: Finished difference Result 92 states and 99 transitions. [2023-11-12 00:43:51,763 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-12 00:43:51,763 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 73 [2023-11-12 00:43:51,764 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:43:51,765 INFO L225 Difference]: With dead ends: 92 [2023-11-12 00:43:51,765 INFO L226 Difference]: Without dead ends: 80 [2023-11-12 00:43:51,765 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2023-11-12 00:43:51,766 INFO L413 NwaCegarLoop]: 35 mSDtfsCounter, 3 mSDsluCounter, 40 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 75 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:43:51,767 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 75 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 00:43:51,767 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2023-11-12 00:43:51,792 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 80. [2023-11-12 00:43:51,793 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 80 states, 50 states have (on average 1.06) internal successors, (53), 51 states have internal predecessors, (53), 17 states have call successors, (17), 12 states have call predecessors, (17), 12 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2023-11-12 00:43:51,793 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 86 transitions. [2023-11-12 00:43:51,794 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 86 transitions. Word has length 73 [2023-11-12 00:43:51,794 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:43:51,794 INFO L495 AbstractCegarLoop]: Abstraction has 80 states and 86 transitions. [2023-11-12 00:43:51,795 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-11-12 00:43:51,795 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 86 transitions. [2023-11-12 00:43:51,796 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2023-11-12 00:43:51,796 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:43:51,796 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2023-11-12 00:43:51,807 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-12 00:43:52,002 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2023-11-12 00:43:52,003 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:43:52,003 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:43:52,003 INFO L85 PathProgramCache]: Analyzing trace with hash -2080478280, now seen corresponding path program 2 times [2023-11-12 00:43:52,003 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:43:52,003 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1928435336] [2023-11-12 00:43:52,003 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:43:52,003 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:43:52,017 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:43:52,019 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1931878375] [2023-11-12 00:43:52,019 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-12 00:43:52,020 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:43:52,020 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:43:52,021 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:43:52,038 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-12 00:43:52,088 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-11-12 00:43:52,088 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 00:43:52,090 INFO L262 TraceCheckSpWp]: Trace formula consists of 123 conjuncts, 31 conjunts are in the unsatisfiable core [2023-11-12 00:43:52,093 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:43:52,343 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 41 proven. 34 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-11-12 00:43:52,343 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:43:54,208 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 41 proven. 29 refuted. 0 times theorem prover too weak. 236 trivial. 0 not checked. [2023-11-12 00:43:54,209 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:43:54,209 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1928435336] [2023-11-12 00:43:54,209 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:43:54,209 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1931878375] [2023-11-12 00:43:54,209 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1931878375] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:43:54,210 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1245331068] [2023-11-12 00:43:54,212 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-11-12 00:43:54,212 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:43:54,212 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:43:54,213 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:43:54,213 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:43:55,990 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-11-12 00:43:55,993 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:43:56,551 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3625#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:43:56,551 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:43:56,551 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:43:56,552 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 17 [2023-11-12 00:43:56,552 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [493133648] [2023-11-12 00:43:56,552 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:43:56,553 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-11-12 00:43:56,553 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:43:56,554 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-11-12 00:43:56,554 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=101, Invalid=451, Unknown=0, NotChecked=0, Total=552 [2023-11-12 00:43:56,555 INFO L87 Difference]: Start difference. First operand 80 states and 86 transitions. Second operand has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 16 states have internal predecessors, (32), 9 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) [2023-11-12 00:44:01,774 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-12 00:44:03,777 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-12 00:44:05,870 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-12 00:44:08,223 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-12 00:44:10,225 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-12 00:44:10,290 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:44:10,290 INFO L93 Difference]: Finished difference Result 112 states and 130 transitions. [2023-11-12 00:44:10,291 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-11-12 00:44:10,291 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 16 states have internal predecessors, (32), 9 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) Word has length 74 [2023-11-12 00:44:10,291 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:44:10,293 INFO L225 Difference]: With dead ends: 112 [2023-11-12 00:44:10,293 INFO L226 Difference]: Without dead ends: 110 [2023-11-12 00:44:10,293 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 223 GetRequests, 196 SyntacticMatches, 3 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 157 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=124, Invalid=526, Unknown=0, NotChecked=0, Total=650 [2023-11-12 00:44:10,294 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 26 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 206 mSolverCounterSat, 33 mSolverCounterUnsat, 5 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 10.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 244 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 206 IncrementalHoareTripleChecker+Invalid, 5 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 10.7s IncrementalHoareTripleChecker+Time [2023-11-12 00:44:10,295 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 124 Invalid, 244 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 206 Invalid, 5 Unknown, 0 Unchecked, 10.7s Time] [2023-11-12 00:44:10,295 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2023-11-12 00:44:10,338 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 108. [2023-11-12 00:44:10,338 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 108 states, 65 states have (on average 1.0769230769230769) internal successors, (70), 67 states have internal predecessors, (70), 28 states have call successors, (28), 14 states have call predecessors, (28), 14 states have return successors, (27), 26 states have call predecessors, (27), 27 states have call successors, (27) [2023-11-12 00:44:10,339 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 108 states to 108 states and 125 transitions. [2023-11-12 00:44:10,340 INFO L78 Accepts]: Start accepts. Automaton has 108 states and 125 transitions. Word has length 74 [2023-11-12 00:44:10,340 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:44:10,340 INFO L495 AbstractCegarLoop]: Abstraction has 108 states and 125 transitions. [2023-11-12 00:44:10,341 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 16 states have internal predecessors, (32), 9 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) [2023-11-12 00:44:10,341 INFO L276 IsEmpty]: Start isEmpty. Operand 108 states and 125 transitions. [2023-11-12 00:44:10,342 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2023-11-12 00:44:10,342 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:44:10,342 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1] [2023-11-12 00:44:10,348 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-12 00:44:10,548 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:44:10,548 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:44:10,549 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:44:10,550 INFO L85 PathProgramCache]: Analyzing trace with hash -72875315, now seen corresponding path program 3 times [2023-11-12 00:44:10,550 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:44:10,550 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1332548019] [2023-11-12 00:44:10,550 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:44:10,551 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:44:10,572 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:44:10,582 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [221691882] [2023-11-12 00:44:10,582 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-12 00:44:10,582 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:44:10,583 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:44:10,584 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:44:10,606 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_24f2fc94-e443-4710-bcbf-2ac2ca1c77e5/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-12 00:44:10,674 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-12 00:44:10,674 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 00:44:10,676 INFO L262 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 51 conjunts are in the unsatisfiable core [2023-11-12 00:44:10,679 INFO L285 TraceCheckSpWp]: Computing forward predicates...