./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound10.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version cf1a7837 Calling Ultimate with: /usr/lib/jvm/java-11-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/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_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound10.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/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_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/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 8d4ed8c57ce722a6c7368f844e0bd557207245c570ed48ded2021df85adb4676 --- Real Ultimate output --- This is Ultimate 0.2.3-dev-cf1a783 [2023-11-12 00:09:25,269 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-12 00:09:25,345 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-12 00:09:25,351 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-12 00:09:25,351 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-12 00:09:25,382 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-12 00:09:25,383 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-12 00:09:25,383 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-12 00:09:25,384 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-12 00:09:25,385 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-12 00:09:25,385 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-12 00:09:25,386 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-12 00:09:25,387 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-12 00:09:25,387 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-12 00:09:25,388 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-12 00:09:25,388 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-12 00:09:25,389 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-12 00:09:25,389 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-12 00:09:25,390 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-12 00:09:25,391 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-12 00:09:25,391 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-12 00:09:25,392 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-12 00:09:25,393 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-12 00:09:25,393 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-12 00:09:25,394 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-12 00:09:25,394 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-12 00:09:25,394 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-12 00:09:25,395 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-12 00:09:25,395 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-12 00:09:25,396 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-12 00:09:25,396 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-12 00:09:25,397 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-12 00:09:25,397 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-12 00:09:25,398 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-12 00:09:25,398 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-12 00:09:25,399 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-12 00:09:25,399 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 00:09:25,400 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-12 00:09:25,400 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-12 00:09:25,400 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-12 00:09:25,401 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-12 00:09:25,401 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-12 00:09:25,402 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-12 00:09:25,402 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-12 00:09:25,403 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-12 00:09:25,403 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_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/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_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/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 -> 8d4ed8c57ce722a6c7368f844e0bd557207245c570ed48ded2021df85adb4676 [2023-11-12 00:09:25,701 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-12 00:09:25,738 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-12 00:09:25,741 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-12 00:09:25,742 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-12 00:09:25,743 INFO L274 PluginConnector]: CDTParser initialized [2023-11-12 00:09:25,744 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/../../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound10.c [2023-11-12 00:09:28,921 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-12 00:09:29,137 INFO L384 CDTParser]: Found 1 translation units. [2023-11-12 00:09:29,138 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound10.c [2023-11-12 00:09:29,144 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/data/49a0b3181/5eb77ff1c08d4ffab70ae324ab3bd2cc/FLAGb4401fcc4 [2023-11-12 00:09:29,159 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/data/49a0b3181/5eb77ff1c08d4ffab70ae324ab3bd2cc [2023-11-12 00:09:29,162 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-12 00:09:29,164 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-12 00:09:29,165 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-12 00:09:29,166 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-12 00:09:29,175 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-12 00:09:29,176 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 12:09:29" (1/1) ... [2023-11-12 00:09:29,177 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3d2f6035 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:09:29, skipping insertion in model container [2023-11-12 00:09:29,177 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 12:09:29" (1/1) ... [2023-11-12 00:09:29,200 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-12 00:09:29,379 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_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound10.c[588,601] [2023-11-12 00:09:29,403 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 00:09:29,415 INFO L202 MainTranslator]: Completed pre-run [2023-11-12 00:09:29,428 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_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_unwindbound10.c[588,601] [2023-11-12 00:09:29,445 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 00:09:29,467 INFO L206 MainTranslator]: Completed translation [2023-11-12 00:09:29,468 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:09:29 WrapperNode [2023-11-12 00:09:29,473 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-12 00:09:29,474 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-12 00:09:29,475 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-12 00:09:29,475 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-12 00:09:29,483 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:09:29" (1/1) ... [2023-11-12 00:09:29,502 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:09:29" (1/1) ... [2023-11-12 00:09:29,532 INFO L138 Inliner]: procedures = 14, calls = 18, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 49 [2023-11-12 00:09:29,532 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-12 00:09:29,533 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-12 00:09:29,533 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-12 00:09:29,534 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-12 00:09:29,542 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:09:29" (1/1) ... [2023-11-12 00:09:29,543 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:09:29" (1/1) ... [2023-11-12 00:09:29,544 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:09:29" (1/1) ... [2023-11-12 00:09:29,545 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:09:29" (1/1) ... [2023-11-12 00:09:29,548 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:09:29" (1/1) ... [2023-11-12 00:09:29,552 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:09:29" (1/1) ... [2023-11-12 00:09:29,553 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:09:29" (1/1) ... [2023-11-12 00:09:29,554 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:09:29" (1/1) ... [2023-11-12 00:09:29,556 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-12 00:09:29,557 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-12 00:09:29,558 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-12 00:09:29,558 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-12 00:09:29,559 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:09:29" (1/1) ... [2023-11-12 00:09:29,573 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 00:09:29,586 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:09:29,604 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/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:09:29,631 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/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:09:29,656 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-12 00:09:29,656 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-12 00:09:29,656 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-12 00:09:29,657 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-12 00:09:29,657 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-11-12 00:09:29,657 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-11-12 00:09:29,720 INFO L236 CfgBuilder]: Building ICFG [2023-11-12 00:09:29,722 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-12 00:09:29,908 INFO L277 CfgBuilder]: Performing block encoding [2023-11-12 00:09:29,925 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-12 00:09:29,926 INFO L302 CfgBuilder]: Removed 1 assume(true) statements. [2023-11-12 00:09:29,928 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 12:09:29 BoogieIcfgContainer [2023-11-12 00:09:29,929 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-12 00:09:29,932 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-12 00:09:29,932 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-12 00:09:29,935 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-12 00:09:29,936 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.11 12:09:29" (1/3) ... [2023-11-12 00:09:29,936 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@21adad58 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 12:09:29, skipping insertion in model container [2023-11-12 00:09:29,937 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:09:29" (2/3) ... [2023-11-12 00:09:29,937 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@21adad58 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 12:09:29, skipping insertion in model container [2023-11-12 00:09:29,937 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 12:09:29" (3/3) ... [2023-11-12 00:09:29,939 INFO L112 eAbstractionObserver]: Analyzing ICFG cohencu-ll_unwindbound10.c [2023-11-12 00:09:29,959 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-12 00:09:29,960 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-12 00:09:30,011 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-12 00:09:30,019 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;@258f32ee, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-12 00:09:30,019 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-12 00:09:30,023 INFO L276 IsEmpty]: Start isEmpty. Operand has 23 states, 9 states have (on average 1.5555555555555556) internal successors, (14), 10 states have internal predecessors, (14), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2023-11-12 00:09:30,030 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2023-11-12 00:09:30,031 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:09:30,031 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2023-11-12 00:09:30,032 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:09:30,038 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:09:30,061 INFO L85 PathProgramCache]: Analyzing trace with hash -1379524608, now seen corresponding path program 1 times [2023-11-12 00:09:30,082 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:09:30,092 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2050600241] [2023-11-12 00:09:30,092 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:09:30,092 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:09:30,194 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:09:30,242 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:09:30,242 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:09:30,243 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2050600241] [2023-11-12 00:09:30,244 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2050600241] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:09:30,244 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:09:30,244 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-12 00:09:30,246 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [270580088] [2023-11-12 00:09:30,247 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:09:30,251 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-11-12 00:09:30,252 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:09:30,280 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-11-12 00:09:30,281 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-11-12 00:09:30,283 INFO L87 Difference]: Start difference. First operand has 23 states, 9 states have (on average 1.5555555555555556) internal successors, (14), 10 states have internal predecessors, (14), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 00:09:30,328 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:09:30,328 INFO L93 Difference]: Finished difference Result 45 states and 82 transitions. [2023-11-12 00:09:30,329 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-11-12 00:09:30,331 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 6 [2023-11-12 00:09:30,332 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:09:30,339 INFO L225 Difference]: With dead ends: 45 [2023-11-12 00:09:30,339 INFO L226 Difference]: Without dead ends: 21 [2023-11-12 00:09:30,342 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-11-12 00:09:30,346 INFO L413 NwaCegarLoop]: 32 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 32 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:09:30,347 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 32 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 00:09:30,360 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2023-11-12 00:09:30,378 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2023-11-12 00:09:30,379 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 8 states have (on average 1.375) internal successors, (11), 9 states have internal predecessors, (11), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2023-11-12 00:09:30,381 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 32 transitions. [2023-11-12 00:09:30,383 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 32 transitions. Word has length 6 [2023-11-12 00:09:30,383 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:09:30,384 INFO L495 AbstractCegarLoop]: Abstraction has 21 states and 32 transitions. [2023-11-12 00:09:30,384 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 00:09:30,384 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 32 transitions. [2023-11-12 00:09:30,385 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-11-12 00:09:30,385 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:09:30,385 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:09:30,385 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-12 00:09:30,386 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:09:30,387 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:09:30,387 INFO L85 PathProgramCache]: Analyzing trace with hash -345068235, now seen corresponding path program 1 times [2023-11-12 00:09:30,387 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:09:30,388 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1625733203] [2023-11-12 00:09:30,388 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:09:30,388 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:09:30,407 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:09:30,498 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:09:30,498 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:09:30,499 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1625733203] [2023-11-12 00:09:30,499 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1625733203] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:09:30,499 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:09:30,499 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-12 00:09:30,500 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [54051979] [2023-11-12 00:09:30,500 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:09:30,501 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-12 00:09:30,501 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:09:30,502 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-12 00:09:30,503 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-12 00:09:30,503 INFO L87 Difference]: Start difference. First operand 21 states and 32 transitions. Second operand has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 00:09:30,529 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:09:30,529 INFO L93 Difference]: Finished difference Result 35 states and 51 transitions. [2023-11-12 00:09:30,530 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-12 00:09:30,530 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2023-11-12 00:09:30,531 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:09:30,531 INFO L225 Difference]: With dead ends: 35 [2023-11-12 00:09:30,532 INFO L226 Difference]: Without dead ends: 23 [2023-11-12 00:09:30,533 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-12 00:09:30,534 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 0 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 86 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:09:30,535 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 86 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 00:09:30,536 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2023-11-12 00:09:30,544 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2023-11-12 00:09:30,544 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2023-11-12 00:09:30,546 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 34 transitions. [2023-11-12 00:09:30,547 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 34 transitions. Word has length 7 [2023-11-12 00:09:30,547 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:09:30,547 INFO L495 AbstractCegarLoop]: Abstraction has 23 states and 34 transitions. [2023-11-12 00:09:30,547 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 00:09:30,547 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 34 transitions. [2023-11-12 00:09:30,548 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-11-12 00:09:30,548 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:09:30,548 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:09:30,548 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-12 00:09:30,549 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:09:30,549 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:09:30,549 INFO L85 PathProgramCache]: Analyzing trace with hash -343519103, now seen corresponding path program 1 times [2023-11-12 00:09:30,550 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:09:30,550 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [326151458] [2023-11-12 00:09:30,550 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:09:30,550 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:09:30,570 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:09:30,745 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:09:30,745 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:09:30,746 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [326151458] [2023-11-12 00:09:30,746 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [326151458] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:09:30,746 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:09:30,747 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-11-12 00:09:30,747 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [72135799] [2023-11-12 00:09:30,747 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:09:30,748 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:09:30,748 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:09:30,749 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:09:30,749 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-12 00:09:30,750 INFO L87 Difference]: Start difference. First operand 23 states and 34 transitions. Second operand has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 00:09:30,842 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:09:30,842 INFO L93 Difference]: Finished difference Result 29 states and 39 transitions. [2023-11-12 00:09:30,842 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-12 00:09:30,843 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2023-11-12 00:09:30,843 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:09:30,845 INFO L225 Difference]: With dead ends: 29 [2023-11-12 00:09:30,845 INFO L226 Difference]: Without dead ends: 27 [2023-11-12 00:09:30,846 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-11-12 00:09:30,849 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 8 mSDsluCounter, 52 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 77 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 00:09:30,851 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 77 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 00:09:30,854 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2023-11-12 00:09:30,882 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2023-11-12 00:09:30,884 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 14 states have internal predecessors, (16), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2023-11-12 00:09:30,886 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 37 transitions. [2023-11-12 00:09:30,887 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 37 transitions. Word has length 7 [2023-11-12 00:09:30,887 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:09:30,887 INFO L495 AbstractCegarLoop]: Abstraction has 27 states and 37 transitions. [2023-11-12 00:09:30,887 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 00:09:30,888 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 37 transitions. [2023-11-12 00:09:30,888 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2023-11-12 00:09:30,888 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:09:30,888 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:09:30,889 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2023-11-12 00:09:30,889 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:09:30,890 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:09:30,890 INFO L85 PathProgramCache]: Analyzing trace with hash -875596316, now seen corresponding path program 1 times [2023-11-12 00:09:30,890 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:09:30,890 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1417317060] [2023-11-12 00:09:30,891 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:09:30,891 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:09:30,932 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:09:30,932 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1438746401] [2023-11-12 00:09:30,933 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:09:30,933 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:09:30,933 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:09:30,946 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:09:30,980 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-12 00:09:31,043 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:09:31,055 INFO L262 TraceCheckSpWp]: Trace formula consists of 56 conjuncts, 17 conjunts are in the unsatisfiable core [2023-11-12 00:09:31,061 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:09:31,250 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-12 00:09:31,250 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:09:31,462 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-12 00:09:31,463 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:09:31,463 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1417317060] [2023-11-12 00:09:31,464 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:09:31,464 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1438746401] [2023-11-12 00:09:31,464 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1438746401] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:09:31,465 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1305634994] [2023-11-12 00:09:31,496 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2023-11-12 00:09:31,496 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:09:31,500 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:09:31,506 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:09:31,506 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:09:32,015 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 48 for LOIs [2023-11-12 00:09:32,123 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:09:32,708 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [1305634994] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:09:32,708 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:09:32,709 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [8, 7] total 17 [2023-11-12 00:09:32,709 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [884183540] [2023-11-12 00:09:32,710 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:09:32,712 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-11-12 00:09:32,713 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:09:32,714 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-11-12 00:09:32,715 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2023-11-12 00:09:32,715 INFO L87 Difference]: Start difference. First operand 27 states and 37 transitions. Second operand has 7 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (2), 1 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:09:33,123 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:09:33,123 INFO L93 Difference]: Finished difference Result 49 states and 68 transitions. [2023-11-12 00:09:33,124 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-11-12 00:09:33,124 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2023-11-12 00:09:33,124 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:09:33,125 INFO L225 Difference]: With dead ends: 49 [2023-11-12 00:09:33,125 INFO L226 Difference]: Without dead ends: 41 [2023-11-12 00:09:33,126 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 18 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 74 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2023-11-12 00:09:33,127 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 1 mSDsluCounter, 44 mSDsCounter, 0 mSdLazyCounter, 111 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 69 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 111 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-12 00:09:33,128 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 69 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 111 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-12 00:09:33,129 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2023-11-12 00:09:33,145 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2023-11-12 00:09:33,145 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 20 states have (on average 1.15) internal successors, (23), 21 states have internal predecessors, (23), 16 states have call successors, (16), 4 states have call predecessors, (16), 4 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2023-11-12 00:09:33,147 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 54 transitions. [2023-11-12 00:09:33,147 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 54 transitions. Word has length 12 [2023-11-12 00:09:33,147 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:09:33,148 INFO L495 AbstractCegarLoop]: Abstraction has 41 states and 54 transitions. [2023-11-12 00:09:33,148 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (2), 1 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:09:33,148 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 54 transitions. [2023-11-12 00:09:33,150 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2023-11-12 00:09:33,150 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:09:33,150 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:09:33,159 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-12 00:09:33,355 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:09:33,356 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:09:33,356 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:09:33,357 INFO L85 PathProgramCache]: Analyzing trace with hash 1666200982, now seen corresponding path program 1 times [2023-11-12 00:09:33,357 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:09:33,357 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [989589042] [2023-11-12 00:09:33,357 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:09:33,357 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:09:33,371 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:09:33,371 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1170159170] [2023-11-12 00:09:33,372 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:09:33,372 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:09:33,372 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:09:33,373 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:09:33,392 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-12 00:09:33,450 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:09:33,451 INFO L262 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 5 conjunts are in the unsatisfiable core [2023-11-12 00:09:33,454 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:09:33,516 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 30 proven. 2 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2023-11-12 00:09:33,517 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:09:33,582 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 12 proven. 2 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2023-11-12 00:09:33,583 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:09:33,583 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [989589042] [2023-11-12 00:09:33,583 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:09:33,584 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1170159170] [2023-11-12 00:09:33,585 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1170159170] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:09:33,585 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1209447606] [2023-11-12 00:09:33,589 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-12 00:09:33,589 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:09:33,590 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:09:33,590 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:09:33,591 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:09:35,633 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-12 00:09:35,638 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:09:35,985 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '788#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:09:35,986 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:09:35,986 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:09:35,986 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5] total 8 [2023-11-12 00:09:35,986 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [917115784] [2023-11-12 00:09:35,987 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:09:35,987 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-11-12 00:09:35,987 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:09:35,988 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-11-12 00:09:35,988 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=181, Unknown=0, NotChecked=0, Total=240 [2023-11-12 00:09:35,989 INFO L87 Difference]: Start difference. First operand 41 states and 54 transitions. Second operand has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2023-11-12 00:09:36,195 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:09:36,195 INFO L93 Difference]: Finished difference Result 107 states and 144 transitions. [2023-11-12 00:09:36,196 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-12 00:09:36,196 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 40 [2023-11-12 00:09:36,196 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:09:36,198 INFO L225 Difference]: With dead ends: 107 [2023-11-12 00:09:36,198 INFO L226 Difference]: Without dead ends: 91 [2023-11-12 00:09:36,199 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 103 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 102 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=82, Invalid=260, Unknown=0, NotChecked=0, Total=342 [2023-11-12 00:09:36,200 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 51 mSDsluCounter, 108 mSDsCounter, 0 mSdLazyCounter, 82 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 51 SdHoareTripleChecker+Valid, 137 SdHoareTripleChecker+Invalid, 83 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 82 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 00:09:36,200 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [51 Valid, 137 Invalid, 83 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 82 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 00:09:36,201 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2023-11-12 00:09:36,224 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 87. [2023-11-12 00:09:36,225 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 87 states, 40 states have (on average 1.175) internal successors, (47), 43 states have internal predecessors, (47), 38 states have call successors, (38), 8 states have call predecessors, (38), 8 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2023-11-12 00:09:36,227 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 120 transitions. [2023-11-12 00:09:36,228 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 120 transitions. Word has length 40 [2023-11-12 00:09:36,228 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:09:36,228 INFO L495 AbstractCegarLoop]: Abstraction has 87 states and 120 transitions. [2023-11-12 00:09:36,228 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2023-11-12 00:09:36,229 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 120 transitions. [2023-11-12 00:09:36,230 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2023-11-12 00:09:36,230 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:09:36,230 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:09:36,243 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-12 00:09:36,435 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:09:36,436 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:09:36,436 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:09:36,436 INFO L85 PathProgramCache]: Analyzing trace with hash -2136650998, now seen corresponding path program 1 times [2023-11-12 00:09:36,436 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:09:36,437 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [200676872] [2023-11-12 00:09:36,437 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:09:36,437 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:09:36,457 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:09:36,469 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [196672770] [2023-11-12 00:09:36,469 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:09:36,469 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:09:36,469 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:09:36,470 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:09:36,493 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-12 00:09:36,542 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:09:36,544 INFO L262 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 21 conjunts are in the unsatisfiable core [2023-11-12 00:09:36,547 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:09:36,675 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 11 proven. 20 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2023-11-12 00:09:36,676 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:09:36,880 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 14 proven. 17 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2023-11-12 00:09:36,880 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:09:36,881 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [200676872] [2023-11-12 00:09:36,881 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:09:36,882 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [196672770] [2023-11-12 00:09:36,882 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [196672770] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:09:36,884 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1920798388] [2023-11-12 00:09:36,889 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-11-12 00:09:36,889 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:09:36,889 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:09:36,890 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:09:36,890 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:09:38,424 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-12 00:09:38,432 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:09:38,878 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1353#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:09:38,878 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:09:38,878 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:09:38,878 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2023-11-12 00:09:38,878 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1809841141] [2023-11-12 00:09:38,878 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:09:38,879 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-11-12 00:09:38,879 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:09:38,880 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-11-12 00:09:38,880 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=338, Unknown=0, NotChecked=0, Total=420 [2023-11-12 00:09:38,880 INFO L87 Difference]: Start difference. First operand 87 states and 120 transitions. Second operand has 13 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 5 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2023-11-12 00:09:39,281 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:09:39,281 INFO L93 Difference]: Finished difference Result 105 states and 136 transitions. [2023-11-12 00:09:39,282 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-12 00:09:39,282 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 5 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) Word has length 40 [2023-11-12 00:09:39,283 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:09:39,284 INFO L225 Difference]: With dead ends: 105 [2023-11-12 00:09:39,284 INFO L226 Difference]: Without dead ends: 103 [2023-11-12 00:09:39,285 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 122 GetRequests, 97 SyntacticMatches, 2 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 168 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=114, Invalid=486, Unknown=0, NotChecked=0, Total=600 [2023-11-12 00:09:39,286 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 25 mSDsluCounter, 118 mSDsCounter, 0 mSdLazyCounter, 167 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 220 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 167 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-12 00:09:39,287 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 141 Invalid, 220 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 167 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-12 00:09:39,287 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2023-11-12 00:09:39,319 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 103. [2023-11-12 00:09:39,320 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 52 states have (on average 1.1346153846153846) internal successors, (59), 55 states have internal predecessors, (59), 38 states have call successors, (38), 12 states have call predecessors, (38), 12 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2023-11-12 00:09:39,322 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 132 transitions. [2023-11-12 00:09:39,323 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 132 transitions. Word has length 40 [2023-11-12 00:09:39,323 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:09:39,323 INFO L495 AbstractCegarLoop]: Abstraction has 103 states and 132 transitions. [2023-11-12 00:09:39,324 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 5 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2023-11-12 00:09:39,324 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 132 transitions. [2023-11-12 00:09:39,325 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2023-11-12 00:09:39,325 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:09:39,326 INFO L195 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:09:39,335 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-12 00:09:39,531 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2023-11-12 00:09:39,532 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:09:39,532 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:09:39,532 INFO L85 PathProgramCache]: Analyzing trace with hash 1054982331, now seen corresponding path program 2 times [2023-11-12 00:09:39,532 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:09:39,533 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [422557317] [2023-11-12 00:09:39,533 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:09:39,533 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:09:39,545 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:09:39,545 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1896929927] [2023-11-12 00:09:39,545 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-12 00:09:39,545 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:09:39,546 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:09:39,547 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:09:39,559 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-12 00:09:39,615 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-11-12 00:09:39,615 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 00:09:39,616 INFO L262 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 16 conjunts are in the unsatisfiable core [2023-11-12 00:09:39,619 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:09:39,713 INFO L134 CoverageAnalysis]: Checked inductivity of 103 backedges. 14 proven. 5 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2023-11-12 00:09:39,713 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:09:39,828 INFO L134 CoverageAnalysis]: Checked inductivity of 103 backedges. 14 proven. 5 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2023-11-12 00:09:39,828 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:09:39,829 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [422557317] [2023-11-12 00:09:39,829 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:09:39,829 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1896929927] [2023-11-12 00:09:39,829 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1896929927] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:09:39,829 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [214684902] [2023-11-12 00:09:39,832 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-11-12 00:09:39,832 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:09:39,832 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:09:39,833 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:09:39,833 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:09:41,277 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-12 00:09:41,283 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:09:41,727 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1961#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:09:41,727 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:09:41,728 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:09:41,728 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2023-11-12 00:09:41,728 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1759916498] [2023-11-12 00:09:41,728 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:09:41,729 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-11-12 00:09:41,729 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:09:41,730 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-11-12 00:09:41,730 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=246, Unknown=0, NotChecked=0, Total=306 [2023-11-12 00:09:41,730 INFO L87 Difference]: Start difference. First operand 103 states and 132 transitions. Second operand has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (16), 3 states have call predecessors, (16), 1 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2023-11-12 00:09:41,905 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:09:41,905 INFO L93 Difference]: Finished difference Result 117 states and 143 transitions. [2023-11-12 00:09:41,906 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-11-12 00:09:41,906 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (16), 3 states have call predecessors, (16), 1 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 45 [2023-11-12 00:09:41,907 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:09:41,908 INFO L225 Difference]: With dead ends: 117 [2023-11-12 00:09:41,909 INFO L226 Difference]: Without dead ends: 115 [2023-11-12 00:09:41,909 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 115 SyntacticMatches, 2 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 91 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=66, Invalid=276, Unknown=0, NotChecked=0, Total=342 [2023-11-12 00:09:41,910 INFO L413 NwaCegarLoop]: 39 mSDtfsCounter, 8 mSDsluCounter, 175 mSDsCounter, 0 mSdLazyCounter, 109 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 214 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 109 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 00:09:41,911 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 214 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 109 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 00:09:41,912 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states. [2023-11-12 00:09:41,940 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 115. [2023-11-12 00:09:41,941 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 115 states, 61 states have (on average 1.1147540983606556) internal successors, (68), 64 states have internal predecessors, (68), 38 states have call successors, (38), 15 states have call predecessors, (38), 15 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2023-11-12 00:09:41,943 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 115 states to 115 states and 141 transitions. [2023-11-12 00:09:41,943 INFO L78 Accepts]: Start accepts. Automaton has 115 states and 141 transitions. Word has length 45 [2023-11-12 00:09:41,944 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:09:41,944 INFO L495 AbstractCegarLoop]: Abstraction has 115 states and 141 transitions. [2023-11-12 00:09:41,944 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (16), 3 states have call predecessors, (16), 1 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2023-11-12 00:09:41,944 INFO L276 IsEmpty]: Start isEmpty. Operand 115 states and 141 transitions. [2023-11-12 00:09:41,945 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2023-11-12 00:09:41,945 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:09:41,946 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:09:41,957 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-12 00:09:42,157 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2023-11-12 00:09:42,157 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:09:42,158 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:09:42,158 INFO L85 PathProgramCache]: Analyzing trace with hash -615691926, now seen corresponding path program 3 times [2023-11-12 00:09:42,158 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:09:42,158 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1139623084] [2023-11-12 00:09:42,158 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:09:42,158 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:09:42,170 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:09:42,170 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1702025949] [2023-11-12 00:09:42,170 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-12 00:09:42,171 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:09:42,171 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:09:42,172 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:09:42,195 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-12 00:09:42,245 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-12 00:09:42,245 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 00:09:42,247 INFO L262 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 23 conjunts are in the unsatisfiable core [2023-11-12 00:09:42,249 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:09:42,391 INFO L134 CoverageAnalysis]: Checked inductivity of 134 backedges. 18 proven. 25 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-11-12 00:09:42,391 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:09:42,905 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:09:42,905 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1139623084] [2023-11-12 00:09:42,905 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:09:42,905 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1702025949] [2023-11-12 00:09:42,905 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1702025949] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:09:42,905 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1645648932] [2023-11-12 00:09:42,907 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-11-12 00:09:42,908 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:09:42,908 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:09:42,908 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:09:42,908 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:09:44,232 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-12 00:09:44,237 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:09:44,667 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2592#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:09:44,667 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:09:44,667 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-12 00:09:44,667 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2023-11-12 00:09:44,668 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1494128791] [2023-11-12 00:09:44,668 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-12 00:09:44,668 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-11-12 00:09:44,668 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:09:44,669 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-11-12 00:09:44,669 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=306, Unknown=0, NotChecked=0, Total=380 [2023-11-12 00:09:44,669 INFO L87 Difference]: Start difference. First operand 115 states and 141 transitions. Second operand has 8 states, 8 states have (on average 1.875) internal successors, (15), 7 states have internal predecessors, (15), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2023-11-12 00:09:44,901 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:09:44,901 INFO L93 Difference]: Finished difference Result 125 states and 149 transitions. [2023-11-12 00:09:44,901 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-11-12 00:09:44,901 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 1.875) internal successors, (15), 7 states have internal predecessors, (15), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 50 [2023-11-12 00:09:44,902 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:09:44,903 INFO L225 Difference]: With dead ends: 125 [2023-11-12 00:09:44,903 INFO L226 Difference]: Without dead ends: 120 [2023-11-12 00:09:44,904 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 117 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 123 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=88, Invalid=374, Unknown=0, NotChecked=0, Total=462 [2023-11-12 00:09:44,905 INFO L413 NwaCegarLoop]: 26 mSDtfsCounter, 11 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 144 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 156 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 144 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-12 00:09:44,905 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 112 Invalid, 156 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 144 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-12 00:09:44,906 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 120 states. [2023-11-12 00:09:44,938 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 120 to 120. [2023-11-12 00:09:44,938 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 120 states, 67 states have (on average 1.1044776119402986) internal successors, (74), 70 states have internal predecessors, (74), 35 states have call successors, (35), 17 states have call predecessors, (35), 17 states have return successors, (32), 32 states have call predecessors, (32), 32 states have call successors, (32) [2023-11-12 00:09:44,940 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 141 transitions. [2023-11-12 00:09:44,940 INFO L78 Accepts]: Start accepts. Automaton has 120 states and 141 transitions. Word has length 50 [2023-11-12 00:09:44,941 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:09:44,941 INFO L495 AbstractCegarLoop]: Abstraction has 120 states and 141 transitions. [2023-11-12 00:09:44,941 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 1.875) internal successors, (15), 7 states have internal predecessors, (15), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2023-11-12 00:09:44,941 INFO L276 IsEmpty]: Start isEmpty. Operand 120 states and 141 transitions. [2023-11-12 00:09:44,942 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2023-11-12 00:09:44,943 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:09:44,943 INFO L195 NwaCegarLoop]: trace histogram [12, 11, 11, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:09:44,951 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-12 00:09:45,147 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2023-11-12 00:09:45,147 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:09:45,147 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:09:45,147 INFO L85 PathProgramCache]: Analyzing trace with hash -1733391679, now seen corresponding path program 1 times [2023-11-12 00:09:45,148 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:09:45,148 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [148251750] [2023-11-12 00:09:45,148 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:09:45,148 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:09:45,157 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:09:45,157 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [970011779] [2023-11-12 00:09:45,157 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:09:45,157 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:09:45,157 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:09:45,158 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:09:45,182 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-12 00:09:45,237 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:09:45,239 INFO L262 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 26 conjunts are in the unsatisfiable core [2023-11-12 00:09:45,242 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:09:45,466 INFO L134 CoverageAnalysis]: Checked inductivity of 250 backedges. 21 proven. 39 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2023-11-12 00:09:45,466 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:09:45,711 INFO L134 CoverageAnalysis]: Checked inductivity of 250 backedges. 24 proven. 36 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2023-11-12 00:09:45,711 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:09:45,711 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [148251750] [2023-11-12 00:09:45,711 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:09:45,711 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [970011779] [2023-11-12 00:09:45,712 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [970011779] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:09:45,712 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1913083101] [2023-11-12 00:09:45,715 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-12 00:09:45,715 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:09:45,716 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:09:45,716 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:09:45,716 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:09:46,708 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-12 00:09:46,712 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:09:47,193 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3370#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:09:47,194 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:09:47,194 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:09:47,194 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 14 [2023-11-12 00:09:47,194 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2060732648] [2023-11-12 00:09:47,194 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:09:47,195 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-11-12 00:09:47,195 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:09:47,196 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-11-12 00:09:47,198 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=378, Unknown=0, NotChecked=0, Total=462 [2023-11-12 00:09:47,198 INFO L87 Difference]: Start difference. First operand 120 states and 141 transitions. Second operand has 14 states, 12 states have (on average 2.25) internal successors, (27), 12 states have internal predecessors, (27), 7 states have call successors, (24), 3 states have call predecessors, (24), 2 states have return successors, (22), 6 states have call predecessors, (22), 7 states have call successors, (22) [2023-11-12 00:09:47,875 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:09:47,875 INFO L93 Difference]: Finished difference Result 136 states and 158 transitions. [2023-11-12 00:09:47,876 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-11-12 00:09:47,876 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 2.25) internal successors, (27), 12 states have internal predecessors, (27), 7 states have call successors, (24), 3 states have call predecessors, (24), 2 states have return successors, (22), 6 states have call predecessors, (22), 7 states have call successors, (22) Word has length 66 [2023-11-12 00:09:47,876 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:09:47,879 INFO L225 Difference]: With dead ends: 136 [2023-11-12 00:09:47,879 INFO L226 Difference]: Without dead ends: 132 [2023-11-12 00:09:47,880 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 203 GetRequests, 175 SyntacticMatches, 2 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 196 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=134, Invalid=622, Unknown=0, NotChecked=0, Total=756 [2023-11-12 00:09:47,883 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 20 mSDsluCounter, 116 mSDsCounter, 0 mSdLazyCounter, 236 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 139 SdHoareTripleChecker+Invalid, 267 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 236 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2023-11-12 00:09:47,883 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 139 Invalid, 267 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 236 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2023-11-12 00:09:47,884 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 132 states. [2023-11-12 00:09:47,925 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 132 to 132. [2023-11-12 00:09:47,926 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 132 states, 75 states have (on average 1.08) internal successors, (81), 78 states have internal predecessors, (81), 37 states have call successors, (37), 20 states have call predecessors, (37), 19 states have return successors, (34), 33 states have call predecessors, (34), 34 states have call successors, (34) [2023-11-12 00:09:47,928 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 132 states to 132 states and 152 transitions. [2023-11-12 00:09:47,928 INFO L78 Accepts]: Start accepts. Automaton has 132 states and 152 transitions. Word has length 66 [2023-11-12 00:09:47,928 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:09:47,929 INFO L495 AbstractCegarLoop]: Abstraction has 132 states and 152 transitions. [2023-11-12 00:09:47,929 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 2.25) internal successors, (27), 12 states have internal predecessors, (27), 7 states have call successors, (24), 3 states have call predecessors, (24), 2 states have return successors, (22), 6 states have call predecessors, (22), 7 states have call successors, (22) [2023-11-12 00:09:47,929 INFO L276 IsEmpty]: Start isEmpty. Operand 132 states and 152 transitions. [2023-11-12 00:09:47,931 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2023-11-12 00:09:47,931 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:09:47,931 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:09:47,942 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-12 00:09:48,138 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:09:48,138 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:09:48,138 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:09:48,138 INFO L85 PathProgramCache]: Analyzing trace with hash 2124427812, now seen corresponding path program 1 times [2023-11-12 00:09:48,138 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:09:48,139 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1420843136] [2023-11-12 00:09:48,139 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:09:48,139 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:09:48,148 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:09:48,148 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1519830337] [2023-11-12 00:09:48,148 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:09:48,149 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:09:48,149 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:09:48,150 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:09:48,158 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-12 00:09:48,215 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:09:48,216 INFO L262 TraceCheckSpWp]: Trace formula consists of 170 conjuncts, 26 conjunts are in the unsatisfiable core [2023-11-12 00:09:48,223 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:09:48,574 INFO L134 CoverageAnalysis]: Checked inductivity of 296 backedges. 23 proven. 42 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-11-12 00:09:48,574 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:09:48,872 INFO L134 CoverageAnalysis]: Checked inductivity of 296 backedges. 23 proven. 42 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-11-12 00:09:48,872 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:09:48,873 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1420843136] [2023-11-12 00:09:48,873 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:09:48,873 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1519830337] [2023-11-12 00:09:48,873 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1519830337] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:09:48,873 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [177395939] [2023-11-12 00:09:48,875 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2023-11-12 00:09:48,875 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:09:48,876 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:09:48,876 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:09:48,876 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:09:50,085 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-12 00:09:50,090 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:09:50,532 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4218#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:09:50,533 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:09:50,533 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:09:50,533 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2023-11-12 00:09:50,533 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1944748514] [2023-11-12 00:09:50,533 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:09:50,534 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-12 00:09:50,534 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:09:50,535 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-12 00:09:50,536 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=93, Invalid=413, Unknown=0, NotChecked=0, Total=506 [2023-11-12 00:09:50,536 INFO L87 Difference]: Start difference. First operand 132 states and 152 transitions. Second operand has 15 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 7 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 6 states have call predecessors, (24), 7 states have call successors, (24) [2023-11-12 00:09:51,857 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:09:51,858 INFO L93 Difference]: Finished difference Result 155 states and 186 transitions. [2023-11-12 00:09:51,858 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2023-11-12 00:09:51,858 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 7 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 6 states have call predecessors, (24), 7 states have call successors, (24) Word has length 71 [2023-11-12 00:09:51,859 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:09:51,860 INFO L225 Difference]: With dead ends: 155 [2023-11-12 00:09:51,860 INFO L226 Difference]: Without dead ends: 144 [2023-11-12 00:09:51,861 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 219 GetRequests, 188 SyntacticMatches, 2 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 250 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=174, Invalid=756, Unknown=0, NotChecked=0, Total=930 [2023-11-12 00:09:51,862 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 22 mSDsluCounter, 120 mSDsCounter, 0 mSdLazyCounter, 171 mSolverCounterSat, 46 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 143 SdHoareTripleChecker+Invalid, 217 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 46 IncrementalHoareTripleChecker+Valid, 171 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:09:51,863 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 143 Invalid, 217 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [46 Valid, 171 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2023-11-12 00:09:51,863 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 144 states. [2023-11-12 00:09:51,930 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 144 to 140. [2023-11-12 00:09:51,931 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 140 states, 77 states have (on average 1.077922077922078) internal successors, (83), 81 states have internal predecessors, (83), 42 states have call successors, (42), 20 states have call predecessors, (42), 20 states have return successors, (40), 38 states have call predecessors, (40), 40 states have call successors, (40) [2023-11-12 00:09:51,932 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 165 transitions. [2023-11-12 00:09:51,933 INFO L78 Accepts]: Start accepts. Automaton has 140 states and 165 transitions. Word has length 71 [2023-11-12 00:09:51,933 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:09:51,933 INFO L495 AbstractCegarLoop]: Abstraction has 140 states and 165 transitions. [2023-11-12 00:09:51,933 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 7 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 6 states have call predecessors, (24), 7 states have call successors, (24) [2023-11-12 00:09:51,933 INFO L276 IsEmpty]: Start isEmpty. Operand 140 states and 165 transitions. [2023-11-12 00:09:51,935 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2023-11-12 00:09:51,935 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:09:51,935 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1] [2023-11-12 00:09:51,943 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-12 00:09:52,139 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:09:52,139 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:09:52,140 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:09:52,140 INFO L85 PathProgramCache]: Analyzing trace with hash -1181636523, now seen corresponding path program 4 times [2023-11-12 00:09:52,140 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:09:52,140 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1460254857] [2023-11-12 00:09:52,140 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:09:52,141 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:09:52,157 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:09:52,158 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [644120161] [2023-11-12 00:09:52,158 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-11-12 00:09:52,158 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:09:52,159 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:09:52,160 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:09:52,179 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-12 00:09:52,230 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:09:52,232 INFO L262 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 36 conjunts are in the unsatisfiable core [2023-11-12 00:09:52,235 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:09:52,545 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 52 proven. 50 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2023-11-12 00:09:52,545 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:09:52,947 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 52 proven. 50 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2023-11-12 00:09:52,948 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:09:52,948 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1460254857] [2023-11-12 00:09:52,948 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:09:52,948 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [644120161] [2023-11-12 00:09:52,948 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [644120161] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:09:52,949 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1863264621] [2023-11-12 00:09:52,951 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-11-12 00:09:52,951 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:09:52,952 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:09:52,952 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:09:52,952 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:09:54,033 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-12 00:09:54,037 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:09:54,556 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5129#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:09:54,556 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:09:54,556 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:09:54,556 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2023-11-12 00:09:54,556 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [83752341] [2023-11-12 00:09:54,557 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:09:54,557 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-11-12 00:09:54,557 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:09:54,558 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-11-12 00:09:54,558 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=107, Invalid=493, Unknown=0, NotChecked=0, Total=600 [2023-11-12 00:09:54,559 INFO L87 Difference]: Start difference. First operand 140 states and 165 transitions. Second operand has 17 states, 15 states have (on average 2.066666666666667) internal successors, (31), 13 states have internal predecessors, (31), 9 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 8 states have call predecessors, (24), 7 states have call successors, (24) [2023-11-12 00:09:57,028 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:09:59,188 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:10:01,910 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.56s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-12 00:10:02,161 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:10:02,161 INFO L93 Difference]: Finished difference Result 164 states and 199 transitions. [2023-11-12 00:10:02,162 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-11-12 00:10:02,162 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 2.066666666666667) internal successors, (31), 13 states have internal predecessors, (31), 9 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 8 states have call predecessors, (24), 7 states have call successors, (24) Word has length 73 [2023-11-12 00:10:02,162 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:10:02,164 INFO L225 Difference]: With dead ends: 164 [2023-11-12 00:10:02,164 INFO L226 Difference]: Without dead ends: 162 [2023-11-12 00:10:02,165 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 226 GetRequests, 191 SyntacticMatches, 3 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 333 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=214, Invalid=908, Unknown=0, NotChecked=0, Total=1122 [2023-11-12 00:10:02,165 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 33 mSDsluCounter, 165 mSDsCounter, 0 mSdLazyCounter, 253 mSolverCounterSat, 91 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 195 SdHoareTripleChecker+Invalid, 347 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 91 IncrementalHoareTripleChecker+Valid, 253 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.2s IncrementalHoareTripleChecker+Time [2023-11-12 00:10:02,166 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 195 Invalid, 347 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [91 Valid, 253 Invalid, 3 Unknown, 0 Unchecked, 7.2s Time] [2023-11-12 00:10:02,167 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 162 states. [2023-11-12 00:10:02,238 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 162 to 148. [2023-11-12 00:10:02,238 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 148 states, 83 states have (on average 1.072289156626506) internal successors, (89), 87 states have internal predecessors, (89), 42 states have call successors, (42), 22 states have call predecessors, (42), 22 states have return successors, (40), 38 states have call predecessors, (40), 40 states have call successors, (40) [2023-11-12 00:10:02,239 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 171 transitions. [2023-11-12 00:10:02,240 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 171 transitions. Word has length 73 [2023-11-12 00:10:02,240 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:10:02,240 INFO L495 AbstractCegarLoop]: Abstraction has 148 states and 171 transitions. [2023-11-12 00:10:02,240 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 2.066666666666667) internal successors, (31), 13 states have internal predecessors, (31), 9 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 8 states have call predecessors, (24), 7 states have call successors, (24) [2023-11-12 00:10:02,240 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 171 transitions. [2023-11-12 00:10:02,242 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2023-11-12 00:10:02,244 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:10:02,244 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1] [2023-11-12 00:10:02,251 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-11-12 00:10:02,451 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:10:02,451 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:10:02,451 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:10:02,451 INFO L85 PathProgramCache]: Analyzing trace with hash -331345392, now seen corresponding path program 5 times [2023-11-12 00:10:02,451 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:10:02,451 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [319071120] [2023-11-12 00:10:02,452 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:10:02,452 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:10:02,465 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:10:02,466 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1378299715] [2023-11-12 00:10:02,466 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-12 00:10:02,466 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:10:02,466 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:10:02,472 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:10:02,474 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-11-12 00:10:02,539 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-11-12 00:10:02,539 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 00:10:02,541 INFO L262 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 35 conjunts are in the unsatisfiable core [2023-11-12 00:10:02,544 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:10:02,800 INFO L134 CoverageAnalysis]: Checked inductivity of 358 backedges. 55 proven. 27 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2023-11-12 00:10:02,800 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:10:03,523 INFO L134 CoverageAnalysis]: Checked inductivity of 358 backedges. 55 proven. 27 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2023-11-12 00:10:03,523 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:10:03,523 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [319071120] [2023-11-12 00:10:03,524 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:10:03,524 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1378299715] [2023-11-12 00:10:03,524 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1378299715] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:10:03,524 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [609556270] [2023-11-12 00:10:03,526 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-11-12 00:10:03,526 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:10:03,527 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:10:03,527 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:10:03,527 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:10:04,644 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-12 00:10:04,648 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:10:05,171 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '6096#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:10:05,171 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:10:05,171 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:10:05,172 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 16 [2023-11-12 00:10:05,172 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [411840216] [2023-11-12 00:10:05,172 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:10:05,173 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2023-11-12 00:10:05,173 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:10:05,173 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2023-11-12 00:10:05,174 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=102, Invalid=450, Unknown=0, NotChecked=0, Total=552 [2023-11-12 00:10:05,174 INFO L87 Difference]: Start difference. First operand 148 states and 171 transitions. Second operand has 16 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 13 states have internal predecessors, (31), 8 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 6 states have call predecessors, (26), 8 states have call successors, (26) [2023-11-12 00:10:07,003 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:10:07,003 INFO L93 Difference]: Finished difference Result 154 states and 176 transitions. [2023-11-12 00:10:07,004 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-11-12 00:10:07,004 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 13 states have internal predecessors, (31), 8 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 6 states have call predecessors, (26), 8 states have call successors, (26) Word has length 78 [2023-11-12 00:10:07,004 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:10:07,005 INFO L225 Difference]: With dead ends: 154 [2023-11-12 00:10:07,006 INFO L226 Difference]: Without dead ends: 136 [2023-11-12 00:10:07,007 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 236 GetRequests, 207 SyntacticMatches, 3 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 223 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=144, Invalid=612, Unknown=0, NotChecked=0, Total=756 [2023-11-12 00:10:07,007 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 27 mSDsluCounter, 163 mSDsCounter, 0 mSdLazyCounter, 245 mSolverCounterSat, 68 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 193 SdHoareTripleChecker+Invalid, 313 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 68 IncrementalHoareTripleChecker+Valid, 245 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2023-11-12 00:10:07,008 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 193 Invalid, 313 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [68 Valid, 245 Invalid, 0 Unknown, 0 Unchecked, 1.5s Time] [2023-11-12 00:10:07,008 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2023-11-12 00:10:07,060 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 136. [2023-11-12 00:10:07,060 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 136 states, 80 states have (on average 1.05) internal successors, (84), 83 states have internal predecessors, (84), 34 states have call successors, (34), 21 states have call predecessors, (34), 21 states have return successors, (33), 31 states have call predecessors, (33), 33 states have call successors, (33) [2023-11-12 00:10:07,061 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 136 states to 136 states and 151 transitions. [2023-11-12 00:10:07,062 INFO L78 Accepts]: Start accepts. Automaton has 136 states and 151 transitions. Word has length 78 [2023-11-12 00:10:07,062 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:10:07,062 INFO L495 AbstractCegarLoop]: Abstraction has 136 states and 151 transitions. [2023-11-12 00:10:07,063 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 13 states have internal predecessors, (31), 8 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 6 states have call predecessors, (26), 8 states have call successors, (26) [2023-11-12 00:10:07,063 INFO L276 IsEmpty]: Start isEmpty. Operand 136 states and 151 transitions. [2023-11-12 00:10:07,064 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 125 [2023-11-12 00:10:07,065 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:10:07,065 INFO L195 NwaCegarLoop]: trace histogram [22, 21, 21, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:10:07,079 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-11-12 00:10:07,279 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:10:07,279 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:10:07,279 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:10:07,279 INFO L85 PathProgramCache]: Analyzing trace with hash -1753860344, now seen corresponding path program 2 times [2023-11-12 00:10:07,279 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:10:07,280 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [147122055] [2023-11-12 00:10:07,280 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:10:07,280 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:10:07,297 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:10:07,304 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [859328608] [2023-11-12 00:10:07,304 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-12 00:10:07,304 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:10:07,304 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:10:07,305 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:10:07,316 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-11-12 00:10:08,458 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2023-11-12 00:10:08,458 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 00:10:08,462 INFO L262 TraceCheckSpWp]: Trace formula consists of 265 conjuncts, 11 conjunts are in the unsatisfiable core [2023-11-12 00:10:08,466 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:10:08,611 INFO L134 CoverageAnalysis]: Checked inductivity of 938 backedges. 120 proven. 656 refuted. 0 times theorem prover too weak. 162 trivial. 0 not checked. [2023-11-12 00:10:08,611 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:10:08,744 INFO L134 CoverageAnalysis]: Checked inductivity of 938 backedges. 42 proven. 56 refuted. 0 times theorem prover too weak. 840 trivial. 0 not checked. [2023-11-12 00:10:08,744 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:10:08,744 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [147122055] [2023-11-12 00:10:08,744 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:10:08,744 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [859328608] [2023-11-12 00:10:08,744 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [859328608] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:10:08,744 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1434247801] [2023-11-12 00:10:08,746 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-12 00:10:08,746 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:10:08,747 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:10:08,747 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:10:08,747 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:10:09,700 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-12 00:10:09,705 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:10:10,065 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '7284#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:10:10,066 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:10:10,066 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:10:10,066 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8] total 14 [2023-11-12 00:10:10,066 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1425115542] [2023-11-12 00:10:10,066 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:10:10,067 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-11-12 00:10:10,067 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:10:10,068 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-11-12 00:10:10,068 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=128, Invalid=334, Unknown=0, NotChecked=0, Total=462 [2023-11-12 00:10:10,069 INFO L87 Difference]: Start difference. First operand 136 states and 151 transitions. Second operand has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (43), 6 states have call predecessors, (43), 6 states have return successors, (42), 9 states have call predecessors, (42), 9 states have call successors, (42) [2023-11-12 00:10:10,672 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:10:10,672 INFO L93 Difference]: Finished difference Result 369 states and 400 transitions. [2023-11-12 00:10:10,673 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2023-11-12 00:10:10,673 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (43), 6 states have call predecessors, (43), 6 states have return successors, (42), 9 states have call predecessors, (42), 9 states have call successors, (42) Word has length 124 [2023-11-12 00:10:10,674 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:10:10,677 INFO L225 Difference]: With dead ends: 369 [2023-11-12 00:10:10,678 INFO L226 Difference]: Without dead ends: 353 [2023-11-12 00:10:10,679 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 379 GetRequests, 346 SyntacticMatches, 4 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 351 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=250, Invalid=680, Unknown=0, NotChecked=0, Total=930 [2023-11-12 00:10:10,687 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 134 mSDsluCounter, 132 mSDsCounter, 0 mSdLazyCounter, 170 mSolverCounterSat, 56 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 134 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 226 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 56 IncrementalHoareTripleChecker+Valid, 170 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-12 00:10:10,687 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [134 Valid, 157 Invalid, 226 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [56 Valid, 170 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-12 00:10:10,689 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 353 states. [2023-11-12 00:10:10,823 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 353 to 297. [2023-11-12 00:10:10,824 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 297 states, 180 states have (on average 1.0555555555555556) internal successors, (190), 187 states have internal predecessors, (190), 68 states have call successors, (68), 49 states have call predecessors, (68), 48 states have return successors, (65), 60 states have call predecessors, (65), 65 states have call successors, (65) [2023-11-12 00:10:10,826 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 297 states to 297 states and 323 transitions. [2023-11-12 00:10:10,826 INFO L78 Accepts]: Start accepts. Automaton has 297 states and 323 transitions. Word has length 124 [2023-11-12 00:10:10,827 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:10:10,827 INFO L495 AbstractCegarLoop]: Abstraction has 297 states and 323 transitions. [2023-11-12 00:10:10,827 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.5714285714285716) internal successors, (50), 14 states have internal predecessors, (50), 9 states have call successors, (43), 6 states have call predecessors, (43), 6 states have return successors, (42), 9 states have call predecessors, (42), 9 states have call successors, (42) [2023-11-12 00:10:10,828 INFO L276 IsEmpty]: Start isEmpty. Operand 297 states and 323 transitions. [2023-11-12 00:10:10,829 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 133 [2023-11-12 00:10:10,829 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:10:10,830 INFO L195 NwaCegarLoop]: trace histogram [24, 23, 23, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:10:10,839 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2023-11-12 00:10:11,038 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:10:11,038 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:10:11,038 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:10:11,038 INFO L85 PathProgramCache]: Analyzing trace with hash 109149613, now seen corresponding path program 1 times [2023-11-12 00:10:11,039 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:10:11,039 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1169361733] [2023-11-12 00:10:11,039 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:10:11,039 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:10:11,066 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:10:11,067 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [554385480] [2023-11-12 00:10:11,067 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:10:11,068 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:10:11,068 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:10:11,069 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:10:11,076 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2afa6d8e-01f8-4ffb-818d-cbf6459d16a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-11-12 00:10:11,166 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:10:11,168 INFO L262 TraceCheckSpWp]: Trace formula consists of 297 conjuncts, 37 conjunts are in the unsatisfiable core [2023-11-12 00:10:11,171 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:10:11,442 INFO L134 CoverageAnalysis]: Checked inductivity of 1106 backedges. 45 proven. 115 refuted. 0 times theorem prover too weak. 946 trivial. 0 not checked. [2023-11-12 00:10:11,442 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:10:17,212 INFO L134 CoverageAnalysis]: Checked inductivity of 1106 backedges. 45 proven. 115 refuted. 0 times theorem prover too weak. 946 trivial. 0 not checked. [2023-11-12 00:10:17,212 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:10:17,212 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1169361733] [2023-11-12 00:10:17,212 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:10:17,212 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [554385480] [2023-11-12 00:10:17,212 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [554385480] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:10:17,212 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2125330964] [2023-11-12 00:10:17,214 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-11-12 00:10:17,214 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:10:17,215 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:10:17,215 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:10:17,215 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:10:18,257 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-11-12 00:10:18,261 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:10:20,910 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '9062#(and (<= 1 |#StackHeapBarrier|) (<= 1 ~counter~0) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:10:20,910 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:10:20,911 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:10:20,911 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10] total 18 [2023-11-12 00:10:20,911 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [397543187] [2023-11-12 00:10:20,911 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:10:20,912 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2023-11-12 00:10:20,912 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:10:20,912 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2023-11-12 00:10:20,913 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=121, Invalid=528, Unknown=1, NotChecked=0, Total=650 [2023-11-12 00:10:20,913 INFO L87 Difference]: Start difference. First operand 297 states and 323 transitions. Second operand has 18 states, 18 states have (on average 2.1666666666666665) internal successors, (39), 15 states have internal predecessors, (39), 10 states have call successors, (48), 3 states have call predecessors, (48), 2 states have return successors, (46), 8 states have call predecessors, (46), 10 states have call successors, (46)