./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound5.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 0e0057cc Calling Ultimate with: /usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound5.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh --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 1eba5bc7e50ef659abfe155713ae512eb1ae4032ecb78db63a02f9acbcdf9dbe --- Real Ultimate output --- This is Ultimate 0.2.4-dev-0e0057c [2023-12-02 18:55:25,849 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-12-02 18:55:25,925 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-12-02 18:55:25,930 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-12-02 18:55:25,930 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-12-02 18:55:25,960 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-12-02 18:55:25,960 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-12-02 18:55:25,961 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-12-02 18:55:25,961 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-12-02 18:55:25,962 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-12-02 18:55:25,962 INFO L153 SettingsManager]: * User list type=DISABLED [2023-12-02 18:55:25,963 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-12-02 18:55:25,963 INFO L153 SettingsManager]: * Explicit value domain=true [2023-12-02 18:55:25,964 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-12-02 18:55:25,964 INFO L153 SettingsManager]: * Octagon Domain=false [2023-12-02 18:55:25,965 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-12-02 18:55:25,965 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-12-02 18:55:25,966 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-12-02 18:55:25,966 INFO L153 SettingsManager]: * Interval Domain=false [2023-12-02 18:55:25,967 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-12-02 18:55:25,967 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-12-02 18:55:25,968 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-12-02 18:55:25,969 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-12-02 18:55:25,969 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-12-02 18:55:25,970 INFO L153 SettingsManager]: * sizeof long=4 [2023-12-02 18:55:25,970 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-12-02 18:55:25,970 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-12-02 18:55:25,971 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-12-02 18:55:25,971 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-12-02 18:55:25,971 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-12-02 18:55:25,971 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-12-02 18:55:25,972 INFO L153 SettingsManager]: * sizeof long double=12 [2023-12-02 18:55:25,972 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-12-02 18:55:25,972 INFO L153 SettingsManager]: * Use constant arrays=true [2023-12-02 18:55:25,973 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-12-02 18:55:25,973 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-12-02 18:55:25,973 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-12-02 18:55:25,973 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-12-02 18:55:25,973 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-12-02 18:55:25,973 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-12-02 18:55:25,974 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-12-02 18:55:25,974 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-12-02 18:55:25,974 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-12-02 18:55:25,974 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-12-02 18:55:25,975 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-12-02 18:55:25,975 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-12-02 18:55:25,975 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-12-02 18:55:25,975 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_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/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_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh 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 -> 1eba5bc7e50ef659abfe155713ae512eb1ae4032ecb78db63a02f9acbcdf9dbe [2023-12-02 18:55:26,191 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-12-02 18:55:26,212 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-12-02 18:55:26,215 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-12-02 18:55:26,216 INFO L270 PluginConnector]: Initializing CDTParser... [2023-12-02 18:55:26,216 INFO L274 PluginConnector]: CDTParser initialized [2023-12-02 18:55:26,217 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/../../sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound5.c [2023-12-02 18:55:28,959 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-12-02 18:55:29,151 INFO L384 CDTParser]: Found 1 translation units. [2023-12-02 18:55:29,151 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound5.c [2023-12-02 18:55:29,157 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/data/051dc7a12/fefcb041c78841e498a8c171dff0bc75/FLAGbfbc845bb [2023-12-02 18:55:29,169 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/data/051dc7a12/fefcb041c78841e498a8c171dff0bc75 [2023-12-02 18:55:29,170 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-12-02 18:55:29,172 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-12-02 18:55:29,173 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-12-02 18:55:29,173 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-12-02 18:55:29,177 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-12-02 18:55:29,178 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.12 06:55:29" (1/1) ... [2023-12-02 18:55:29,179 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3bcc3aa2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:55:29, skipping insertion in model container [2023-12-02 18:55:29,179 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.12 06:55:29" (1/1) ... [2023-12-02 18:55:29,201 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-12-02 18:55:29,320 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_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound5.c[538,551] [2023-12-02 18:55:29,338 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-02 18:55:29,348 INFO L202 MainTranslator]: Completed pre-run [2023-12-02 18:55:29,358 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_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound5.c[538,551] [2023-12-02 18:55:29,367 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-02 18:55:29,379 INFO L206 MainTranslator]: Completed translation [2023-12-02 18:55:29,380 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:55:29 WrapperNode [2023-12-02 18:55:29,380 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-12-02 18:55:29,381 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-12-02 18:55:29,381 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-12-02 18:55:29,382 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-12-02 18:55:29,388 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:55:29" (1/1) ... [2023-12-02 18:55:29,394 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:55:29" (1/1) ... [2023-12-02 18:55:29,417 INFO L138 Inliner]: procedures = 14, calls = 15, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 66 [2023-12-02 18:55:29,417 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-12-02 18:55:29,418 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-12-02 18:55:29,418 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-12-02 18:55:29,418 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-12-02 18:55:29,426 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:55:29" (1/1) ... [2023-12-02 18:55:29,426 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:55:29" (1/1) ... [2023-12-02 18:55:29,428 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:55:29" (1/1) ... [2023-12-02 18:55:29,429 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:55:29" (1/1) ... [2023-12-02 18:55:29,432 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:55:29" (1/1) ... [2023-12-02 18:55:29,435 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:55:29" (1/1) ... [2023-12-02 18:55:29,437 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:55:29" (1/1) ... [2023-12-02 18:55:29,438 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:55:29" (1/1) ... [2023-12-02 18:55:29,440 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-12-02 18:55:29,441 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-12-02 18:55:29,441 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-12-02 18:55:29,441 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-12-02 18:55:29,442 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:55:29" (1/1) ... [2023-12-02 18:55:29,450 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-12-02 18:55:29,459 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:55:29,471 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-12-02 18:55:29,480 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-12-02 18:55:29,509 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-12-02 18:55:29,509 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-12-02 18:55:29,509 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-12-02 18:55:29,510 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-12-02 18:55:29,510 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-12-02 18:55:29,510 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-12-02 18:55:29,573 INFO L241 CfgBuilder]: Building ICFG [2023-12-02 18:55:29,575 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-12-02 18:55:29,755 INFO L282 CfgBuilder]: Performing block encoding [2023-12-02 18:55:29,798 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-12-02 18:55:29,798 INFO L309 CfgBuilder]: Removed 2 assume(true) statements. [2023-12-02 18:55:29,799 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.12 06:55:29 BoogieIcfgContainer [2023-12-02 18:55:29,799 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-12-02 18:55:29,801 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-12-02 18:55:29,801 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-12-02 18:55:29,803 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-12-02 18:55:29,803 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 02.12 06:55:29" (1/3) ... [2023-12-02 18:55:29,804 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@66106b0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.12 06:55:29, skipping insertion in model container [2023-12-02 18:55:29,804 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:55:29" (2/3) ... [2023-12-02 18:55:29,804 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@66106b0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.12 06:55:29, skipping insertion in model container [2023-12-02 18:55:29,804 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.12 06:55:29" (3/3) ... [2023-12-02 18:55:29,805 INFO L112 eAbstractionObserver]: Analyzing ICFG hard-ll_unwindbound5.c [2023-12-02 18:55:29,819 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-12-02 18:55:29,820 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-12-02 18:55:29,858 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-12-02 18:55:29,865 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;@718707d, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-12-02 18:55:29,865 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-12-02 18:55:29,869 INFO L276 IsEmpty]: Start isEmpty. Operand has 22 states, 12 states have (on average 1.6666666666666667) internal successors, (20), 13 states have internal predecessors, (20), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2023-12-02 18:55:29,875 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-12-02 18:55:29,875 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:55:29,875 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:55:29,876 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:55:29,881 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:55:29,881 INFO L85 PathProgramCache]: Analyzing trace with hash 151460259, now seen corresponding path program 1 times [2023-12-02 18:55:29,890 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:55:29,890 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1802320937] [2023-12-02 18:55:29,890 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:29,891 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:55:30,009 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:55:30,040 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:55:30,040 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1802320937] [2023-12-02 18:55:30,041 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-12-02 18:55:30,041 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [455695187] [2023-12-02 18:55:30,041 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:30,041 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:55:30,042 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:55:30,043 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:55:30,051 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-12-02 18:55:30,118 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:55:30,120 INFO L262 TraceCheckSpWp]: Trace formula consists of 43 conjuncts, 1 conjunts are in the unsatisfiable core [2023-12-02 18:55:30,125 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:55:30,142 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 18:55:30,142 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-02 18:55:30,143 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [455695187] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 18:55:30,143 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 18:55:30,144 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-12-02 18:55:30,145 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2051290006] [2023-12-02 18:55:30,146 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 18:55:30,149 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-12-02 18:55:30,150 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:55:30,177 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-12-02 18:55:30,178 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-12-02 18:55:30,180 INFO L87 Difference]: Start difference. First operand has 22 states, 12 states have (on average 1.6666666666666667) internal successors, (20), 13 states have internal predecessors, (20), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 18:55:30,220 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:55:30,221 INFO L93 Difference]: Finished difference Result 43 states and 74 transitions. [2023-12-02 18:55:30,222 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-12-02 18:55:30,224 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2023-12-02 18:55:30,224 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:55:30,231 INFO L225 Difference]: With dead ends: 43 [2023-12-02 18:55:30,232 INFO L226 Difference]: Without dead ends: 20 [2023-12-02 18:55:30,236 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-12-02 18:55:30,240 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 3 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 28 SdHoareTripleChecker+Invalid, 3 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 3 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 18:55:30,242 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 28 Invalid, 3 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 3 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 18:55:30,259 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2023-12-02 18:55:30,278 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2023-12-02 18:55:30,279 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 12 states have internal predecessors, (16), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-02 18:55:30,281 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 29 transitions. [2023-12-02 18:55:30,282 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 29 transitions. Word has length 7 [2023-12-02 18:55:30,283 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:55:30,283 INFO L495 AbstractCegarLoop]: Abstraction has 20 states and 29 transitions. [2023-12-02 18:55:30,283 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.0) internal successors, (6), 2 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 18:55:30,284 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 29 transitions. [2023-12-02 18:55:30,284 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-12-02 18:55:30,284 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:55:30,285 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:55:30,291 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-12-02 18:55:30,487 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2023-12-02 18:55:30,487 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:55:30,488 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:55:30,488 INFO L85 PathProgramCache]: Analyzing trace with hash -310598151, now seen corresponding path program 1 times [2023-12-02 18:55:30,489 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:55:30,489 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1223161208] [2023-12-02 18:55:30,489 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:30,489 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:55:30,511 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:55:30,652 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 18:55:30,653 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:55:30,653 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1223161208] [2023-12-02 18:55:30,653 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1223161208] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 18:55:30,654 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 18:55:30,654 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-12-02 18:55:30,654 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1932735677] [2023-12-02 18:55:30,655 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 18:55:30,655 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-02 18:55:30,656 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:55:30,657 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-02 18:55:30,657 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-12-02 18:55:30,657 INFO L87 Difference]: Start difference. First operand 20 states and 29 transitions. Second operand has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 18:55:30,726 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:55:30,727 INFO L93 Difference]: Finished difference Result 33 states and 46 transitions. [2023-12-02 18:55:30,727 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-02 18:55:30,727 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-12-02 18:55:30,728 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:55:30,729 INFO L225 Difference]: With dead ends: 33 [2023-12-02 18:55:30,729 INFO L226 Difference]: Without dead ends: 31 [2023-12-02 18:55:30,729 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-12-02 18:55:30,731 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 13 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 18:55:30,732 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 81 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 18:55:30,733 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2023-12-02 18:55:30,739 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 24. [2023-12-02 18:55:30,740 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 14 states have (on average 1.3571428571428572) internal successors, (19), 15 states have internal predecessors, (19), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-02 18:55:30,741 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 32 transitions. [2023-12-02 18:55:30,741 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 32 transitions. Word has length 7 [2023-12-02 18:55:30,742 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:55:30,742 INFO L495 AbstractCegarLoop]: Abstraction has 24 states and 32 transitions. [2023-12-02 18:55:30,742 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-12-02 18:55:30,742 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 32 transitions. [2023-12-02 18:55:30,743 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2023-12-02 18:55:30,743 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:55:30,743 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:55:30,744 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-12-02 18:55:30,744 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:55:30,745 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:55:30,745 INFO L85 PathProgramCache]: Analyzing trace with hash -751211152, now seen corresponding path program 1 times [2023-12-02 18:55:30,745 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:55:30,745 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [367584731] [2023-12-02 18:55:30,745 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:30,746 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:55:30,758 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:55:30,766 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:55:30,766 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [367584731] [2023-12-02 18:55:30,766 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-12-02 18:55:30,767 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1769765887] [2023-12-02 18:55:30,767 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:30,767 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:55:30,767 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:55:30,768 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:55:30,775 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-12-02 18:55:30,821 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:55:30,822 INFO L262 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 3 conjunts are in the unsatisfiable core [2023-12-02 18:55:30,823 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:55:30,860 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 18:55:30,860 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-02 18:55:30,861 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1769765887] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 18:55:30,861 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 18:55:30,861 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-12-02 18:55:30,862 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [668885695] [2023-12-02 18:55:30,862 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 18:55:30,863 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-12-02 18:55:30,863 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:55:30,863 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-12-02 18:55:30,864 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-12-02 18:55:30,864 INFO L87 Difference]: Start difference. First operand 24 states and 32 transitions. Second operand has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 18:55:30,893 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:55:30,894 INFO L93 Difference]: Finished difference Result 39 states and 52 transitions. [2023-12-02 18:55:30,894 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-12-02 18:55:30,895 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2023-12-02 18:55:30,895 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:55:30,896 INFO L225 Difference]: With dead ends: 39 [2023-12-02 18:55:30,896 INFO L226 Difference]: Without dead ends: 26 [2023-12-02 18:55:30,897 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-12-02 18:55:30,898 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 0 mSDsluCounter, 48 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 13 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 18:55:30,899 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 73 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 18:55:30,900 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2023-12-02 18:55:30,907 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2023-12-02 18:55:30,907 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 16 states have (on average 1.3125) internal successors, (21), 17 states have internal predecessors, (21), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-02 18:55:30,909 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 34 transitions. [2023-12-02 18:55:30,909 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 34 transitions. Word has length 9 [2023-12-02 18:55:30,909 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:55:30,909 INFO L495 AbstractCegarLoop]: Abstraction has 26 states and 34 transitions. [2023-12-02 18:55:30,910 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-02 18:55:30,910 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 34 transitions. [2023-12-02 18:55:30,910 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2023-12-02 18:55:30,911 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:55:30,911 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:55:30,916 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2023-12-02 18:55:31,111 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:55:31,112 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:55:31,112 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:55:31,112 INFO L85 PathProgramCache]: Analyzing trace with hash 1841718534, now seen corresponding path program 1 times [2023-12-02 18:55:31,112 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:55:31,113 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2000031705] [2023-12-02 18:55:31,113 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:31,113 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:55:31,127 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:55:31,260 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-02 18:55:31,260 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:55:31,260 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2000031705] [2023-12-02 18:55:31,260 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2000031705] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 18:55:31,261 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 18:55:31,261 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-12-02 18:55:31,261 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1347308015] [2023-12-02 18:55:31,261 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 18:55:31,262 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-02 18:55:31,262 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:55:31,263 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-02 18:55:31,263 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-12-02 18:55:31,263 INFO L87 Difference]: Start difference. First operand 26 states and 34 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-12-02 18:55:31,322 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:55:31,322 INFO L93 Difference]: Finished difference Result 39 states and 51 transitions. [2023-12-02 18:55:31,323 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-02 18:55:31,323 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2023-12-02 18:55:31,323 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:55:31,324 INFO L225 Difference]: With dead ends: 39 [2023-12-02 18:55:31,324 INFO L226 Difference]: Without dead ends: 37 [2023-12-02 18:55:31,325 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-12-02 18:55:31,326 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 11 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 18:55:31,326 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 81 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 18:55:31,327 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2023-12-02 18:55:31,335 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 30. [2023-12-02 18:55:31,336 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-02 18:55:31,336 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 37 transitions. [2023-12-02 18:55:31,337 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 37 transitions. Word has length 12 [2023-12-02 18:55:31,337 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:55:31,337 INFO L495 AbstractCegarLoop]: Abstraction has 30 states and 37 transitions. [2023-12-02 18:55:31,337 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-12-02 18:55:31,337 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 37 transitions. [2023-12-02 18:55:31,338 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2023-12-02 18:55:31,338 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:55:31,338 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:55:31,338 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2023-12-02 18:55:31,339 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:55:31,339 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:55:31,339 INFO L85 PathProgramCache]: Analyzing trace with hash -1224204839, now seen corresponding path program 1 times [2023-12-02 18:55:31,339 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:55:31,340 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1390513383] [2023-12-02 18:55:31,340 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:31,340 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:55:31,351 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:55:31,351 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2034212456] [2023-12-02 18:55:31,352 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:31,352 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:55:31,352 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:55:31,353 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:55:31,372 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-12-02 18:55:31,422 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:55:31,424 INFO L262 TraceCheckSpWp]: Trace formula consists of 64 conjuncts, 19 conjunts are in the unsatisfiable core [2023-12-02 18:55:31,434 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:55:31,576 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-12-02 18:55:31,576 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:55:31,740 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-12-02 18:55:31,741 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:55:31,741 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1390513383] [2023-12-02 18:55:31,741 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:55:31,741 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2034212456] [2023-12-02 18:55:31,741 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2034212456] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:55:31,741 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [631843765] [2023-12-02 18:55:31,759 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2023-12-02 18:55:31,759 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:55:31,762 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:55:31,766 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:55:31,766 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:55:32,092 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 8 for LOIs [2023-12-02 18:55:32,099 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:55:32,430 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [631843765] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 18:55:32,431 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:55:32,431 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [8, 7] total 17 [2023-12-02 18:55:32,432 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [808434327] [2023-12-02 18:55:32,432 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 18:55:32,433 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-12-02 18:55:32,433 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:55:32,433 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-12-02 18:55:32,434 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2023-12-02 18:55:32,434 INFO L87 Difference]: Start difference. First operand 30 states and 37 transitions. Second operand has 7 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-12-02 18:55:32,546 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:55:32,546 INFO L93 Difference]: Finished difference Result 49 states and 57 transitions. [2023-12-02 18:55:32,546 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-12-02 18:55:32,546 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2023-12-02 18:55:32,547 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:55:32,547 INFO L225 Difference]: With dead ends: 49 [2023-12-02 18:55:32,548 INFO L226 Difference]: Without dead ends: 47 [2023-12-02 18:55:32,548 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 63 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2023-12-02 18:55:32,549 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 1 mSDsluCounter, 41 mSDsCounter, 0 mSdLazyCounter, 65 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 58 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 65 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 18:55:32,550 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 58 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 65 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 18:55:32,550 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2023-12-02 18:55:32,562 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 45. [2023-12-02 18:55:32,563 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 28 states have (on average 1.1785714285714286) internal successors, (33), 30 states have internal predecessors, (33), 10 states have call successors, (10), 6 states have call predecessors, (10), 6 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-02 18:55:32,564 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 52 transitions. [2023-12-02 18:55:32,564 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 52 transitions. Word has length 17 [2023-12-02 18:55:32,564 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:55:32,564 INFO L495 AbstractCegarLoop]: Abstraction has 45 states and 52 transitions. [2023-12-02 18:55:32,565 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-12-02 18:55:32,565 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 52 transitions. [2023-12-02 18:55:32,565 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2023-12-02 18:55:32,566 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:55:32,566 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:55:32,570 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2023-12-02 18:55:32,766 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:55:32,767 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:55:32,767 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:55:32,767 INFO L85 PathProgramCache]: Analyzing trace with hash 1437524276, now seen corresponding path program 1 times [2023-12-02 18:55:32,768 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:55:32,768 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [984161726] [2023-12-02 18:55:32,768 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:32,768 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:55:32,781 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:55:32,781 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1995038939] [2023-12-02 18:55:32,781 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:32,781 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:55:32,782 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:55:32,783 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:55:32,798 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-12-02 18:55:32,843 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:55:32,844 INFO L262 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 5 conjunts are in the unsatisfiable core [2023-12-02 18:55:32,846 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:55:32,891 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-02 18:55:32,892 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-02 18:55:32,892 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:55:32,892 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [984161726] [2023-12-02 18:55:32,892 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:55:32,892 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1995038939] [2023-12-02 18:55:32,892 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1995038939] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 18:55:32,892 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 18:55:32,892 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-12-02 18:55:32,893 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2009447294] [2023-12-02 18:55:32,893 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 18:55:32,893 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-02 18:55:32,893 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:55:32,894 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-02 18:55:32,894 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-12-02 18:55:32,894 INFO L87 Difference]: Start difference. First operand 45 states and 52 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-12-02 18:55:32,938 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:55:32,938 INFO L93 Difference]: Finished difference Result 57 states and 66 transitions. [2023-12-02 18:55:32,939 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-12-02 18:55:32,939 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 25 [2023-12-02 18:55:32,940 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:55:32,941 INFO L225 Difference]: With dead ends: 57 [2023-12-02 18:55:32,941 INFO L226 Difference]: Without dead ends: 49 [2023-12-02 18:55:32,941 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-12-02 18:55:32,942 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 1 mSDsluCounter, 53 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 77 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-02 18:55:32,943 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 77 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-02 18:55:32,943 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2023-12-02 18:55:32,956 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 48. [2023-12-02 18:55:32,957 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 31 states have (on average 1.1935483870967742) internal successors, (37), 32 states have internal predecessors, (37), 10 states have call successors, (10), 6 states have call predecessors, (10), 6 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-02 18:55:32,958 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 56 transitions. [2023-12-02 18:55:32,958 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 56 transitions. Word has length 25 [2023-12-02 18:55:32,958 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:55:32,958 INFO L495 AbstractCegarLoop]: Abstraction has 48 states and 56 transitions. [2023-12-02 18:55:32,958 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-12-02 18:55:32,959 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 56 transitions. [2023-12-02 18:55:32,959 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2023-12-02 18:55:32,960 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:55:32,960 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:55:32,965 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2023-12-02 18:55:33,161 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2023-12-02 18:55:33,162 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:55:33,162 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:55:33,162 INFO L85 PathProgramCache]: Analyzing trace with hash 1439252154, now seen corresponding path program 1 times [2023-12-02 18:55:33,162 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:55:33,163 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [486409218] [2023-12-02 18:55:33,163 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:33,163 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:55:33,174 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:55:33,174 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [289637635] [2023-12-02 18:55:33,174 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:33,174 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:55:33,174 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:55:33,175 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:55:33,184 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-12-02 18:55:33,225 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:55:33,226 INFO L262 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 16 conjunts are in the unsatisfiable core [2023-12-02 18:55:33,228 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:55:33,381 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-12-02 18:55:33,382 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:55:33,578 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-12-02 18:55:33,578 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:55:33,578 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [486409218] [2023-12-02 18:55:33,578 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:55:33,578 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [289637635] [2023-12-02 18:55:33,579 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [289637635] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:55:33,579 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [313209301] [2023-12-02 18:55:33,582 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-12-02 18:55:33,582 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:55:33,582 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:55:33,583 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:55:33,583 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:55:34,006 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 48 for LOIs [2023-12-02 18:55:34,061 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:55:34,931 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [313209301] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 18:55:34,931 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:55:34,931 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [7, 7] total 19 [2023-12-02 18:55:34,932 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [786881676] [2023-12-02 18:55:34,932 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 18:55:34,932 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-12-02 18:55:34,932 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:55:34,933 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-12-02 18:55:34,933 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=268, Unknown=0, NotChecked=0, Total=342 [2023-12-02 18:55:34,933 INFO L87 Difference]: Start difference. First operand 48 states and 56 transitions. Second operand has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 8 states have internal predecessors, (11), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-12-02 18:55:35,181 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:55:35,181 INFO L93 Difference]: Finished difference Result 70 states and 86 transitions. [2023-12-02 18:55:35,182 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-12-02 18:55:35,183 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 8 states have internal predecessors, (11), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 25 [2023-12-02 18:55:35,183 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:55:35,184 INFO L225 Difference]: With dead ends: 70 [2023-12-02 18:55:35,184 INFO L226 Difference]: Without dead ends: 46 [2023-12-02 18:55:35,185 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 50 SyntacticMatches, 6 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 143 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=74, Invalid=268, Unknown=0, NotChecked=0, Total=342 [2023-12-02 18:55:35,186 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 1 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 188 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 192 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 188 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-02 18:55:35,186 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 83 Invalid, 192 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 188 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-02 18:55:35,187 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2023-12-02 18:55:35,197 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 46. [2023-12-02 18:55:35,197 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 29 states have (on average 1.1724137931034482) internal successors, (34), 30 states have internal predecessors, (34), 10 states have call successors, (10), 6 states have call predecessors, (10), 6 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-12-02 18:55:35,198 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 53 transitions. [2023-12-02 18:55:35,198 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 53 transitions. Word has length 25 [2023-12-02 18:55:35,199 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:55:35,199 INFO L495 AbstractCegarLoop]: Abstraction has 46 states and 53 transitions. [2023-12-02 18:55:35,199 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 8 states have internal predecessors, (11), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-12-02 18:55:35,199 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 53 transitions. [2023-12-02 18:55:35,200 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2023-12-02 18:55:35,200 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:55:35,200 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:55:35,205 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-12-02 18:55:35,403 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:55:35,403 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:55:35,403 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:55:35,403 INFO L85 PathProgramCache]: Analyzing trace with hash 964329913, now seen corresponding path program 1 times [2023-12-02 18:55:35,403 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:55:35,403 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [265346806] [2023-12-02 18:55:35,403 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:35,404 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:55:35,413 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:55:35,413 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1871843228] [2023-12-02 18:55:35,413 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:35,413 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:55:35,413 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:55:35,414 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:55:35,415 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-12-02 18:55:35,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:55:35,463 INFO L262 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 5 conjunts are in the unsatisfiable core [2023-12-02 18:55:35,465 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:55:35,505 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-02 18:55:35,505 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:55:35,545 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-02 18:55:35,545 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:55:35,545 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [265346806] [2023-12-02 18:55:35,545 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:55:35,545 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1871843228] [2023-12-02 18:55:35,546 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1871843228] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:55:35,546 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1636164093] [2023-12-02 18:55:35,548 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-12-02 18:55:35,548 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:55:35,549 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:55:35,549 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:55:35,549 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:55:37,098 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 18:55:37,102 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:55:43,937 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1424#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 18:55:43,937 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 18:55:43,937 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:55:43,937 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5] total 8 [2023-12-02 18:55:43,937 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2015927781] [2023-12-02 18:55:43,938 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 18:55:43,938 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-12-02 18:55:43,938 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:55:43,938 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-12-02 18:55:43,939 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=315, Unknown=1, NotChecked=0, Total=380 [2023-12-02 18:55:43,939 INFO L87 Difference]: Start difference. First operand 46 states and 53 transitions. Second operand has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-12-02 18:55:44,124 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:55:44,124 INFO L93 Difference]: Finished difference Result 109 states and 130 transitions. [2023-12-02 18:55:44,125 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-12-02 18:55:44,125 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 27 [2023-12-02 18:55:44,125 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:55:44,126 INFO L225 Difference]: With dead ends: 109 [2023-12-02 18:55:44,126 INFO L226 Difference]: Without dead ends: 96 [2023-12-02 18:55:44,127 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 61 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 105 ImplicationChecksByTransitivity, 6.9s TimeCoverageRelationStatistics Valid=84, Invalid=421, Unknown=1, NotChecked=0, Total=506 [2023-12-02 18:55:44,127 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 40 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 63 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 68 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 63 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 18:55:44,128 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 119 Invalid, 68 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 63 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 18:55:44,128 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2023-12-02 18:55:44,145 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 91. [2023-12-02 18:55:44,145 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 58 states have (on average 1.1896551724137931) internal successors, (69), 60 states have internal predecessors, (69), 20 states have call successors, (20), 12 states have call predecessors, (20), 12 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2023-12-02 18:55:44,147 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 107 transitions. [2023-12-02 18:55:44,147 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 107 transitions. Word has length 27 [2023-12-02 18:55:44,147 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:55:44,148 INFO L495 AbstractCegarLoop]: Abstraction has 91 states and 107 transitions. [2023-12-02 18:55:44,148 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.875) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-12-02 18:55:44,148 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 107 transitions. [2023-12-02 18:55:44,149 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2023-12-02 18:55:44,149 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:55:44,149 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2023-12-02 18:55:44,155 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-12-02 18:55:44,355 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:55:44,355 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:55:44,355 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:55:44,356 INFO L85 PathProgramCache]: Analyzing trace with hash -327624414, now seen corresponding path program 1 times [2023-12-02 18:55:44,356 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:55:44,356 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1490823319] [2023-12-02 18:55:44,356 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:44,356 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:55:44,364 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:55:44,364 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1674097252] [2023-12-02 18:55:44,364 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:44,364 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:55:44,365 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:55:44,366 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:55:44,369 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-12-02 18:55:44,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:55:44,417 INFO L262 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 28 conjunts are in the unsatisfiable core [2023-12-02 18:55:44,420 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:55:44,627 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 11 proven. 22 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2023-12-02 18:55:44,627 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:55:44,728 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 20 proven. 7 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2023-12-02 18:55:44,728 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:55:44,728 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1490823319] [2023-12-02 18:55:44,728 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:55:44,729 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1674097252] [2023-12-02 18:55:44,729 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1674097252] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:55:44,729 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2060275504] [2023-12-02 18:55:44,731 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2023-12-02 18:55:44,731 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:55:44,732 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:55:44,732 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:55:44,732 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:55:45,909 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 18:55:45,912 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:55:48,868 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1944#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 18:55:48,868 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 18:55:48,868 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:55:48,868 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 6] total 13 [2023-12-02 18:55:48,868 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [28740624] [2023-12-02 18:55:48,868 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 18:55:48,869 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-12-02 18:55:48,869 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:55:48,870 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-12-02 18:55:48,870 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=355, Unknown=0, NotChecked=0, Total=420 [2023-12-02 18:55:48,870 INFO L87 Difference]: Start difference. First operand 91 states and 107 transitions. Second operand has 13 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 10 states have internal predecessors, (25), 5 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) [2023-12-02 18:55:49,242 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:55:49,243 INFO L93 Difference]: Finished difference Result 131 states and 161 transitions. [2023-12-02 18:55:49,243 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-12-02 18:55:49,243 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 10 states have internal predecessors, (25), 5 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) Word has length 35 [2023-12-02 18:55:49,244 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:55:49,246 INFO L225 Difference]: With dead ends: 131 [2023-12-02 18:55:49,246 INFO L226 Difference]: Without dead ends: 111 [2023-12-02 18:55:49,247 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 85 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 107 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=80, Invalid=426, Unknown=0, NotChecked=0, Total=506 [2023-12-02 18:55:49,247 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 34 mSDsluCounter, 161 mSDsCounter, 0 mSdLazyCounter, 162 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 188 SdHoareTripleChecker+Invalid, 188 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 162 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-12-02 18:55:49,248 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [44 Valid, 188 Invalid, 188 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 162 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-12-02 18:55:49,248 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2023-12-02 18:55:49,265 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 109. [2023-12-02 18:55:49,265 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 109 states, 69 states have (on average 1.1594202898550725) internal successors, (80), 73 states have internal predecessors, (80), 25 states have call successors, (25), 14 states have call predecessors, (25), 14 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) [2023-12-02 18:55:49,267 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 127 transitions. [2023-12-02 18:55:49,267 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 127 transitions. Word has length 35 [2023-12-02 18:55:49,267 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:55:49,267 INFO L495 AbstractCegarLoop]: Abstraction has 109 states and 127 transitions. [2023-12-02 18:55:49,267 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 10 states have internal predecessors, (25), 5 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) [2023-12-02 18:55:49,268 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 127 transitions. [2023-12-02 18:55:49,269 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2023-12-02 18:55:49,269 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:55:49,269 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:55:49,274 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2023-12-02 18:55:49,469 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2023-12-02 18:55:49,470 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:55:49,470 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:55:49,470 INFO L85 PathProgramCache]: Analyzing trace with hash 1605911421, now seen corresponding path program 1 times [2023-12-02 18:55:49,470 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:55:49,470 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1292077897] [2023-12-02 18:55:49,470 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:49,470 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:55:49,478 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:55:49,478 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [613150450] [2023-12-02 18:55:49,479 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:49,479 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:55:49,479 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:55:49,480 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:55:49,480 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-12-02 18:55:49,523 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:55:49,524 INFO L262 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 7 conjunts are in the unsatisfiable core [2023-12-02 18:55:49,526 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:55:49,582 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 42 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-12-02 18:55:49,582 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:55:49,640 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2023-12-02 18:55:49,640 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:55:49,641 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1292077897] [2023-12-02 18:55:49,641 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:55:49,641 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [613150450] [2023-12-02 18:55:49,641 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [613150450] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:55:49,641 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [759229283] [2023-12-02 18:55:49,644 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-12-02 18:55:49,644 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:55:49,644 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:55:49,644 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:55:49,645 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:55:50,572 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 18:55:50,575 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:55:55,121 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2567#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 18:55:55,122 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 18:55:55,122 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:55:55,122 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6] total 9 [2023-12-02 18:55:55,122 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [411440215] [2023-12-02 18:55:55,122 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 18:55:55,123 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-12-02 18:55:55,123 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:55:55,123 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-12-02 18:55:55,123 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=353, Unknown=0, NotChecked=0, Total=420 [2023-12-02 18:55:55,124 INFO L87 Difference]: Start difference. First operand 109 states and 127 transitions. Second operand has 9 states, 9 states have (on average 3.3333333333333335) internal successors, (30), 9 states have internal predecessors, (30), 5 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-12-02 18:55:55,310 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:55:55,310 INFO L93 Difference]: Finished difference Result 158 states and 182 transitions. [2023-12-02 18:55:55,310 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-12-02 18:55:55,310 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.3333333333333335) internal successors, (30), 9 states have internal predecessors, (30), 5 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 43 [2023-12-02 18:55:55,310 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:55:55,311 INFO L225 Difference]: With dead ends: 158 [2023-12-02 18:55:55,312 INFO L226 Difference]: Without dead ends: 143 [2023-12-02 18:55:55,312 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 107 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 114 ImplicationChecksByTransitivity, 4.6s TimeCoverageRelationStatistics Valid=78, Invalid=428, Unknown=0, NotChecked=0, Total=506 [2023-12-02 18:55:55,313 INFO L413 NwaCegarLoop]: 26 mSDtfsCounter, 35 mSDsluCounter, 116 mSDsCounter, 0 mSdLazyCounter, 84 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 142 SdHoareTripleChecker+Invalid, 86 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 84 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 18:55:55,313 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 142 Invalid, 86 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 84 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 18:55:55,314 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2023-12-02 18:55:55,332 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 138. [2023-12-02 18:55:55,332 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 138 states, 89 states have (on average 1.1348314606741574) internal successors, (101), 93 states have internal predecessors, (101), 30 states have call successors, (30), 18 states have call predecessors, (30), 18 states have return successors, (27), 26 states have call predecessors, (27), 27 states have call successors, (27) [2023-12-02 18:55:55,334 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 158 transitions. [2023-12-02 18:55:55,334 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 158 transitions. Word has length 43 [2023-12-02 18:55:55,334 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:55:55,334 INFO L495 AbstractCegarLoop]: Abstraction has 138 states and 158 transitions. [2023-12-02 18:55:55,335 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.3333333333333335) internal successors, (30), 9 states have internal predecessors, (30), 5 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-12-02 18:55:55,335 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 158 transitions. [2023-12-02 18:55:55,336 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2023-12-02 18:55:55,336 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:55:55,336 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:55:55,340 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2023-12-02 18:55:55,536 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-12-02 18:55:55,537 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:55:55,537 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:55:55,537 INFO L85 PathProgramCache]: Analyzing trace with hash 1607639299, now seen corresponding path program 1 times [2023-12-02 18:55:55,537 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:55:55,537 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1105886700] [2023-12-02 18:55:55,537 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:55,538 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:55:55,545 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:55:55,545 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [81431478] [2023-12-02 18:55:55,545 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:55,545 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:55:55,545 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:55:55,546 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:55:55,551 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-12-02 18:55:55,600 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:55:55,601 INFO L262 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 16 conjunts are in the unsatisfiable core [2023-12-02 18:55:55,603 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:55:55,761 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 11 proven. 16 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2023-12-02 18:55:55,761 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:55:55,997 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 14 proven. 16 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2023-12-02 18:55:55,997 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:55:55,997 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1105886700] [2023-12-02 18:55:55,997 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:55:55,997 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [81431478] [2023-12-02 18:55:55,997 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [81431478] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:55:55,997 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2000866959] [2023-12-02 18:55:56,000 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-12-02 18:55:56,000 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:55:56,000 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:55:56,000 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:55:56,000 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:55:56,883 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 18:55:56,889 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:55:57,966 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3270#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 18:55:57,967 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 18:55:57,967 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:55:57,967 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 11 [2023-12-02 18:55:57,967 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [535168502] [2023-12-02 18:55:57,967 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 18:55:57,968 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-12-02 18:55:57,968 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:55:57,968 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-12-02 18:55:57,969 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=391, Unknown=0, NotChecked=0, Total=462 [2023-12-02 18:55:57,969 INFO L87 Difference]: Start difference. First operand 138 states and 158 transitions. Second operand has 11 states, 11 states have (on average 2.6363636363636362) internal successors, (29), 10 states have internal predecessors, (29), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2023-12-02 18:55:58,119 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:55:58,119 INFO L93 Difference]: Finished difference Result 153 states and 175 transitions. [2023-12-02 18:55:58,119 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-12-02 18:55:58,119 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.6363636363636362) internal successors, (29), 10 states have internal predecessors, (29), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) Word has length 43 [2023-12-02 18:55:58,120 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:55:58,121 INFO L225 Difference]: With dead ends: 153 [2023-12-02 18:55:58,121 INFO L226 Difference]: Without dead ends: 151 [2023-12-02 18:55:58,122 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 107 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 99 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=80, Invalid=426, Unknown=0, NotChecked=0, Total=506 [2023-12-02 18:55:58,122 INFO L413 NwaCegarLoop]: 18 mSDtfsCounter, 21 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 63 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 74 SdHoareTripleChecker+Invalid, 74 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 63 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 18:55:58,123 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 74 Invalid, 74 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 63 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 18:55:58,124 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 151 states. [2023-12-02 18:55:58,139 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 151 to 148. [2023-12-02 18:55:58,139 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 148 states, 96 states have (on average 1.125) internal successors, (108), 100 states have internal predecessors, (108), 31 states have call successors, (31), 20 states have call predecessors, (31), 20 states have return successors, (28), 27 states have call predecessors, (28), 28 states have call successors, (28) [2023-12-02 18:55:58,140 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 167 transitions. [2023-12-02 18:55:58,140 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 167 transitions. Word has length 43 [2023-12-02 18:55:58,140 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:55:58,140 INFO L495 AbstractCegarLoop]: Abstraction has 148 states and 167 transitions. [2023-12-02 18:55:58,141 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.6363636363636362) internal successors, (29), 10 states have internal predecessors, (29), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2023-12-02 18:55:58,141 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 167 transitions. [2023-12-02 18:55:58,142 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2023-12-02 18:55:58,143 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:55:58,143 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:55:58,148 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-12-02 18:55:58,343 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:55:58,343 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:55:58,344 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:55:58,344 INFO L85 PathProgramCache]: Analyzing trace with hash -2003316837, now seen corresponding path program 1 times [2023-12-02 18:55:58,344 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:55:58,344 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2135512315] [2023-12-02 18:55:58,344 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:58,344 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:55:58,350 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:55:58,350 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1808251320] [2023-12-02 18:55:58,350 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:55:58,350 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:55:58,351 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:55:58,351 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:55:58,353 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-12-02 18:55:58,401 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:55:58,402 INFO L262 TraceCheckSpWp]: Trace formula consists of 145 conjuncts, 30 conjunts are in the unsatisfiable core [2023-12-02 18:55:58,405 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:55:58,769 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 15 proven. 31 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-12-02 18:55:58,769 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:56:04,943 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 15 proven. 31 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-12-02 18:56:04,944 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:56:04,944 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2135512315] [2023-12-02 18:56:04,944 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:56:04,944 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1808251320] [2023-12-02 18:56:04,944 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1808251320] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:56:04,944 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1265376156] [2023-12-02 18:56:04,946 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2023-12-02 18:56:04,946 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:56:04,946 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:56:04,947 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:56:04,947 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:56:06,358 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 18:56:06,361 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:56:22,476 WARN L293 SmtUtils]: Spent 14.20s on a formula simplification. DAG size of input: 83 DAG size of output: 79 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 18:56:25,453 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4059#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 18:56:25,454 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 18:56:25,454 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:56:25,454 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2023-12-02 18:56:25,454 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1195715289] [2023-12-02 18:56:25,454 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 18:56:25,455 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-12-02 18:56:25,455 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:56:25,456 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-12-02 18:56:25,456 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=616, Unknown=1, NotChecked=0, Total=702 [2023-12-02 18:56:25,456 INFO L87 Difference]: Start difference. First operand 148 states and 167 transitions. Second operand has 15 states, 15 states have (on average 2.466666666666667) internal successors, (37), 13 states have internal predecessors, (37), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2023-12-02 18:56:29,136 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:56:29,136 INFO L93 Difference]: Finished difference Result 177 states and 196 transitions. [2023-12-02 18:56:29,137 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-12-02 18:56:29,137 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.466666666666667) internal successors, (37), 13 states have internal predecessors, (37), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) Word has length 56 [2023-12-02 18:56:29,138 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:56:29,139 INFO L225 Difference]: With dead ends: 177 [2023-12-02 18:56:29,139 INFO L226 Difference]: Without dead ends: 173 [2023-12-02 18:56:29,140 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 171 GetRequests, 139 SyntacticMatches, 3 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 191 ImplicationChecksByTransitivity, 22.6s TimeCoverageRelationStatistics Valid=117, Invalid=812, Unknown=1, NotChecked=0, Total=930 [2023-12-02 18:56:29,140 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 57 mSDsluCounter, 136 mSDsCounter, 0 mSdLazyCounter, 156 mSolverCounterSat, 58 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 58 SdHoareTripleChecker+Valid, 161 SdHoareTripleChecker+Invalid, 214 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 58 IncrementalHoareTripleChecker+Valid, 156 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2023-12-02 18:56:29,140 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [58 Valid, 161 Invalid, 214 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [58 Valid, 156 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2023-12-02 18:56:29,141 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 173 states. [2023-12-02 18:56:29,172 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 173 to 169. [2023-12-02 18:56:29,173 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 169 states, 112 states have (on average 1.1071428571428572) internal successors, (124), 116 states have internal predecessors, (124), 32 states have call successors, (32), 25 states have call predecessors, (32), 24 states have return successors, (29), 27 states have call predecessors, (29), 29 states have call successors, (29) [2023-12-02 18:56:29,174 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 169 states to 169 states and 185 transitions. [2023-12-02 18:56:29,174 INFO L78 Accepts]: Start accepts. Automaton has 169 states and 185 transitions. Word has length 56 [2023-12-02 18:56:29,175 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:56:29,175 INFO L495 AbstractCegarLoop]: Abstraction has 169 states and 185 transitions. [2023-12-02 18:56:29,175 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.466666666666667) internal successors, (37), 13 states have internal predecessors, (37), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2023-12-02 18:56:29,175 INFO L276 IsEmpty]: Start isEmpty. Operand 169 states and 185 transitions. [2023-12-02 18:56:29,176 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2023-12-02 18:56:29,176 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:56:29,177 INFO L195 NwaCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:56:29,182 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2023-12-02 18:56:29,377 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:56:29,377 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:56:29,378 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:56:29,378 INFO L85 PathProgramCache]: Analyzing trace with hash -1317937589, now seen corresponding path program 1 times [2023-12-02 18:56:29,378 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:56:29,378 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1880431249] [2023-12-02 18:56:29,378 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:56:29,378 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:56:29,384 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:56:29,385 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1376829679] [2023-12-02 18:56:29,385 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:56:29,385 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:56:29,385 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:56:29,386 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:56:29,387 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-12-02 18:56:29,436 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:56:29,438 INFO L262 TraceCheckSpWp]: Trace formula consists of 165 conjuncts, 26 conjunts are in the unsatisfiable core [2023-12-02 18:56:29,441 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:56:29,796 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 19 proven. 39 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2023-12-02 18:56:29,796 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:56:30,470 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 22 proven. 36 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2023-12-02 18:56:30,470 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:56:30,470 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1880431249] [2023-12-02 18:56:30,470 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:56:30,470 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1376829679] [2023-12-02 18:56:30,470 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1376829679] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:56:30,470 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2023050726] [2023-12-02 18:56:30,473 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-12-02 18:56:30,473 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:56:30,473 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:56:30,473 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:56:30,473 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:56:31,905 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 18:56:31,907 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:57:00,816 WARN L293 SmtUtils]: Spent 25.66s on a formula simplification. DAG size of input: 83 DAG size of output: 79 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 18:57:03,586 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4983#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 18:57:03,586 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 18:57:03,587 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:57:03,587 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2023-12-02 18:57:03,587 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [258693275] [2023-12-02 18:57:03,587 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 18:57:03,587 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-12-02 18:57:03,587 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:57:03,588 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-12-02 18:57:03,588 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=115, Invalid=754, Unknown=1, NotChecked=0, Total=870 [2023-12-02 18:57:03,589 INFO L87 Difference]: Start difference. First operand 169 states and 185 transitions. Second operand has 17 states, 15 states have (on average 2.6) internal successors, (39), 15 states have internal predecessors, (39), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 7 states have call successors, (20) [2023-12-02 18:57:05,026 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:57:05,026 INFO L93 Difference]: Finished difference Result 184 states and 204 transitions. [2023-12-02 18:57:05,027 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-12-02 18:57:05,027 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 2.6) internal successors, (39), 15 states have internal predecessors, (39), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 7 states have call successors, (20) Word has length 67 [2023-12-02 18:57:05,027 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:57:05,028 INFO L225 Difference]: With dead ends: 184 [2023-12-02 18:57:05,028 INFO L226 Difference]: Without dead ends: 157 [2023-12-02 18:57:05,029 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 203 GetRequests, 169 SyntacticMatches, 3 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 246 ImplicationChecksByTransitivity, 32.1s TimeCoverageRelationStatistics Valid=138, Invalid=917, Unknown=1, NotChecked=0, Total=1056 [2023-12-02 18:57:05,030 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 27 mSDsluCounter, 198 mSDsCounter, 0 mSdLazyCounter, 235 mSolverCounterSat, 25 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 226 SdHoareTripleChecker+Invalid, 260 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 235 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2023-12-02 18:57:05,030 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 226 Invalid, 260 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 235 Invalid, 0 Unknown, 0 Unchecked, 1.3s Time] [2023-12-02 18:57:05,031 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 157 states. [2023-12-02 18:57:05,060 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 157 to 148. [2023-12-02 18:57:05,061 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 148 states, 98 states have (on average 1.1224489795918366) internal successors, (110), 100 states have internal predecessors, (110), 28 states have call successors, (28), 22 states have call predecessors, (28), 21 states have return successors, (26), 25 states have call predecessors, (26), 26 states have call successors, (26) [2023-12-02 18:57:05,062 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 164 transitions. [2023-12-02 18:57:05,062 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 164 transitions. Word has length 67 [2023-12-02 18:57:05,062 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:57:05,062 INFO L495 AbstractCegarLoop]: Abstraction has 148 states and 164 transitions. [2023-12-02 18:57:05,062 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 2.6) internal successors, (39), 15 states have internal predecessors, (39), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 7 states have call successors, (20) [2023-12-02 18:57:05,062 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 164 transitions. [2023-12-02 18:57:05,063 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2023-12-02 18:57:05,063 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:57:05,063 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:57:05,068 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2023-12-02 18:57:05,263 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:57:05,264 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:57:05,264 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:57:05,264 INFO L85 PathProgramCache]: Analyzing trace with hash 575510565, now seen corresponding path program 1 times [2023-12-02 18:57:05,264 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:57:05,264 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [302594135] [2023-12-02 18:57:05,264 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:57:05,265 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:57:05,271 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:57:05,271 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [481935757] [2023-12-02 18:57:05,271 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:57:05,271 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:57:05,271 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:57:05,272 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:57:05,273 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-12-02 18:57:05,319 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:57:05,320 INFO L262 TraceCheckSpWp]: Trace formula consists of 182 conjuncts, 4 conjunts are in the unsatisfiable core [2023-12-02 18:57:05,322 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:57:05,352 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 84 proven. 0 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2023-12-02 18:57:05,352 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-02 18:57:05,352 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:57:05,352 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [302594135] [2023-12-02 18:57:05,352 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:57:05,352 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [481935757] [2023-12-02 18:57:05,352 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [481935757] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-02 18:57:05,352 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-02 18:57:05,352 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-12-02 18:57:05,352 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1750492125] [2023-12-02 18:57:05,352 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-02 18:57:05,353 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-02 18:57:05,353 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:57:05,353 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-02 18:57:05,354 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2023-12-02 18:57:05,354 INFO L87 Difference]: Start difference. First operand 148 states and 164 transitions. Second operand has 5 states, 5 states have (on average 4.2) internal successors, (21), 5 states have internal predecessors, (21), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-12-02 18:57:05,460 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:57:05,460 INFO L93 Difference]: Finished difference Result 163 states and 179 transitions. [2023-12-02 18:57:05,461 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-12-02 18:57:05,461 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 5 states have internal predecessors, (21), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 77 [2023-12-02 18:57:05,461 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:57:05,462 INFO L225 Difference]: With dead ends: 163 [2023-12-02 18:57:05,462 INFO L226 Difference]: Without dead ends: 143 [2023-12-02 18:57:05,462 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 73 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2023-12-02 18:57:05,463 INFO L413 NwaCegarLoop]: 43 mSDtfsCounter, 11 mSDsluCounter, 48 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 18:57:05,463 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 91 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 18:57:05,464 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2023-12-02 18:57:05,496 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 140. [2023-12-02 18:57:05,496 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 140 states, 93 states have (on average 1.096774193548387) internal successors, (102), 95 states have internal predecessors, (102), 26 states have call successors, (26), 20 states have call predecessors, (26), 20 states have return successors, (25), 24 states have call predecessors, (25), 25 states have call successors, (25) [2023-12-02 18:57:05,497 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 153 transitions. [2023-12-02 18:57:05,497 INFO L78 Accepts]: Start accepts. Automaton has 140 states and 153 transitions. Word has length 77 [2023-12-02 18:57:05,497 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:57:05,497 INFO L495 AbstractCegarLoop]: Abstraction has 140 states and 153 transitions. [2023-12-02 18:57:05,498 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 5 states have internal predecessors, (21), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-12-02 18:57:05,498 INFO L276 IsEmpty]: Start isEmpty. Operand 140 states and 153 transitions. [2023-12-02 18:57:05,499 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2023-12-02 18:57:05,499 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:57:05,499 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2023-12-02 18:57:05,503 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2023-12-02 18:57:05,699 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2023-12-02 18:57:05,700 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:57:05,700 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:57:05,700 INFO L85 PathProgramCache]: Analyzing trace with hash -362747475, now seen corresponding path program 2 times [2023-12-02 18:57:05,700 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:57:05,700 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1293477702] [2023-12-02 18:57:05,700 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:57:05,700 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:57:05,708 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:57:05,708 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [843758386] [2023-12-02 18:57:05,708 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-02 18:57:05,708 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:57:05,708 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:57:05,709 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:57:05,710 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-12-02 18:57:05,801 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-12-02 18:57:05,801 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 18:57:05,803 INFO L262 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 30 conjunts are in the unsatisfiable core [2023-12-02 18:57:05,805 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:57:06,100 INFO L134 CoverageAnalysis]: Checked inductivity of 310 backedges. 41 proven. 38 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-12-02 18:57:06,101 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:57:07,545 INFO L134 CoverageAnalysis]: Checked inductivity of 310 backedges. 41 proven. 32 refuted. 0 times theorem prover too weak. 237 trivial. 0 not checked. [2023-12-02 18:57:07,546 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:57:07,546 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1293477702] [2023-12-02 18:57:07,546 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:57:07,546 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [843758386] [2023-12-02 18:57:07,546 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [843758386] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:57:07,546 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [103064246] [2023-12-02 18:57:07,548 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2023-12-02 18:57:07,548 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:57:07,549 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:57:07,549 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:57:07,549 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:57:08,869 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 18:57:08,872 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:57:26,825 WARN L293 SmtUtils]: Spent 14.73s on a formula simplification. DAG size of input: 83 DAG size of output: 79 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 18:57:29,465 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '6620#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 18:57:29,465 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 18:57:29,465 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:57:29,465 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 17 [2023-12-02 18:57:29,465 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [395960752] [2023-12-02 18:57:29,465 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 18:57:29,466 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-12-02 18:57:29,466 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:57:29,466 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-12-02 18:57:29,467 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=98, Invalid=713, Unknown=1, NotChecked=0, Total=812 [2023-12-02 18:57:29,467 INFO L87 Difference]: Start difference. First operand 140 states and 153 transitions. Second operand has 17 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 9 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) [2023-12-02 18:57:30,838 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:57:30,838 INFO L93 Difference]: Finished difference Result 156 states and 174 transitions. [2023-12-02 18:57:30,838 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-12-02 18:57:30,838 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 9 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) Word has length 79 [2023-12-02 18:57:30,839 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:57:30,840 INFO L225 Difference]: With dead ends: 156 [2023-12-02 18:57:30,840 INFO L226 Difference]: Without dead ends: 154 [2023-12-02 18:57:30,840 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 238 GetRequests, 205 SyntacticMatches, 4 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 223 ImplicationChecksByTransitivity, 21.8s TimeCoverageRelationStatistics Valid=117, Invalid=812, Unknown=1, NotChecked=0, Total=930 [2023-12-02 18:57:30,841 INFO L413 NwaCegarLoop]: 32 mSDtfsCounter, 34 mSDsluCounter, 155 mSDsCounter, 0 mSdLazyCounter, 191 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 42 SdHoareTripleChecker+Valid, 187 SdHoareTripleChecker+Invalid, 230 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 191 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-12-02 18:57:30,841 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [42 Valid, 187 Invalid, 230 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 191 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-12-02 18:57:30,842 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 154 states. [2023-12-02 18:57:30,874 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 154 to 151. [2023-12-02 18:57:30,875 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 151 states, 99 states have (on average 1.101010101010101) internal successors, (109), 102 states have internal predecessors, (109), 30 states have call successors, (30), 21 states have call predecessors, (30), 21 states have return successors, (29), 27 states have call predecessors, (29), 29 states have call successors, (29) [2023-12-02 18:57:30,876 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 151 states to 151 states and 168 transitions. [2023-12-02 18:57:30,876 INFO L78 Accepts]: Start accepts. Automaton has 151 states and 168 transitions. Word has length 79 [2023-12-02 18:57:30,877 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:57:30,877 INFO L495 AbstractCegarLoop]: Abstraction has 151 states and 168 transitions. [2023-12-02 18:57:30,877 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 9 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) [2023-12-02 18:57:30,877 INFO L276 IsEmpty]: Start isEmpty. Operand 151 states and 168 transitions. [2023-12-02 18:57:30,878 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2023-12-02 18:57:30,878 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:57:30,878 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 5, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 18:57:30,882 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2023-12-02 18:57:31,078 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2023-12-02 18:57:31,078 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:57:31,079 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:57:31,079 INFO L85 PathProgramCache]: Analyzing trace with hash -1935639157, now seen corresponding path program 1 times [2023-12-02 18:57:31,079 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:57:31,079 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [910193036] [2023-12-02 18:57:31,079 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:57:31,079 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:57:31,087 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:57:31,087 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [839745416] [2023-12-02 18:57:31,087 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:57:31,087 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:57:31,088 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:57:31,088 INFO L229 MonitoredProcess]: Starting monitored process 15 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:57:31,089 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2023-12-02 18:57:31,139 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:57:31,140 INFO L262 TraceCheckSpWp]: Trace formula consists of 208 conjuncts, 11 conjunts are in the unsatisfiable core [2023-12-02 18:57:31,142 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:57:31,232 INFO L134 CoverageAnalysis]: Checked inductivity of 382 backedges. 72 proven. 260 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2023-12-02 18:57:31,232 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:57:31,305 INFO L134 CoverageAnalysis]: Checked inductivity of 382 backedges. 26 proven. 44 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2023-12-02 18:57:31,305 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:57:31,305 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [910193036] [2023-12-02 18:57:31,305 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:57:31,305 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [839745416] [2023-12-02 18:57:31,305 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [839745416] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:57:31,306 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1339562025] [2023-12-02 18:57:31,307 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-12-02 18:57:31,308 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:57:31,308 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:57:31,308 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:57:31,308 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:57:32,145 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 18:57:32,148 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:57:37,466 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '7591#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 18:57:37,466 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 18:57:37,466 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 18:57:37,466 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8] total 8 [2023-12-02 18:57:37,466 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [686697027] [2023-12-02 18:57:37,466 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 18:57:37,467 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-12-02 18:57:37,467 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 18:57:37,467 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-12-02 18:57:37,468 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=345, Unknown=1, NotChecked=0, Total=420 [2023-12-02 18:57:37,468 INFO L87 Difference]: Start difference. First operand 151 states and 168 transitions. Second operand has 8 states, 8 states have (on average 4.625) internal successors, (37), 8 states have internal predecessors, (37), 5 states have call successors, (27), 6 states have call predecessors, (27), 6 states have return successors, (26), 5 states have call predecessors, (26), 5 states have call successors, (26) [2023-12-02 18:57:37,604 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 18:57:37,604 INFO L93 Difference]: Finished difference Result 197 states and 221 transitions. [2023-12-02 18:57:37,604 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-12-02 18:57:37,604 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 4.625) internal successors, (37), 8 states have internal predecessors, (37), 5 states have call successors, (27), 6 states have call predecessors, (27), 6 states have return successors, (26), 5 states have call predecessors, (26), 5 states have call successors, (26) Word has length 86 [2023-12-02 18:57:37,605 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 18:57:37,606 INFO L225 Difference]: With dead ends: 197 [2023-12-02 18:57:37,606 INFO L226 Difference]: Without dead ends: 153 [2023-12-02 18:57:37,606 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 260 GetRequests, 231 SyntacticMatches, 6 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 129 ImplicationChecksByTransitivity, 5.4s TimeCoverageRelationStatistics Valid=102, Invalid=497, Unknown=1, NotChecked=0, Total=600 [2023-12-02 18:57:37,607 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 8 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 59 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 109 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 59 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 18:57:37,607 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 109 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 59 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 18:57:37,608 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 153 states. [2023-12-02 18:57:37,641 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 153 to 153. [2023-12-02 18:57:37,641 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 153 states, 101 states have (on average 1.099009900990099) internal successors, (111), 104 states have internal predecessors, (111), 30 states have call successors, (30), 21 states have call predecessors, (30), 21 states have return successors, (29), 27 states have call predecessors, (29), 29 states have call successors, (29) [2023-12-02 18:57:37,642 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 153 states to 153 states and 170 transitions. [2023-12-02 18:57:37,643 INFO L78 Accepts]: Start accepts. Automaton has 153 states and 170 transitions. Word has length 86 [2023-12-02 18:57:37,643 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 18:57:37,643 INFO L495 AbstractCegarLoop]: Abstraction has 153 states and 170 transitions. [2023-12-02 18:57:37,643 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 4.625) internal successors, (37), 8 states have internal predecessors, (37), 5 states have call successors, (27), 6 states have call predecessors, (27), 6 states have return successors, (26), 5 states have call predecessors, (26), 5 states have call successors, (26) [2023-12-02 18:57:37,643 INFO L276 IsEmpty]: Start isEmpty. Operand 153 states and 170 transitions. [2023-12-02 18:57:37,644 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2023-12-02 18:57:37,644 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 18:57:37,644 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2023-12-02 18:57:37,648 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2023-12-02 18:57:37,844 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2023-12-02 18:57:37,844 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 18:57:37,845 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 18:57:37,845 INFO L85 PathProgramCache]: Analyzing trace with hash 9999174, now seen corresponding path program 1 times [2023-12-02 18:57:37,845 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 18:57:37,845 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [596713025] [2023-12-02 18:57:37,845 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:57:37,845 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 18:57:37,851 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 18:57:37,852 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [94931115] [2023-12-02 18:57:37,852 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 18:57:37,852 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 18:57:37,852 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 18:57:37,853 INFO L229 MonitoredProcess]: Starting monitored process 16 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 18:57:37,858 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2023-12-02 18:57:38,211 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 18:57:38,213 INFO L262 TraceCheckSpWp]: Trace formula consists of 211 conjuncts, 39 conjunts are in the unsatisfiable core [2023-12-02 18:57:38,215 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 18:57:38,908 INFO L134 CoverageAnalysis]: Checked inductivity of 365 backedges. 25 proven. 64 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2023-12-02 18:57:38,908 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 18:58:07,369 WARN L293 SmtUtils]: Spent 8.89s on a formula simplification that was a NOOP. DAG size: 215 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 18:59:44,317 INFO L134 CoverageAnalysis]: Checked inductivity of 365 backedges. 25 proven. 64 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2023-12-02 18:59:44,317 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 18:59:44,317 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [596713025] [2023-12-02 18:59:44,317 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 18:59:44,317 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [94931115] [2023-12-02 18:59:44,317 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [94931115] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 18:59:44,317 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1828587976] [2023-12-02 18:59:44,319 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2023-12-02 18:59:44,319 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 18:59:44,320 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 18:59:44,320 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 18:59:44,320 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 18:59:45,630 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 18:59:45,633 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 18:59:57,441 WARN L293 SmtUtils]: Spent 9.53s on a formula simplification. DAG size of input: 83 DAG size of output: 79 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 19:00:02,196 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '8643#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 19:00:02,196 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 19:00:02,196 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 19:00:02,196 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 19 [2023-12-02 19:00:02,196 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [365256485] [2023-12-02 19:00:02,196 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 19:00:02,197 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2023-12-02 19:00:02,197 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 19:00:02,198 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2023-12-02 19:00:02,198 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=890, Unknown=2, NotChecked=0, Total=992 [2023-12-02 19:00:02,198 INFO L87 Difference]: Start difference. First operand 153 states and 170 transitions. Second operand has 19 states, 19 states have (on average 2.5789473684210527) internal successors, (49), 17 states have internal predecessors, (49), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 8 states have call predecessors, (26), 9 states have call successors, (26) [2023-12-02 19:00:16,521 WARN L293 SmtUtils]: Spent 11.88s on a formula simplification. DAG size of input: 85 DAG size of output: 74 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 19:00:18,834 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-12-02 19:00:25,063 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 19:00:25,063 INFO L93 Difference]: Finished difference Result 172 states and 196 transitions. [2023-12-02 19:00:25,064 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-12-02 19:00:25,064 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 2.5789473684210527) internal successors, (49), 17 states have internal predecessors, (49), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 8 states have call predecessors, (26), 9 states have call successors, (26) Word has length 87 [2023-12-02 19:00:25,065 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 19:00:25,066 INFO L225 Difference]: With dead ends: 172 [2023-12-02 19:00:25,066 INFO L226 Difference]: Without dead ends: 170 [2023-12-02 19:00:25,067 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 266 GetRequests, 226 SyntacticMatches, 4 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 291 ImplicationChecksByTransitivity, 45.3s TimeCoverageRelationStatistics Valid=143, Invalid=1261, Unknown=2, NotChecked=0, Total=1406 [2023-12-02 19:00:25,067 INFO L413 NwaCegarLoop]: 36 mSDtfsCounter, 43 mSDsluCounter, 315 mSDsCounter, 0 mSdLazyCounter, 338 mSolverCounterSat, 42 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 351 SdHoareTripleChecker+Invalid, 381 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 42 IncrementalHoareTripleChecker+Valid, 338 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.0s IncrementalHoareTripleChecker+Time [2023-12-02 19:00:25,067 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 351 Invalid, 381 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [42 Valid, 338 Invalid, 1 Unknown, 0 Unchecked, 5.0s Time] [2023-12-02 19:00:25,068 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 170 states. [2023-12-02 19:00:25,116 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 170 to 154. [2023-12-02 19:00:25,117 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 154 states, 102 states have (on average 1.107843137254902) internal successors, (113), 104 states have internal predecessors, (113), 30 states have call successors, (30), 21 states have call predecessors, (30), 21 states have return successors, (29), 28 states have call predecessors, (29), 29 states have call successors, (29) [2023-12-02 19:00:25,118 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 154 states to 154 states and 172 transitions. [2023-12-02 19:00:25,118 INFO L78 Accepts]: Start accepts. Automaton has 154 states and 172 transitions. Word has length 87 [2023-12-02 19:00:25,118 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 19:00:25,118 INFO L495 AbstractCegarLoop]: Abstraction has 154 states and 172 transitions. [2023-12-02 19:00:25,119 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 2.5789473684210527) internal successors, (49), 17 states have internal predecessors, (49), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 8 states have call predecessors, (26), 9 states have call successors, (26) [2023-12-02 19:00:25,119 INFO L276 IsEmpty]: Start isEmpty. Operand 154 states and 172 transitions. [2023-12-02 19:00:25,120 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2023-12-02 19:00:25,120 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 19:00:25,120 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1] [2023-12-02 19:00:25,124 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2023-12-02 19:00:25,320 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2023-12-02 19:00:25,321 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 19:00:25,321 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 19:00:25,321 INFO L85 PathProgramCache]: Analyzing trace with hash 11727052, now seen corresponding path program 3 times [2023-12-02 19:00:25,321 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 19:00:25,321 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1986365749] [2023-12-02 19:00:25,321 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:00:25,321 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 19:00:25,330 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 19:00:25,330 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [577689212] [2023-12-02 19:00:25,330 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-12-02 19:00:25,330 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:00:25,330 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 19:00:25,331 INFO L229 MonitoredProcess]: Starting monitored process 17 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 19:00:25,332 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2023-12-02 19:00:25,392 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-12-02 19:00:25,392 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-02 19:00:25,394 INFO L262 TraceCheckSpWp]: Trace formula consists of 211 conjuncts, 13 conjunts are in the unsatisfiable core [2023-12-02 19:00:25,395 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 19:00:25,504 INFO L134 CoverageAnalysis]: Checked inductivity of 367 backedges. 321 proven. 2 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2023-12-02 19:00:25,504 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 19:00:25,584 INFO L134 CoverageAnalysis]: Checked inductivity of 367 backedges. 53 proven. 2 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2023-12-02 19:00:25,584 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 19:00:25,584 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1986365749] [2023-12-02 19:00:25,584 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 19:00:25,584 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [577689212] [2023-12-02 19:00:25,584 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [577689212] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 19:00:25,585 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1865861780] [2023-12-02 19:00:25,586 INFO L159 IcfgInterpreter]: Started Sifa with 18 locations of interest [2023-12-02 19:00:25,586 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 19:00:25,587 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 19:00:25,587 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 19:00:25,587 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 19:00:27,117 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 19:00:27,120 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 19:00:38,895 WARN L293 SmtUtils]: Spent 10.56s on a formula simplification. DAG size of input: 83 DAG size of output: 79 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 19:00:41,391 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '9658#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 19:00:41,391 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 19:00:41,391 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 19:00:41,391 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 9] total 9 [2023-12-02 19:00:41,391 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1993677983] [2023-12-02 19:00:41,392 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 19:00:41,392 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-12-02 19:00:41,392 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 19:00:41,393 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-12-02 19:00:41,393 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=372, Unknown=1, NotChecked=0, Total=462 [2023-12-02 19:00:41,393 INFO L87 Difference]: Start difference. First operand 154 states and 172 transitions. Second operand has 9 states, 9 states have (on average 4.333333333333333) internal successors, (39), 9 states have internal predecessors, (39), 6 states have call successors, (27), 7 states have call predecessors, (27), 6 states have return successors, (26), 5 states have call predecessors, (26), 5 states have call successors, (26) [2023-12-02 19:00:41,603 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 19:00:41,603 INFO L93 Difference]: Finished difference Result 188 states and 205 transitions. [2023-12-02 19:00:41,603 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-12-02 19:00:41,603 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 4.333333333333333) internal successors, (39), 9 states have internal predecessors, (39), 6 states have call successors, (27), 7 states have call predecessors, (27), 6 states have return successors, (26), 5 states have call predecessors, (26), 5 states have call successors, (26) Word has length 87 [2023-12-02 19:00:41,604 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 19:00:41,604 INFO L225 Difference]: With dead ends: 188 [2023-12-02 19:00:41,605 INFO L226 Difference]: Without dead ends: 143 [2023-12-02 19:00:41,605 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 260 GetRequests, 230 SyntacticMatches, 9 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 119 ImplicationChecksByTransitivity, 14.3s TimeCoverageRelationStatistics Valid=98, Invalid=407, Unknown=1, NotChecked=0, Total=506 [2023-12-02 19:00:41,606 INFO L413 NwaCegarLoop]: 74 mSDtfsCounter, 30 mSDsluCounter, 111 mSDsCounter, 0 mSdLazyCounter, 84 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 185 SdHoareTripleChecker+Invalid, 89 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 84 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-02 19:00:41,606 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 185 Invalid, 89 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 84 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-02 19:00:41,606 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2023-12-02 19:00:41,649 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 141. [2023-12-02 19:00:41,649 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 141 states, 95 states have (on average 1.0526315789473684) internal successors, (100), 97 states have internal predecessors, (100), 24 states have call successors, (24), 21 states have call predecessors, (24), 21 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2023-12-02 19:00:41,650 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 141 states to 141 states and 147 transitions. [2023-12-02 19:00:41,651 INFO L78 Accepts]: Start accepts. Automaton has 141 states and 147 transitions. Word has length 87 [2023-12-02 19:00:41,651 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 19:00:41,651 INFO L495 AbstractCegarLoop]: Abstraction has 141 states and 147 transitions. [2023-12-02 19:00:41,651 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 4.333333333333333) internal successors, (39), 9 states have internal predecessors, (39), 6 states have call successors, (27), 7 states have call predecessors, (27), 6 states have return successors, (26), 5 states have call predecessors, (26), 5 states have call successors, (26) [2023-12-02 19:00:41,651 INFO L276 IsEmpty]: Start isEmpty. Operand 141 states and 147 transitions. [2023-12-02 19:00:41,652 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2023-12-02 19:00:41,653 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 19:00:41,653 INFO L195 NwaCegarLoop]: trace histogram [15, 14, 14, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 19:00:41,657 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2023-12-02 19:00:41,853 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2023-12-02 19:00:41,853 INFO L420 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 19:00:41,854 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 19:00:41,854 INFO L85 PathProgramCache]: Analyzing trace with hash 67974809, now seen corresponding path program 1 times [2023-12-02 19:00:41,854 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 19:00:41,854 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1652848613] [2023-12-02 19:00:41,854 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:00:41,854 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 19:00:41,861 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 19:00:41,861 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [962585369] [2023-12-02 19:00:41,861 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:00:41,861 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:00:41,861 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 19:00:41,862 INFO L229 MonitoredProcess]: Starting monitored process 18 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 19:00:41,864 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2023-12-02 19:00:41,925 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-02 19:00:41,926 INFO L262 TraceCheckSpWp]: Trace formula consists of 220 conjuncts, 26 conjunts are in the unsatisfiable core [2023-12-02 19:00:41,928 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-02 19:00:42,144 INFO L134 CoverageAnalysis]: Checked inductivity of 419 backedges. 27 proven. 67 refuted. 0 times theorem prover too weak. 325 trivial. 0 not checked. [2023-12-02 19:00:42,144 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-02 19:00:43,080 INFO L134 CoverageAnalysis]: Checked inductivity of 419 backedges. 27 proven. 67 refuted. 0 times theorem prover too weak. 325 trivial. 0 not checked. [2023-12-02 19:00:43,080 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-12-02 19:00:43,081 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1652848613] [2023-12-02 19:00:43,081 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-02 19:00:43,081 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [962585369] [2023-12-02 19:00:43,081 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [962585369] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-02 19:00:43,081 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [483970738] [2023-12-02 19:00:43,082 INFO L159 IcfgInterpreter]: Started Sifa with 20 locations of interest [2023-12-02 19:00:43,082 INFO L166 IcfgInterpreter]: Building call graph [2023-12-02 19:00:43,083 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-12-02 19:00:43,083 INFO L176 IcfgInterpreter]: Starting interpretation [2023-12-02 19:00:43,083 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-12-02 19:00:44,417 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-12-02 19:00:44,420 INFO L180 IcfgInterpreter]: Interpretation finished [2023-12-02 19:01:01,543 WARN L293 SmtUtils]: Spent 14.01s on a formula simplification. DAG size of input: 83 DAG size of output: 79 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-02 19:01:04,224 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '10696#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-12-02 19:01:04,225 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-12-02 19:01:04,225 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-02 19:01:04,225 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 16 [2023-12-02 19:01:04,225 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1480658754] [2023-12-02 19:01:04,225 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-02 19:01:04,225 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2023-12-02 19:01:04,225 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-12-02 19:01:04,226 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2023-12-02 19:01:04,226 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=778, Unknown=1, NotChecked=0, Total=870 [2023-12-02 19:01:04,226 INFO L87 Difference]: Start difference. First operand 141 states and 147 transitions. Second operand has 16 states, 16 states have (on average 3.0625) internal successors, (49), 15 states have internal predecessors, (49), 8 states have call successors, (30), 3 states have call predecessors, (30), 2 states have return successors, (28), 6 states have call predecessors, (28), 8 states have call successors, (28) [2023-12-02 19:01:04,591 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-02 19:01:04,591 INFO L93 Difference]: Finished difference Result 151 states and 157 transitions. [2023-12-02 19:01:04,591 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-12-02 19:01:04,591 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.0625) internal successors, (49), 15 states have internal predecessors, (49), 8 states have call successors, (30), 3 states have call predecessors, (30), 2 states have return successors, (28), 6 states have call predecessors, (28), 8 states have call successors, (28) Word has length 92 [2023-12-02 19:01:04,592 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-02 19:01:04,592 INFO L225 Difference]: With dead ends: 151 [2023-12-02 19:01:04,592 INFO L226 Difference]: Without dead ends: 119 [2023-12-02 19:01:04,593 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 276 GetRequests, 242 SyntacticMatches, 5 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 239 ImplicationChecksByTransitivity, 20.1s TimeCoverageRelationStatistics Valid=100, Invalid=829, Unknown=1, NotChecked=0, Total=930 [2023-12-02 19:01:04,593 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 16 mSDsluCounter, 192 mSDsCounter, 0 mSdLazyCounter, 216 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 222 SdHoareTripleChecker+Invalid, 218 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 216 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-12-02 19:01:04,594 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 222 Invalid, 218 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 216 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-12-02 19:01:04,594 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2023-12-02 19:01:04,630 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 119. [2023-12-02 19:01:04,631 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 119 states, 80 states have (on average 1.05) internal successors, (84), 82 states have internal predecessors, (84), 20 states have call successors, (20), 18 states have call predecessors, (20), 18 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2023-12-02 19:01:04,631 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 119 states to 119 states and 123 transitions. [2023-12-02 19:01:04,631 INFO L78 Accepts]: Start accepts. Automaton has 119 states and 123 transitions. Word has length 92 [2023-12-02 19:01:04,631 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-02 19:01:04,632 INFO L495 AbstractCegarLoop]: Abstraction has 119 states and 123 transitions. [2023-12-02 19:01:04,632 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.0625) internal successors, (49), 15 states have internal predecessors, (49), 8 states have call successors, (30), 3 states have call predecessors, (30), 2 states have return successors, (28), 6 states have call predecessors, (28), 8 states have call successors, (28) [2023-12-02 19:01:04,632 INFO L276 IsEmpty]: Start isEmpty. Operand 119 states and 123 transitions. [2023-12-02 19:01:04,632 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2023-12-02 19:01:04,633 INFO L187 NwaCegarLoop]: Found error trace [2023-12-02 19:01:04,633 INFO L195 NwaCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 19:01:04,637 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2023-12-02 19:01:04,833 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,18 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:01:04,833 INFO L420 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-02 19:01:04,834 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-02 19:01:04,834 INFO L85 PathProgramCache]: Analyzing trace with hash -1281801341, now seen corresponding path program 2 times [2023-12-02 19:01:04,834 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-12-02 19:01:04,834 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [701234818] [2023-12-02 19:01:04,834 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-02 19:01:04,834 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-02 19:01:04,841 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-02 19:01:04,841 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [927092853] [2023-12-02 19:01:04,842 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-02 19:01:04,842 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:01:04,842 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 [2023-12-02 19:01:04,843 INFO L229 MonitoredProcess]: Starting monitored process 19 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-02 19:01:04,843 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2023-12-02 19:01:04,944 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2023-12-02 19:01:04,944 INFO L229 tOrderPrioritization]: Conjunction of SSA is sat [2023-12-02 19:01:04,944 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-12-02 19:01:04,969 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-12-02 19:01:04,999 INFO L130 FreeRefinementEngine]: Strategy SIFA_TAIPAN found a feasible trace [2023-12-02 19:01:04,999 INFO L360 BasicCegarLoop]: Counterexample is feasible [2023-12-02 19:01:05,000 INFO L805 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2023-12-02 19:01:05,006 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2023-12-02 19:01:05,201 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,19 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-02 19:01:05,204 INFO L445 BasicCegarLoop]: Path program histogram: [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-02 19:01:05,207 INFO L178 ceAbstractionStarter]: Computing trace abstraction results [2023-12-02 19:01:05,224 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated [2023-12-02 19:01:05,226 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated [2023-12-02 19:01:05,227 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated [2023-12-02 19:01:05,228 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated [2023-12-02 19:01:05,229 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post7 could not be translated [2023-12-02 19:01:05,230 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post7 could not be translated [2023-12-02 19:01:05,240 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 02.12 07:01:05 BoogieIcfgContainer [2023-12-02 19:01:05,240 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2023-12-02 19:01:05,241 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2023-12-02 19:01:05,241 INFO L270 PluginConnector]: Initializing Witness Printer... [2023-12-02 19:01:05,241 INFO L274 PluginConnector]: Witness Printer initialized [2023-12-02 19:01:05,241 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.12 06:55:29" (3/4) ... [2023-12-02 19:01:05,242 INFO L131 WitnessPrinter]: Generating witness for reachability counterexample [2023-12-02 19:01:05,250 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated [2023-12-02 19:01:05,251 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated [2023-12-02 19:01:05,253 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated [2023-12-02 19:01:05,254 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated [2023-12-02 19:01:05,255 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post7 could not be translated [2023-12-02 19:01:05,256 WARN L1572 BoogieBacktranslator]: Unfinished Backtranslation: IdentifierExpression #t~post7 could not be translated [2023-12-02 19:01:05,296 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/witness.graphml [2023-12-02 19:01:05,297 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2023-12-02 19:01:05,297 INFO L158 Benchmark]: Toolchain (without parser) took 336125.62ms. Allocated memory was 161.5MB in the beginning and 234.9MB in the end (delta: 73.4MB). Free memory was 129.3MB in the beginning and 163.0MB in the end (delta: -33.7MB). Peak memory consumption was 39.6MB. Max. memory is 16.1GB. [2023-12-02 19:01:05,298 INFO L158 Benchmark]: CDTParser took 0.17ms. Allocated memory is still 115.3MB. Free memory is still 88.4MB. There was no memory consumed. Max. memory is 16.1GB. [2023-12-02 19:01:05,298 INFO L158 Benchmark]: CACSL2BoogieTranslator took 207.53ms. Allocated memory is still 161.5MB. Free memory was 128.6MB in the beginning and 118.3MB in the end (delta: 10.3MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2023-12-02 19:01:05,298 INFO L158 Benchmark]: Boogie Procedure Inliner took 36.43ms. Allocated memory is still 161.5MB. Free memory was 118.3MB in the beginning and 116.2MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2023-12-02 19:01:05,299 INFO L158 Benchmark]: Boogie Preprocessor took 22.12ms. Allocated memory is still 161.5MB. Free memory was 116.2MB in the beginning and 115.5MB in the end (delta: 683.8kB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2023-12-02 19:01:05,299 INFO L158 Benchmark]: RCFGBuilder took 358.15ms. Allocated memory is still 161.5MB. Free memory was 114.8MB in the beginning and 124.7MB in the end (delta: -9.9MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2023-12-02 19:01:05,300 INFO L158 Benchmark]: TraceAbstraction took 335439.91ms. Allocated memory was 161.5MB in the beginning and 234.9MB in the end (delta: 73.4MB). Free memory was 124.3MB in the beginning and 167.2MB in the end (delta: -42.9MB). Peak memory consumption was 33.6MB. Max. memory is 16.1GB. [2023-12-02 19:01:05,300 INFO L158 Benchmark]: Witness Printer took 55.92ms. Allocated memory is still 234.9MB. Free memory was 167.2MB in the beginning and 163.0MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2023-12-02 19:01:05,302 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.17ms. Allocated memory is still 115.3MB. Free memory is still 88.4MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 207.53ms. Allocated memory is still 161.5MB. Free memory was 128.6MB in the beginning and 118.3MB in the end (delta: 10.3MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 36.43ms. Allocated memory is still 161.5MB. Free memory was 118.3MB in the beginning and 116.2MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 22.12ms. Allocated memory is still 161.5MB. Free memory was 116.2MB in the beginning and 115.5MB in the end (delta: 683.8kB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 358.15ms. Allocated memory is still 161.5MB. Free memory was 114.8MB in the beginning and 124.7MB in the end (delta: -9.9MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * TraceAbstraction took 335439.91ms. Allocated memory was 161.5MB in the beginning and 234.9MB in the end (delta: 73.4MB). Free memory was 124.3MB in the beginning and 167.2MB in the end (delta: -42.9MB). Peak memory consumption was 33.6MB. Max. memory is 16.1GB. * Witness Printer took 55.92ms. Allocated memory is still 234.9MB. Free memory was 167.2MB in the beginning and 163.0MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post7 could not be translated - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post7 could not be translated - GenericResult: Unfinished Backtranslation The program execution was not completely translated back. - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post6 could not be translated - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post7 could not be translated - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: IdentifierExpression #t~post7 could not be translated - GenericResult: Unfinished Backtranslation The program execution was not completely translated back. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 17]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L22] int counter = 0; [L24] unsigned int A, B; [L25] long long r, d, p, q; [L26] A = __VERIFIER_nondet_uint() [L27] B = __VERIFIER_nondet_uint() [L28] CALL assume_abort_if_not(B >= 1) [L12] COND FALSE !(!cond) [L28] RET assume_abort_if_not(B >= 1) [L30] r = A [L31] d = B [L32] p = 1 [L33] q = 0 VAL [A=-4294967292, B=1, counter=0, d=1, p=1, q=0, r=4] [L35] EXPR counter++ VAL [A=-4294967292, B=1, counter=1, d=1, p=1, q=0, r=4] [L35] COND TRUE counter++<5 [L36] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=1] [L36] RET __VERIFIER_assert(q == 0) VAL [A=-4294967292, B=1, counter=1, d=1, p=1, q=0, r=4] [L37] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=1] [L37] RET __VERIFIER_assert(r == A) VAL [A=-4294967292, B=1, counter=1, d=1, p=1, q=0, r=4] [L38] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, counter=1] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=1] [L38] RET __VERIFIER_assert(d == B * p) VAL [A=-4294967292, B=1, counter=1, d=1, p=1, q=0, r=4] [L39] COND FALSE !(!(r >= d)) [L41] d = 2 * d [L42] p = 2 * p VAL [A=-4294967292, B=1, counter=1, d=2, p=2, q=0, r=4] [L35] EXPR counter++ VAL [A=-4294967292, B=1, counter=2, d=2, p=2, q=0, r=4] [L35] COND TRUE counter++<5 [L36] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=2] [L36] RET __VERIFIER_assert(q == 0) VAL [A=-4294967292, B=1, counter=2, d=2, p=2, q=0, r=4] [L37] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=2] [L37] RET __VERIFIER_assert(r == A) VAL [A=-4294967292, B=1, counter=2, d=2, p=2, q=0, r=4] [L38] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, counter=2] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=2] [L38] RET __VERIFIER_assert(d == B * p) VAL [A=-4294967292, B=1, counter=2, d=2, p=2, q=0, r=4] [L39] COND FALSE !(!(r >= d)) [L41] d = 2 * d [L42] p = 2 * p VAL [A=-4294967292, B=1, counter=2, d=4, p=4, q=0, r=4] [L35] EXPR counter++ VAL [A=-4294967292, B=1, counter=3, d=4, p=4, q=0, r=4] [L35] COND TRUE counter++<5 [L36] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=3] [L36] RET __VERIFIER_assert(q == 0) VAL [A=-4294967292, B=1, counter=3, d=4, p=4, q=0, r=4] [L37] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=3] [L37] RET __VERIFIER_assert(r == A) VAL [A=-4294967292, B=1, counter=3, d=4, p=4, q=0, r=4] [L38] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, counter=3] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=3] [L38] RET __VERIFIER_assert(d == B * p) VAL [A=-4294967292, B=1, counter=3, d=4, p=4, q=0, r=4] [L39] COND FALSE !(!(r >= d)) [L41] d = 2 * d [L42] p = 2 * p VAL [A=-4294967292, B=1, counter=3, d=8, p=8, q=0, r=4] [L35] EXPR counter++ VAL [A=-4294967292, B=1, counter=4, d=8, p=8, q=0, r=4] [L35] COND TRUE counter++<5 [L36] CALL __VERIFIER_assert(q == 0) VAL [\old(cond)=1, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=4] [L36] RET __VERIFIER_assert(q == 0) VAL [A=-4294967292, B=1, counter=4, d=8, p=8, q=0, r=4] [L37] CALL __VERIFIER_assert(r == A) VAL [\old(cond)=1, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=4] [L37] RET __VERIFIER_assert(r == A) VAL [A=-4294967292, B=1, counter=4, d=8, p=8, q=0, r=4] [L38] CALL __VERIFIER_assert(d == B * p) VAL [\old(cond)=1, counter=4] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=4] [L38] RET __VERIFIER_assert(d == B * p) VAL [A=-4294967292, B=1, counter=4, d=8, p=8, q=0, r=4] [L39] COND TRUE !(r >= d) VAL [A=-4294967292, B=1, counter=4, d=8, p=8, q=0, r=4] [L45] EXPR counter++ VAL [A=-4294967292, B=1, counter=5, d=8, p=8, q=0, r=4] [L45] COND TRUE counter++<5 [L46] CALL __VERIFIER_assert(A == q*B + r) VAL [\old(cond)=1, counter=5] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=5] [L46] RET __VERIFIER_assert(A == q*B + r) VAL [A=-4294967292, B=1, counter=5, d=8, p=8, q=0, r=4] [L47] CALL __VERIFIER_assert(d == B*p) VAL [\old(cond)=1, counter=5] [L15] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=5] [L47] RET __VERIFIER_assert(d == B*p) VAL [A=-4294967292, B=1, counter=5, d=8, p=8, q=0, r=4] [L49] COND FALSE !(!(p != 1)) [L51] d = d / 2 [L52] p = p / 2 [L53] COND TRUE r >= d [L54] r = r - d [L55] q = q + p VAL [A=-4294967292, B=1, counter=5, d=4, p=4, q=4, r=0] [L45] EXPR counter++ VAL [A=-4294967292, B=1, counter=6, d=4, p=4, q=4, r=0] [L45] COND FALSE !(counter++<5) [L59] CALL __VERIFIER_assert(A == d*q + r) VAL [\old(cond)=0, counter=6] [L15] COND TRUE !(cond) VAL [\old(cond)=0, cond=0, counter=6] [L17] reach_error() VAL [\old(cond)=0, cond=0, counter=6] - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 22 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 335.4s, OverallIterations: 20, TraceHistogramMax: 15, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 31.8s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 1 mSolverCounterUnknown, 441 SdHoareTripleChecker+Valid, 9.3s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 383 mSDsluCounter, 2536 SdHoareTripleChecker+Invalid, 8.9s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1989 mSDsCounter, 227 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 2017 IncrementalHoareTripleChecker+Invalid, 2245 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 227 mSolverCounterUnsat, 547 mSDtfsCounter, 2017 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 2368 GetRequests, 1995 SyntacticMatches, 43 SemanticMatches, 330 ConstructedPredicates, 0 IntricatePredicates, 2 DeprecatedPredicates, 2070 ImplicationChecksByTransitivity, 178.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=169occurred in iteration=12, InterpolantAutomatonStates: 168, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.5s AutomataMinimizationTime, 19 MinimizatonAttempts, 69 StatesRemovedByMinimization, 14 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.8s SatisfiabilityAnalysisTime, 139.0s InterpolantComputationTime, 989 NumberOfCodeBlocks, 951 NumberOfCodeBlocksAsserted, 30 NumberOfCheckSat, 1593 ConstructedInterpolants, 0 QuantifiedInterpolants, 37197 SizeOfPredicates, 48 NumberOfNonLiveVariables, 2201 ConjunctsInSsa, 279 ConjunctsInUnsatCore, 32 InterpolantComputations, 6 PerfectInterpolantSequences, 4310/5222 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: OVERALL_TIME: 0.8s, ICFG_INTERPRETER_ENTERED_PROCEDURES: 4, DAG_INTERPRETER_EARLY_EXIT_QUERIES_NONTRIVIAL: 29, DAG_INTERPRETER_EARLY_EXITS: 2, TOOLS_POST_APPLICATIONS: 23, TOOLS_POST_TIME: 0.2s, TOOLS_POST_CALL_APPLICATIONS: 17, TOOLS_POST_CALL_TIME: 0.2s, TOOLS_POST_RETURN_APPLICATIONS: 10, TOOLS_POST_RETURN_TIME: 0.2s, TOOLS_QUANTIFIERELIM_APPLICATIONS: 50, TOOLS_QUANTIFIERELIM_TIME: 0.5s, TOOLS_QUANTIFIERELIM_MAX_TIME: 0.0s, FLUID_QUERY_TIME: 0.0s, FLUID_QUERIES: 72, FLUID_YES_ANSWERS: 0, DOMAIN_JOIN_APPLICATIONS: 21, DOMAIN_JOIN_TIME: 0.2s, DOMAIN_ALPHA_APPLICATIONS: 0, DOMAIN_ALPHA_TIME: 0.0s, DOMAIN_WIDEN_APPLICATIONS: 0, DOMAIN_WIDEN_TIME: 0.0s, DOMAIN_ISSUBSETEQ_APPLICATIONS: 0, DOMAIN_ISSUBSETEQ_TIME: 0.0s, DOMAIN_ISBOTTOM_APPLICATIONS: 29, DOMAIN_ISBOTTOM_TIME: 0.0s, LOOP_SUMMARIZER_APPLICATIONS: 0, LOOP_SUMMARIZER_CACHE_MISSES: 0, LOOP_SUMMARIZER_OVERALL_TIME: 0.0s, LOOP_SUMMARIZER_NEW_COMPUTATION_TIME: 0.0s, LOOP_SUMMARIZER_FIXPOINT_ITERATIONS: 0, CALL_SUMMARIZER_APPLICATIONS: 10, CALL_SUMMARIZER_CACHE_MISSES: 2, CALL_SUMMARIZER_OVERALL_TIME: 0.0s, CALL_SUMMARIZER_NEW_COMPUTATION_TIME: 0.0s, PROCEDURE_GRAPH_BUILDER_TIME: 0.0s, PATH_EXPR_TIME: 0.0s, REGEX_TO_DAG_TIME: 0.0s, DAG_COMPRESSION_TIME: 0.0s, DAG_COMPRESSION_PROCESSED_NODES: 231, DAG_COMPRESSION_RETAINED_NODES: 80, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2023-12-02 19:01:05,480 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d8e9469d-64c4-4aa1-b60d-20b9d4572a04/bin/utaipan-verify-nQ1chXbOIh/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Writing human readable error path to file UltimateCounterExample.errorpath Result: FALSE