./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version a0165632 Calling Ultimate with: /usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound2.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje --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 942b28ff7c0583b7db8395d2c315e70afc8fe68ba69d39faf867ac75d7628edb --- Real Ultimate output --- This is Ultimate 0.2.5-dev-a016563 [2024-11-09 05:01:35,850 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 05:01:35,951 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/config/svcomp-Reach-32bit-Taipan_Default.epf [2024-11-09 05:01:35,959 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 05:01:35,962 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 05:01:36,005 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 05:01:36,007 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 05:01:36,007 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 05:01:36,008 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-09 05:01:36,010 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-09 05:01:36,010 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-09 05:01:36,011 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-09 05:01:36,011 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-09 05:01:36,011 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-09 05:01:36,014 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-09 05:01:36,014 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-09 05:01:36,015 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-09 05:01:36,015 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-09 05:01:36,015 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-09 05:01:36,016 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-09 05:01:36,016 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-09 05:01:36,020 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-09 05:01:36,021 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 05:01:36,021 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-09 05:01:36,021 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 05:01:36,022 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 05:01:36,022 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 05:01:36,022 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 05:01:36,023 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-09 05:01:36,023 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-09 05:01:36,023 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-09 05:01:36,023 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 05:01:36,024 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 05:01:36,026 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 05:01:36,027 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 05:01:36,027 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-09 05:01:36,028 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-09 05:01:36,028 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-09 05:01:36,029 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-09 05:01:36,029 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 05:01:36,029 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-09 05:01:36,030 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-09 05:01:36,030 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-09 05:01:36,030 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-09 05:01:36,031 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-09 05:01:36,031 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-09 05:01:36,032 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-09 05:01:36,032 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_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/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_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje 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 -> 942b28ff7c0583b7db8395d2c315e70afc8fe68ba69d39faf867ac75d7628edb [2024-11-09 05:01:36,363 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 05:01:36,385 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 05:01:36,389 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 05:01:36,392 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 05:01:36,393 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 05:01:36,394 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/../../sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound2.c Unable to find full path for "g++" [2024-11-09 05:01:38,719 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 05:01:38,973 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 05:01:38,974 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound2.c [2024-11-09 05:01:38,995 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/data/0570057b0/c7a53ddc33b94e47a0d776746bc710d6/FLAGa1fd96d7c [2024-11-09 05:01:39,022 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/data/0570057b0/c7a53ddc33b94e47a0d776746bc710d6 [2024-11-09 05:01:39,025 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 05:01:39,030 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 05:01:39,032 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 05:01:39,036 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 05:01:39,045 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 05:01:39,047 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 05:01:39" (1/1) ... [2024-11-09 05:01:39,049 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@43139d77 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:01:39, skipping insertion in model container [2024-11-09 05:01:39,049 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 05:01:39" (1/1) ... [2024-11-09 05:01:39,104 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 05:01:39,370 WARN L250 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_dafa1051-3b43-4746-beb7-69f6f0a8db96/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound2.c[588,601] [2024-11-09 05:01:39,401 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 05:01:39,413 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 05:01:39,428 WARN L250 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_dafa1051-3b43-4746-beb7-69f6f0a8db96/sv-benchmarks/c/nla-digbench-scaling/cohencu-ll_valuebound2.c[588,601] [2024-11-09 05:01:39,441 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 05:01:39,461 INFO L204 MainTranslator]: Completed translation [2024-11-09 05:01:39,461 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:01:39 WrapperNode [2024-11-09 05:01:39,461 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 05:01:39,463 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 05:01:39,463 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 05:01:39,463 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 05:01:39,472 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:01:39" (1/1) ... [2024-11-09 05:01:39,479 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:01:39" (1/1) ... [2024-11-09 05:01:39,500 INFO L138 Inliner]: procedures = 14, calls = 19, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 47 [2024-11-09 05:01:39,500 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 05:01:39,501 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 05:01:39,501 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 05:01:39,502 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 05:01:39,515 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:01:39" (1/1) ... [2024-11-09 05:01:39,515 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:01:39" (1/1) ... [2024-11-09 05:01:39,517 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:01:39" (1/1) ... [2024-11-09 05:01:39,517 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:01:39" (1/1) ... [2024-11-09 05:01:39,522 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:01:39" (1/1) ... [2024-11-09 05:01:39,526 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:01:39" (1/1) ... [2024-11-09 05:01:39,528 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:01:39" (1/1) ... [2024-11-09 05:01:39,529 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:01:39" (1/1) ... [2024-11-09 05:01:39,531 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 05:01:39,532 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-09 05:01:39,532 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-09 05:01:39,533 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-09 05:01:39,534 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:01:39" (1/1) ... [2024-11-09 05:01:39,544 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-09 05:01:39,559 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:01:39,577 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-09 05:01:39,585 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-09 05:01:39,624 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 05:01:39,625 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-09 05:01:39,625 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 05:01:39,625 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 05:01:39,626 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-09 05:01:39,628 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-09 05:01:39,714 INFO L238 CfgBuilder]: Building ICFG [2024-11-09 05:01:39,716 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 05:01:39,926 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-09 05:01:39,927 INFO L287 CfgBuilder]: Performing block encoding [2024-11-09 05:01:39,984 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 05:01:39,985 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-09 05:01:39,985 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 05:01:39 BoogieIcfgContainer [2024-11-09 05:01:39,986 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-09 05:01:39,989 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-09 05:01:39,993 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-09 05:01:39,999 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-09 05:01:39,999 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.11 05:01:39" (1/3) ... [2024-11-09 05:01:40,000 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@33529f47 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 05:01:40, skipping insertion in model container [2024-11-09 05:01:40,002 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 05:01:39" (2/3) ... [2024-11-09 05:01:40,002 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@33529f47 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 05:01:40, skipping insertion in model container [2024-11-09 05:01:40,004 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 05:01:39" (3/3) ... [2024-11-09 05:01:40,006 INFO L112 eAbstractionObserver]: Analyzing ICFG cohencu-ll_valuebound2.c [2024-11-09 05:01:40,027 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-09 05:01:40,027 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-09 05:01:40,107 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-09 05:01:40,116 INFO L333 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, 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;@14118fb6, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-09 05:01:40,116 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-09 05:01:40,121 INFO L276 IsEmpty]: Start isEmpty. Operand has 22 states, 8 states have (on average 1.5) internal successors, (12), 9 states have internal predecessors, (12), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-09 05:01:40,131 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2024-11-09 05:01:40,131 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:01:40,132 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2024-11-09 05:01:40,133 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:01:40,140 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:01:40,141 INFO L85 PathProgramCache]: Analyzing trace with hash -1099841735, now seen corresponding path program 1 times [2024-11-09 05:01:40,154 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:01:40,155 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1416823189] [2024-11-09 05:01:40,156 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:01:40,156 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:01:40,287 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:01:40,713 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 05:01:40,714 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:01:40,715 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1416823189] [2024-11-09 05:01:40,715 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1416823189] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 05:01:40,716 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 05:01:40,716 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-09 05:01:40,719 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1278858913] [2024-11-09 05:01:40,721 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 05:01:40,725 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 05:01:40,725 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:01:40,753 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 05:01:40,754 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 05:01:40,757 INFO L87 Difference]: Start difference. First operand has 22 states, 8 states have (on average 1.5) internal successors, (12), 9 states have internal predecessors, (12), 11 states have call successors, (11), 1 states have call predecessors, (11), 1 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 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) [2024-11-09 05:01:40,993 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:01:40,993 INFO L93 Difference]: Finished difference Result 47 states and 82 transitions. [2024-11-09 05:01:40,997 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 05:01:40,998 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 [2024-11-09 05:01:40,999 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:01:41,011 INFO L225 Difference]: With dead ends: 47 [2024-11-09 05:01:41,011 INFO L226 Difference]: Without dead ends: 24 [2024-11-09 05:01:41,015 INFO L431 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 [2024-11-09 05:01:41,022 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 4 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 75 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 05:01:41,024 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 75 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 05:01:41,047 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2024-11-09 05:01:41,086 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-09 05:01:41,088 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 10 states have (on average 1.2) internal successors, (12), 11 states have internal predecessors, (12), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-09 05:01:41,090 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 33 transitions. [2024-11-09 05:01:41,092 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 33 transitions. Word has length 6 [2024-11-09 05:01:41,095 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:01:41,095 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 33 transitions. [2024-11-09 05:01:41,096 INFO L472 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) [2024-11-09 05:01:41,097 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 33 transitions. [2024-11-09 05:01:41,099 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-11-09 05:01:41,100 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:01:41,101 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:01:41,102 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-09 05:01:41,102 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:01:41,103 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:01:41,104 INFO L85 PathProgramCache]: Analyzing trace with hash 52250865, now seen corresponding path program 1 times [2024-11-09 05:01:41,107 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:01:41,107 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1615498138] [2024-11-09 05:01:41,107 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:01:41,108 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:01:41,153 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:01:41,161 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [370133875] [2024-11-09 05:01:41,161 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:01:41,161 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:01:41,162 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:01:41,167 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:01:41,171 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-09 05:01:41,243 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:01:41,246 INFO L255 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 05:01:41,256 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:01:41,383 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 05:01:41,384 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 05:01:41,385 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:01:41,385 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1615498138] [2024-11-09 05:01:41,386 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:01:41,387 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [370133875] [2024-11-09 05:01:41,387 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [370133875] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 05:01:41,387 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 05:01:41,387 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 05:01:41,388 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [793019222] [2024-11-09 05:01:41,389 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 05:01:41,391 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 05:01:41,392 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:01:41,393 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 05:01:41,394 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 05:01:41,395 INFO L87 Difference]: Start difference. First operand 24 states and 33 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) [2024-11-09 05:01:41,540 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:01:41,540 INFO L93 Difference]: Finished difference Result 43 states and 62 transitions. [2024-11-09 05:01:41,542 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 05:01:41,543 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 [2024-11-09 05:01:41,543 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:01:41,545 INFO L225 Difference]: With dead ends: 43 [2024-11-09 05:01:41,546 INFO L226 Difference]: Without dead ends: 41 [2024-11-09 05:01:41,547 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 05:01:41,549 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 4 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 93 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 05:01:41,550 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 93 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 05:01:41,551 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2024-11-09 05:01:41,570 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 31. [2024-11-09 05:01:41,571 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 14 states have (on average 1.1428571428571428) internal successors, (16), 16 states have internal predecessors, (16), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-09 05:01:41,572 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 41 transitions. [2024-11-09 05:01:41,574 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 41 transitions. Word has length 11 [2024-11-09 05:01:41,575 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:01:41,576 INFO L471 AbstractCegarLoop]: Abstraction has 31 states and 41 transitions. [2024-11-09 05:01:41,576 INFO L472 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) [2024-11-09 05:01:41,576 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 41 transitions. [2024-11-09 05:01:41,578 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2024-11-09 05:01:41,579 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:01:41,579 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:01:41,606 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-09 05:01:41,783 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:01:41,784 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:01:41,785 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:01:41,785 INFO L85 PathProgramCache]: Analyzing trace with hash -212325895, now seen corresponding path program 1 times [2024-11-09 05:01:41,785 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:01:41,785 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1001996144] [2024-11-09 05:01:41,786 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:01:41,786 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:01:41,812 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:01:41,814 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [169635473] [2024-11-09 05:01:41,814 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:01:41,814 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:01:41,815 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:01:41,817 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:01:41,819 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-09 05:01:41,895 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:01:41,897 INFO L255 TraceCheckSpWp]: Trace formula consists of 60 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 05:01:41,899 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:01:41,997 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 05:01:41,997 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 05:01:41,997 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:01:41,997 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1001996144] [2024-11-09 05:01:41,997 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:01:41,998 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [169635473] [2024-11-09 05:01:41,998 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [169635473] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 05:01:41,998 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 05:01:41,998 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 05:01:41,998 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [201465461] [2024-11-09 05:01:41,999 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 05:01:42,002 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 05:01:42,003 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:01:42,003 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 05:01:42,003 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 05:01:42,004 INFO L87 Difference]: Start difference. First operand 31 states and 41 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 05:01:42,139 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:01:42,142 INFO L93 Difference]: Finished difference Result 47 states and 65 transitions. [2024-11-09 05:01:42,143 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 05:01:42,143 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, (3), 2 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 [2024-11-09 05:01:42,144 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:01:42,145 INFO L225 Difference]: With dead ends: 47 [2024-11-09 05:01:42,145 INFO L226 Difference]: Without dead ends: 45 [2024-11-09 05:01:42,145 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 05:01:42,147 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 4 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 90 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 05:01:42,149 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 90 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 05:01:42,150 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2024-11-09 05:01:42,178 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 41. [2024-11-09 05:01:42,179 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 18 states have call successors, (18), 4 states have call predecessors, (18), 4 states have return successors, (17), 16 states have call predecessors, (17), 17 states have call successors, (17) [2024-11-09 05:01:42,182 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 56 transitions. [2024-11-09 05:01:42,183 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 56 transitions. Word has length 16 [2024-11-09 05:01:42,183 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:01:42,183 INFO L471 AbstractCegarLoop]: Abstraction has 41 states and 56 transitions. [2024-11-09 05:01:42,183 INFO L472 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, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 05:01:42,184 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 56 transitions. [2024-11-09 05:01:42,184 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2024-11-09 05:01:42,184 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:01:42,185 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:01:42,210 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-09 05:01:42,390 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:01:42,391 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:01:42,391 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:01:42,391 INFO L85 PathProgramCache]: Analyzing trace with hash 394642865, now seen corresponding path program 1 times [2024-11-09 05:01:42,392 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:01:42,392 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [117979253] [2024-11-09 05:01:42,392 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:01:42,392 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:01:42,419 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:01:42,421 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [370439687] [2024-11-09 05:01:42,421 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:01:42,421 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:01:42,421 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:01:42,423 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:01:42,426 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-09 05:01:42,492 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:01:42,493 INFO L255 TraceCheckSpWp]: Trace formula consists of 69 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-09 05:01:42,496 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:01:42,594 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-09 05:01:42,594 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 05:01:42,594 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:01:42,594 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [117979253] [2024-11-09 05:01:42,595 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:01:42,595 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [370439687] [2024-11-09 05:01:42,595 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [370439687] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 05:01:42,595 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 05:01:42,595 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 05:01:42,596 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [911518427] [2024-11-09 05:01:42,596 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 05:01:42,596 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 05:01:42,597 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:01:42,598 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 05:01:42,598 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 05:01:42,598 INFO L87 Difference]: Start difference. First operand 41 states and 56 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, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-09 05:01:42,760 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:01:42,760 INFO L93 Difference]: Finished difference Result 55 states and 71 transitions. [2024-11-09 05:01:42,761 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 05:01:42,762 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, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 21 [2024-11-09 05:01:42,763 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:01:42,764 INFO L225 Difference]: With dead ends: 55 [2024-11-09 05:01:42,766 INFO L226 Difference]: Without dead ends: 43 [2024-11-09 05:01:42,766 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 05:01:42,768 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 4 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 45 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 51 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 45 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 05:01:42,771 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 82 Invalid, 51 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 05:01:42,772 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-11-09 05:01:42,799 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2024-11-09 05:01:42,800 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 21 states have (on average 1.0952380952380953) internal successors, (23), 22 states have internal predecessors, (23), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-09 05:01:42,801 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 54 transitions. [2024-11-09 05:01:42,802 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 54 transitions. Word has length 21 [2024-11-09 05:01:42,804 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:01:42,804 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 54 transitions. [2024-11-09 05:01:42,804 INFO L472 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, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-09 05:01:42,805 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 54 transitions. [2024-11-09 05:01:42,806 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-11-09 05:01:42,806 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:01:42,807 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:01:42,825 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-09 05:01:43,011 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:01:43,012 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:01:43,012 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:01:43,012 INFO L85 PathProgramCache]: Analyzing trace with hash -526999271, now seen corresponding path program 1 times [2024-11-09 05:01:43,012 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:01:43,013 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [264710711] [2024-11-09 05:01:43,013 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:01:43,013 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:01:43,065 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:01:43,071 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [700593415] [2024-11-09 05:01:43,075 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:01:43,075 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:01:43,076 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:01:43,080 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:01:43,084 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-09 05:01:43,170 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:01:43,172 INFO L255 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 23 conjuncts are in the unsatisfiable core [2024-11-09 05:01:43,175 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:01:43,415 INFO L134 CoverageAnalysis]: Checked inductivity of 75 backedges. 11 proven. 19 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-09 05:01:43,415 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:01:43,728 INFO L134 CoverageAnalysis]: Checked inductivity of 75 backedges. 13 proven. 17 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-09 05:01:43,730 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:01:43,730 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [264710711] [2024-11-09 05:01:43,730 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:01:43,730 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [700593415] [2024-11-09 05:01:43,731 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [700593415] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:01:43,731 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [760483205] [2024-11-09 05:01:43,761 INFO L159 IcfgInterpreter]: Started Sifa with 14 locations of interest [2024-11-09 05:01:43,762 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:01:43,766 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:01:43,773 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:01:43,774 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:01:45,638 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2024-11-09 05:01:45,646 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:01:45,987 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '977#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 05:01:45,987 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:01:45,988 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 05:01:45,988 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2024-11-09 05:01:45,988 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2102117828] [2024-11-09 05:01:45,988 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 05:01:45,988 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-09 05:01:45,989 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:01:45,989 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-09 05:01:45,989 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=281, Unknown=0, NotChecked=0, Total=342 [2024-11-09 05:01:45,990 INFO L87 Difference]: Start difference. First operand 43 states and 54 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, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-09 05:01:46,341 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:01:46,342 INFO L93 Difference]: Finished difference Result 66 states and 86 transitions. [2024-11-09 05:01:46,342 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 05:01:46,343 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, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) Word has length 38 [2024-11-09 05:01:46,343 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:01:46,345 INFO L225 Difference]: With dead ends: 66 [2024-11-09 05:01:46,345 INFO L226 Difference]: Without dead ends: 64 [2024-11-09 05:01:46,346 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 93 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 110 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=83, Invalid=379, Unknown=0, NotChecked=0, Total=462 [2024-11-09 05:01:46,347 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 10 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 144 mSolverCounterSat, 58 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 86 SdHoareTripleChecker+Invalid, 202 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 58 IncrementalHoareTripleChecker+Valid, 144 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-09 05:01:46,347 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 86 Invalid, 202 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [58 Valid, 144 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-09 05:01:46,348 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2024-11-09 05:01:46,368 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 51. [2024-11-09 05:01:46,368 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 27 states have (on average 1.0740740740740742) internal successors, (29), 28 states have internal predecessors, (29), 16 states have call successors, (16), 7 states have call predecessors, (16), 7 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-09 05:01:46,369 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 60 transitions. [2024-11-09 05:01:46,370 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 60 transitions. Word has length 38 [2024-11-09 05:01:46,370 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:01:46,370 INFO L471 AbstractCegarLoop]: Abstraction has 51 states and 60 transitions. [2024-11-09 05:01:46,371 INFO L472 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, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-09 05:01:46,371 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 60 transitions. [2024-11-09 05:01:46,372 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-09 05:01:46,372 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:01:46,372 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:01:46,397 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-09 05:01:46,573 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:01:46,573 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:01:46,574 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:01:46,574 INFO L85 PathProgramCache]: Analyzing trace with hash 137865937, now seen corresponding path program 2 times [2024-11-09 05:01:46,574 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:01:46,574 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [288296644] [2024-11-09 05:01:46,574 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:01:46,575 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:01:46,607 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:01:46,609 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [275596527] [2024-11-09 05:01:46,610 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 05:01:46,610 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:01:46,610 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:01:46,612 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:01:46,620 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-09 05:01:46,701 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2024-11-09 05:01:46,701 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 05:01:46,705 INFO L255 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-09 05:01:46,707 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:01:46,832 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 14 proven. 4 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-11-09 05:01:46,832 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:01:46,973 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 14 proven. 4 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-11-09 05:01:46,974 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:01:46,974 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [288296644] [2024-11-09 05:01:46,974 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:01:46,974 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [275596527] [2024-11-09 05:01:46,974 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [275596527] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:01:46,975 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1670816445] [2024-11-09 05:01:46,977 INFO L159 IcfgInterpreter]: Started Sifa with 14 locations of interest [2024-11-09 05:01:46,978 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:01:46,978 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:01:46,978 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:01:46,978 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:01:48,187 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2024-11-09 05:01:48,194 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:01:48,475 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1444#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 05:01:48,475 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:01:48,475 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 05:01:48,475 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2024-11-09 05:01:48,476 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [276783446] [2024-11-09 05:01:48,476 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 05:01:48,476 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-09 05:01:48,476 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:01:48,477 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-09 05:01:48,478 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=196, Unknown=0, NotChecked=0, Total=240 [2024-11-09 05:01:48,478 INFO L87 Difference]: Start difference. First operand 51 states and 60 transitions. Second operand has 10 states, 10 states have (on average 1.6) internal successors, (16), 8 states have internal predecessors, (16), 4 states have call successors, (16), 3 states have call predecessors, (16), 1 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-09 05:01:48,683 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:01:48,683 INFO L93 Difference]: Finished difference Result 70 states and 89 transitions. [2024-11-09 05:01:48,684 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-09 05:01:48,684 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 1.6) internal successors, (16), 8 states have internal predecessors, (16), 4 states have call successors, (16), 3 states have call predecessors, (16), 1 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 43 [2024-11-09 05:01:48,685 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:01:48,686 INFO L225 Difference]: With dead ends: 70 [2024-11-09 05:01:48,686 INFO L226 Difference]: Without dead ends: 68 [2024-11-09 05:01:48,687 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 128 GetRequests, 111 SyntacticMatches, 2 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 63 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=50, Invalid=222, Unknown=0, NotChecked=0, Total=272 [2024-11-09 05:01:48,688 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 7 mSDsluCounter, 168 mSDsCounter, 0 mSdLazyCounter, 82 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 204 SdHoareTripleChecker+Invalid, 85 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 82 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 05:01:48,688 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 204 Invalid, 85 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 82 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 05:01:48,689 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 68 states. [2024-11-09 05:01:48,712 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 68 to 59. [2024-11-09 05:01:48,712 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 31 states have (on average 1.064516129032258) internal successors, (33), 33 states have internal predecessors, (33), 19 states have call successors, (19), 8 states have call predecessors, (19), 8 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) [2024-11-09 05:01:48,713 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 70 transitions. [2024-11-09 05:01:48,714 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 70 transitions. Word has length 43 [2024-11-09 05:01:48,714 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:01:48,714 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 70 transitions. [2024-11-09 05:01:48,715 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 1.6) internal successors, (16), 8 states have internal predecessors, (16), 4 states have call successors, (16), 3 states have call predecessors, (16), 1 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-09 05:01:48,715 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 70 transitions. [2024-11-09 05:01:48,716 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2024-11-09 05:01:48,716 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:01:48,716 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:01:48,741 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-09 05:01:48,917 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:01:48,917 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:01:48,919 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:01:48,919 INFO L85 PathProgramCache]: Analyzing trace with hash 317524953, now seen corresponding path program 3 times [2024-11-09 05:01:48,919 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:01:48,920 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1379720628] [2024-11-09 05:01:48,920 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:01:48,920 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:01:48,947 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:01:48,949 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1600283065] [2024-11-09 05:01:48,949 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-09 05:01:48,950 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:01:48,950 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:01:48,952 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:01:48,957 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-09 05:01:49,028 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-09 05:01:49,028 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 05:01:49,030 INFO L255 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-09 05:01:49,033 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:01:49,204 INFO L134 CoverageAnalysis]: Checked inductivity of 133 backedges. 16 proven. 5 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2024-11-09 05:01:49,204 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:01:49,402 INFO L134 CoverageAnalysis]: Checked inductivity of 133 backedges. 16 proven. 5 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2024-11-09 05:01:49,402 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:01:49,402 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1379720628] [2024-11-09 05:01:49,403 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:01:49,403 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1600283065] [2024-11-09 05:01:49,403 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1600283065] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:01:49,403 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [91117576] [2024-11-09 05:01:49,405 INFO L159 IcfgInterpreter]: Started Sifa with 14 locations of interest [2024-11-09 05:01:49,405 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:01:49,406 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:01:49,406 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:01:49,406 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:01:50,615 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2024-11-09 05:01:50,622 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:01:50,913 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1955#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 05:01:50,914 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:01:50,914 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 05:01:50,914 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2024-11-09 05:01:50,914 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1015020353] [2024-11-09 05:01:50,915 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 05:01:50,915 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-09 05:01:50,915 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:01:50,916 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-09 05:01:50,916 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=144, Unknown=0, NotChecked=0, Total=182 [2024-11-09 05:01:50,917 INFO L87 Difference]: Start difference. First operand 59 states and 70 transitions. Second operand has 8 states, 8 states have (on average 1.75) internal successors, (14), 7 states have internal predecessors, (14), 4 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2024-11-09 05:01:51,311 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:01:51,311 INFO L93 Difference]: Finished difference Result 82 states and 98 transitions. [2024-11-09 05:01:51,312 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-09 05:01:51,312 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 1.75) internal successors, (14), 7 states have internal predecessors, (14), 4 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) Word has length 48 [2024-11-09 05:01:51,312 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:01:51,313 INFO L225 Difference]: With dead ends: 82 [2024-11-09 05:01:51,313 INFO L226 Difference]: Without dead ends: 74 [2024-11-09 05:01:51,314 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 144 GetRequests, 126 SyntacticMatches, 4 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 44 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=49, Invalid=191, Unknown=0, NotChecked=0, Total=240 [2024-11-09 05:01:51,315 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 6 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 79 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 128 SdHoareTripleChecker+Invalid, 105 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 79 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-09 05:01:51,315 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 128 Invalid, 105 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 79 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-09 05:01:51,316 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2024-11-09 05:01:51,347 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 68. [2024-11-09 05:01:51,348 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 40 states have (on average 1.05) internal successors, (42), 42 states have internal predecessors, (42), 16 states have call successors, (16), 11 states have call predecessors, (16), 11 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-09 05:01:51,352 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 73 transitions. [2024-11-09 05:01:51,352 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 73 transitions. Word has length 48 [2024-11-09 05:01:51,353 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:01:51,353 INFO L471 AbstractCegarLoop]: Abstraction has 68 states and 73 transitions. [2024-11-09 05:01:51,353 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 1.75) internal successors, (14), 7 states have internal predecessors, (14), 4 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2024-11-09 05:01:51,354 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 73 transitions. [2024-11-09 05:01:51,355 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2024-11-09 05:01:51,356 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:01:51,357 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:01:51,380 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-09 05:01:51,557 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:01:51,557 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:01:51,558 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:01:51,558 INFO L85 PathProgramCache]: Analyzing trace with hash 1940075568, now seen corresponding path program 1 times [2024-11-09 05:01:51,558 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:01:51,558 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1283070334] [2024-11-09 05:01:51,559 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:01:51,559 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:01:51,592 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:01:51,594 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1604279151] [2024-11-09 05:01:51,594 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:01:51,594 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:01:51,594 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:01:51,596 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:01:51,601 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-09 05:01:51,688 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:01:51,690 INFO L255 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-11-09 05:01:51,693 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:01:52,047 INFO L134 CoverageAnalysis]: Checked inductivity of 249 backedges. 21 proven. 38 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2024-11-09 05:01:52,048 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:01:53,690 INFO L134 CoverageAnalysis]: Checked inductivity of 249 backedges. 21 proven. 38 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2024-11-09 05:01:53,690 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:01:53,691 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1283070334] [2024-11-09 05:01:53,691 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:01:53,691 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1604279151] [2024-11-09 05:01:53,691 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1604279151] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:01:53,691 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1277026107] [2024-11-09 05:01:53,693 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2024-11-09 05:01:53,693 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:01:53,694 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:01:53,694 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:01:53,694 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:01:54,724 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2024-11-09 05:01:54,730 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:01:55,298 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2601#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 05:01:55,298 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:01:55,299 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 05:01:55,299 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2024-11-09 05:01:55,299 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2109731376] [2024-11-09 05:01:55,299 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 05:01:55,299 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-09 05:01:55,299 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:01:55,300 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-09 05:01:55,300 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=352, Unknown=0, NotChecked=0, Total=420 [2024-11-09 05:01:55,301 INFO L87 Difference]: Start difference. First operand 68 states and 73 transitions. Second operand has 15 states, 13 states have (on average 1.7692307692307692) internal successors, (23), 13 states have internal predecessors, (23), 7 states have call successors, (24), 3 states have call predecessors, (24), 2 states have return successors, (22), 6 states have call predecessors, (22), 7 states have call successors, (22) [2024-11-09 05:01:55,812 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:01:55,812 INFO L93 Difference]: Finished difference Result 97 states and 112 transitions. [2024-11-09 05:01:55,813 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-09 05:01:55,813 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 1.7692307692307692) internal successors, (23), 13 states have internal predecessors, (23), 7 states have call successors, (24), 3 states have call predecessors, (24), 2 states have return successors, (22), 6 states have call predecessors, (22), 7 states have call successors, (22) Word has length 64 [2024-11-09 05:01:55,814 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:01:55,817 INFO L225 Difference]: With dead ends: 97 [2024-11-09 05:01:55,817 INFO L226 Difference]: Without dead ends: 95 [2024-11-09 05:01:55,822 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 192 GetRequests, 169 SyntacticMatches, 2 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 119 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=82, Invalid=424, Unknown=0, NotChecked=0, Total=506 [2024-11-09 05:01:55,823 INFO L432 NwaCegarLoop]: 17 mSDtfsCounter, 5 mSDsluCounter, 126 mSDsCounter, 0 mSdLazyCounter, 208 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 143 SdHoareTripleChecker+Invalid, 232 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 208 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-09 05:01:55,824 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 143 Invalid, 232 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 208 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-09 05:01:55,824 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2024-11-09 05:01:55,871 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 93. [2024-11-09 05:01:55,873 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 52 states have (on average 1.0769230769230769) internal successors, (56), 55 states have internal predecessors, (56), 26 states have call successors, (26), 14 states have call predecessors, (26), 14 states have return successors, (25), 23 states have call predecessors, (25), 25 states have call successors, (25) [2024-11-09 05:01:55,876 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 107 transitions. [2024-11-09 05:01:55,876 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 107 transitions. Word has length 64 [2024-11-09 05:01:55,877 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:01:55,877 INFO L471 AbstractCegarLoop]: Abstraction has 93 states and 107 transitions. [2024-11-09 05:01:55,878 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 1.7692307692307692) internal successors, (23), 13 states have internal predecessors, (23), 7 states have call successors, (24), 3 states have call predecessors, (24), 2 states have return successors, (22), 6 states have call predecessors, (22), 7 states have call successors, (22) [2024-11-09 05:01:55,878 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 107 transitions. [2024-11-09 05:01:55,880 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2024-11-09 05:01:55,883 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:01:55,883 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:01:55,903 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-09 05:01:56,087 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2024-11-09 05:01:56,088 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:01:56,088 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:01:56,088 INFO L85 PathProgramCache]: Analyzing trace with hash 2095047898, now seen corresponding path program 1 times [2024-11-09 05:01:56,088 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:01:56,088 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1595494456] [2024-11-09 05:01:56,089 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:01:56,089 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:01:56,119 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:01:56,121 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1254105697] [2024-11-09 05:01:56,122 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:01:56,122 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:01:56,122 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:01:56,124 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:01:56,130 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-09 05:01:56,202 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:01:56,204 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-11-09 05:01:56,208 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:01:56,476 INFO L134 CoverageAnalysis]: Checked inductivity of 295 backedges. 23 proven. 41 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2024-11-09 05:01:56,476 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:01:57,251 INFO L134 CoverageAnalysis]: Checked inductivity of 295 backedges. 23 proven. 41 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2024-11-09 05:01:57,251 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:01:57,251 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1595494456] [2024-11-09 05:01:57,251 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:01:57,252 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1254105697] [2024-11-09 05:01:57,252 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1254105697] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:01:57,252 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1032444086] [2024-11-09 05:01:57,254 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2024-11-09 05:01:57,254 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:01:57,254 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:01:57,255 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:01:57,255 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:01:58,199 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2024-11-09 05:01:58,205 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:01:58,504 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3342#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 05:01:58,504 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:01:58,505 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 05:01:58,505 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2024-11-09 05:01:58,505 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1441108570] [2024-11-09 05:01:58,505 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 05:01:58,506 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-09 05:01:58,506 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:01:58,506 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-09 05:01:58,507 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=352, Unknown=0, NotChecked=0, Total=420 [2024-11-09 05:01:58,507 INFO L87 Difference]: Start difference. First operand 93 states and 107 transitions. Second operand has 15 states, 13 states have (on average 1.7692307692307692) internal successors, (23), 13 states have internal predecessors, (23), 7 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 6 states have call predecessors, (24), 7 states have call successors, (24) [2024-11-09 05:01:59,249 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:01:59,250 INFO L93 Difference]: Finished difference Result 114 states and 125 transitions. [2024-11-09 05:01:59,250 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-09 05:01:59,251 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 1.7692307692307692) internal successors, (23), 13 states have internal predecessors, (23), 7 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 6 states have call predecessors, (24), 7 states have call successors, (24) Word has length 69 [2024-11-09 05:01:59,252 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:01:59,253 INFO L225 Difference]: With dead ends: 114 [2024-11-09 05:01:59,253 INFO L226 Difference]: Without dead ends: 94 [2024-11-09 05:01:59,254 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 207 GetRequests, 184 SyntacticMatches, 2 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 119 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=82, Invalid=424, Unknown=0, NotChecked=0, Total=506 [2024-11-09 05:01:59,255 INFO L432 NwaCegarLoop]: 17 mSDtfsCounter, 4 mSDsluCounter, 123 mSDsCounter, 0 mSdLazyCounter, 200 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 140 SdHoareTripleChecker+Invalid, 212 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 200 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2024-11-09 05:01:59,257 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 140 Invalid, 212 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 200 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2024-11-09 05:01:59,257 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 94 states. [2024-11-09 05:01:59,303 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 94 to 94. [2024-11-09 05:01:59,304 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 55 states have (on average 1.0363636363636364) internal successors, (57), 56 states have internal predecessors, (57), 23 states have call successors, (23), 15 states have call predecessors, (23), 15 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-11-09 05:01:59,304 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 102 transitions. [2024-11-09 05:01:59,305 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 102 transitions. Word has length 69 [2024-11-09 05:01:59,305 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:01:59,305 INFO L471 AbstractCegarLoop]: Abstraction has 94 states and 102 transitions. [2024-11-09 05:01:59,306 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 1.7692307692307692) internal successors, (23), 13 states have internal predecessors, (23), 7 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 6 states have call predecessors, (24), 7 states have call successors, (24) [2024-11-09 05:01:59,306 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 102 transitions. [2024-11-09 05:01:59,309 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2024-11-09 05:01:59,309 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:01:59,310 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1] [2024-11-09 05:01:59,333 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-09 05:01:59,510 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:01:59,510 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:01:59,511 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:01:59,511 INFO L85 PathProgramCache]: Analyzing trace with hash -1811520775, now seen corresponding path program 4 times [2024-11-09 05:01:59,511 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:01:59,511 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [232607607] [2024-11-09 05:01:59,511 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:01:59,512 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:01:59,549 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:01:59,555 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [242845418] [2024-11-09 05:01:59,557 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-09 05:01:59,558 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:01:59,558 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:01:59,560 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:01:59,564 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-09 05:01:59,628 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 05:01:59,629 INFO L255 TraceCheckSpWp]: Trace formula consists of 170 conjuncts, 31 conjuncts are in the unsatisfiable core [2024-11-09 05:01:59,631 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:01:59,822 INFO L134 CoverageAnalysis]: Checked inductivity of 303 backedges. 23 proven. 49 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2024-11-09 05:01:59,822 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:02:00,128 INFO L134 CoverageAnalysis]: Checked inductivity of 303 backedges. 23 proven. 49 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2024-11-09 05:02:00,129 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:02:00,129 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [232607607] [2024-11-09 05:02:00,129 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:02:00,129 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [242845418] [2024-11-09 05:02:00,129 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [242845418] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:02:00,129 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [75803215] [2024-11-09 05:02:00,132 INFO L159 IcfgInterpreter]: Started Sifa with 14 locations of interest [2024-11-09 05:02:00,133 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:02:00,133 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:02:00,134 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:02:00,134 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:02:00,990 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2024-11-09 05:02:00,996 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:02:01,300 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4115#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 05:02:01,301 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:02:01,301 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 05:02:01,301 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2024-11-09 05:02:01,301 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [907941136] [2024-11-09 05:02:01,301 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 05:02:01,302 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-09 05:02:01,302 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:02:01,302 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-09 05:02:01,303 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=352, Unknown=0, NotChecked=0, Total=420 [2024-11-09 05:02:01,303 INFO L87 Difference]: Start difference. First operand 94 states and 102 transitions. Second operand has 15 states, 15 states have (on average 1.6666666666666667) internal successors, (25), 13 states have internal predecessors, (25), 7 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 6 states have call predecessors, (24), 7 states have call successors, (24) [2024-11-09 05:02:03,786 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.18s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 05:02:03,988 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:02:03,988 INFO L93 Difference]: Finished difference Result 100 states and 107 transitions. [2024-11-09 05:02:03,988 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-09 05:02:03,989 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 1.6666666666666667) internal successors, (25), 13 states have internal predecessors, (25), 7 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 6 states have call predecessors, (24), 7 states have call successors, (24) Word has length 70 [2024-11-09 05:02:03,989 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:02:03,990 INFO L225 Difference]: With dead ends: 100 [2024-11-09 05:02:03,990 INFO L226 Difference]: Without dead ends: 98 [2024-11-09 05:02:03,991 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 213 GetRequests, 187 SyntacticMatches, 3 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 151 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=100, Invalid=500, Unknown=0, NotChecked=0, Total=600 [2024-11-09 05:02:03,991 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 10 mSDsluCounter, 127 mSDsCounter, 0 mSdLazyCounter, 230 mSolverCounterSat, 40 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 150 SdHoareTripleChecker+Invalid, 271 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 230 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.6s IncrementalHoareTripleChecker+Time [2024-11-09 05:02:03,992 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 150 Invalid, 271 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 230 Invalid, 1 Unknown, 0 Unchecked, 2.6s Time] [2024-11-09 05:02:03,993 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2024-11-09 05:02:04,027 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 98. [2024-11-09 05:02:04,027 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 58 states have (on average 1.0344827586206897) internal successors, (60), 59 states have internal predecessors, (60), 23 states have call successors, (23), 16 states have call predecessors, (23), 16 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-11-09 05:02:04,028 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 105 transitions. [2024-11-09 05:02:04,028 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 105 transitions. Word has length 70 [2024-11-09 05:02:04,028 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:02:04,029 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 105 transitions. [2024-11-09 05:02:04,029 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 1.6666666666666667) internal successors, (25), 13 states have internal predecessors, (25), 7 states have call successors, (26), 3 states have call predecessors, (26), 2 states have return successors, (24), 6 states have call predecessors, (24), 7 states have call successors, (24) [2024-11-09 05:02:04,029 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 105 transitions. [2024-11-09 05:02:04,030 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 119 [2024-11-09 05:02:04,031 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:02:04,031 INFO L215 NwaCegarLoop]: trace histogram [22, 21, 21, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:02:04,049 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-11-09 05:02:04,231 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-09 05:02:04,232 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:02:04,232 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:02:04,232 INFO L85 PathProgramCache]: Analyzing trace with hash 1671130416, now seen corresponding path program 2 times [2024-11-09 05:02:04,232 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:02:04,232 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1788805398] [2024-11-09 05:02:04,233 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:02:04,233 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:02:04,307 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:02:04,309 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [297499070] [2024-11-09 05:02:04,310 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 05:02:04,310 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:02:04,310 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:02:04,317 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:02:04,322 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-09 05:02:04,456 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-09 05:02:04,456 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 05:02:04,457 INFO L255 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-09 05:02:04,460 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:02:04,768 INFO L134 CoverageAnalysis]: Checked inductivity of 924 backedges. 107 proven. 16 refuted. 0 times theorem prover too weak. 801 trivial. 0 not checked. [2024-11-09 05:02:04,769 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:02:04,935 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:02:04,935 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1788805398] [2024-11-09 05:02:04,935 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:02:04,935 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [297499070] [2024-11-09 05:02:04,935 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [297499070] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 05:02:04,935 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [210778371] [2024-11-09 05:02:04,937 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2024-11-09 05:02:04,938 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:02:04,938 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:02:04,938 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:02:04,938 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:02:05,706 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2024-11-09 05:02:05,710 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:02:06,019 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4824#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 05:02:06,019 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:02:06,019 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-09 05:02:06,019 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2024-11-09 05:02:06,019 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1438904939] [2024-11-09 05:02:06,019 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-09 05:02:06,020 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-09 05:02:06,020 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:02:06,020 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-09 05:02:06,020 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=254, Unknown=0, NotChecked=0, Total=306 [2024-11-09 05:02:06,021 INFO L87 Difference]: Start difference. First operand 98 states and 105 transitions. Second operand has 10 states, 9 states have (on average 1.6666666666666667) internal successors, (15), 8 states have internal predecessors, (15), 4 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-09 05:02:06,180 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:02:06,180 INFO L93 Difference]: Finished difference Result 104 states and 110 transitions. [2024-11-09 05:02:06,180 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-09 05:02:06,180 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 1.6666666666666667) internal successors, (15), 8 states have internal predecessors, (15), 4 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) Word has length 118 [2024-11-09 05:02:06,181 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:02:06,182 INFO L225 Difference]: With dead ends: 104 [2024-11-09 05:02:06,182 INFO L226 Difference]: Without dead ends: 100 [2024-11-09 05:02:06,182 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 242 GetRequests, 220 SyntacticMatches, 4 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 102 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=66, Invalid=314, Unknown=0, NotChecked=0, Total=380 [2024-11-09 05:02:06,183 INFO L432 NwaCegarLoop]: 11 mSDtfsCounter, 7 mSDsluCounter, 38 mSDsCounter, 0 mSdLazyCounter, 77 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 49 SdHoareTripleChecker+Invalid, 89 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 77 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 05:02:06,183 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 49 Invalid, 89 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 77 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 05:02:06,184 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2024-11-09 05:02:06,211 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 100. [2024-11-09 05:02:06,212 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 100 states, 60 states have (on average 1.0166666666666666) internal successors, (61), 60 states have internal predecessors, (61), 23 states have call successors, (23), 17 states have call predecessors, (23), 16 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-11-09 05:02:06,213 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 106 transitions. [2024-11-09 05:02:06,213 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 106 transitions. Word has length 118 [2024-11-09 05:02:06,214 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:02:06,214 INFO L471 AbstractCegarLoop]: Abstraction has 100 states and 106 transitions. [2024-11-09 05:02:06,214 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 1.6666666666666667) internal successors, (15), 8 states have internal predecessors, (15), 4 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-09 05:02:06,215 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 106 transitions. [2024-11-09 05:02:06,216 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 124 [2024-11-09 05:02:06,216 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 05:02:06,217 INFO L215 NwaCegarLoop]: trace histogram [23, 22, 22, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 05:02:06,224 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-09 05:02:06,420 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-09 05:02:06,420 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 05:02:06,421 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 05:02:06,421 INFO L85 PathProgramCache]: Analyzing trace with hash 203639770, now seen corresponding path program 2 times [2024-11-09 05:02:06,421 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 05:02:06,421 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2105729138] [2024-11-09 05:02:06,421 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 05:02:06,421 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 05:02:06,461 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 05:02:06,462 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1259314366] [2024-11-09 05:02:06,463 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 05:02:06,463 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 05:02:06,463 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 05:02:06,465 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 05:02:06,470 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-09 05:02:06,572 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-09 05:02:06,572 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 05:02:06,574 INFO L255 TraceCheckSpWp]: Trace formula consists of 135 conjuncts, 41 conjuncts are in the unsatisfiable core [2024-11-09 05:02:06,578 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 05:02:07,068 INFO L134 CoverageAnalysis]: Checked inductivity of 1010 backedges. 181 proven. 69 refuted. 0 times theorem prover too weak. 760 trivial. 0 not checked. [2024-11-09 05:02:07,068 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 05:02:11,910 INFO L134 CoverageAnalysis]: Checked inductivity of 1010 backedges. 148 proven. 39 refuted. 0 times theorem prover too weak. 823 trivial. 0 not checked. [2024-11-09 05:02:11,910 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 05:02:11,910 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2105729138] [2024-11-09 05:02:11,911 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 05:02:11,911 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1259314366] [2024-11-09 05:02:11,911 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1259314366] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 05:02:11,911 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [618719575] [2024-11-09 05:02:11,914 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2024-11-09 05:02:11,914 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 05:02:11,914 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 05:02:11,914 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 05:02:11,914 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 05:02:12,928 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2024-11-09 05:02:12,933 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 05:02:13,424 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5908#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 05:02:13,424 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 05:02:13,425 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 05:02:13,425 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 17 [2024-11-09 05:02:13,425 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1215736172] [2024-11-09 05:02:13,425 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 05:02:13,426 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-09 05:02:13,426 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 05:02:13,426 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-09 05:02:13,427 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=418, Unknown=0, NotChecked=0, Total=506 [2024-11-09 05:02:13,427 INFO L87 Difference]: Start difference. First operand 100 states and 106 transitions. Second operand has 17 states, 15 states have (on average 1.8) internal successors, (27), 13 states have internal predecessors, (27), 9 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (31), 8 states have call predecessors, (31), 9 states have call successors, (31) [2024-11-09 05:02:13,834 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 05:02:13,834 INFO L93 Difference]: Finished difference Result 100 states and 106 transitions. [2024-11-09 05:02:13,835 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 05:02:13,835 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 1.8) internal successors, (27), 13 states have internal predecessors, (27), 9 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (31), 8 states have call predecessors, (31), 9 states have call successors, (31) Word has length 123 [2024-11-09 05:02:13,835 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 05:02:13,836 INFO L225 Difference]: With dead ends: 100 [2024-11-09 05:02:13,836 INFO L226 Difference]: Without dead ends: 0 [2024-11-09 05:02:13,837 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 370 GetRequests, 342 SyntacticMatches, 4 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 208 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=119, Invalid=531, Unknown=0, NotChecked=0, Total=650 [2024-11-09 05:02:13,838 INFO L432 NwaCegarLoop]: 10 mSDtfsCounter, 7 mSDsluCounter, 52 mSDsCounter, 0 mSdLazyCounter, 77 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 62 SdHoareTripleChecker+Invalid, 105 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 77 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 05:02:13,838 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 62 Invalid, 105 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 77 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 05:02:13,839 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2024-11-09 05:02:13,839 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2024-11-09 05:02:13,839 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 05:02:13,839 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2024-11-09 05:02:13,840 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 123 [2024-11-09 05:02:13,840 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 05:02:13,840 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 05:02:13,840 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 1.8) internal successors, (27), 13 states have internal predecessors, (27), 9 states have call successors, (31), 3 states have call predecessors, (31), 2 states have return successors, (31), 8 states have call predecessors, (31), 9 states have call successors, (31) [2024-11-09 05:02:13,841 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2024-11-09 05:02:13,841 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2024-11-09 05:02:13,843 INFO L782 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-09 05:02:13,849 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2024-11-09 05:02:14,044 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2024-11-09 05:02:14,048 INFO L407 BasicCegarLoop]: Path program histogram: [4, 2, 2, 1, 1, 1, 1] [2024-11-09 05:02:14,051 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2024-11-09 05:02:19,245 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-11-09 05:02:19,275 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 09.11 05:02:19 BoogieIcfgContainer [2024-11-09 05:02:19,275 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-09 05:02:19,276 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-09 05:02:19,276 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-09 05:02:19,277 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-09 05:02:19,277 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 05:01:39" (3/4) ... [2024-11-09 05:02:19,281 INFO L142 WitnessPrinter]: Generating witness for correct program [2024-11-09 05:02:19,285 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2024-11-09 05:02:19,290 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 14 nodes and edges [2024-11-09 05:02:19,291 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 6 nodes and edges [2024-11-09 05:02:19,291 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2024-11-09 05:02:19,291 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2024-11-09 05:02:19,402 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/witness.graphml [2024-11-09 05:02:19,403 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/witness.yml [2024-11-09 05:02:19,403 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-09 05:02:19,404 INFO L158 Benchmark]: Toolchain (without parser) took 40373.82ms. Allocated memory was 144.7MB in the beginning and 436.2MB in the end (delta: 291.5MB). Free memory was 107.8MB in the beginning and 366.2MB in the end (delta: -258.3MB). Peak memory consumption was 35.1MB. Max. memory is 16.1GB. [2024-11-09 05:02:19,405 INFO L158 Benchmark]: CDTParser took 0.31ms. Allocated memory is still 144.7MB. Free memory is still 91.7MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 05:02:19,405 INFO L158 Benchmark]: CACSL2BoogieTranslator took 429.92ms. Allocated memory is still 144.7MB. Free memory was 107.8MB in the beginning and 94.8MB in the end (delta: 13.1MB). Peak memory consumption was 14.7MB. Max. memory is 16.1GB. [2024-11-09 05:02:19,406 INFO L158 Benchmark]: Boogie Procedure Inliner took 37.63ms. Allocated memory is still 144.7MB. Free memory was 94.8MB in the beginning and 93.1MB in the end (delta: 1.7MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 05:02:19,406 INFO L158 Benchmark]: Boogie Preprocessor took 30.20ms. Allocated memory is still 144.7MB. Free memory was 93.1MB in the beginning and 91.9MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 05:02:19,406 INFO L158 Benchmark]: RCFGBuilder took 453.85ms. Allocated memory is still 144.7MB. Free memory was 91.9MB in the beginning and 77.5MB in the end (delta: 14.4MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. [2024-11-09 05:02:19,407 INFO L158 Benchmark]: TraceAbstraction took 39286.06ms. Allocated memory was 144.7MB in the beginning and 436.2MB in the end (delta: 291.5MB). Free memory was 77.0MB in the beginning and 371.4MB in the end (delta: -294.4MB). Peak memory consumption was 223.9MB. Max. memory is 16.1GB. [2024-11-09 05:02:19,408 INFO L158 Benchmark]: Witness Printer took 127.24ms. Allocated memory is still 436.2MB. Free memory was 371.4MB in the beginning and 366.2MB in the end (delta: 5.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2024-11-09 05:02:19,410 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.31ms. Allocated memory is still 144.7MB. Free memory is still 91.7MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 429.92ms. Allocated memory is still 144.7MB. Free memory was 107.8MB in the beginning and 94.8MB in the end (delta: 13.1MB). Peak memory consumption was 14.7MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 37.63ms. Allocated memory is still 144.7MB. Free memory was 94.8MB in the beginning and 93.1MB in the end (delta: 1.7MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 30.20ms. Allocated memory is still 144.7MB. Free memory was 93.1MB in the beginning and 91.9MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 453.85ms. Allocated memory is still 144.7MB. Free memory was 91.9MB in the beginning and 77.5MB in the end (delta: 14.4MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. * TraceAbstraction took 39286.06ms. Allocated memory was 144.7MB in the beginning and 436.2MB in the end (delta: 291.5MB). Free memory was 77.0MB in the beginning and 371.4MB in the end (delta: -294.4MB). Peak memory consumption was 223.9MB. Max. memory is 16.1GB. * Witness Printer took 127.24ms. Allocated memory is still 436.2MB. Free memory was 371.4MB in the beginning and 366.2MB in the end (delta: 5.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 17]: a call to reach_error is unreachable For all program executions holds that a call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 22 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 34.0s, OverallIterations: 12, TraceHistogramMax: 23, PathProgramHistogramMax: 4, EmptinessCheckTime: 0.0s, AutomataDifference: 6.3s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 1 mSolverCounterUnknown, 123 SdHoareTripleChecker+Valid, 5.0s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 72 mSDsluCounter, 1302 SdHoareTripleChecker+Invalid, 4.7s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1040 mSDsCounter, 213 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1249 IncrementalHoareTripleChecker+Invalid, 1463 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 213 mSolverCounterUnsat, 262 mSDtfsCounter, 1249 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1664 GetRequests, 1469 SyntacticMatches, 23 SemanticMatches, 172 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 916 ImplicationChecksByTransitivity, 5.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=100occurred in iteration=11, InterpolantAutomatonStates: 91, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.4s AutomataMinimizationTime, 12 MinimizatonAttempts, 44 StatesRemovedByMinimization, 6 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.8s SatisfiabilityAnalysisTime, 11.3s InterpolantComputationTime, 1248 NumberOfCodeBlocks, 1069 NumberOfCodeBlocksAsserted, 30 NumberOfCheckSat, 1063 ConstructedInterpolants, 0 QuantifiedInterpolants, 4796 SizeOfPredicates, 22 NumberOfNonLiveVariables, 1206 ConjunctsInSsa, 224 ConjunctsInUnsatCore, 19 InterpolantComputations, 4 PerfectInterpolantSequences, 4852/5286 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 33]: Loop Invariant Derived loop invariant: ((((((a <= 2) && (y == ((((__int128) 3 * n) + (3 * ((__int128) n * n))) + 1))) && (n <= (a + 1))) && (0 <= a)) && (((((6 * ((__int128) n * n)) + ((__int128) n * 12)) + (((__int128) n * n) * n)) + 8) == ((((__int128) 2 * y) + x) + z))) && ((((((__int128) 3 * n) + (3 * ((__int128) n * n))) + (((__int128) n * n) * n)) + 1) == ((__int128) x + y))) - ProcedureContractResult [Line: 14]: Procedure Contract for __VERIFIER_assert Derived contract for procedure __VERIFIER_assert. Requires: (cond != 0) Ensures: (cond != 0) RESULT: Ultimate proved your program to be correct! [2024-11-09 05:02:19,450 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_dafa1051-3b43-4746-beb7-69f6f0a8db96/bin/utaipan-verify-YMUCfTKeje/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE