./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/ps6-ll_valuebound5.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 826ab2ba Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/ps6-ll_valuebound5.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E --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 9671c34313c5e47de5bd2f842db47c3009aa180bae8c949f2010db1179ac602f --- Real Ultimate output --- This is Ultimate 0.3.0-dev-826ab2b [2024-11-14 03:29:43,380 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-14 03:29:43,474 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-32bit-Taipan_Default.epf [2024-11-14 03:29:43,480 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-14 03:29:43,481 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-14 03:29:43,509 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-14 03:29:43,510 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-14 03:29:43,510 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-14 03:29:43,511 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-14 03:29:43,511 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-14 03:29:43,511 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-14 03:29:43,511 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-14 03:29:43,512 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-14 03:29:43,512 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-14 03:29:43,512 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-14 03:29:43,512 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-14 03:29:43,512 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-14 03:29:43,512 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-14 03:29:43,513 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-14 03:29:43,513 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-14 03:29:43,513 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-14 03:29:43,513 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-14 03:29:43,514 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-14 03:29:43,514 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-14 03:29:43,514 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-14 03:29:43,514 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-14 03:29:43,514 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-14 03:29:43,514 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-14 03:29:43,514 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-14 03:29:43,515 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-14 03:29:43,515 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-14 03:29:43,515 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-14 03:29:43,515 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-14 03:29:43,515 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-14 03:29:43,515 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-14 03:29:43,515 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-14 03:29:43,515 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-14 03:29:43,516 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-14 03:29:43,516 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 03:29:43,516 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-14 03:29:43,516 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-14 03:29:43,517 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-14 03:29:43,517 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-14 03:29:43,517 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-14 03:29:43,517 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-14 03:29:43,517 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-14 03:29:43,517 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-14 03:29:43,518 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES 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_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E 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 -> 9671c34313c5e47de5bd2f842db47c3009aa180bae8c949f2010db1179ac602f [2024-11-14 03:29:43,892 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-14 03:29:43,902 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-14 03:29:43,905 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-14 03:29:43,906 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-14 03:29:43,907 INFO L274 PluginConnector]: CDTParser initialized [2024-11-14 03:29:43,909 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/../../sv-benchmarks/c/nla-digbench-scaling/ps6-ll_valuebound5.c Unable to find full path for "g++" [2024-11-14 03:29:46,063 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-14 03:29:46,359 INFO L384 CDTParser]: Found 1 translation units. [2024-11-14 03:29:46,360 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/sv-benchmarks/c/nla-digbench-scaling/ps6-ll_valuebound5.c [2024-11-14 03:29:46,369 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/data/788a4673b/fcb866f2d58d4fb282ebffe4ce5bf0fd/FLAG8c5e9cf8c [2024-11-14 03:29:46,649 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/data/788a4673b/fcb866f2d58d4fb282ebffe4ce5bf0fd [2024-11-14 03:29:46,652 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-14 03:29:46,654 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-14 03:29:46,655 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-14 03:29:46,655 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-14 03:29:46,663 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-14 03:29:46,664 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 03:29:46" (1/1) ... [2024-11-14 03:29:46,669 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1649065d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:29:46, skipping insertion in model container [2024-11-14 03:29:46,669 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 03:29:46" (1/1) ... [2024-11-14 03:29:46,689 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-14 03:29:46,893 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_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/sv-benchmarks/c/nla-digbench-scaling/ps6-ll_valuebound5.c[458,471] [2024-11-14 03:29:46,917 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 03:29:46,933 INFO L200 MainTranslator]: Completed pre-run [2024-11-14 03:29:46,945 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_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/sv-benchmarks/c/nla-digbench-scaling/ps6-ll_valuebound5.c[458,471] [2024-11-14 03:29:46,954 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 03:29:46,970 INFO L204 MainTranslator]: Completed translation [2024-11-14 03:29:46,971 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:29:46 WrapperNode [2024-11-14 03:29:46,971 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-14 03:29:46,972 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-14 03:29:46,973 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-14 03:29:46,975 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-14 03:29:46,983 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:29:46" (1/1) ... [2024-11-14 03:29:46,991 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:29:46" (1/1) ... [2024-11-14 03:29:47,012 INFO L138 Inliner]: procedures = 14, calls = 12, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 35 [2024-11-14 03:29:47,012 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-14 03:29:47,013 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-14 03:29:47,013 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-14 03:29:47,013 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-14 03:29:47,022 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:29:46" (1/1) ... [2024-11-14 03:29:47,022 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:29:46" (1/1) ... [2024-11-14 03:29:47,024 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:29:46" (1/1) ... [2024-11-14 03:29:47,024 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:29:46" (1/1) ... [2024-11-14 03:29:47,027 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:29:46" (1/1) ... [2024-11-14 03:29:47,031 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:29:46" (1/1) ... [2024-11-14 03:29:47,032 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:29:46" (1/1) ... [2024-11-14 03:29:47,033 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:29:46" (1/1) ... [2024-11-14 03:29:47,034 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-14 03:29:47,035 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-14 03:29:47,036 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-14 03:29:47,036 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-14 03:29:47,037 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:29:46" (1/1) ... [2024-11-14 03:29:47,044 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 03:29:47,062 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:29:47,077 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-14 03:29:47,083 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-14 03:29:47,119 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-14 03:29:47,119 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-14 03:29:47,119 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-14 03:29:47,119 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-14 03:29:47,120 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-14 03:29:47,120 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-14 03:29:47,120 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-14 03:29:47,120 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-14 03:29:47,213 INFO L238 CfgBuilder]: Building ICFG [2024-11-14 03:29:47,215 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-14 03:29:47,413 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-14 03:29:47,413 INFO L287 CfgBuilder]: Performing block encoding [2024-11-14 03:29:47,464 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-14 03:29:47,464 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-14 03:29:47,468 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 03:29:47 BoogieIcfgContainer [2024-11-14 03:29:47,468 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-14 03:29:47,471 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-14 03:29:47,473 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-14 03:29:47,478 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-14 03:29:47,479 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.11 03:29:46" (1/3) ... [2024-11-14 03:29:47,481 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6ff49b7c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 03:29:47, skipping insertion in model container [2024-11-14 03:29:47,481 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 03:29:46" (2/3) ... [2024-11-14 03:29:47,482 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6ff49b7c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 03:29:47, skipping insertion in model container [2024-11-14 03:29:47,482 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 03:29:47" (3/3) ... [2024-11-14 03:29:47,484 INFO L112 eAbstractionObserver]: Analyzing ICFG ps6-ll_valuebound5.c [2024-11-14 03:29:47,502 INFO L217 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-14 03:29:47,504 INFO L154 ceAbstractionStarter]: Applying trace abstraction to ICFG ps6-ll_valuebound5.c that has 3 procedures, 19 locations, 1 initial locations, 1 loop locations, and 1 error locations. [2024-11-14 03:29:47,576 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-14 03:29:47,594 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;@50e69ebe, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-14 03:29:47,595 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-14 03:29:47,600 INFO L276 IsEmpty]: Start isEmpty. Operand has 19 states, 10 states have (on average 1.4) internal successors, (14), 11 states have internal predecessors, (14), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-14 03:29:47,608 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2024-11-14 03:29:47,608 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:29:47,609 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:29:47,610 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:29:47,615 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:29:47,616 INFO L85 PathProgramCache]: Analyzing trace with hash -847073814, now seen corresponding path program 1 times [2024-11-14 03:29:47,628 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:29:47,629 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1263440479] [2024-11-14 03:29:47,629 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:29:47,630 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:29:47,731 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:29:47,804 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 03:29:47,806 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:29:47,806 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1263440479] [2024-11-14 03:29:47,807 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1263440479] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 03:29:47,807 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 03:29:47,807 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-14 03:29:47,809 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1353300535] [2024-11-14 03:29:47,812 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 03:29:47,816 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-14 03:29:47,816 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:29:47,840 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-14 03:29:47,841 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-14 03:29:47,843 INFO L87 Difference]: Start difference. First operand has 19 states, 10 states have (on average 1.4) internal successors, (14), 11 states have internal predecessors, (14), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Second operand has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 2 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-14 03:29:47,877 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:29:47,877 INFO L93 Difference]: Finished difference Result 32 states and 44 transitions. [2024-11-14 03:29:47,879 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-14 03:29:47,880 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 2 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 13 [2024-11-14 03:29:47,881 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:29:47,888 INFO L225 Difference]: With dead ends: 32 [2024-11-14 03:29:47,888 INFO L226 Difference]: Without dead ends: 17 [2024-11-14 03:29:47,892 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-14 03:29:47,898 INFO L432 NwaCegarLoop]: 19 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 3 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 19 SdHoareTripleChecker+Invalid, 3 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 3 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 03:29:47,899 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 19 Invalid, 3 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 3 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 03:29:47,920 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states. [2024-11-14 03:29:47,937 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2024-11-14 03:29:47,939 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 10 states have internal predecessors, (11), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-14 03:29:47,947 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 20 transitions. [2024-11-14 03:29:47,950 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 20 transitions. Word has length 13 [2024-11-14 03:29:47,954 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:29:47,954 INFO L471 AbstractCegarLoop]: Abstraction has 17 states and 20 transitions. [2024-11-14 03:29:47,955 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 2 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-14 03:29:47,955 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 20 transitions. [2024-11-14 03:29:47,956 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2024-11-14 03:29:47,956 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:29:47,956 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:29:47,956 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-14 03:29:47,957 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:29:47,957 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:29:47,958 INFO L85 PathProgramCache]: Analyzing trace with hash -894232967, now seen corresponding path program 1 times [2024-11-14 03:29:47,958 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:29:47,958 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [5303704] [2024-11-14 03:29:47,958 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:29:47,958 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:29:48,021 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 03:29:48,024 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1933353812] [2024-11-14 03:29:48,024 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:29:48,024 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:29:48,024 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:29:48,027 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:29:48,030 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-14 03:29:48,103 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:29:48,105 INFO L255 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-14 03:29:48,112 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:29:48,271 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 03:29:48,271 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 03:29:48,272 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:29:48,272 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [5303704] [2024-11-14 03:29:48,273 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 03:29:48,273 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1933353812] [2024-11-14 03:29:48,273 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1933353812] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 03:29:48,273 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 03:29:48,273 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-14 03:29:48,274 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1949022262] [2024-11-14 03:29:48,275 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 03:29:48,275 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 03:29:48,275 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:29:48,276 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 03:29:48,276 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-14 03:29:48,277 INFO L87 Difference]: Start difference. First operand 17 states and 20 transitions. Second operand has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 2 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-14 03:29:48,382 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:29:48,383 INFO L93 Difference]: Finished difference Result 28 states and 33 transitions. [2024-11-14 03:29:48,383 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-14 03:29:48,383 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 2 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 13 [2024-11-14 03:29:48,384 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:29:48,384 INFO L225 Difference]: With dead ends: 28 [2024-11-14 03:29:48,384 INFO L226 Difference]: Without dead ends: 24 [2024-11-14 03:29:48,385 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 9 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-14 03:29:48,386 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 4 mSDsluCounter, 37 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 50 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 03:29:48,387 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 50 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 03:29:48,391 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2024-11-14 03:29:48,401 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-14 03:29:48,403 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 14 states have (on average 1.1428571428571428) internal successors, (16), 15 states have internal predecessors, (16), 6 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-14 03:29:48,404 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 27 transitions. [2024-11-14 03:29:48,405 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 27 transitions. Word has length 13 [2024-11-14 03:29:48,405 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:29:48,405 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 27 transitions. [2024-11-14 03:29:48,405 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 states have internal predecessors, (7), 2 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-14 03:29:48,405 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 27 transitions. [2024-11-14 03:29:48,406 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2024-11-14 03:29:48,406 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:29:48,406 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:29:48,422 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-14 03:29:48,607 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable1 [2024-11-14 03:29:48,607 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:29:48,608 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:29:48,608 INFO L85 PathProgramCache]: Analyzing trace with hash -891803703, now seen corresponding path program 1 times [2024-11-14 03:29:48,608 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:29:48,608 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1807130303] [2024-11-14 03:29:48,608 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:29:48,609 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:29:48,665 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 03:29:48,667 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1303671202] [2024-11-14 03:29:48,667 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:29:48,667 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:29:48,667 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:29:48,670 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:29:48,671 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-14 03:29:48,783 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:29:48,785 INFO L255 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-14 03:29:48,795 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:29:48,968 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 03:29:48,969 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:29:49,219 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 03:29:49,220 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:29:49,220 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1807130303] [2024-11-14 03:29:49,220 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 03:29:49,220 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1303671202] [2024-11-14 03:29:49,220 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1303671202] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:29:49,220 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2076961056] [2024-11-14 03:29:49,252 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2024-11-14 03:29:49,252 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:29:49,256 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:29:49,261 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:29:49,262 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:29:50,612 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 33 for LOIs [2024-11-14 03:29:50,703 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 55 for LOIs [2024-11-14 03:29:50,737 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:29:53,867 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '351#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (exists ((|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11| Int) (|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_11| Int)) (and (not (= (+ (* (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11|) 5) (* (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11|) 2) (* 6 (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11|))) (+ (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11|) (* |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_11| 12)))) (<= 0 |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_11|) (<= 0 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_11|))))' at error location [2024-11-14 03:29:53,867 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:29:53,868 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 03:29:53,868 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6] total 11 [2024-11-14 03:29:53,868 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1494680604] [2024-11-14 03:29:53,868 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 03:29:53,869 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-14 03:29:53,869 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:29:53,869 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-14 03:29:53,870 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=362, Unknown=1, NotChecked=0, Total=420 [2024-11-14 03:29:53,874 INFO L87 Difference]: Start difference. First operand 24 states and 27 transitions. Second operand has 11 states, 11 states have (on average 1.8181818181818181) internal successors, (20), 10 states have internal predecessors, (20), 4 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-14 03:29:54,043 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:29:54,043 INFO L93 Difference]: Finished difference Result 35 states and 40 transitions. [2024-11-14 03:29:54,044 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-14 03:29:54,044 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 1.8181818181818181) internal successors, (20), 10 states have internal predecessors, (20), 4 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) Word has length 20 [2024-11-14 03:29:54,045 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:29:54,047 INFO L225 Difference]: With dead ends: 35 [2024-11-14 03:29:54,047 INFO L226 Difference]: Without dead ends: 31 [2024-11-14 03:29:54,048 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 38 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=65, Invalid=396, Unknown=1, NotChecked=0, Total=462 [2024-11-14 03:29:54,049 INFO L432 NwaCegarLoop]: 14 mSDtfsCounter, 5 mSDsluCounter, 49 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 63 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 54 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 03:29:54,050 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 63 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 54 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 03:29:54,053 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2024-11-14 03:29:54,068 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 26. [2024-11-14 03:29:54,069 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 16 states have (on average 1.0625) internal successors, (17), 16 states have internal predecessors, (17), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-14 03:29:54,071 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 28 transitions. [2024-11-14 03:29:54,072 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 28 transitions. Word has length 20 [2024-11-14 03:29:54,073 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:29:54,073 INFO L471 AbstractCegarLoop]: Abstraction has 26 states and 28 transitions. [2024-11-14 03:29:54,073 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 1.8181818181818181) internal successors, (20), 10 states have internal predecessors, (20), 4 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-14 03:29:54,073 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 28 transitions. [2024-11-14 03:29:54,074 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-11-14 03:29:54,074 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:29:54,074 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:29:54,099 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-14 03:29:54,278 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:29:54,279 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:29:54,280 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:29:54,281 INFO L85 PathProgramCache]: Analyzing trace with hash 1574787184, now seen corresponding path program 1 times [2024-11-14 03:29:54,281 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:29:54,281 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [514113486] [2024-11-14 03:29:54,283 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:29:54,283 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:29:54,335 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 03:29:54,336 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1256370627] [2024-11-14 03:29:54,336 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:29:54,337 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:29:54,337 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:29:54,342 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:29:54,345 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-14 03:29:54,425 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:29:54,426 INFO L255 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-14 03:29:54,429 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:29:54,577 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-14 03:29:54,578 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:29:54,787 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-14 03:29:54,787 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:29:54,787 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [514113486] [2024-11-14 03:29:54,787 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 03:29:54,787 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1256370627] [2024-11-14 03:29:54,787 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1256370627] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:29:54,788 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [334299931] [2024-11-14 03:29:54,791 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2024-11-14 03:29:54,792 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:29:54,792 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:29:54,792 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:29:54,792 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:29:55,547 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2024-11-14 03:29:55,554 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 55 for LOIs [2024-11-14 03:29:55,582 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:29:56,318 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '649#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-14 03:29:56,319 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:29:56,319 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 03:29:56,319 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2024-11-14 03:29:56,319 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [803663130] [2024-11-14 03:29:56,319 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 03:29:56,319 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-14 03:29:56,320 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:29:56,321 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-14 03:29:56,322 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=360, Unknown=0, NotChecked=0, Total=420 [2024-11-14 03:29:56,322 INFO L87 Difference]: Start difference. First operand 26 states and 28 transitions. Second operand has 10 states, 8 states have (on average 2.25) internal successors, (18), 9 states have internal predecessors, (18), 7 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) [2024-11-14 03:29:56,560 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:29:56,561 INFO L93 Difference]: Finished difference Result 43 states and 52 transitions. [2024-11-14 03:29:56,561 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-14 03:29:56,561 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 9 states have internal predecessors, (18), 7 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) Word has length 31 [2024-11-14 03:29:56,562 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:29:56,564 INFO L225 Difference]: With dead ends: 43 [2024-11-14 03:29:56,565 INFO L226 Difference]: Without dead ends: 35 [2024-11-14 03:29:56,565 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 70 SyntacticMatches, 2 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 77 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=75, Invalid=477, Unknown=0, NotChecked=0, Total=552 [2024-11-14 03:29:56,569 INFO L432 NwaCegarLoop]: 19 mSDtfsCounter, 1 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 62 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 110 SdHoareTripleChecker+Invalid, 64 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 62 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 03:29:56,569 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 110 Invalid, 64 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 62 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 03:29:56,570 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2024-11-14 03:29:56,591 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2024-11-14 03:29:56,592 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 22 states have (on average 1.0454545454545454) internal successors, (23), 22 states have internal predecessors, (23), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-14 03:29:56,593 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 40 transitions. [2024-11-14 03:29:56,594 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 40 transitions. Word has length 31 [2024-11-14 03:29:56,595 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:29:56,595 INFO L471 AbstractCegarLoop]: Abstraction has 35 states and 40 transitions. [2024-11-14 03:29:56,595 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 9 states have internal predecessors, (18), 7 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) [2024-11-14 03:29:56,595 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 40 transitions. [2024-11-14 03:29:56,596 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2024-11-14 03:29:56,597 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:29:56,597 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 5, 5, 5, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:29:56,622 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-14 03:29:56,797 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:29:56,798 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:29:56,798 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:29:56,798 INFO L85 PathProgramCache]: Analyzing trace with hash -311128128, now seen corresponding path program 2 times [2024-11-14 03:29:56,798 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:29:56,798 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [426486839] [2024-11-14 03:29:56,798 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:29:56,799 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:29:56,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-14 03:29:56,888 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [734213846] [2024-11-14 03:29:56,892 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 03:29:56,892 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:29:56,892 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:29:56,895 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:29:56,897 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-14 03:29:56,997 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-14 03:29:56,998 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 03:29:57,000 INFO L255 TraceCheckSpWp]: Trace formula consists of 138 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-11-14 03:29:57,003 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:29:57,388 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 12 proven. 31 refuted. 0 times theorem prover too weak. 61 trivial. 0 not checked. [2024-11-14 03:29:57,388 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:29:57,851 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 12 proven. 30 refuted. 0 times theorem prover too weak. 62 trivial. 0 not checked. [2024-11-14 03:29:57,851 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:29:57,851 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [426486839] [2024-11-14 03:29:57,852 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-14 03:29:57,852 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [734213846] [2024-11-14 03:29:57,852 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [734213846] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:29:57,852 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [605817577] [2024-11-14 03:29:57,855 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2024-11-14 03:29:57,859 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:29:57,859 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:29:57,860 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:29:57,860 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:29:58,403 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2024-11-14 03:29:58,409 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 55 for LOIs [2024-11-14 03:29:58,423 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:29:59,244 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1117#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-14 03:29:59,244 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:29:59,244 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 03:29:59,244 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10] total 20 [2024-11-14 03:29:59,245 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [263799393] [2024-11-14 03:29:59,245 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 03:29:59,246 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-14 03:29:59,247 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:29:59,247 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-14 03:29:59,249 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=109, Invalid=821, Unknown=0, NotChecked=0, Total=930 [2024-11-14 03:29:59,249 INFO L87 Difference]: Start difference. First operand 35 states and 40 transitions. Second operand has 20 states, 17 states have (on average 1.9411764705882353) internal successors, (33), 17 states have internal predecessors, (33), 14 states have call successors, (17), 3 states have call predecessors, (17), 2 states have return successors, (16), 14 states have call predecessors, (16), 14 states have call successors, (16) [2024-11-14 03:30:00,085 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:30:00,085 INFO L93 Difference]: Finished difference Result 59 states and 75 transitions. [2024-11-14 03:30:00,086 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-14 03:30:00,086 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 17 states have (on average 1.9411764705882353) internal successors, (33), 17 states have internal predecessors, (33), 14 states have call successors, (17), 3 states have call predecessors, (17), 2 states have return successors, (16), 14 states have call predecessors, (16), 14 states have call successors, (16) Word has length 52 [2024-11-14 03:30:00,086 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:30:00,087 INFO L225 Difference]: With dead ends: 59 [2024-11-14 03:30:00,087 INFO L226 Difference]: Without dead ends: 51 [2024-11-14 03:30:00,088 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 164 GetRequests, 125 SyntacticMatches, 0 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 350 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=209, Invalid=1431, Unknown=0, NotChecked=0, Total=1640 [2024-11-14 03:30:00,092 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 17 mSDsluCounter, 197 mSDsCounter, 0 mSdLazyCounter, 189 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 223 SdHoareTripleChecker+Invalid, 197 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 189 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-14 03:30:00,093 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 223 Invalid, 197 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 189 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-14 03:30:00,095 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2024-11-14 03:30:00,119 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 50. [2024-11-14 03:30:00,120 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 32 states have (on average 1.03125) internal successors, (33), 32 states have internal predecessors, (33), 14 states have call successors, (14), 4 states have call predecessors, (14), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2024-11-14 03:30:00,121 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 60 transitions. [2024-11-14 03:30:00,121 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 60 transitions. Word has length 52 [2024-11-14 03:30:00,122 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:30:00,122 INFO L471 AbstractCegarLoop]: Abstraction has 50 states and 60 transitions. [2024-11-14 03:30:00,122 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 17 states have (on average 1.9411764705882353) internal successors, (33), 17 states have internal predecessors, (33), 14 states have call successors, (17), 3 states have call predecessors, (17), 2 states have return successors, (16), 14 states have call predecessors, (16), 14 states have call successors, (16) [2024-11-14 03:30:00,122 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 60 transitions. [2024-11-14 03:30:00,125 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2024-11-14 03:30:00,125 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 03:30:00,125 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 10, 10, 10, 9, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 03:30:00,150 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-14 03:30:00,329 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:30:00,330 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 03:30:00,331 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 03:30:00,331 INFO L85 PathProgramCache]: Analyzing trace with hash -2012483472, now seen corresponding path program 3 times [2024-11-14 03:30:00,331 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 03:30:00,331 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1049075235] [2024-11-14 03:30:00,331 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 03:30:00,331 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 03:30:00,415 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 03:30:01,214 INFO L134 CoverageAnalysis]: Checked inductivity of 379 backedges. 133 proven. 25 refuted. 0 times theorem prover too weak. 221 trivial. 0 not checked. [2024-11-14 03:30:01,214 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 03:30:01,214 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1049075235] [2024-11-14 03:30:01,216 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1049075235] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 03:30:01,216 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1031753700] [2024-11-14 03:30:01,216 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-14 03:30:01,216 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 03:30:01,216 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 03:30:01,221 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 03:30:01,222 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-14 03:30:01,301 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-14 03:30:01,301 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 03:30:01,302 INFO L255 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-14 03:30:01,306 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 03:30:01,741 INFO L134 CoverageAnalysis]: Checked inductivity of 379 backedges. 225 proven. 1 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2024-11-14 03:30:01,741 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 03:30:02,038 INFO L134 CoverageAnalysis]: Checked inductivity of 379 backedges. 157 proven. 1 refuted. 0 times theorem prover too weak. 221 trivial. 0 not checked. [2024-11-14 03:30:02,038 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1031753700] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 03:30:02,039 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1534174042] [2024-11-14 03:30:02,041 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2024-11-14 03:30:02,041 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 03:30:02,042 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 03:30:02,042 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 03:30:02,042 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 03:30:02,488 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2024-11-14 03:30:02,494 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 55 for LOIs [2024-11-14 03:30:02,520 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 03:30:03,128 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1873#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-14 03:30:03,128 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 03:30:03,128 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-14 03:30:03,128 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 13] total 32 [2024-11-14 03:30:03,128 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2009146671] [2024-11-14 03:30:03,128 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-14 03:30:03,129 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2024-11-14 03:30:03,129 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 03:30:03,131 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2024-11-14 03:30:03,132 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=432, Invalid=1374, Unknown=0, NotChecked=0, Total=1806 [2024-11-14 03:30:03,132 INFO L87 Difference]: Start difference. First operand 50 states and 60 transitions. Second operand has 32 states, 31 states have (on average 2.2580645161290325) internal successors, (70), 30 states have internal predecessors, (70), 31 states have call successors, (35), 2 states have call predecessors, (35), 3 states have return successors, (35), 30 states have call predecessors, (35), 31 states have call successors, (35) [2024-11-14 03:30:03,258 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 03:30:03,258 INFO L93 Difference]: Finished difference Result 55 states and 64 transitions. [2024-11-14 03:30:03,261 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-14 03:30:03,262 INFO L78 Accepts]: Start accepts. Automaton has has 32 states, 31 states have (on average 2.2580645161290325) internal successors, (70), 30 states have internal predecessors, (70), 31 states have call successors, (35), 2 states have call predecessors, (35), 3 states have return successors, (35), 30 states have call predecessors, (35), 31 states have call successors, (35) Word has length 87 [2024-11-14 03:30:03,262 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 03:30:03,263 INFO L225 Difference]: With dead ends: 55 [2024-11-14 03:30:03,263 INFO L226 Difference]: Without dead ends: 0 [2024-11-14 03:30:03,264 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 272 GetRequests, 231 SyntacticMatches, 0 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 773 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=432, Invalid=1374, Unknown=0, NotChecked=0, Total=1806 [2024-11-14 03:30:03,265 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 0 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 83 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 113 SdHoareTripleChecker+Invalid, 84 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 83 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 03:30:03,265 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 113 Invalid, 84 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 83 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 03:30:03,266 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2024-11-14 03:30:03,266 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2024-11-14 03:30:03,266 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-14 03:30:03,266 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2024-11-14 03:30:03,267 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 87 [2024-11-14 03:30:03,267 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 03:30:03,269 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-14 03:30:03,270 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 31 states have (on average 2.2580645161290325) internal successors, (70), 30 states have internal predecessors, (70), 31 states have call successors, (35), 2 states have call predecessors, (35), 3 states have return successors, (35), 30 states have call predecessors, (35), 31 states have call successors, (35) [2024-11-14 03:30:03,270 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2024-11-14 03:30:03,271 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2024-11-14 03:30:03,276 INFO L782 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-14 03:30:03,301 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-14 03:30:03,481 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2024-11-14 03:30:03,484 INFO L407 BasicCegarLoop]: Path program histogram: [3, 1, 1, 1] [2024-11-14 03:30:03,486 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2024-11-14 03:30:04,291 INFO L173 ceAbstractionStarter]: Computing trace abstraction results [2024-11-14 03:30:04,336 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 14.11 03:30:04 BoogieIcfgContainer [2024-11-14 03:30:04,336 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-14 03:30:04,337 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-14 03:30:04,337 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-14 03:30:04,337 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-14 03:30:04,338 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 03:29:47" (3/4) ... [2024-11-14 03:30:04,341 INFO L142 WitnessPrinter]: Generating witness for correct program [2024-11-14 03:30:04,345 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure assume_abort_if_not [2024-11-14 03:30:04,345 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2024-11-14 03:30:04,349 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 16 nodes and edges [2024-11-14 03:30:04,349 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 6 nodes and edges [2024-11-14 03:30:04,349 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2024-11-14 03:30:04,350 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2024-11-14 03:30:04,453 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/witness.graphml [2024-11-14 03:30:04,453 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/witness.yml [2024-11-14 03:30:04,453 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-14 03:30:04,455 INFO L158 Benchmark]: Toolchain (without parser) took 17800.95ms. Allocated memory was 142.6MB in the beginning and 427.8MB in the end (delta: 285.2MB). Free memory was 119.0MB in the beginning and 275.0MB in the end (delta: -156.0MB). Peak memory consumption was 123.3MB. Max. memory is 16.1GB. [2024-11-14 03:30:04,456 INFO L158 Benchmark]: CDTParser took 0.46ms. Allocated memory is still 167.8MB. Free memory is still 105.1MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 03:30:04,456 INFO L158 Benchmark]: CACSL2BoogieTranslator took 316.61ms. Allocated memory is still 142.6MB. Free memory was 119.0MB in the beginning and 107.8MB in the end (delta: 11.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-14 03:30:04,457 INFO L158 Benchmark]: Boogie Procedure Inliner took 39.91ms. Allocated memory is still 142.6MB. Free memory was 107.8MB in the beginning and 106.7MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 03:30:04,458 INFO L158 Benchmark]: Boogie Preprocessor took 21.73ms. Allocated memory is still 142.6MB. Free memory was 106.7MB in the beginning and 106.0MB in the end (delta: 763.8kB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 03:30:04,458 INFO L158 Benchmark]: RCFGBuilder took 432.63ms. Allocated memory is still 142.6MB. Free memory was 106.0MB in the beginning and 93.5MB in the end (delta: 12.5MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. [2024-11-14 03:30:04,459 INFO L158 Benchmark]: TraceAbstraction took 16865.33ms. Allocated memory was 142.6MB in the beginning and 427.8MB in the end (delta: 285.2MB). Free memory was 93.1MB in the beginning and 279.0MB in the end (delta: -185.9MB). Peak memory consumption was 98.2MB. Max. memory is 16.1GB. [2024-11-14 03:30:04,459 INFO L158 Benchmark]: Witness Printer took 116.55ms. Allocated memory is still 427.8MB. Free memory was 279.0MB in the beginning and 275.0MB in the end (delta: 4.0MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 03:30:04,461 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.46ms. Allocated memory is still 167.8MB. Free memory is still 105.1MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 316.61ms. Allocated memory is still 142.6MB. Free memory was 119.0MB in the beginning and 107.8MB in the end (delta: 11.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 39.91ms. Allocated memory is still 142.6MB. Free memory was 107.8MB in the beginning and 106.7MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 21.73ms. Allocated memory is still 142.6MB. Free memory was 106.7MB in the beginning and 106.0MB in the end (delta: 763.8kB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 432.63ms. Allocated memory is still 142.6MB. Free memory was 106.0MB in the beginning and 93.5MB in the end (delta: 12.5MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. * TraceAbstraction took 16865.33ms. Allocated memory was 142.6MB in the beginning and 427.8MB in the end (delta: 285.2MB). Free memory was 93.1MB in the beginning and 279.0MB in the end (delta: -185.9MB). Peak memory consumption was 98.2MB. Max. memory is 16.1GB. * Witness Printer took 116.55ms. Allocated memory is still 427.8MB. Free memory was 279.0MB in the beginning and 275.0MB in the end (delta: 4.0MB). There was no memory consumed. 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: 12]: 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 3 procedures, 19 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 15.9s, OverallIterations: 6, TraceHistogramMax: 12, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 1.6s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 34 SdHoareTripleChecker+Valid, 0.7s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 27 mSDsluCounter, 578 SdHoareTripleChecker+Invalid, 0.6s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 463 mSDsCounter, 19 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 420 IncrementalHoareTripleChecker+Invalid, 439 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 19 mSolverCounterUnsat, 115 mSDtfsCounter, 420 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 604 GetRequests, 475 SyntacticMatches, 3 SemanticMatches, 126 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1275 ImplicationChecksByTransitivity, 7.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=50occurred in iteration=5, InterpolantAutomatonStates: 53, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 6 MinimizatonAttempts, 6 StatesRemovedByMinimization, 2 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 3.4s InterpolantComputationTime, 419 NumberOfCodeBlocks, 406 NumberOfCodeBlocksAsserted, 15 NumberOfCheckSat, 482 ConstructedInterpolants, 0 QuantifiedInterpolants, 1976 SizeOfPredicates, 6 NumberOfNonLiveVariables, 498 ConjunctsInSsa, 83 ConjunctsInUnsatCore, 11 InterpolantComputations, 2 PerfectInterpolantSequences, 1309/1407 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: 28]: Loop Invariant Derived loop invariant: ((((((((((276 == x) && (3 == y)) && (k <= 5)) && ((3 < k) || (3 == k))) && (3 == c)) || (((((1300 == x) && (y == 4)) && (4 <= k)) && (k <= 5)) && (c == 4))) || (((((2 == y) && (k <= 5)) && (x == 33)) && ((2 < k) || (2 == k))) && (2 == c))) || (((((0 <= k) && (c == 0)) && (y == 0)) && (k <= 5)) && (x == 0))) || (((((c == 1) && (x == 1)) && (k <= 5)) && (y == 1)) && (1 <= k))) || (((((0 <= k) && (((__int128) k * y) == ((__int128) y * y))) && (k <= 5)) && ((((6 * (((((__int128) y * y) * y) * y) * y)) + (2 * ((((((__int128) y * y) * y) * y) * y) * y))) + (5 * ((((__int128) y * y) * y) * y))) == (((__int128) x * 12) + ((__int128) y * y)))) && (5 <= c))) - ProcedureContractResult [Line: 6]: Procedure Contract for assume_abort_if_not Derived contract for procedure assume_abort_if_not. Ensures: (cond != 0) - ProcedureContractResult [Line: 9]: Procedure Contract for __VERIFIER_assert Derived contract for procedure __VERIFIER_assert. Requires: (1 <= cond) Ensures: (1 <= cond) RESULT: Ultimate proved your program to be correct! [2024-11-14 03:30:04,489 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd99c5f7-2bc7-463b-a00a-8a7f048213bb/bin/utaipan-verify-sOmjnqqW8E/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