./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound50.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version cf1a7837 Calling Ultimate with: /usr/lib/jvm/java-11-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound50.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 63cd3e528fa28694be9f2ecbe948122395c3f48db5408253e949dc50f2a74038 --- Real Ultimate output --- This is Ultimate 0.2.3-dev-cf1a783 [2023-11-12 00:50:48,339 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-12 00:50:48,415 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-12 00:50:48,421 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-12 00:50:48,421 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-12 00:50:48,472 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-12 00:50:48,475 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-12 00:50:48,476 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-12 00:50:48,477 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-12 00:50:48,482 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-12 00:50:48,483 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-12 00:50:48,484 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-12 00:50:48,485 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-12 00:50:48,486 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-12 00:50:48,495 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-12 00:50:48,496 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-12 00:50:48,496 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-12 00:50:48,497 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-12 00:50:48,498 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-12 00:50:48,499 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-12 00:50:48,500 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-12 00:50:48,500 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-12 00:50:48,501 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-12 00:50:48,502 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-12 00:50:48,502 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-12 00:50:48,503 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-12 00:50:48,503 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-12 00:50:48,504 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-12 00:50:48,504 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-12 00:50:48,505 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-12 00:50:48,506 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-12 00:50:48,506 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-12 00:50:48,507 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-12 00:50:48,507 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-12 00:50:48,507 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-12 00:50:48,508 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-12 00:50:48,508 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 00:50:48,508 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-12 00:50:48,509 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-12 00:50:48,509 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-12 00:50:48,509 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-12 00:50:48,510 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-12 00:50:48,510 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-12 00:50:48,510 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-12 00:50:48,511 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-12 00:50:48,511 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_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Taipan Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 63cd3e528fa28694be9f2ecbe948122395c3f48db5408253e949dc50f2a74038 [2023-11-12 00:50:48,806 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-12 00:50:48,827 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-12 00:50:48,830 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-12 00:50:48,832 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-12 00:50:48,832 INFO L274 PluginConnector]: CDTParser initialized [2023-11-12 00:50:48,833 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/../../sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound50.c [2023-11-12 00:50:51,956 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-12 00:50:52,147 INFO L384 CDTParser]: Found 1 translation units. [2023-11-12 00:50:52,147 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound50.c [2023-11-12 00:50:52,155 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/data/971676a55/14ee4b191a304b8293be4b267d44c47e/FLAGa63ad0e4a [2023-11-12 00:50:52,169 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/data/971676a55/14ee4b191a304b8293be4b267d44c47e [2023-11-12 00:50:52,172 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-12 00:50:52,173 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-12 00:50:52,174 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-12 00:50:52,175 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-12 00:50:52,180 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-12 00:50:52,181 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 12:50:52" (1/1) ... [2023-11-12 00:50:52,182 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5e57e568 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:52, skipping insertion in model container [2023-11-12 00:50:52,182 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 12:50:52" (1/1) ... [2023-11-12 00:50:52,205 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-12 00:50:52,371 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_819238cf-bf07-4d28-9cb3-30800c5565a4/sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound50.c[526,539] [2023-11-12 00:50:52,391 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 00:50:52,403 INFO L202 MainTranslator]: Completed pre-run [2023-11-12 00:50:52,416 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_819238cf-bf07-4d28-9cb3-30800c5565a4/sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound50.c[526,539] [2023-11-12 00:50:52,424 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 00:50:52,439 INFO L206 MainTranslator]: Completed translation [2023-11-12 00:50:52,439 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:52 WrapperNode [2023-11-12 00:50:52,440 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-12 00:50:52,441 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-12 00:50:52,441 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-12 00:50:52,442 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-12 00:50:52,449 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:52" (1/1) ... [2023-11-12 00:50:52,457 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:52" (1/1) ... [2023-11-12 00:50:52,478 INFO L138 Inliner]: procedures = 14, calls = 23, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 64 [2023-11-12 00:50:52,479 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-12 00:50:52,479 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-12 00:50:52,480 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-12 00:50:52,480 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-12 00:50:52,490 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:52" (1/1) ... [2023-11-12 00:50:52,490 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:52" (1/1) ... [2023-11-12 00:50:52,492 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:52" (1/1) ... [2023-11-12 00:50:52,493 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:52" (1/1) ... [2023-11-12 00:50:52,496 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:52" (1/1) ... [2023-11-12 00:50:52,500 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:52" (1/1) ... [2023-11-12 00:50:52,501 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:52" (1/1) ... [2023-11-12 00:50:52,502 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:52" (1/1) ... [2023-11-12 00:50:52,504 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-12 00:50:52,506 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-12 00:50:52,506 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-12 00:50:52,506 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-12 00:50:52,507 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:52" (1/1) ... [2023-11-12 00:50:52,514 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 00:50:52,530 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:50:52,544 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-12 00:50:52,555 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-12 00:50:52,589 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-12 00:50:52,590 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-12 00:50:52,590 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-12 00:50:52,590 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-12 00:50:52,590 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-11-12 00:50:52,591 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-11-12 00:50:52,663 INFO L236 CfgBuilder]: Building ICFG [2023-11-12 00:50:52,666 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-12 00:50:52,815 INFO L277 CfgBuilder]: Performing block encoding [2023-11-12 00:50:52,916 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-12 00:50:52,916 INFO L302 CfgBuilder]: Removed 2 assume(true) statements. [2023-11-12 00:50:52,919 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 12:50:52 BoogieIcfgContainer [2023-11-12 00:50:52,919 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-12 00:50:52,928 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-12 00:50:52,928 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-12 00:50:52,931 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-12 00:50:52,932 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.11 12:50:52" (1/3) ... [2023-11-12 00:50:52,932 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5c04ae7c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 12:50:52, skipping insertion in model container [2023-11-12 00:50:52,933 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:50:52" (2/3) ... [2023-11-12 00:50:52,933 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5c04ae7c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 12:50:52, skipping insertion in model container [2023-11-12 00:50:52,933 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 12:50:52" (3/3) ... [2023-11-12 00:50:52,935 INFO L112 eAbstractionObserver]: Analyzing ICFG hard2_valuebound50.c [2023-11-12 00:50:52,957 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-12 00:50:52,957 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-12 00:50:53,015 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-12 00:50:53,023 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;@4134a46, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-12 00:50:53,023 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-12 00:50:53,028 INFO L276 IsEmpty]: Start isEmpty. Operand has 20 states, 10 states have (on average 1.6) internal successors, (16), 11 states have internal predecessors, (16), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2023-11-12 00:50:53,036 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2023-11-12 00:50:53,036 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:50:53,037 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2023-11-12 00:50:53,037 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:50:53,046 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:50:53,046 INFO L85 PathProgramCache]: Analyzing trace with hash -697525204, now seen corresponding path program 1 times [2023-11-12 00:50:53,054 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:50:53,054 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [664795047] [2023-11-12 00:50:53,055 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:50:53,055 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:50:53,197 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:50:53,498 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-12 00:50:53,499 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:50:53,499 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [664795047] [2023-11-12 00:50:53,500 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [664795047] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:50:53,500 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:50:53,500 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-11-12 00:50:53,502 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1032860070] [2023-11-12 00:50:53,511 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:50:53,515 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:50:53,515 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:50:53,561 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:50:53,561 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-12 00:50:53,564 INFO L87 Difference]: Start difference. First operand has 20 states, 10 states have (on average 1.6) internal successors, (16), 11 states have internal predecessors, (16), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 5 states, 5 states have (on average 1.0) internal successors, (5), 3 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 00:50:53,661 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:50:53,661 INFO L93 Difference]: Finished difference Result 50 states and 87 transitions. [2023-11-12 00:50:53,662 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-12 00:50:53,664 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.0) internal successors, (5), 3 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 6 [2023-11-12 00:50:53,664 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:50:53,672 INFO L225 Difference]: With dead ends: 50 [2023-11-12 00:50:53,672 INFO L226 Difference]: Without dead ends: 28 [2023-11-12 00:50:53,675 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-11-12 00:50:53,679 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 10 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 71 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:50:53,681 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 71 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 00:50:53,700 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2023-11-12 00:50:53,722 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 22. [2023-11-12 00:50:53,724 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-11-12 00:50:53,725 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 28 transitions. [2023-11-12 00:50:53,726 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 28 transitions. Word has length 6 [2023-11-12 00:50:53,727 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:50:53,727 INFO L495 AbstractCegarLoop]: Abstraction has 22 states and 28 transitions. [2023-11-12 00:50:53,728 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.0) internal successors, (5), 3 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 00:50:53,728 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 28 transitions. [2023-11-12 00:50:53,729 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2023-11-12 00:50:53,730 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:50:53,730 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:50:53,730 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-12 00:50:53,731 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:50:53,731 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:50:53,732 INFO L85 PathProgramCache]: Analyzing trace with hash -515229903, now seen corresponding path program 1 times [2023-11-12 00:50:53,732 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:50:53,732 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1947605681] [2023-11-12 00:50:53,733 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:50:53,733 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:50:53,749 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:50:53,874 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-12 00:50:53,874 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:50:53,874 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1947605681] [2023-11-12 00:50:53,875 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1947605681] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:50:53,875 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:50:53,875 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-12 00:50:53,876 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [771394543] [2023-11-12 00:50:53,876 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:50:53,877 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:50:53,877 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:50:53,879 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:50:53,879 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-12 00:50:53,879 INFO L87 Difference]: Start difference. First operand 22 states and 28 transitions. Second operand has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-12 00:50:53,938 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:50:53,939 INFO L93 Difference]: Finished difference Result 34 states and 43 transitions. [2023-11-12 00:50:53,939 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-12 00:50:53,940 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2023-11-12 00:50:53,940 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:50:53,941 INFO L225 Difference]: With dead ends: 34 [2023-11-12 00:50:53,941 INFO L226 Difference]: Without dead ends: 32 [2023-11-12 00:50:53,942 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-11-12 00:50:53,944 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 8 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 67 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:50:53,947 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 67 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 00:50:53,948 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2023-11-12 00:50:53,957 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 26. [2023-11-12 00:50:53,957 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-11-12 00:50:53,959 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 31 transitions. [2023-11-12 00:50:53,959 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 31 transitions. Word has length 11 [2023-11-12 00:50:53,959 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:50:53,960 INFO L495 AbstractCegarLoop]: Abstraction has 26 states and 31 transitions. [2023-11-12 00:50:53,960 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-12 00:50:53,960 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 31 transitions. [2023-11-12 00:50:53,961 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2023-11-12 00:50:53,961 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:50:53,961 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:50:53,961 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-12 00:50:53,962 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:50:53,962 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:50:53,962 INFO L85 PathProgramCache]: Analyzing trace with hash -1604661492, now seen corresponding path program 1 times [2023-11-12 00:50:53,963 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:50:53,963 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [833619409] [2023-11-12 00:50:53,963 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:50:53,963 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:50:53,978 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:50:53,979 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [887208979] [2023-11-12 00:50:53,979 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:50:53,979 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:50:53,980 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:50:53,983 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:50:54,004 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-12 00:50:54,092 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:50:54,094 INFO L262 TraceCheckSpWp]: Trace formula consists of 78 conjuncts, 19 conjunts are in the unsatisfiable core [2023-11-12 00:50:54,100 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:50:54,352 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-11-12 00:50:54,353 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:50:54,569 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-11-12 00:50:54,569 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:50:54,569 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [833619409] [2023-11-12 00:50:54,569 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:50:54,570 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [887208979] [2023-11-12 00:50:54,573 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [887208979] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:50:54,574 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1873516644] [2023-11-12 00:50:54,601 INFO L159 IcfgInterpreter]: Started Sifa with 11 locations of interest [2023-11-12 00:50:54,602 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:50:54,609 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:50:54,615 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:50:54,615 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:50:55,334 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 62 for LOIs [2023-11-12 00:50:55,392 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:50:55,792 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [1873516644] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:50:55,792 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:50:55,792 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [8, 7] total 15 [2023-11-12 00:50:55,793 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1139577460] [2023-11-12 00:50:55,793 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:50:55,794 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:50:55,794 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:50:55,795 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:50:55,795 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=158, Unknown=0, NotChecked=0, Total=210 [2023-11-12 00:50:55,795 INFO L87 Difference]: Start difference. First operand 26 states and 31 transitions. Second operand has 5 states, 5 states have (on average 1.4) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-11-12 00:50:55,946 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:50:55,946 INFO L93 Difference]: Finished difference Result 61 states and 75 transitions. [2023-11-12 00:50:55,947 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-12 00:50:55,947 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 16 [2023-11-12 00:50:55,947 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:50:55,948 INFO L225 Difference]: With dead ends: 61 [2023-11-12 00:50:55,948 INFO L226 Difference]: Without dead ends: 43 [2023-11-12 00:50:55,949 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 31 SyntacticMatches, 2 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 61 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=52, Invalid=158, Unknown=0, NotChecked=0, Total=210 [2023-11-12 00:50:55,950 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 3 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 52 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 29 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 52 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 00:50:55,951 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 29 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 52 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 00:50:55,952 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2023-11-12 00:50:55,965 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2023-11-12 00:50:55,965 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 26 states have (on average 1.1153846153846154) internal successors, (29), 27 states have internal predecessors, (29), 10 states have call successors, (10), 6 states have call predecessors, (10), 6 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-11-12 00:50:55,967 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 48 transitions. [2023-11-12 00:50:55,967 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 48 transitions. Word has length 16 [2023-11-12 00:50:55,967 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:50:55,967 INFO L495 AbstractCegarLoop]: Abstraction has 43 states and 48 transitions. [2023-11-12 00:50:55,967 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2023-11-12 00:50:55,968 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 48 transitions. [2023-11-12 00:50:55,969 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2023-11-12 00:50:55,969 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:50:55,969 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2023-11-12 00:50:55,983 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-12 00:50:56,175 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:50:56,175 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:50:56,176 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:50:56,176 INFO L85 PathProgramCache]: Analyzing trace with hash 1042343919, now seen corresponding path program 1 times [2023-11-12 00:50:56,176 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:50:56,177 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1380208229] [2023-11-12 00:50:56,177 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:50:56,177 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:50:56,188 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:50:56,188 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1248283963] [2023-11-12 00:50:56,188 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:50:56,189 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:50:56,189 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:50:56,190 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:50:56,194 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-12 00:50:56,251 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:50:56,252 INFO L262 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 23 conjunts are in the unsatisfiable core [2023-11-12 00:50:56,258 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:50:56,406 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 12 proven. 14 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2023-11-12 00:50:56,406 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:50:56,552 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 15 proven. 10 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2023-11-12 00:50:56,552 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:50:56,553 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1380208229] [2023-11-12 00:50:56,553 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:50:56,553 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1248283963] [2023-11-12 00:50:56,553 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1248283963] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:50:56,553 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [710996001] [2023-11-12 00:50:56,556 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2023-11-12 00:50:56,556 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:50:56,556 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:50:56,557 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:50:56,557 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:50:58,282 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 00:50:58,287 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:50:58,857 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '698#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:50:58,857 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:50:58,858 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:50:58,858 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7] total 13 [2023-11-12 00:50:58,858 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [772101214] [2023-11-12 00:50:58,858 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:50:58,859 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-11-12 00:50:58,859 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:50:58,860 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-11-12 00:50:58,860 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=79, Invalid=341, Unknown=0, NotChecked=0, Total=420 [2023-11-12 00:50:58,861 INFO L87 Difference]: Start difference. First operand 43 states and 48 transitions. Second operand has 13 states, 13 states have (on average 1.6153846153846154) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (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-11-12 00:50:59,128 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:50:59,129 INFO L93 Difference]: Finished difference Result 77 states and 98 transitions. [2023-11-12 00:50:59,129 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-11-12 00:50:59,129 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 1.6153846153846154) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (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 33 [2023-11-12 00:50:59,130 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:50:59,132 INFO L225 Difference]: With dead ends: 77 [2023-11-12 00:50:59,132 INFO L226 Difference]: Without dead ends: 64 [2023-11-12 00:50:59,133 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 103 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=95, Invalid=411, Unknown=0, NotChecked=0, Total=506 [2023-11-12 00:50:59,135 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 25 mSDsluCounter, 54 mSDsCounter, 0 mSdLazyCounter, 155 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 74 SdHoareTripleChecker+Invalid, 182 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 155 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-12 00:50:59,135 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 74 Invalid, 182 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 155 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-12 00:50:59,136 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2023-11-12 00:50:59,151 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 64. [2023-11-12 00:50:59,151 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 36 states have (on average 1.1111111111111112) internal successors, (40), 39 states have internal predecessors, (40), 20 states have call successors, (20), 7 states have call predecessors, (20), 7 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) [2023-11-12 00:50:59,153 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 78 transitions. [2023-11-12 00:50:59,153 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 78 transitions. Word has length 33 [2023-11-12 00:50:59,153 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:50:59,153 INFO L495 AbstractCegarLoop]: Abstraction has 64 states and 78 transitions. [2023-11-12 00:50:59,154 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 1.6153846153846154) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (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-11-12 00:50:59,154 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 78 transitions. [2023-11-12 00:50:59,155 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2023-11-12 00:50:59,155 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:50:59,155 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:50:59,175 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2023-11-12 00:50:59,370 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:50:59,370 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:50:59,371 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:50:59,371 INFO L85 PathProgramCache]: Analyzing trace with hash -1798480357, now seen corresponding path program 1 times [2023-11-12 00:50:59,371 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:50:59,371 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [111318495] [2023-11-12 00:50:59,372 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:50:59,372 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:50:59,382 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:50:59,382 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1403821118] [2023-11-12 00:50:59,382 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:50:59,383 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:50:59,383 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:50:59,384 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:50:59,392 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-12 00:50:59,441 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:50:59,442 INFO L262 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 17 conjunts are in the unsatisfiable core [2023-11-12 00:50:59,445 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:50:59,562 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 14 proven. 13 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2023-11-12 00:50:59,563 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:50:59,689 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 17 proven. 13 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2023-11-12 00:50:59,692 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:50:59,693 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [111318495] [2023-11-12 00:50:59,693 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:50:59,693 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1403821118] [2023-11-12 00:50:59,693 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1403821118] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:50:59,693 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1228443244] [2023-11-12 00:50:59,698 INFO L159 IcfgInterpreter]: Started Sifa with 14 locations of interest [2023-11-12 00:50:59,698 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:50:59,698 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:50:59,698 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:50:59,704 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:51:01,268 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2023-11-12 00:51:01,275 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:51:01,886 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1171#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:51:01,886 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:51:01,886 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:51:01,886 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 11 [2023-11-12 00:51:01,886 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1383153747] [2023-11-12 00:51:01,887 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:51:01,887 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2023-11-12 00:51:01,887 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:51:01,888 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2023-11-12 00:51:01,889 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=295, Unknown=0, NotChecked=0, Total=380 [2023-11-12 00:51:01,889 INFO L87 Difference]: Start difference. First operand 64 states and 78 transitions. Second operand has 11 states, 11 states have (on average 2.1818181818181817) internal successors, (24), 10 states have internal predecessors, (24), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2023-11-12 00:51:02,068 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:51:02,068 INFO L93 Difference]: Finished difference Result 73 states and 88 transitions. [2023-11-12 00:51:02,069 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-11-12 00:51:02,069 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.1818181818181817) internal successors, (24), 10 states have internal predecessors, (24), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 40 [2023-11-12 00:51:02,072 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:51:02,073 INFO L225 Difference]: With dead ends: 73 [2023-11-12 00:51:02,074 INFO L226 Difference]: Without dead ends: 71 [2023-11-12 00:51:02,075 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 100 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 117 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=101, Invalid=361, Unknown=0, NotChecked=0, Total=462 [2023-11-12 00:51:02,076 INFO L413 NwaCegarLoop]: 14 mSDtfsCounter, 18 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 71 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 70 SdHoareTripleChecker+Invalid, 85 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 71 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 00:51:02,076 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 70 Invalid, 85 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 71 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 00:51:02,077 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2023-11-12 00:51:02,096 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 70. [2023-11-12 00:51:02,096 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 70 states, 40 states have (on average 1.125) internal successors, (45), 43 states have internal predecessors, (45), 21 states have call successors, (21), 8 states have call predecessors, (21), 8 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2023-11-12 00:51:02,098 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 85 transitions. [2023-11-12 00:51:02,098 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 85 transitions. Word has length 40 [2023-11-12 00:51:02,099 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:51:02,099 INFO L495 AbstractCegarLoop]: Abstraction has 70 states and 85 transitions. [2023-11-12 00:51:02,099 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.1818181818181817) internal successors, (24), 10 states have internal predecessors, (24), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2023-11-12 00:51:02,099 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 85 transitions. [2023-11-12 00:51:02,101 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2023-11-12 00:51:02,102 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:51:02,102 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:51:02,114 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-12 00:51:02,314 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:51:02,314 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:51:02,315 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:51:02,315 INFO L85 PathProgramCache]: Analyzing trace with hash -1731990838, now seen corresponding path program 1 times [2023-11-12 00:51:02,315 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:51:02,315 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [307348748] [2023-11-12 00:51:02,315 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:02,315 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:51:02,328 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:51:02,328 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1203922815] [2023-11-12 00:51:02,328 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:02,328 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:51:02,329 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:51:02,330 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:51:02,347 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-12 00:51:02,432 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:51:02,434 INFO L262 TraceCheckSpWp]: Trace formula consists of 147 conjuncts, 31 conjunts are in the unsatisfiable core [2023-11-12 00:51:02,442 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:51:02,766 INFO L134 CoverageAnalysis]: Checked inductivity of 135 backedges. 18 proven. 26 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-11-12 00:51:02,766 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:51:05,462 INFO L134 CoverageAnalysis]: Checked inductivity of 135 backedges. 18 proven. 26 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-11-12 00:51:05,462 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:51:05,463 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [307348748] [2023-11-12 00:51:05,463 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:51:05,463 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1203922815] [2023-11-12 00:51:05,463 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1203922815] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:51:05,463 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1369976434] [2023-11-12 00:51:05,466 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-11-12 00:51:05,466 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:51:05,467 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:51:05,467 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:51:05,467 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:51:07,193 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-11-12 00:51:07,198 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:51:07,896 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1721#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:51:07,896 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:51:07,897 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:51:07,897 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2023-11-12 00:51:07,897 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1704726393] [2023-11-12 00:51:07,897 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:51:07,898 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-12 00:51:07,898 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:51:07,899 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-12 00:51:07,899 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=87, Invalid=419, Unknown=0, NotChecked=0, Total=506 [2023-11-12 00:51:07,899 INFO L87 Difference]: Start difference. First operand 70 states and 85 transitions. Second operand has 15 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 13 states have internal predecessors, (29), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2023-11-12 00:51:09,377 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:51:09,377 INFO L93 Difference]: Finished difference Result 96 states and 108 transitions. [2023-11-12 00:51:09,378 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-11-12 00:51:09,378 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 13 states have internal predecessors, (29), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) Word has length 52 [2023-11-12 00:51:09,378 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:51:09,380 INFO L225 Difference]: With dead ends: 96 [2023-11-12 00:51:09,380 INFO L226 Difference]: Without dead ends: 94 [2023-11-12 00:51:09,381 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 159 GetRequests, 132 SyntacticMatches, 2 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 150 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=125, Invalid=577, Unknown=0, NotChecked=0, Total=702 [2023-11-12 00:51:09,382 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 29 mSDsluCounter, 165 mSDsCounter, 0 mSdLazyCounter, 199 mSolverCounterSat, 45 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 184 SdHoareTripleChecker+Invalid, 244 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 45 IncrementalHoareTripleChecker+Valid, 199 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2023-11-12 00:51:09,383 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 184 Invalid, 244 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [45 Valid, 199 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2023-11-12 00:51:09,383 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 94 states. [2023-11-12 00:51:09,418 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 94 to 92. [2023-11-12 00:51:09,418 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 56 states have (on average 1.0892857142857142) internal successors, (61), 60 states have internal predecessors, (61), 22 states have call successors, (22), 13 states have call predecessors, (22), 13 states have return successors, (20), 18 states have call predecessors, (20), 20 states have call successors, (20) [2023-11-12 00:51:09,420 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 103 transitions. [2023-11-12 00:51:09,420 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 103 transitions. Word has length 52 [2023-11-12 00:51:09,420 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:51:09,421 INFO L495 AbstractCegarLoop]: Abstraction has 92 states and 103 transitions. [2023-11-12 00:51:09,421 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 13 states have internal predecessors, (29), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2023-11-12 00:51:09,421 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 103 transitions. [2023-11-12 00:51:09,424 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2023-11-12 00:51:09,424 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:51:09,424 INFO L195 NwaCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:51:09,436 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-12 00:51:09,631 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:51:09,631 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:51:09,631 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:51:09,631 INFO L85 PathProgramCache]: Analyzing trace with hash -1143375622, now seen corresponding path program 1 times [2023-11-12 00:51:09,631 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:51:09,631 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [167173431] [2023-11-12 00:51:09,632 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:09,632 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:51:09,642 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:51:09,647 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1494183106] [2023-11-12 00:51:09,647 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:09,647 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:51:09,647 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:51:09,648 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:51:09,652 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-12 00:51:09,733 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:51:09,735 INFO L262 TraceCheckSpWp]: Trace formula consists of 167 conjuncts, 33 conjunts are in the unsatisfiable core [2023-11-12 00:51:09,739 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:51:10,101 INFO L134 CoverageAnalysis]: Checked inductivity of 209 backedges. 22 proven. 34 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2023-11-12 00:51:10,101 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:51:10,898 INFO L134 CoverageAnalysis]: Checked inductivity of 209 backedges. 22 proven. 34 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2023-11-12 00:51:10,898 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:51:10,900 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [167173431] [2023-11-12 00:51:10,900 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:51:10,900 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1494183106] [2023-11-12 00:51:10,901 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1494183106] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:51:10,901 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2121169712] [2023-11-12 00:51:10,913 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2023-11-12 00:51:10,913 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:51:10,914 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:51:10,914 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:51:10,914 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:51:12,414 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-11-12 00:51:12,417 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:51:13,012 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2403#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:51:13,012 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:51:13,012 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:51:13,013 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2023-11-12 00:51:13,013 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2023373346] [2023-11-12 00:51:13,013 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:51:13,015 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-11-12 00:51:13,015 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:51:13,016 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-11-12 00:51:13,019 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=118, Invalid=532, Unknown=0, NotChecked=0, Total=650 [2023-11-12 00:51:13,019 INFO L87 Difference]: Start difference. First operand 92 states and 103 transitions. Second operand has 17 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2023-11-12 00:51:15,547 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-12 00:51:17,702 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-12 00:51:17,720 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:51:17,720 INFO L93 Difference]: Finished difference Result 114 states and 133 transitions. [2023-11-12 00:51:17,721 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-11-12 00:51:17,721 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) Word has length 63 [2023-11-12 00:51:17,722 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:51:17,723 INFO L225 Difference]: With dead ends: 114 [2023-11-12 00:51:17,724 INFO L226 Difference]: Without dead ends: 99 [2023-11-12 00:51:17,725 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 191 GetRequests, 161 SyntacticMatches, 3 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 221 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=153, Invalid=659, Unknown=0, NotChecked=0, Total=812 [2023-11-12 00:51:17,726 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 26 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 182 mSolverCounterSat, 44 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 228 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 182 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.4s IncrementalHoareTripleChecker+Time [2023-11-12 00:51:17,727 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 124 Invalid, 228 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 182 Invalid, 2 Unknown, 0 Unchecked, 4.4s Time] [2023-11-12 00:51:17,728 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2023-11-12 00:51:17,768 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 85. [2023-11-12 00:51:17,768 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 85 states, 53 states have (on average 1.0943396226415094) internal successors, (58), 55 states have internal predecessors, (58), 18 states have call successors, (18), 13 states have call predecessors, (18), 13 states have return successors, (17), 16 states have call predecessors, (17), 17 states have call successors, (17) [2023-11-12 00:51:17,769 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 85 states to 85 states and 93 transitions. [2023-11-12 00:51:17,770 INFO L78 Accepts]: Start accepts. Automaton has 85 states and 93 transitions. Word has length 63 [2023-11-12 00:51:17,770 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:51:17,770 INFO L495 AbstractCegarLoop]: Abstraction has 85 states and 93 transitions. [2023-11-12 00:51:17,771 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 9 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2023-11-12 00:51:17,771 INFO L276 IsEmpty]: Start isEmpty. Operand 85 states and 93 transitions. [2023-11-12 00:51:17,773 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2023-11-12 00:51:17,773 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:51:17,773 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:51:17,781 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-12 00:51:17,979 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:51:17,979 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:51:17,980 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:51:17,980 INFO L85 PathProgramCache]: Analyzing trace with hash 2113244439, now seen corresponding path program 1 times [2023-11-12 00:51:17,980 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:51:17,980 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1185994769] [2023-11-12 00:51:17,980 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:17,980 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:51:17,991 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:51:17,991 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [17191427] [2023-11-12 00:51:17,992 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:17,992 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:51:17,992 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:51:17,993 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:51:17,999 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-12 00:51:18,084 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:51:18,085 INFO L262 TraceCheckSpWp]: Trace formula consists of 184 conjuncts, 4 conjunts are in the unsatisfiable core [2023-11-12 00:51:18,088 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:51:18,137 INFO L134 CoverageAnalysis]: Checked inductivity of 303 backedges. 81 proven. 0 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2023-11-12 00:51:18,138 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 00:51:18,138 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:51:18,138 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1185994769] [2023-11-12 00:51:18,138 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:51:18,138 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [17191427] [2023-11-12 00:51:18,139 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [17191427] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:51:18,139 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:51:18,139 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-12 00:51:18,139 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1842793983] [2023-11-12 00:51:18,139 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:51:18,140 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:51:18,140 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:51:18,141 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:51:18,141 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2023-11-12 00:51:18,141 INFO L87 Difference]: Start difference. First operand 85 states and 93 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-11-12 00:51:18,221 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:51:18,221 INFO L93 Difference]: Finished difference Result 92 states and 99 transitions. [2023-11-12 00:51:18,222 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-12 00:51:18,222 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 73 [2023-11-12 00:51:18,223 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:51:18,224 INFO L225 Difference]: With dead ends: 92 [2023-11-12 00:51:18,224 INFO L226 Difference]: Without dead ends: 80 [2023-11-12 00:51:18,225 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2023-11-12 00:51:18,226 INFO L413 NwaCegarLoop]: 35 mSDtfsCounter, 3 mSDsluCounter, 40 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 75 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:51:18,226 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 75 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 00:51:18,227 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2023-11-12 00:51:18,262 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 80. [2023-11-12 00:51:18,263 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 80 states, 50 states have (on average 1.06) internal successors, (53), 51 states have internal predecessors, (53), 17 states have call successors, (17), 12 states have call predecessors, (17), 12 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2023-11-12 00:51:18,264 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 86 transitions. [2023-11-12 00:51:18,264 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 86 transitions. Word has length 73 [2023-11-12 00:51:18,265 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:51:18,265 INFO L495 AbstractCegarLoop]: Abstraction has 80 states and 86 transitions. [2023-11-12 00:51:18,265 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-11-12 00:51:18,265 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 86 transitions. [2023-11-12 00:51:18,267 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2023-11-12 00:51:18,267 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:51:18,267 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2023-11-12 00:51:18,280 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2023-11-12 00:51:18,474 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:51:18,474 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:51:18,474 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:51:18,475 INFO L85 PathProgramCache]: Analyzing trace with hash 1241228560, now seen corresponding path program 2 times [2023-11-12 00:51:18,475 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:51:18,475 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1280346162] [2023-11-12 00:51:18,475 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:18,476 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:51:18,497 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:51:18,498 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1888115478] [2023-11-12 00:51:18,498 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-12 00:51:18,498 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:51:18,498 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:51:18,500 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:51:18,527 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-12 00:51:18,581 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-11-12 00:51:18,582 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 00:51:18,584 INFO L262 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 31 conjunts are in the unsatisfiable core [2023-11-12 00:51:18,587 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:51:18,902 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 41 proven. 34 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2023-11-12 00:51:18,902 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:51:20,658 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 41 proven. 29 refuted. 0 times theorem prover too weak. 236 trivial. 0 not checked. [2023-11-12 00:51:20,659 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:51:20,659 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1280346162] [2023-11-12 00:51:20,659 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:51:20,659 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1888115478] [2023-11-12 00:51:20,659 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1888115478] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:51:20,659 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [737226992] [2023-11-12 00:51:20,662 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-11-12 00:51:20,662 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:51:20,662 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:51:20,663 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:51:20,663 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:51:22,091 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-11-12 00:51:22,094 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:51:22,662 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3631#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:51:22,662 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:51:22,663 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:51:22,663 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 17 [2023-11-12 00:51:22,663 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [296185955] [2023-11-12 00:51:22,663 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:51:22,664 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-11-12 00:51:22,664 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:51:22,664 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-11-12 00:51:22,665 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=107, Invalid=493, Unknown=0, NotChecked=0, Total=600 [2023-11-12 00:51:22,665 INFO L87 Difference]: Start difference. First operand 80 states and 86 transitions. Second operand has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 16 states have internal predecessors, (32), 9 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) [2023-11-12 00:51:27,864 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-12 00:51:29,868 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-12 00:51:32,239 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-11-12 00:51:32,308 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:51:32,308 INFO L93 Difference]: Finished difference Result 112 states and 130 transitions. [2023-11-12 00:51:32,308 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-11-12 00:51:32,309 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 16 states have internal predecessors, (32), 9 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) Word has length 74 [2023-11-12 00:51:32,309 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:51:32,311 INFO L225 Difference]: With dead ends: 112 [2023-11-12 00:51:32,311 INFO L226 Difference]: Without dead ends: 110 [2023-11-12 00:51:32,311 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 223 GetRequests, 195 SyntacticMatches, 3 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 179 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=130, Invalid=572, Unknown=0, NotChecked=0, Total=702 [2023-11-12 00:51:32,312 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 24 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 212 mSolverCounterSat, 37 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 125 SdHoareTripleChecker+Invalid, 252 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 212 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 6.6s IncrementalHoareTripleChecker+Time [2023-11-12 00:51:32,313 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [32 Valid, 125 Invalid, 252 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 212 Invalid, 3 Unknown, 0 Unchecked, 6.6s Time] [2023-11-12 00:51:32,313 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2023-11-12 00:51:32,356 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 108. [2023-11-12 00:51:32,357 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 108 states, 65 states have (on average 1.0769230769230769) internal successors, (70), 67 states have internal predecessors, (70), 28 states have call successors, (28), 14 states have call predecessors, (28), 14 states have return successors, (27), 26 states have call predecessors, (27), 27 states have call successors, (27) [2023-11-12 00:51:32,358 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 108 states to 108 states and 125 transitions. [2023-11-12 00:51:32,358 INFO L78 Accepts]: Start accepts. Automaton has 108 states and 125 transitions. Word has length 74 [2023-11-12 00:51:32,359 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:51:32,359 INFO L495 AbstractCegarLoop]: Abstraction has 108 states and 125 transitions. [2023-11-12 00:51:32,359 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 16 states have internal predecessors, (32), 9 states have call successors, (23), 3 states have call predecessors, (23), 2 states have return successors, (21), 7 states have call predecessors, (21), 9 states have call successors, (21) [2023-11-12 00:51:32,359 INFO L276 IsEmpty]: Start isEmpty. Operand 108 states and 125 transitions. [2023-11-12 00:51:32,361 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2023-11-12 00:51:32,361 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:51:32,361 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1] [2023-11-12 00:51:32,371 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-12 00:51:32,567 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:51:32,568 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:51:32,568 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:51:32,568 INFO L85 PathProgramCache]: Analyzing trace with hash 1175687132, now seen corresponding path program 3 times [2023-11-12 00:51:32,569 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:51:32,569 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [487221743] [2023-11-12 00:51:32,569 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:51:32,569 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:51:32,577 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:51:32,577 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1779937003] [2023-11-12 00:51:32,578 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-12 00:51:32,578 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:51:32,578 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:51:32,579 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:51:32,586 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_819238cf-bf07-4d28-9cb3-30800c5565a4/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-12 00:51:32,657 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-12 00:51:32,657 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 00:51:32,659 INFO L262 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 51 conjunts are in the unsatisfiable core [2023-11-12 00:51:32,663 INFO L285 TraceCheckSpWp]: Computing forward predicates...